Глобальный случайный поиск с независимым выбором плотности распределения пробных шагов.

Процедура поиска значительно усложняется в тех случаях, когда функция качества является не унимодальной, а многоэкстремальной (рис. 11.11). Практически все рассмотренные способы поиска локального экстремума не могут быть использованы без специальных модификаций для поиска глобального экстремума. Исключение составляет метод полного перебора. Однако на практике им пользоваться бывает неудобно из-за слишком больших затрат времени на поиск. Как правило, методы поиска глобального экстремума базируются на статистических принципах.

Это объясняется тем, что поиск статистическими методами позволяет управлять плотностью распределения независимых пробных шагов и сосредоточивать поисковые шаги в местах наиболее вероятного нахождения глобального экстремума.

Глобальный случайный поиск с независимым выбором плотности распределения пробных шагов может быть описан следующей рекуррентной формулой:

где это пробное состояние, выбранное случайно и сохраненное в памяти в случае удачной пробы; вычисленное в пробном состоянии значение функции качества и сохраненное в памяти в случае удачной пробы; пробный значение функции качества на пробном шаге.

При равномерной плотности распределения пробных шагов поиск разделяется на этапов из пробных шагов, где

Каждый пробный этап осуществляется внутри гиперпараллелепипеда в пространстве состояний X, т. е.

причем стороны гиперпараллелепипеда с каждым этапом уменьшаются в раз по сравнению с этапом в соответствии с формулой:

где — точка, соответствующая пробному шагу с меньшим значением функции качества из всех проб на этапе.

Несмотря на равномерную плотность распределения пробных шагов внутри каждого этапа, происходит увеличение плотности распределения от этапа к этапу за счет уменьшения зоны поиска (11.62), т. е.

где — плотность распределения пробных шагов на этапе; — объем гиперпараллелепипеда на этапе.

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

Иногда целесообразно пробные шаги на каждом последующем этапе распределять не равномерно, а по нормальному закону, например

где

— исходная дисперсия;

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

Обычно время, отводимое на поиск, ограничено, поэтому целесообразно управлять не только плотностью распределения пробных шагов внутри этапов, но и количеством таких проб. Например, в начале поиска количество пробных шагов внутри этапа может быть относительно небольшим, что связано с приблизительным выделением «подозреваемой» на глобальный экстремум подобласти, а затем для более точного определения положения глобального экстремума используется оставшееся количество пробных шагов.