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

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

Генетические алгоритмы работают с совокупностью «особей»  популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.

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

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

Генетические алгоритмы [1−4] работают по аналогии с алгоритмом эволюции видов (популяций) живых организмов. В генетическом алгоритме каждый индивид кодируется сходным с ДНК методом  в виде строки из символов одного типа. Длина строки (ДНК) постоянна. В дальнейшем в качестве кодовой строки будет использоваться битовая (двоичная) строка. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием скрещивания и мутаций.

Кодовую строку каждого индивида назовем геномом. Для каждого индивида в популяции задается целевая функция. Значение целевой функции назовем целевым значением. Вектор, состоящий из целевых значений всех индивидов в популяции, назовем вектором целевых значений. Тогда если вычислен вектор целевых значений, то можно определить приспособленность (fitness) индивида в популяции.