4.1 Генетический алгоритм

Генетический алгоритм - адаптивный метод поиска, который в последнее время часто используется для решения задач функциональной оптимизации. Он основан на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу «выживает наиболее приспособленный» [15]. Подражая этому процессу генетический алгоритм способен “развивать” решения реальных задач, если те соответствующим образом закодированы. Генетический алгоритм может использоваться для проектирования структуры моста, поиска максимального отношения прочности, для использования интерактивного управления процессом или балансировании загрузки на многопроцессорном компьютере. Основные принципы генетического алгоритма были сформулированы Голландом (Holland, 1975) [15]. Алгоритм моделирует те процессы в популяциях, которые являются существенными для развития. Генетический алгоритм работает с совокупностью “особей” - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее “приспособленности” согласно тому, насколько “хорошо” соответствующее ей решение задачи. Воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи.

Рис. 7. Принцип работы генетического алгоритма

Преимущество генетического алгоритма:

1) Поиск оптимального решения осуществляется в кодовом пространстве;

2) С каждым разом после операции селекции мы получаем две новые пары, которые являются возможным решением.

3) Благодаря множеству операций (селекция, мутация, скрещивания) можно получить разнообразный набор возможных решений.

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

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