Влияние параметров алгоритма на эффективность поиска

Проанализируем влияние параметров a, g, b на эффективность процедуры поиска.

Коэффициент отражения a используется для проектирования вершины с наибольшим значением f(X) через центр тяжести деформируемого многогранника.

Коэффициент g вводится для растяжения вектора поиска в случае, если отражение дает вершину со значением f(X), меньшим, чем наименьшее значение f(X), полученное до отражения.

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

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

Влияние на процедуру поиска параметров b и g менее четко выражено. Как показывают результаты решения тестовых задач, можно рекомендовать следующие диапазоны значений для этих параметров: 0,4£b£0,6; 2£g£3. При этом отмечается, что влияние коэффициента b на эффективность поиска заметнее, чем влияние g. При bÎ(0;0,4) имеет место преждевременное окончание поиска, а при b>0,6 требуется выполнить больше шагов для достижения окончательного решения.

 

Типовой пример.

Выполним одну итерацию поиска по методу деформируемого многогранника для задачи минимизации функции f(X)=4(x₁-5)²+(x₂-6)².

Поскольку функция зависит от двух переменных, в начале поиска используется многогранник с тремя вершинами X¹=(8;9)^T, X²=(10;11)^T, X³=(8;11)^T.

Зададим значения параметров a=1, g=2. Вычислим значения функции в них: f(X¹)=45; f(X²)=125; f(X³)=65.

Вершиной с наименьшим значением функции оказывается X^L=X¹. Вершиной с наибольшим значением функции является X^h=X². Далее находим центр тяжести вершин, исключая X².

.

Отражая “худшую” точку X^h относительно найденной X⁴ , получим точку

Xⁿ⁺³= X⁵= X⁴+a(X⁴- X²)= ,

значение функции в которой f(X⁵)=13.

Поскольку f(X⁵)< f(X^L)=45, выполняем операцию растяжения, определяя точку

Xⁿ⁺⁴= X⁶= X⁴+g(X⁵- X⁴)= ,

и значение функции в ней f(X⁶)=8,

Так как f(X⁶)< f(X^L), заменяем вершину X^h на Xⁿ⁺⁴, полагая X²= X⁶ и тем самым завершая первую итерацию поиска.

На рис.4 приведена геометрическая интерпретация поиска по деформируемому многограннику на пяти начальных этапах минимизации функции f(X)=4x₁²+x₂²-40x₁-12x₂+136.

Рис.4. Траектория поиска по деформируемому многограннику.

Очевидно, линиями уровня функции являются эллипсы. На рисунке изображены линии уровня, соответствующие значениям функции 2, 5, 10, 20 и 30. Пунктиром выделены многогранники с вершинами X_j⁽ⁱ⁾, в обозначениях которых j – номер вершины деформируемого многогранника на i-том этапе поиска. Сплошными линиями показана траектория поиска, соединяющая вершины многогранника, соответствующие наименьшим значениям f(X) в каждом из них. Убедитесь в соответствии графической иллюстрации описанному с помощью формул (6)-(9) алгоритму.