Алгоритм конкурирующих точек
Алгоритм конкурирующих точек в общем виде включает следующие операции.
1. По процедуре СДС синтезируется l (l = h + l0) точек
(j = 1, ..., l), в которых определяется значение минимизируемой функции (критерия сравнения). Из этих l точек отбирается h точек, имеющих наилучшие значения критерия, которые в дальнейшем называются основными. Запоминается наихудшее значение критерия основных точек j0. При этом считается, что совершен нулевой глобальный (групповой) шаг поиска (t = 0).
Таким образом, на t-м групповом шаге поиска имеем основные точки
, (10)
и, соответственно, невозрастающую последовательность чисел
j 0, j1, …, j t. (11)
2. Каждая основная точка делает шаг локального поиска, в результате чего точки (10) переходят в новую последовательность
. (12)
3. Синтезируется lt+1 дополнительных допустимых точек, каждой из которых разрешается сделать t+1 шагов локального поиска при условии, что после каждого шага с номером t (0 <= t <= t) ее критерий не хуже, чем соответствующий член последовательности (11). При нарушении этого условия точка исключается и не участвует в дальнейшем поиске глобального экстремума. Таким образом, имеется q (q <= l t+1) дополнительных точек, сделавших t + 1 шаг локального поиска:
, (13)
4. Среди точек (12) и (13) отбирается h точек с лучшими критериями:
, (14)
которые являются основными на (t + 1)-м групповом шаге поиска. Значение худшего критерия точек из последовательности (14) дополняет последовательность (11) числом jt+1.
5. Цикл по пп. 2-4 повторяется до нахождения глобального экстремума по заданным условиям прекращения поиска. В качестве условий прекращения поиска могут быть использованы, например, выполнение заданного числа Т групповых шагов.
Считая параметры li независимыми от i, будем иметь только два настраиваемых параметра алгоритма; h - число основных точек и l - число дополнительных точек.
Проведенные исследования позволяют рекомендовать следующие оптимальные значения этих параметров: h = 2…3, l = 12…18. Для простоты реализации алгоритма можно брать постоянные значения h и l.
В качестве процедуры ШЛП рекомендуется использовать следующие алгоритмы поиска локального экстремума:
алгоритм случайного поиска в подпространствах;
алгоритм случайного поиска с выбором по наилучшей пробе;
алгоритм сопряженных градиентов;
алгоритм Нельдера-Мида.
