Классический генетический алгоритм. Часть V. Выбор наилучшей хромосомы

Классический генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

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

Рассмотрим последний этап: выбор наилучшей хромосомы.

Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.

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

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

Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности $p_{c}$ . Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью $N$ , то $p_{c}~=~2/N$ . Аналогично, если из родительской популяции численностью $N$ выбирается $2z$ хромосом (), которые образуют $z$ пар родителей, то $p_{c}~=~~{2z}/{N}$ . Обратим внимание, что если все хромосомы текущей популяции объединены в пары до скрещивания, то $p_{c}~=~1$ . После операции скрещивания родители в родительской популяции замещаются их потомками.

Операция мутации изменяет значения генов в хромосомах с заданной вероятностью $p_{m}$ . Это приводит к инвертированию значений отобранных генов с на и обратно. Значение $p_{m}$ , как правило, очень мало, поэтому мутации подвергается лишь небольшое количество генов. Скрещивание – это ключевой оператор генетических алгоритмов, определяющий их возможности и эффективность. Мутация играет более ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания.