Генетические операторы

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

Оператор отбора [селекция]. Служит для создания промежуточной популяции . В промежуточную популяцию копируются хромосомы из текущей популяции в соответствии с их вероятностью воспроизведения Pi. Существуют различные схемы отбора, самая популярная из них – пропорциональный отбор: .

Простейший пропорциональный отбор - рулетка (roulette-wheel selection, Goldberg, 1989c) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

Для устранения зависимости от положительных значений и влияний больших чисел используется масштабирование оценок или ранжирование.

При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

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

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

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

Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:

Таблица

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

Оператор кроссинговера (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) - операция, при которой две хромосомы обмениваются своими частями. Производит обмен генетического материала между родителями для получения потомков. Кроссинговер смешивает "генетический материал" двух родителей, причем можно ожидать, что приспособленность родителей выше средней в предыдущем поколении, так как они только что прошли очередной раунд борьбы за выживание. Это аналогично соперничеству настоящих живых существ, где лишь сильнейшим удается передать свои (предположительно хорошие) гены следующему поколению. Важно, что кроссинговер может порождать новые хромосомы, ранее не встречавшиеся в популяции. Простейший одноточечный кроссинговер (рис. 3) производит обмен частями, на которые хромосома разбивается точкой кроссинговера. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков. Двухточечный кроссинговер обменивает кусок строки, попавшей между двумя точками. Предельным случаем является равномерный кроссинговер, в результате которого все биты хромосом обмениваются с некоторой вероятностью. Этот оператор служит для исследования новых областей пространства и улучшения существующих (приспособление).

Рис. 3. Кроссинговер

Все типы кроссинговера обладают общим свойством: они контролируют баланс между дальнейшим использованием уже найденных хороших подобластей пространства и исследованием новых подобластей. Достигается это за счет неразрушения общих блоков внутри хромосом-родителей, сохраняющем "хорошие" паттерны, и одновременном исследовании новых областей в результате обмена частями строк (хромосом). Совместное использование отбора и кроссинговера приводит к тому, что области пространства, обладающие лучшей средней оптимальностью, содержат больше элементов популяции, чем другие. Таким образом, эволюция популяции направляется к областям, содержащим оптимум с большей вероятностью, чем другие.

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

Рис. 4. Мутация

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

Рис. 5. Блок-схема генетического алгоритма

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация. Блок-схема генетического алгоритма достаточно проста (рис.5)