Генетические алгоритмы

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

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

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

Начальные элементы в генетическом алгоритме называют «родителями». «Родители» в генетических алгоритмах выбираются из популяции на основе заданных правил, а затем скрещиваются для производства «детей» (потомков).

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

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

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

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

В простых генетических алгоритмах существуют три основных оператора:

- селекция (репродукция);

- кроссинговер (скрещивание);

- мутация.

Рассмотрим кратко эти основные операторы.

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

Существует много различных видов селекции. Рассмотрим некоторые из них.

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

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

Элитная селекция состоит в выборе лучших, элитных элементов популяции на основе сравнения целевых функций.

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

Основной функцией операторов или методов кроссинговера является создание хромосом «потомков» на основе скрещивания «родителей». Существует весьма значительное количество операторов кроссинговера и от них в значительной степени зависит эффективность генетических алгоритмов.

Кратко рассмотрим некоторые из операторов кроссинговера.

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

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

Одноточечная операция кроссинговера выполняется в три этапа.

1. Пусть две хромосомы

и

,

выбираются случайно из некоторой популяции в качестве «родителей».

2. Точка «разреза»  выбирается из  случайным образом, где  длина хромосомы ().

3. Две новых хромосомы формируются из  и  путем перестановок компонентов согласно правилу:

,

.

Возможно также формирование хромосом из  и  путем перестановок других компонентов согласно следующему правилу:

,

.

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

Существует много модификаций двухточечной операции кроссинговера, а также и многоточечные операторы.

Рассмотрим кратко основные операторы мутации.

Одноточечный оператор мутации, в котором случайно выбирается ген в хромосоме и меняется местами с рядом расположенным геном, является основной операцией мутации в генетических алгоритмах. В качестве примера рассмотрим хромосому:

который после операции одноточечной мутации в -м гене принимает вид:

или

.

Двухточечная операция мутации заключается в перестановке генов, расположенных справа от точек «разреза»  и . Например, хромосома:

 

после операции двухточечной мутации принимает вид:

.

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

Результат одноточечной операции инверсии с точкой «разреза»  для хромосомы  можно представить в виде:

.

Результат двухточечной операции инверсии с точками «разреза»  и  для хромосомы  можно представить в виде:

.

Операция транслокации представляет собой комбинацию оператора кроссинговера и оператора инверсии. Результат одноточечной операции транслокации с точкой «разреза»  для хромосом  и  можно представить в виде:

,

.

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

Действительно, пусть имеются две хромосомы, которые удобно представить в следующем виде:

Номер или шифр детали	1	2	3	4	5
Порядок запуска деталей	1	2	3	4	5

 

Номер или шифр детали	5	4	3	2	1
Порядок запуска деталей	1	2	3	4	5

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

После проведения операции кроссенговера с точкой «разреза» =4 получим:

Номер или шифр детали	1	2	3	2	1
Порядок запуска деталей	1	2	3	4	5

 

Номер или шифр детали	5	4	3	4	5
Порядок запуска деталей	1	2	3	4	5

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

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

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

Рассмотрим вычислительную схему простейшего генетического алгоритма для построения расписания обработки деталей по шагам.

Шаг 1. Производится формирование начальной популяции хромосом, которые определяют порядок запуска деталей на обработку. Включается отсчет времени, а также счетчик поколений популяций. Следует переход к Шагу 2.

Шаг 2. Производится вычисление приспособленности хромосом популяции, т. е. производится вычисление целевой функции для каждой хромосомы популяции, которое сводится к построению расписания обработки и вычислению значения критерия оценки расписания. Определяется рекордное значение критерия оценки расписания для имеющейся популяции. Следует переход к Шагу 3.

Шаг 3. Производится проверка окончания вычислений. Если время вычислений или количество поколений превышает заданную величину, или рекордное значение критерия оценки расписания превышает заданное, то следует переход к Шагу 7, в противном случае к Шагу 4.

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

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

Шаг 6. Завершение работы алгоритма. Выдача отчета с данными лучшего построенного расписания.

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