Реализация поисковых методов в системе matlab
Одним из наиболее популярных методов поиска является алгоритм Нелдера-Мида. [J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308—313]
Алгоритм заключается в следующем:
- в пространстве поиска создается правильный многогранник, число вершин которого на единицу больше размерности пространства поиска. В дальнейшем этот многоугольник называется симплексом;
- поиск минимума выполняется путем перемещения симплекса к точке минимума исследуемой функции;
- перемещение симплекса производится за счет операций «отражение», «растяжение», «сжатие» и «редукция».
Операция
«отражение» заключается в переносе
вершины
исходного симплекса в соответствии с
вектором
Вершина
- наихудшая вершина исходного симплекса,
т.е. вершина в которой значение исследуемой
функции является наибольшим (при поиске
минимума) или наименьшим (при поиске
максимума) по сравнению с остальными
вершинами исходного симплекса.
Вектор
направлен от вершины
к середине противоположной грани. Длина
вектора
равна удвоенному расстоянию от вершины
до середины противоположной грани.
Операция
«растяжение» заключается в переносе
вершины
исходного симплекса в соответствии с
вектором
.
Вершина
это вершина симплекса, положение которой
изменяется при выполнении рассматриваемой
операции.
Вектор
направлен от середины грани, противоположной
вершине
к вершине
.
Длина вектора
в
раз больше расстояния между вершиной
и серединой противоположной грани.
Величина
зависит от варианта реализации алгоритма
поиска, причем
>1.
Операция
«сжатие» заключается в переносе вершины
исходного симплекса в соответствии с
вектором
.
Вершина
это вершина симплекса, положение которой
изменяется при выполнении рассматриваемой
операции.
Вектор
направлен от середины грани, противоположной
вершине
к вершине
.
Длина вектора
в
раз больше расстояния между вершиной
и серединой противоположной грани.
Величина
зависит от варианта реализации алгоритма
поиска, причем
<1.
Предусмотрен
вариант операции «сжатие», который
называется «сжатие в минус». Этот вариант
отличается тем, что перемещение вершины
производится в соответствии с вектором
.
При выполнении операции «редукция» формируется симплекс подобный исходному. Длина ребер редуцированного симплекса уменьшается. При выполнении «редукции» сохраняется положение наилучшей вершины.
Выполнение операций над симплексом зависит от ситуации, которая создается при движении симплекса.
Алгоритм применения операций может быть представлен в виде следующей квази-программы:
% Алгоритм поиска минимума методом Нелдера-Мида
% ss - код состояния процесса поиска
do while <не принято решение о завершении поиска>
<ОТРАЖЕНИЕ>
switch
case <отраженная вершина - лучшая>
ss = 1;
<РАСТЯЖЕНИЕ>
if <растяжение привело к улучшению>
ss = 2;
else
ss = 3;
<ОТМЕНА РАСТЯЖЕНИЯ>
ss =12;
end
case <отраженная вершина - худшая>
if <отражение привело к улучшению>
ss = 5;
<СЖАТИЕ В ПЛЮС>
if <после сжатия вершина стала одной из худших>
ss = 6;
<РЕДУКЦИЯ (с предварительной отменой сжатия и отражения)>
ss = 13;
else
ss = 7;
end
else
ss = 8;
<СЖАТИЕ В МИНУС>
if <после сжатия вершина стала одной из худших>
ss = 9;
<РЕДУКЦИЯ (с предварительной отменой сжатия и отражения>
ss = 14;
else
ss = 10;
end
end
otherwise
ss = 11;
end
<ВОЗВРАТ В РЕЖИМ ОТРАЖЕНИЯ>
<ПРИНЯТИЕ РЕШЕНИЯ О ЗАВЕРШЕНИИ ПОИСКА>
end
В среде MATLAB метод Нелдера-Мида реализован в виде функции FMINSEARCH.
В соответствии с соглашениями, принятыми в пакете MATLAB, программы поиска неизвестных параметров управляющего воздействия состоит из двух файлов.
В первом файле выполняется обращение к функции FMINSEARCH и указывается начальная точка в пространстве поиска и ссылка на функцию, выполняющую расчет величины минимизируемой функции, соответствующей текущим значениям искомых параметров.
Второй файл описывает расчет величины минимизируемой функции. В некоторых случаях для обеспечения успешного поиска требуется дополнительная настройка функции FMINSEARCH.
Значения параметров настройки функции, действующих по умолчанию, можно получить следующим образом:
optimset(‘fminsearch’)
Для того, чтобы увеличить допустимое для FMINSEARCH количество поисковых шагов до 10000 требуется выполнить следующие команды MATLAB:
OPTIONS=optimset(‘MaxIter’,10e+4)
p=fminsearch(‘fun’,p0,OPTIONS)
где: fun – имя файл-функции, которая вычисляет значение минимизируемой функции;
p0 – вектор начальных значений искомых параметров;
OPTIONS – структура, содержащая параметры настройки FMINSEARCH.