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

«Отцом» генетических алгоритмов по праву считается Д. Холланд, метод вначале назывался репродуктивным планом Холланда. В дальнейшем генетические алгоритмы развивались в работах учеников Холланда: Д. Голдберга и К. Де Йонга – именно в них и закрепилось название метода.

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

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

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

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

• оптимизация функций;

• разнообразные задачи на графах (задача коммивояжера, раскраска и т.д.);

• настройка и обучение искусственной нейронной сети;

• задачи компоновки;

• составление расписаний;

• игровые стратегии;

• аппроксимация функций;

• искусственная жизнь;

• биоинформатика.

Преимущества генетических алгоритмов:

1. универсальность;

2. высокая обзорность поиска;

3. нет ограничений на целевую функцию;

4. любой способ задания функции.

Недостатки генетических алгоритмов:

1. относительно высокая вычислительная стоимость;

2. квазиоптимальность.

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

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

Схема функционирования генетического алгоритма

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

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

Таблица 3. Пример фенотипа

После определения фенотипа генетический алгоритм функционирует по следующей схеме действий (рис. 15):

Переход к новому

поколению

Рис. 15. Схема функционирования генетического алгоритма

1. Формирование начальной популяции.

2. Оценка особей популяции.

3. Отбор (селекция).

4. Скрещивание.

5. Мутация.

6. Формирование новой популяции.

7. Если популяция не сошлась, то 2, иначе – останов (прекращение функционирования генетического алгоритма).

Формирование начальной популяции

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

Популяция инициируется в начальный момент времени t = 0 и состоит из k особей, каждая из которых представляет возможное решение рассматриваемой проблемы. Особь – это одна или несколько хромосом (обычно одна). Хромосома состоит из генов, то есть это битовая строка (хромосомы не ограничены бинарным представлением, есть реализации генетического алгоритма, построенные на векторах вещественных чисел). Гены располагаются в различных позициях хромосомы и принимают значения, называемые аллелями.

Оценка особей популяции

Для решения задачи с помощью генетического алгоритма необходимо задать меру качества для каждого индивида в пространстве поиска. Для этой цели используется функция приспособленности (fitness function). Функция приспособленности должна принимать неотрицательные значения на ограниченной области определения, при этом совершенно не требуются непрерывность и дифференцируемость. Значение этой функции определяет, насколько хорошо подходит особь для решения задачи.

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

Отбор (селекция)

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

Пропорциональный отбор (proportional selection)

Каждой особи назначается вероятность P_s(i), равная отношению ее приспособленности к суммарной приспособленности популяции. Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки согласно величине P_s(i).

Простейший пропорциональный отбор – рулетка – отбирает особей с помощью n «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине P_s(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью.

Турнирный отбор

Турнирный отбор реализуется следующим образом: из популяции, содержащей m особей, выбирается случайным образом t особей, и наиболее приспособленная особь записывается в промежуточный массив (между выбранными особями проводится турнир). Эта операция повторяется m раз. Строки в полученном промежуточном массиве затем используются для скрещивания (случайным образом). Размер группы строк, отбираемых для турнира, часто равен 2. В этом случае говорят о двоичном/парном турнире.

Отбор усечением

Данная стратегия использует отсортированную по убыванию популяцию. Число особей для скрещивания выбирается в соответствии с порогом T[0;1]. Порог определяет, какая доля особей, начиная с самой первой (самой приспособленной), будет принимать участие в отборе. В принципе, порог можно задать и равным 1, тогда все особи текущей популяции будут допущены к отбору. Среди особей, допущенных к скрещиванию случайным образом m/2 раза, выбираются родительские пары, потомки которых образуют новую популяцию.

Ранговый отбор

Этот вид отбора подразумевает следующее: для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

Элитный отбор

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

Скрещивание

Как известно, в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется оператором скрещивания (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам, к ним применяется вероятностный оператор скрещивания, который строит на их основе новые (1 или 2) решения-потомки. Отобранные особи подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью P_c. Если каждая пара родителей порождает двух потомков, для воспроизводства популяции необходимо скрестить m/2 пары. Для каждой пары с вероятностью P_c применяется кроссовер. Следовательно, с вероятностью 1 - P_c кроссовер не происходит, и тогда неизмененные особи переходят на следующую стадию (мутации).

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

Сначала случайным образом выбирается одна из возможных точек разрыва. (Точка разрыва – участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков:

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

Мутация

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

Особь до мутации: 1 0 0 1 0 1 1 0 0 1 1 1

Особь после мутации: 1 0 0 1 0 1 0 0 0 1 1 1

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

Особь до инверсии: 1 0 0 1 1 1 1 0 0 1 1 1

Особь после инверсии: 1 0 0 1 0 0 1 1 1 1 1 1

Транслокация – это перенос какого-либо участка хромосомы в другой сегмент этой же хромосомы:

Особь до транслокации: 1 0 0 1 1 1 1 0 0 1 1 1

Особь после транслокации: 1 1 1 0 0 0 1 1 0 1 1 1

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

Формирование нового поколения

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

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

2. Следующая популяция включает в себя как родителей, так и их потомков.

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

Критерии останова

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

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

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

Рис. 16. Схождение генетического алгоритма

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