Проектирование систем искусственного интеллекта



         

Как работает генетический алгоритм?


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

Репродукция состоит из четырех шагов:

  • селекции

    и трех генетических операторов (порядок применения не важен)

  • кроссовера;
  • мутации;
  • инверсии.

Роль и значение селекции мы уже рассмотрели в обзоре эволюционных алгоритмов.

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

001100101110010|11000-------->00110010111001011100
110101101101000|11100

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

00110010111001011000-------->00110010111001111000

Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации ГА обходятся без данного генетического оператора.

00110010111001011000-------->11000001100101110010

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




Содержание  Назад  Вперед