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

Условимся вершинам симплекса приписать значение рангов 1,2,…, n+1, если их проранжировать в хронологическом порядке реализации опытов: самой «старой» вершине приписывается значение «1» следующей по «возрасту» – значение «2» и так далее, а самой «молодой» – значение «n+1». Алгоритм поиска учитывает также тот факт, что с приближением к экстремуму полезный сигнал становится слабее (приращение функции отклика уменьшается, так как обычно поверхность отклика становится более пологой), а слежение – более трудным. С этой целью предусматриваются приёмы модулирования длин рабочего шага R(Y) и коэффициента запоминания удачного в прошлом направления движения a(Y) от достигнутого уровня функции отклика (параметра оптимизации) Y. Для упрощения алгоритма можно величину рабочего шага фиксировать (R = const), а коэффициенту a придавать только два значения: a=1, если выход из последней ориентации был удачным, и a=0, если выход был неудачным.

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

Пусть система, находясь в периоде восхождения, совершила неудачный шаг A_i ® A_i+1 (A_i, A_i+1 – два последних следовавших друг за другом состояния системы), то есть, известны значения Y_i+1. Поиск ведется в соответствии со следующей операторной схемой:

P₁ W₂ P₃ P₄ P₅ P₆ W₇ Q₈ P₉ W₁₀ Q₁₁ . (8.17)

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

P₁: Расчетным путем (см. раздел 8.4) находится точка А_i+2, которая вместе с точками А_i и A_i+1 образует случайно ориентированный в двумерном пространстве правильный симплекс. В нашем случае (n=2) это одна из двух возможных точек, образующих с точками А_i и A_i+1 равносторонний треугольник (выбирается случайным образом). При n >2 число правильных симплексов, которые можно построить на двух точках А_i и A_i+1 , бесконечно большое.

W₂: Реализуется опыт в точке А_i+2, получается отклик Y_i+2.

Р₃: Находим единичный вектор

, (8.18)

где — вектор, направленный из точки А_i в точку А_k (Y_k>Y_j), численно равный

, (8.19)

— расстояние между точками А_i и А_k (ребро симплекса; при n=2 – сторона равностороннего треугольника);

; (8.20)

— сумма рангов j-й и k-й точек;

b— коэффициент доверия результатам опытов, учитывающий из возраст (0<b?1). Чем быстрее дрейф, тем меньше должно быть b.

При образовании вектора (8.18) в случае n=2 происходит оценка изменения функции отклика Y по направлениям трех ребер двумерного симплекса – сторон равностороннего треугольника, в то время как в градиентных методах ее изменение оценивается лишь по двум направлениям – вдоль координатных осей. При увеличении размерности n число ребер ощутимо возрастает. Так, при n=3 число ребер равно , при n = 4 — , при n = 5 – и так далее, что даёт возможность весьма тщательного исследования поведения функции отклика Y в факторном пространстве (X₁,X₂,….,X_n) в самых различных направлениях.

Р₄: Находим вектор

, (8.21)

где

, (8.22)

. (8.23)

В векторе сливаются новое перспективное направление движения и прежнее удачное направление. Функции d(Y) и a(Y) необходимо предварительно создать, используя априорные представления о хороших и плохих значениях параметра оптимизации Y. Желательно, чтобы во время поиска функции d(Y) менялась монотонно в интервале (1,5; 2,0), а функция d(Y) — в интервале (0,5; 1,0), причем верхние границы интервалов должны соответствовать отличным ее значениям Y, а нижние – плохим значениям. Рассчитывая значения d(Y) и a(Y) оператора Р₄, необходимо подставить в эти функции значение Y, полученное в последнем опыте.

Р₅: Находится центр тяжести – С_т точек А_i,А_i+1, А_i+2 (центр симплекса).

Р₆: Совершается шаг из центра тяжести С_т, равный и находится точка А_i+3.

W₇: Реализуется опыт в точке А_i+3, определяется значение(величина отклика) Y_i+3.

Q₈: 1) Y_i+3 меньше хотя бы двух значений Y, найденных ранее («неудача»). Переход к оператору P₁. Период ориентации начинается с точек А_i+2, А_i+3. Вектор сохраняется неизменным до тех пор, пока система не совершает удачный шаг при восхождении.

2) Y_i+3 больше хотя бы двух значений Y, найденных раннее (“удача”). Переход к оператору Р₉.

Р₉: Совершается шаг длиной d(Y) в направлении вектора , находится точка A_i+4. Функция d(Y) сохраняет свое прежнее значение.

W₁₀: Реализуется опыт в точке А_i+4, определяется значение Y_i+4.

Q₁₁: 1) Y_i+4>Y_i+3 (“удача”). Переход к оператору Р₉;

2) Y_i+4Y_i+3 (“неудача”). Переход к оператору Р₁.

Период ориентации начинается с точек А_i+3, A_i+4. Поиск начинается со случайного правильного симплекса, построенного на основе этих точек.

Идеи метода иллюстрирует рис. 8.10.

Эффективность метода в значительной степени зависит от параметров движения b, a, d. Рассматривая эти параметры как независимые переменные, которые подлежат непрерывной корректировке во время поиска, мы получим еще большую адаптивность метода.

Рис. 8.10. Определение направления рабочего шага в методе векторного поиска