Генетические алгоритмы
Для компьютерных алгоритмов решения (поиска), использующих вычислительные модели механизмов естественной эволюции в качестве ключевых структурных элементов, используется обобщенное название - эволюционные алгоритмы. Существует множество разновидностей подобного рода алгоритмов, отличающихся использованием или неиспользованием конкретных механизмов, а также различиями трактовки этих механизмов и представлением индивидов.
В генетическом алгоритме (ГА) каждый индивид кодируется сходным с ДНК методом - в виде строки из символов одного типа. Длина строки (ДНК) постоянна. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием скрещивания и мутаций.
Назовем представление каждого индивида геномом. Для каждого вида и каждого представления для данного целевого условия задается целевая функция. Значение целевой функции назовем целевым значением. Вектор, состоящий из целевых значений всех индивидов в популяции, назовем вектором целевых значений. Тогда если вычислен вектор целевых значений, то можно определить приспособленность (fitness) индивида в популяции, для чего задается специальная функция приспособленности от данного целевого значения и от вектора целевых значений. Аналогично вектору целевых значений введем вектор приспособленности. Мы отделяем приспособленность от целевого значения специально, т.к. приспособленность индивида зависит и от остальных индивидов, и важна для выживаемости индивида, а целевое значение важно в первую очередь для нас. Часто целевое значение называют приспособленностью, а значение приспособленности, в смысле вероятность участия в размножении, неявно вычисляется во время отбора. Процесс эволюции останавливается, когда популяция отвечает определенному критерию - критерию завершения.
Принципиальная схема работы ГА состоит из следующих основных фаз:
- Создание начальной популяции. Задание генома каждому из индивидов. Расчет вектора целевых значений.
- Шаг эволюции - построение нового поколения.
- Проверка критерия завершения, если не выполнено - переход на 2.
Шаг эволюции можно разделить на следующие этапы:
- Вычисление вектора приспособленности.
- Отбор кандидатов на скрещивание (Отбор - Selection).
- Скрещивание, т.е. порождение каждой парой отобранных кандидатов новых индивидов, путем геномов.
- Мутация геномов.
- Вычисление вектора целевых значений и построение новой популяции (нового поколения).
Дата добавления: 2015-12-17; просмотров: 22; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!