Генетические алгоритмы поиска глобального экстремума

Как известно, оптимизационные задачи заключаются в нахождении минимума или максимума целевой функции. Как правило, целевая функция - сложная функция, зависящая от некоторых входных параметров. В оптимизационной задаче требуется найти значения входных параметров, при которых целевая функция достигает минимального или максимального значения. Для этого существует целый класс оптимизационных методов, которые можно условно разделить на методы, использующие понятие производной (градиентные методы) и стохастические методы (методы, основанные на получении большого числа реализаций стохастического (случайного) процесса). С их помощью можно найти экстремальное значение целевой функции, но не всегда можно быть уверенным, что получено значение глобального экстремума. Нахождение локального экстремума вместо глобального называется преждевременной сходимостью. Для решения этой проблемы и проводится поиск новых оптимизационных алгоритмов. Предложенные сравнительно недавно - в 1975 году в Мичиганском университете Джоном Холландом (John Holland) генетические алгоритмы (ГА) основаны на принципах естественного отбора Ч. Дарвина и относятся к стохастическим методам.

Изначально новый алгоритм получил название «репродуктивный план Холланда» и в дальнейшем активно использовался в качестве базового алгоритма в эволюционных вычислениях. Идеи Холланда развили его ученики Кеннет Де Йонг (Kenneth De Jong) из университета Джорджа Мейсона (Вирджиния) и Дэвид Голдберг (David E. Goldberg) из лаборатории ГА Иллинойса. Благодаря им, был создан классический ГА, описаны все операторы и исследовано поведение группы тестовых функций (именно алгоритм Голдберга и получил название «генетический алгоритм»).

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

Эти алгоритмы успешно применяются в различных областях деятельности (экономика, физика, технические науки и т.п.). Созданы различные модификации ГА и разработан ряд тестовых функций.

генетический оператор алгоритм функция

• Эволюционные процессы в природе
• Принцип работы генетического алгоритма
• Операторы выбора родителей
• Рекомбинация (воспроизведение)
• Мутация
• Операторы отбора особей в новую популяцию
• Разнообразие генетических алгоритмов
• Модели параллельных генетических алгоритмов
• Модернизация генетических алгоритмов