Общая структура генетического алгоритма

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

Генетические алгоритмы используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.

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

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

begin {генетический алгоритм}

t:= 0;

done:= false;

init_population(P (0) );

{генерация начальной популяции P (0) (случайным образом или случайным в комбинации с некоторым набором начальных решений) и оценка пригодности каждой особи}

while not done do begin

P ':= select_parents ( P (t));

{выбор родителей для скрещивания при помощи оператора селекции согласно пригодности и помещение их в промежуточную популяцию P '}

recombine P '(t);

{промежуточная популяция попарно подвергается оператору рекомбинации или скрещивания}

mutate P ' (t);

{каждая особь в промежуточной популяции подвергается оператору мутации}

evaluate P ' (t);

{расчет целевой функции для всех новых особей}

P (t +1):= P '(t);

{промежуточная популяция копируется в новое поколение P (t +1)}

Done:= || P (t +1) - P (t +1)||<e;

{проверка выполнения критерия сходимости}

t:= t + 1;

end {while}

End

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