Рисунок 3.
Информационная блок-схема поиска методом деформируемого многогранника.
Государственный комитет Российской Федерации
по высшему образованию
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра АСУ
Реферат по дисциплине
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
на тему
МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКА
Студент Борзов Андрей Николаевич
Группа АС–513
Преподаватель Ренин Сергей Васильевич
Новосибирск 1997
Поиск по деформируемому многогранникуВпервые метод деформируемого многогранника был предложен Нелдером и Мидом. Они предложили метод поиска, оказавшийся весьма эффективным и легко осуществляемым на ЭВМ. Чтобы можно было оценить стратегию Нелдера и Мида, кратко опишем симплексный поиск Спендли, Хекста и Химсворта, разработанный в связи со статистическим планированием эксперимента. Вспомним, что регулярные многогранники в En являются симплексами. Например, как видно из рисунка 1, для случая двух переменных регулярный симплекс представляет собой равносторонний треугольник (три точки); в случае трёх переменных регулярный симплекс представляет собой тетраэдр (четыре точки) и т.д.
Рисунок
1.
Регулярные
симплексы для
случая двух
(а) и трёх (б) независимых
переменных.
� обозначает
наибольшее
значение f(x).
Стрелка указывает
направление
наискорейшего
улучшения.
При поиске минимума целевой функции f(x) пробные векторы x могут быть выбраны в точках En, находящихся в вершинах симплекса, как было первоначально предложено Спендли, Хекстом и Химсвортом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются следующей матрицей D, в которой столбцы представляют собой вершины, пронумерованные от 1 до (n+1), а строчки – координаты, i принимает значения от 1 до n:
– матрица n X (n+1),
где
,
,
t – расстояние между двумя вершинами. Например, для n=2 и t=1 треугольник, приведённый на рисунке 1, имеет следующие координаты:
| Вершина | x1,i | x2,i |
| 1 | 0 | 0 |
| 2 | 0.965 | 0.259 |
| 3 | 0.259 | 0.965 |
Целевая функция может быть вычислена в каждой из вершин симплекса; из вершины, где целевая функция максимальна (точка A на рисунке 1), проводится проектирующая прямая через центр тяжести симплекса. Затем точка A исключается и строится новый симплекс, называемый отражённым, из оставшихся прежних точек и одной новой точки B, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести. Продолжение этой процедуры, в которой каждый раз вычёркивается вершина, где целевая функция максимальна, а также использование правил уменьшения размера симплекса и предотвращения циклического движения в окрестности экстремума позволяют осуществить поиск, не использующий производные и в котором величина шага на любом этапе k фиксирована, а направление поиска можно изменять. На рисунке 2 приведены последовательные симплексы, построенные в двумерном пространстве с «хорошей» целевой функцией.
Рисунок
2.
Последовательность
регулярных
симплексов,
полученных
при минимизации
f(x).
----- проекция
Определённые практические трудности, встречающиеся при использовании регулярных симплексов, а именно отсутствие ускорения поиска и трудности при проведении поиска на искривлённых «оврагах» и «хребтах», привели к необходимости некоторых улучшений методов. Далее будет изложен метод Нелдера и Мида, в котором симплекс может изменять свою форму и таким образом уже не будет оставаться симплексом. Именно поэтому здесь использовано более подходящее название «деформируемый многогранник».
В методе Нелдера и Мида минимизируется функция n независимых переменных с использованием n+1 вершин деформируемого многогранника в En. Каждая вершина может быть идентифицирована вектором x. Вершина (точка) в En, в которой значение f(x) максимально, проектируется через центр тяжести (центроид) оставшихся вершин. Улучшенные (более низкие) значения целевой функции находятся последовательной заменой точки с максимальным значением f(x) на более «хорошие точки», пока не будет найден минимум f(x).
Более подробно этот алгоритм может быть описан следующим образом.
Пусть , является i-й вершиной (точкой) в En на k-м этапе поиска, k=0, 1, …, и пусть значение целевой функции в x(k)i равно f(x(k)i). Кроме того, отметим те векторы x многогранника, которые дают максимальное и минимальное значения f(x).
Определим
Поскольку многогранник в En состоит из (n+1) вершин x1, …,xn+1, пусть xn+2 будет центром тяжести всех вершин, исключая xh.
Тогда координаты этого центра определяются формулой
(1)
где индекс j обозначает координатное направление.
Начальный многогранник обычно выбирается в виде регулярного симплекса (но это не обязательно) с точкой 1 в качестве начала координат; можно начало координат поместить в центр тяжести. Процедура отыскания вершины в En, в которой f(x) имеет лучшее значение, состоит из следующих операций:
Отражение – проектирование x(k)h через центр тяжести в соответствии с соотношением
(2)
где a>0 является коэффициентом отражения; – центр тяжести, вычисляемый по формуле (1); – вершина, в которой функция f(x) принимает наибольшее из n+1 значений на k-м этапе.
Растяжение. Эта операция заключается в следующем: если , то вектор растягивается в соответствии с соотношением
(3)
где g>1 представляет собой коэффициент растяжения. Если , то заменяется на и процедура продолжается снова с операции 1 при k=k+1. В противном случае заменяется на и также осуществляется переход к операции 1 при k=k+1.
Сжатие. Если для всех i№h, то вектор сжимается в соответствии с формулой
(4)
где 0 f(xh) ?
Заменить
xh на xn+5
Редукция: заменить
все xi на xl + 1/2(xi - xl)
Останов
Рисунок
3.
Поиск минимума
функции Розенброка
методом деформируемого
многогранника,
начиная с точки
x(0)=[-1,2 1,0]T (числа
указывают номер
шага).
Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(x) через центр тяжести деформируемого многогранника. Коэффициент g вводится для растяжения вектора поиска в случае, если отражение даёт вершину со значением f(x), меньшим, чем наименьшее значение f(x), полученное до отражения. Коэффициент сжатия b используется для уменьшения вектора поиска, если операция отражения не привела к вершине со значением f(x), меньшим, чем второе по величине (после наибольшего) значение f(x), полученное до отражения. Таким образом, с помощью операций растяжений или сжатия размеры и форма деформируемого многогранника масштабируются так, чтобы они удовлетворяли топологии решаемой задачи.
Естественно возникает вопрос, какие значения параметров a, b и g должны быть выбраны. После того как деформируемый многогранник подходящим образом промасштабирован, его размеры должны поддерживаться неизменными, пока изменения в топологии задачи не потребуют применения многогранника другой формы. Это возможно реализовать только при a=1. Кроме того, Нелдер и Мид показали, что при решении задачи с a=1 требуется меньшее количество вычислений функции, чем при a
Похожие работы
... , Флетчера-Ривса). Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) (метод Ньютона и его модификации). Метод конфигураций (Хука - Дживса) Следует выделить два этапа метода конфигураций: 1) исследование с циклическим изменением переменных и 2) ускорение поиска по образцам. Исследующий поиск начинается в точке х0, называемой старым базисом. ...
... работы со справочной системой работа практикума приостанавливается. 3. Организационно-экономическое обоснование проекта В ходе дипломного проекта был разработан компьютерный лабораторный практикум по курсу «Теория оптимизации и численные методы». В данном разделе рассмотрена экономическая сторона проекта. Рассмотрены следующие вопросы: 1) сетевая модель 2) расчёт ...
... luc – программа используется для разложения матрицы на треугольные сомножители; rluc – программа, которая отвечает за решение системы уравнений. 4. Разработка адаптивной системы управления режимами электропотребления 4.1 Функции автоматизированной системы Сбор, накопление и передача информации, характеризующей режим электропотребления комбината (информация о нагрузках). Сбор, накопление ...
... полезные свойства искусственных материалов современной техники – полупроводников, ферромагнетиков, лазерных материалов. Многие вещества могут образовывать кристаллические формы, имеющие различные структуру и свойства, но одинаковый состав (полиморфные модификации). Полиморфизм – способность твердых веществ и жидких кристаллов существовать в двух или нескольких формах с различной кристаллической ...
0 комментариев