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

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

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

   
   точек
   
   , в которых определяется значение минимизируемой функции (критерия сравнения). Из этих
   
   точек отбирается
   
   точек, имеющих наилучшие значения критерия, которые в дальнейшем называются основными. Запоминается наихудшее значение критерия основных точек
   
   . При этом считается, что совершен нулевой глобальный (групповой) шаг поиска (t = 0).

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

   (10)

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

   (11)

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

   (12)

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

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

   (13)

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

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

   (14)

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

   
   .

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

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

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

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

, . Для простоты реализации алгоритма можно брать постоянные значения и .

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

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

Содержание раздела

---