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

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

Генетический алгоритм состоит из набора генетических операторов.

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

Оператор репродукции (селекция) – это процесс, посредством которого хромосомы (альтернативные решения), имеющие более высокое значение целевой функции (с «лучшими» признаками), получают большую возможность для воспроизводства (репродукции) потомков, чем «худшие» хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичных или различных потомков. Существует большое число видов операторов репродукции:

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

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

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

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

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

· «случайный выбор хромосом;

· выбор хромосом на основе значений целевой функции.

При случайном выборе хромосом частота R образования родительских пар не зависит от значения целевой функции хромосом и полностью определяется численностью популяции N:

,

где β – коэффициент селекции, принимающий в зависимости от условий внешней среды значение 1…4.

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

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

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

(2)

где ЦФ – целевая функция, ОР – это оператор репродукции, моделирующий естественный процесс селекции, Рr (ОР) – вероятность выбора хромосом для репродукции.

Вторая стратегия реализуется так: часть хромосом выбирается случайным образом, а вторая – с вероятностью на основе выражения (2).

Если

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

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

К первой группе отнесем вероятностные методы.

Ко второй – детерминированные методы.

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

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