Закрыть

Минимизация по правильному симплексу

Автор: Васин Алексей
Опубликовано 08.02.2008 в 15:56
Раздел: Методы оптимизации

Методы прямого поиска.

Многомерные методы оптимизации, основанные на вычислении целевой функции f(x), можно разделить на эвристические и теоретические. В первых реализуются процедуры поиска с помощью интуитивных геометрических представлений. Данные методы обеспечивают получение частных эмпирических результатов. Теоретические методы основаны на фундаментальных математических теоремах и обладают такими операционными свойствами как сходимость.

Метод поиска по симплексу

Суть метода заключается в исследовании целевой функции в вершинах некого «образца», в двумерном случае треугольника, построенного в пространстве переменных вокруг «базовой» точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В рассматриваемом методе таким образцом является регулярный симплекс. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве – тетраэдр.

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

Некоторые замечания:

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

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

При заданной начальной точке $x^{(0)}$ и масштабном множителе $\alpha$, координаты остальных N вершин симплекса в N – мерном пространстве вычисляются по формуле:

$\displaystyle{x^{(i)}= \left\{ \begin{array}{c} x_j^{(0)}+\delta_1 , i=j \\ x_j^{(0)}+\delta_2, |i-j| \gt 0 \end{array}}$

Приращения $\delta_1$ и $\delta_2$ определяются по формулам:

$\displaystyle{\delta_1 =\frac{\sqrt{N+1}+ N-1}{N \sqrt{2}} \alpha}$

$\displaystyle{\delta_2 =((\sqrt{N+1}-1) / {N \sqrt{2}})\alpha}$

Величина $\alpha$ выбирается исследователем, исходя из характеристики решаемой задачи.

Вычисление центра тяжести: Если $x^{(i)}$ – точка, подлежащая отражению, то координаты центра тяжести определяется по формуле:

$x_c = \frac{1}{N} \sum_{|i-j| \gt 0} x^{(i)}$

Координаты новой вершины удовлетворяют уравнению:

$x_{new}}^{( j )} = x^(j) + \lambda(x_c - x^{( j )})$

Для того, чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е. $\lambda = 2$. $x_{new}^{(j)} = 2x_c - x^{( j )}$

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

Комментарии (0)

Комментировать могут только зарегистрированные пользователи

Подразделы
Новые статьи
Aрхив статей