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

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

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

Впервые подобный алгоритм был предложен в 1975 году Дж. Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов.

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

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

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

  1. из популяции выбираются две особи, которые будут родителями;
  2. определяется (обычно случайным образом) точка разрыва;
  3. потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора

Хромосома_1:  0000000000

Хромосома_2: 1111111111 

Допустим, разрыв происходит после 3-го бита хромосомы, тогда 

Хромосома_1: 0000000000 >>  000 1111111  Результирующая_хромосома_1

Хромосома_2: 1111111111 >>  111 0000000  Результирующая_хромосома_2 

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000 1111111  >>  1111111  000 

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

Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.

  1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B0 = {A1,A2,…,Ak)
  2. Вычислить приспособленность (пригодность) каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь Ac из популяции. Ac = Get(Bt)
  4. С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).
  5. С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).
  6. С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).
  7. Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).
  8. Выполнить операции, начиная с пункта 3, k раз.
  9. Увеличить номер текущей эпохи t=t+1.
  10. Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Рассмотрим подробнее отдельные этапы алгоритма.

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

PGet(Ai) ~ Fit(Ai)/Fit(Bt).

Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор. Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма, которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

Другой важный момент – определение критериев останова.

В качестве критериев останова алгоритма могут использоваться такие:

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

Найти максимум функции f(x)=x2  в диапазоне 0<x<31.

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

Установим размер популяции, равный четырем строкам. 

Таблица 11.1 – Начальная популяция и оценка пригодности

 

Начальная популяция

x

f(x)

Относительная пригодность, %

1

01101

13

169

14,4

2

11000

24

576

49,2

3

01000

8

64

5,5

4

10011

19

361

30,9

 

 

 

1170

100

 

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

Таблица 11.2– Родительский пул и скрещивание 

Родительский пул

Парная строка

До скрещивания

После скрещивания

1

01101

2

0110[1]

1100

2

11000

1

1100[0]

11001

3

11000

4

11[000]

11011

4

10011

2

10[011]

10000

 Второе поколение без мутации приведено ниже.

 Таблица 11.3 – Второе поколение 

Начальная популяция

x

f(x)

Относительная пригодность, %

1

1100

12

144

8,2%

2

11001

25

625

35,6%

3

11011

27

729

41,6%

4

10000

16

256

14,6%

 

 

 

1754

100

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

Генетический алгоритмдля решения любой проблемы должен содержать, как правило, следующие компоненты:

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

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

На рынке программного обеспечения имеется несколько продуктов, использующих генетические алгоритмы: Evoler, GeneHunter, Genetic Training Option for BrainMaker, Auto2Fit, Omega, Genitor, Xpert Rule Gen Asy, PC/Beagle, EM, Escapate, GAGA, Gausd, Genesis, OOGA, EnGENer, Game, GA Workbench, Pegasus и др.