Проектирование систем искусственного интеллекта



         

Алгоритм конкурирующих точек


Алгоритм конкурирующих точек в общем виде включает следующие операции.

  1. По процедуре СДС синтезируется

    l(l=\eta + \lambda_0)
    точек
    \overline{X}_j (j=1,...,l)
    , в которых определяется значение минимизируемой функции (критерия сравнения). Из этих
    l
    точек отбирается
    \eta
    точек, имеющих наилучшие значения критерия, которые в дальнейшем называются основными. Запоминается наихудшее значение критерия основных точек
    \phi_0
    . При этом считается, что совершен нулевой глобальный (групповой) шаг поиска (t = 0).

    Таким образом, на t-м групповом шаге поиска имеем основные точки

    \overline{X}_1^t,\overline{X}_2^t,K,\overline{X}_{\eta}^t
    (10)

    и, соответственно, невозрастающую последовательность чисел

    \phi_0,\phi_1,...,\phi_t
    (11)

  2. Каждая основная точка делает шаг локального поиска, в результате чего точки (10) переходят в новую последовательность

    \overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}
    (12)

  3. Синтезируется

    \lambda_{t+1}
    дополнительных допустимых точек, каждой из которых разрешается сделать t+1 шагов локального поиска при условии, что после каждого шага с номером
    \tau (0 \le \tau \le t)
    ее критерий не хуже, чем соответствующий член последовательности (11). При нарушении этого условия точка исключается и не участвует в дальнейшем поиске глобального экстремума. Таким образом, имеется
    q(q\le \lambda_{t+1})
    дополнительных точек, сделавших t+1 шаг локального поиска:

    \overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{q}^{t+1}
    (13)

  4. Среди точек (12) и (13) отбирается

    \eta
    точек с лучшими критериями:

    \overline{X}_1^{t+1},\overline{X}_2^{t+1},K,\overline{X}_{\eta}^{t+1}
    (14)

    которые являются основными на t+1-м групповом шаге поиска. Значение худшего критерия точек из последовательности (14) дополняет последовательность (11) числом

    \phi_{t+1}
    .

  5. Цикл по пп. 2—4 повторяется до нахождения глобального экстремума по заданным условиям прекращения поиска. В качестве условий прекращения поиска могут быть использованы, например, выполнение заданного числа Т групповых шагов.

Считая параметры

\lambda_i
независимыми от i, будем иметь только два настраиваемых параметра алгоритма;
\eta
— число основных точек и
\lambda
— число дополнительных точек.

Проведенные исследования позволяют рекомендовать следующие оптимальные значения этих параметров:

\eta = 2…3
,
\lambda = 12…18
. Для простоты реализации алгоритма можно брать постоянные значения
\eta
и
\lambda
.

В качестве процедуры ШЛП рекомендуется использовать следующие алгоритмы поиска локального экстремума:

  • алгоритм случайного поиска в подпространствах;
  • алгоритм случайного поиска с выбором по наилучшей пробе;
  • алгоритм сопряженных градиентов;
  • алгоритм Нельдера-Мида.



Содержание  Назад  Вперед