Принципы построения генетических алгоритмов

Генетический алгоритм (ГА) можно рассматривать как одну из разновидностей случайного поиска [30], которая основана на механизмах, напоминающих естественный отбор и размножение.

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

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

Процедура: Генетический алгоритм

Begin

:=0;

Задать_начальное_значение ;

Оценить с помощью функции соответствия;

while (нет условия_завершения) do

Cкрещивать чтобы получить ;

Оценить с помощью функции соответствия;

Выбрать из и ;

:= +1;

End

End.

Таким образом, используются два вида операций:

1. Генетические операции: скрещивание и мутация;

2. Эволюционная операция: выбор.

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

Не нашли, что искали? Воспользуйтесь поиском: