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

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

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

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

Селекция на основе рулетки - это самый простой и наиболее используемый в ПГА метод. При его использовании каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции, причем элемент с большим значением ЦФ имеет большую вероятность для выбора.

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

Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения ЦФ. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс идет до тех пор, пока продолжают появляться элитные элементы.

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

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

Опишем теперь методы кроссинговера. В литературе часто их называют операторами кроссинговера (ОК). Основная функция ОК - создавать хромосомы потомков на основе различного скрещивания родителей. Существует огромное число ОК, так как их структура в основном и определяет эффективность ГА. Кратко рассмотрим основные ОК, известные в литературе, и их модификации.

Одноточечный (простой) ОК. Перед началом работы одноточечного ОК определяется так называемая точка ОК, или разрезающая точка, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны». Например, пусть популяция Р состоит из двух хромосом Р={р1, р2}, которые выступают в качестве родителей. Пусть первый и второй родители имеют вид р1: (11111), р2: (00000). Выберем точку ОК между вторым и третьим генами в р1, р2. Тогда, меняя элементы после или перед точкой ОК между двумя родителями, можно создать два новых потомка. В нашем примере получим:

Рисунок 1 - Одноточечный ОК

Итак, одноточечный ОК в интеллектуальной ИС выполняется в три этапа:

. Две хромосомы А = a1, а2, ., aL и В = а'1, а'2, ., а'L выбираются случайно из текущей популяции.

. Число к выбирается из {1, 2, .,L-1} также случайно. Здесь L - длина хромосомы, к-точка ОК (номер или значение, код гена, после которого выполняется разрез хромосомы).

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