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

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Более подробно описано в статьях:

• Генетические алгоритмы - математический аппарат
• Генетические алгоритмы в MetaTrader 4. Сравнение с прямым перебором оптимизатора

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

• Индивидуум = вариант решения задачи = набор из 10 хромосом Хj
• Хромосома Хj = объем вложения в проект j = 16-разрядная запись этого числа
• Так как объемы вложений ограничены, не все значения хромосом являются допустимыми. Это учитывается при генерации популяций.
• Так как суммарный объем инвестиций фиксирован, то реально варьируются только 9 хромосом, а значение 10-ой определяется по ним однозначно.

Естественный отбор в природе