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

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

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

f(x₁, x₂, x₃, …, x_N). (5.31)

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

в двоичном формате;

в формате с плавающей запятой.

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

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

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

кроссовера;

мутации;

инверсии.

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

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

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

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

Организация ЭВМ и систем/Архитектура ЭВМ и систем