Символьная модель простого генетического алгоритма

Модель эволюции в природе, реализованная программно

Рисунок 34 Модель эволюции в природе, реализованная программно

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

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

Пример:

Дано К=500 – объем капитала.

Задача – распределить капитал между объектами.

1. Создание начальной популяции:

2. Скрещивание:

3. Мутация:

4. Отбор.

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

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

Биологический термин «генотип» относится к полной генетической модели и соответствует структуре генетического алгоритма. Термин «фенотип» относится к внешне наблюдаемым признакам и соответствует вектору в пространстве параметров.