Информатика - Учебное пособие (Воронина М.А.)

2 описание простого генетического алгоритма

 

Генетические алгоритмы носят итерационный характер и имеют дело с обработкой популяций индивидуумов P(t)= для итерации t (поколение t). Каждый индивидуум представляет собой потенциальное решение задачи (испытание) и представлен в некоторой, возможно достаточно сложной, структуре данных S. В качестве S будем рассматривать бинарные строки

Каждое решение оценивается и определяется мера его "пригодности". Затем формируется новая популяция (итерация или поколение t + 1). На первом шаге этого формирования - этапе селекции - происходит отбор индивидуумов, обладающих лучшей пригодностью. На следующем шаге некоторые из отобранных таким образом индивидуумов подвергаются преобразованиям с помощью "генетических операторов": мутации и скрещивания. Оператор мутации создает нового индивидуума путем относительно малого изменения в одном индивидууме, а оператор скрещивания осуществляет более сильные трансформации и создает нового индивидуума путем комбинирования частей из нескольких (двух или больше) индивидуумов. После ряда итерационных шагов алгоритм сходится к лучшему из возможных решений. Остановимся теперь более подробно на трех "генетических операторах" - селекции, скрещивании и мутации.

Селекция. Целью селекции является осуществление выборки индивидуумов в текущей популяции (т.е. из некоторого набора) пропорционально их пригодности. Обычно используют четыре различных механизма селекции - “колесо рулетки”, остаточная стохастическая выборка, стохастическая равномерная выборка и турнирная селекция. Первые три алгоритма являются вариантами пропорциональной селекции, а последний - непропорциональной.

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

Скрещивание. Наиболее простым является одноточечное скрещивание - каждая выбранная таким образом пара строк скрещивается следующим образом: случайным образом выбирается положение точки сечения (целое число k в промежутке от 1 и l-1, где l - длина строки). Затем, путем обмена всеми элементами между позициями k+1 и l включительно, рождаются две новых строки. Например, пусть первая особь -  а вторая соответственно  и пусть случайно выбранная точка сечения будет после третьего гена (бита). Тогда в результате скрещивания получим две особи-потомки -  и . После этого потомки замещают родительские особи в промежуточной популяции . Схематично этот вариант показан на рисунке 1.1.

 

Рисунок - 1.1

 

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

После рекомбинации, применяется также оператор мутации. Каждый бит каждой особи в популяции мутирует (точнее, пытается мутировать) с некоторой низкой вероятностью pm. Обычно мутация применяется с вероятностью меньше чем 1 \%. Обычно мутация интерпретируется как “зеркальное отражение“ бита (инверсия его значения, т.е. изменение его с 1 на 0 или с 0 на 1).

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

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

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

 

Рисунок - 1.2

 

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