Методы прямого поиска в гибридных алгоритмах…
7
ограниченности разностей функций при ограниченной вариации ар-
гумента. К недостаткам следует отнести потерю части информации о
близости точек в исходном многомерном пространстве. Предложен-
ный подход не требует вычисления производных критериальных
функций по переменным модели, что позволяет расширить примене-
ние алгоритма для решения задач локальной недифференцируемой
оптимизации.
Гибридные алгоритмы глобальной оптимизации.
Структуры
алгоритмов глобальной минимизации, представленных ниже, построе-
ны на основе стохастического алгоритма M-PCA [13], объединенного с
процедурами поиска локальных минимумов не всюду дифференциру-
емых функций. Работа современного алгоритма глобальной оптимиза-
ции M-PCA основана на использовании аналогии с физическими про-
цессами абсорбции и рассеяния частиц при ядерных реакциях.
В простейшей версии алгоритма для исследования области поис-
ка используется одна частица. На начальном шаге выбирается проб-
ное решение (Old_Config), которое затем модифицируется посред-
ством стохастического возмущения (Perturbation ()), что позволяет
найти новое решение (New_Config). С помощью функции Fitness ()
дается сравнительная оценка нового и предыдущего решений, на ос-
новании которой новое решение может быть принято или отвергнуто.
Если новое решение отвергнуто, то происходит переход к функции
Scattering (), реализующей схему Метрополиса. Для сканирования
области, перспективной на минимум, применяются функции Perturba-
tion() и Small_Perturbation (). Новое решение принимается, если оно
лучше предыдущего (абсорбция); если найденное решение хуже
предыдущего, то происходит переход в отдаленную область про-
странства поиска (рассеяние), что позволяет преодолевать локальные
минимумы.
Эффективность описанного поиска глобального решения алго-
ритмом значительно повышается за счет одновременного использо-
вания большого числа частиц. Такой подход реализует алгоритм
M-PCA, который непосредственно ориентирован на применение в
среде параллельных вычислений. Наилучшее решение определяется с
учетом данных о всех частицах, участвующих в процессе. Един-
ственным задаваемым параметром для алгоритма M-PCA является
число итераций.
Предложены гибридные алгоритмы, интегрирующие алгоритм
M-PCA и детерминированные методы прямого локального поиска.
Первый гибридный алгоритм объединяет стохастический алгоритм
M-PCA сканирования пространства переменных и детерминирован-
ный метод Хука — Дживса локального поиска. Результирующий ги-
бридный алгоритм M-PCAHJ реализован в виде прикладного про-
граммного обеспечения. Ниже представлен фрагмент псевдокода
гибридного алгоритма M-PCAHJ.
