47732 (665894), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Рис.3.Построение нового симплекса.

а – начальный симплекс

б – новый симплекс

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

Правило 1. «Накрытие» точки минимума

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

Правило 2. Циклическое движение

Если некоторая вершина симплекса не исключается на протя­жении более чем М итераций, то необходимо уменьшить размеры симплекса с помощью коэффициента редукции и построить новый симплекс, выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции. Спендли, Хекст и Химс-ворт предложили вычислять М по формуле

M=1,65n+0,05

где n — размерность задачи, а М округляется до ближайшего целого числа. Для применения данного правила требуется уста­новить величину коэффициента редукции.

Правило 3. Критерий окончания поиска

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

Реализация изучаемого алгоритма основана на вычислениях двух типов: (1) построении регулярного симплекса при заданных базовой точке и масштабном множителе и (2) расчете координат отраженной точки. Построение симплекса является достаточно простой процедурой, так как из элементарной геометрии известно, что при заданных начальной (базовой) точке и масштабном мно­жителе координаты остальных n вершин симплекса в n-мерном пространстве вычисляются по формуле

(7)

для i и j=1,2,3,…,n

Приращения и , зависящие только от n и выбранного мас­штабного множителя , определяются по формулам

(8)

(9)

Заметим, что величина масштабного множителя выбирается ис­следователем, исходя из характеристик решаемой задачи. При =1 ребра регулярного симплекса имеют единичную длину. Вычисления второго типа, связанные с отражением относи­тельно центра тяжести, также представляют несложную процедуру. Пусть — точка, подлежащая отражению. Центр тяжести осталь­ных n точек расположен в точке

(10)

Все точки прямой, проходящей через и х_с, задаются формулой

(11)

При =0 получаем исходную точку , тогда как значение =1 соответствует центру тяжести х_с. Для того чтобы построенный симп­лекс обладал свойством регулярности, отражение должно быть сим­метричным. Следовательно, новая вершина получается при =2. Таким образом,

(12)

Проиллюстрируем вычислительную схему метода следующим при­мером.

Пример 5. Вычисления в соответствии с методом поиска по симплексу

Минимизировать f(x)=

Решение.

Для построения исходного симплекса требуется задать начальную точку и масштабный множитель. Пусть x = и =2. Тогда

Используя эти два параметра, вычислим координаты двух остальных вершин симплекса:

которым соответствуют значения целевой функции, равные =0,2374 и 3,0658. Так как 5, необходимо отразить точку относительно центра тяжести двух остальных вершин симплекса

Используя формулу (12), получаем

В полученной точке 2,3027, т. е. наблюдается уменьшение целевой функции. Новый симплекс образован точками и . В соответствии с алгоритмом следует отразить точку х⁽²⁾, ко­торой соответствует наибольшее значение целевой функции, отно­сительно центра тяжести точек и х⁽³⁾. Итерации продолжаются до тех пор, пока не потребуется применение правил 1, 2 и 3, которые были сформулированы выше.

Изложенный выше алгоритм - метода имеет несколько очевид­ных преимуществ.

1. Расчеты и логическая структура метода отличаются сравни­тельной простотой, и, следовательно, соответствующая программа для ЭВМ оказывается относительно короткой.

2. Уровень требований к объему памяти ЭВМ невысокий, мас­сив имеет размерность (n+1, n+2).

3. Используется сравнительно небольшое число заранее уста­новленных параметров: масштабный множитель , коэффициент уменьшения множителя (если применяется правило 2) и параметры окончания поиска.

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

Перечисленные факторы характеризуют метод поиска по симплек­су как весьма полезный при проведении вычислений в реальном времени.

Алгоритм обладает также рядом существенных недостатков.

1. Не исключено возникновение трудностей, связанных с масштабированием, поскольку все координаты вершин симплекса за­висят от одного и того же масштабного множителя . Чтобы обойти трудности такого рода, в практических задачах следует промасштабировать все переменные с тем, чтобы их значения были сравнимыми по величине.

2. Алгоритм работает слишком медленно, так как полученная на предыдущих итерациях информация не используется для уско­рения поиска.

3. Не существует простого способа расширения симплекса, не требующего пересчета значений целевой функции во всех точках образца. Таким образом, если по какой-либо причине уменьшается (например, если встречается область с узким «оврагом» или «хреб­том»), то поиск должен продолжаться с уменьшенной величиной шага.

4.1.2. Метод поиска Хука-Дживса.

Метод, разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука—Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам».

Исследующий поиск.

Для проведения исследующего поиска необходимо задать величину шага, которая может быть раз­личной для разных координатных направлений и изменяться в про­цессе поиска. Исследующий поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превы­шает значения функции в исходной точке, то шаг поиска рассматри­вается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой значения целевой функции. После пере­бора всех N координат исследующий поиск завершается. Получен­ную в результате точку называют базовой точкой.

Поиск по образцу.

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

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

- текущая базовая точка,

- предыдущая базовая точка,

- точка, построенная при движении по образцу,

- следующая (новая) базовая точка.

Приведенная последовательность характеризует логическую струк­туру поиска по методу Хука — Дживса.

Структура метода поиска Хука — Дживса

Шаг 1 . Определить:

начальную точку ,

приращения

коэффициент уменьшения шага ,

параметр окончания поиска .

Ш а г 2. ровести исследующий поиск.

Ш а г 3. Был ли исследующий поиск удачным (найдена ли точ­ка с меньшим значением

целевой функции)?

Характеристики

Список файлов реферата