Основные этапы генетического алгоритма

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

Создание начального множества решений. Перед первым шагом нужно случайным образом создать начальную популяцию. Создание начального множества решений происходит на основе четырех основных принципов:

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

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

Размножение (скрещивание). Генетический алгоритм предполагает два способа размножения: половое и бесполое. Бесполое размножение — самокопирование особи, которое может применяться, например, при недостаточном количестве элементов во множестве особей. Половое размножение в генетическом алгоритме обычно происходит между двумя особями, но допустимо использование большего количества объектов. Главное требование к размножению — чтобы потоки имели возможность унаследовать признаки от своих родителей. Основные методы кроссинговера:

• · Простой (одноточечный). Перед началом работы оператора выбирается точка оператора кроссинговера, или разрывающая точка, которая обычно определяется случайно, затем генерируется новый потомок, состоящий из двух блоков родительских генов.
• · Двухточечной оператор кроссинговера. В каждой хромосоме выделяются по две точки оператора кроссинговера, и хромосомы обмениваются участками, расположенными между двумя точками разрыва.
• · Упорядоченный оператор. Случайным образом выбирается разрывающая точка в одной из родительской хромосом. Затем блок генов, расположенный до точки разрыва копируется в новую хромосому. Остальные позиции в дочерней хромосоме дополняются генами из второй хромосомы в упорядоченном виде слева направо (берутся гены, которые еще не вошли в генотип дочерней хромосомы).
• · Циклический оператор. Он выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей.
• · Универсальный оператор кроссинговера. Широко применяется в решении задач из теории расписаний. Вместо разрезающей точки в универсальном операторе кроссинговера используется двоичная маска, длина которой равна длине заданных хромосом. Потомки получаются путем сложения в двоичной арифметике родительской хромосомы с маской.
• · «Жадный» оператор. На каждом шаге создания дочерней хромосомы происходит частичный выбор локально оптимального значения между генами родительских хромосом .

Мутации. Проведение преобразований над генотипом одной особи. К основным операторам мутации относят:

• · Одноточечный. Выбирается произвольный ген в родительской хромосоме и меняется местами с рядом стоящим геном.
• · Двухточечная мутация. Выбираются две точки разреза в гене, затем производится перестановка генов между собой, расположенных справа от точек разреза.
• · Обмен строительных блоков (многоточечный оператор). Строительные блоки — тесно связанные между собой гены, которые нежелательно изменять при выполнении генетических операторов. Когда строительные блоки между точками разреза одинаковы, многоточечный оператор выполняется следующим образом: при четном числе точек разреза, меняются местами гены, расположенные справа и слева от выбранных точек, при нечетном — происходит обмен участками хромосом, расположенными между четными точками разреза.

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

• · Селекция на основе рулетки — простой и широко используемый метод. При его реализации каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмеренная с величиной целевой функции. При этом каждый элемент имеет вероятность выбора для селекции.
• · Селекция на основе заданной шкалы. При применении этого метода популяция сортируется на основе заданного критерия. Каждому элементу назначается определенное число, и селекция выполняется согласно этому числу.
• · Элитная селекция. В этом случае выбираются лучшие (элитные) элементы, и преобразования происходят уже над ними. Этот процесс повторяется каждое поколение до тех пор, пока будут появляться новые элитные элементы.
• · Турнирная селекция. Некоторое число элементов выбирается случайно, и лучшие элементы в выбранной группе выбираются для дальнейшего эволюционного поиска.

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

Область применения генетического алгоритма

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

Генетические алгоритмы широко применяются для решения следующих задач:

• · оптимизация функций;
• · оптимизация запросов в базах данных;
• · решение задач на графах;
• · настройка и обучение искусственной нейронной сети;
• · игровые стратегии;
• · моделирование искусственной жизни;
• · теория приближений;
• · решение задач о покрытиях и разбиениях т др.