Метод деформируемого многогранника

Государственный комитет Российской Федерации по высшему образованию НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра АСУ Реферат по дисциплине ИССЛЕДОВАНИЕ ОПЕРАЦИЙ на тему МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА Студент Борзов Андрей Николаевич Группа АС 513 Преподаватель Ренин Сергей Васильевич Новосибирск 1997 Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента.

Вспомним, что регулярные многогранники в En являются симплексами.Например, как видно из рисунка 1, для случая двух переменных регулярный симплекс представляет собой равносторонний треугольник три точки в случае трх переменных регулярный симплекс представляет собой тетраэдр четыре точки и т.д. Рисунок 1.Регулярные симплексы для случая двух а и трх б независимых переменных. обозначает наибольшее значение fx. Стрелка указывает направлениенаискорейшего улучшения.

При поиске минимума целевой функции fx пробные векторы x могут быть выбраны в точках En, находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом.Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D, в которой столбцы представляют собой вершины, пронумерованные от 1 до n1, а строчки координаты, i принимает значения от 1 до n матрица n X n1, где t расстояние между двумя вершинами.

Например, для n2 и t1 треугольник, приведнный на рисунке 1, имеет следующие координаты Вершинаx1,i x2,i5 Целевая функция может быть вычислена в каждой из вершин симплекса из вершины, где целевая функция максимальна точка A на рисунке 1, проводится проектирующая прямая через центр тяжести симплекса. Затем точка A исключается и строится новый симплекс, называемый отражнным, из оставшихся прежних точек и одной новой точки B, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести.

Продолжение этой процедуры, в которой каждый раз вычркивается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума позволяют осуществить поиск, не использующий производные и в котором величина шага на любом этапе k фиксирована, а направление поиска можно изменять.

На рисунке 2 приведены последовательные симплексы, построенные в двумерном пространстве с хорошей целевой функцией.Рисунок 2.Последовательность регулярных симплексов, полученных при минимизации fx проекция Определнные практические трудности, встречающиеся при использовании регулярных симплексов, а именно отсутствие ускорения поиска и трудности при проведении поиска на искривлнных оврагах и хребтах, привели к необходимости некоторых улучшений методов.

Далее будет изложен метод Нелдера и Мида, в котором симплекс может изменять свою форму и таким образом уже не будет оставаться симплексом. Именно поэтому здесь использовано более подходящее название деформируемый многогранник.В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n1 вершин деформируемого многогранника в En. Каждая вершина может быть идентифицирована вектором x. Вершина точка в En, в которой значение fx максимально, проектируется через центр тяжести центроид оставшихся вершин.

Улучшенные более низкие значения целевой функции находятся последовательной заменой точки с максимальным значением fx на более хорошие точки, пока не будет найден минимум fx. Более подробно этот алгоритм может быть описан следующим образом.Пусть , является i-й вершиной точкой в En на k-м этапе поиска, k0, 1 и пусть значение целевой функции в xki равно fxki. Кроме того, отметим те векторы x многогранника, которые дают максимальное и минимальное значения fx. Определим Поскольку многогранник в En состоит из n1 вершин x1, ,xn1, пусть xn2 будет центром тяжести всех вершин, исключая xh. Тогда координаты этого центра определяются формулой 1 где индекс j обозначает координатное направление.

Начальный многогранник обычно выбирается в виде регулярного симплекса но это не обязательно с точкой 1 в качестве начала координат можно начало координат поместить в центр тяжести.Процедура отыскания вершины в En, в которой fx имеет лучшее значение, состоит из следующих операций 1. Отражение проектирование xkh через центр тяжести в соответствии с соотношением 2где 0 является коэффициентом отражения центр тяжести, вычисляемый по формуле 1 вершина, в которой функция fx принимает наибольшее из n1 значений на k-м этапе. 2. Растяжение. Эта операция заключается в следующем если , то вектор растягивается в соответствии с соотношением 3где 1 представляет собой коэффициент растяжения.

Если , то заменяется на и процедура продолжается снова с операции 1 при kk1. В противном случае заменяется на и также осуществляется переход к операции 1 при kk3. Сжатие. Если для всех ih, то вектор сжимается в соответствии с формулой 4где 0 1 представляет собой коэффициент сжатия.

Затем заменяем на и возвращаемся к операции 1 для продолжения поиска на k1-м шаге. 4. Редукция. Если , все векторы уменьшаются в 2 раза с отсчтом от в соответствии с формулой 5Затем возвращаемся к операции 1 для продолжения поиска на k1-м шаге. Критерий окончания поиска, использованный Нелдером и Мидом, состоял в проверке условия 6 где произвольное малое число, а значение целевой функции в центре тяжести . На схеме 1 приведена блок-схема поиска методом деформируемого многогранника, а на рисунке 3 показана последовательность поиска для функции Розенброка, начиная их x0-1,2 1,0T. Деформируемый многогранник в противоположность жсткому симплексу адаптируется к топографии целевой функции, вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутых впадинах и сжимаясь в окрестности минимума.

Пуск Вычислить начальные значения xi0, i 1, 2 n1, и fx0 начального симплекса Вычислить xh и xl и c Отражение вычислить xn3 xn2 xn2 - xn Вычислить fxn3 Выполняется ли неравенство fxn3 fxh Растяжение вычислить xn4 xn2 xn3 - xn2 Вычислить fxn4 Выполняется ли неравенство fxn4 fxl Заменить xh на xn4 Выполняется ли неравенство fxn3 fxi для всех i h Заменить xh на xn3 Схема 1. Информационная блок-схема поиска методом деформируемого многогранника.

Выполняется ли неравенство fxn3 fxh Заменить xh на xn3 Сжатие вычислить xn5 xn2 xh - xn2 Вычислить fxn5 Выполняется ли неравенство fxn5 fxh Заменить xh на xn5 Редукция заменить все xi на xl 12xi - xl Останов Рисунок 3.Поиск минимума функции Розенброка методом деформируемого многогранника, начиная с точки x0-1,2 1,0T числа указывают номер шага. Коэффициент отражения используется для проектирования вершины с наибольшим значением fx через центр тяжести деформируемого многогранника. Коэффициент вводится для растяжения вектора поиска в случае, если отражение дат вершину со значением fx, меньшим, чем наименьшее значение fx, полученное до отражения.

Коэффициент сжатия используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением fx, меньшим, чем второе по величине после наибольшего значение fx, полученное до отражения.

Таким образом, с помощью операций растяжений или сжатия размеры и форма деформируемого многогранника масштабируются так, чтобы они удовлетворяли топологии решаемой задачи.

Естественно возникает вопрос, какие значения параметров , и должны быть выбраны. После того как деформируемый многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы.Это возможно реализовать только при 1. Кроме того, Нелдер и Мид показали, что при решении задачи с 1 требуется меньшее количество вычислений функции, чем при 1. С другой стороны, не должно быть много больше единицы, поскольку 1 деформируемый многогранник легче адаптируется к топологии задачи при меньших значениях , особенно когда необходимо изменять направление поиска, столкнувшись с изогнутой впадиной, и 2 в области локального минимума размеры многогранника должны уменьшаться и большое в этих условиях замедлит сходимость. Таким образом, значение 1 выбирается как компромисс.

Чтобы выяснить, какое влияние на процедуру поиска имеет выбор и , Нелдер и Мид а также Павиани провели решение нескольких тестовых задач, используя большое число различных комбинаций значений и . В качестве удовлетворительных значений этих параметров при оптимизации без ограничений Нелдер и Мид рекомендовали 1, 0,5 и 2. Размеры и ориентация исходного многогранника в некоторой степени влияли на время решения, а значения , и оказывали значительно большее влияние.

Павиани отмечает, что нельзя чтко решить вопрос относительно выбора и и что влияние выбора на эффективность поиска несколько более заметно, чем влияние . Павиани рекомендует следующие диапазоны значений для этих параметров 0,4 0,6, 2,8 3,0. При 0 0,4 существует вероятность того, что из-за уплощения многогранника будет иметь место преждевременное окончание процесса. При 0,6 может потребоваться избыточное число шагов и больше машинного времени для достижения окончательного решения.

Пример Поиск методом деформируемого многогранника.

Для иллюстрации метода Нелдера и Мида рассмотрим задачу минимизации функции fx4x1 52x2 62, имеющей минимум в точке x5 6T. Поскольку fx зависит от двух переменных, в начале поиска используется многоугольник с тремя вершинами.В этом примере в качестве начального многогранника взят треугольник с вершинами x108 9T, x2010 11T и x308 11T, хотя можно было бы использовать любую другую конфигурацию из трх точек.

На нулевом этапе поиска, k0, вычисляя значения функции, получаем f8,945, f10,11125 и f8,1165. Затем отражаем x2010 11T через центр тяжести точек x10 и x30 по формуле 1, который обозначим через x40 , с тем, чтобы получить x50 f6,913. Поскольку f6,913 f8,945, переходим к операции растяжения f4,88. Поскольку f4,88 f8,945, заменяем x20 на x60 и полагаем x60x21 на следующем этапе поиска. Наконец, поскольку , начинаем этап поиска k1. На рисунке 4 приведена траектория поиска на начальных этапах, а в таблице 2 приведены координаты вершин и значения fx для четырх дополнительных этапов.

На рисунке 5 изображена полная траектория поиска до его окончания. Для уменьшения fx до значения потребовалось 32 этапа.Рисунок 4.Метод Нелдера и Мида при отсутствии ограничений. Рисунок 5.Траектория поиска с помощью алгоритма Нелдера и Мида. Содержание Поиск по деформируемому многограннику Пример Содержание Список рисунков Список литературы Список рисунков Рисунок 1. Регулярные симплексы для случая двух а и трх б независимых переменных.

Рисунок 2. Последовательность регулярных симплексов, полученных при минимизации fx. Рисунок 3. Поиск минимума функции Розенброка методом деформируемого многогранника. Рисунок 4. Метод Нелдера и Мида при отсутствии ограничений. Рисунок 5. Траектория поиска с помощью алгоритма Нелдера и Мида. Список литературы Химмельблау Д. Прикладное нелинейное программирование. М 1975.