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

• Что такое эвристика? Зачем вообще множить сущности без необходимости и вводить дополнительные термины? Из определения вообще ничего не понятно. -- АтрашкевичАндрей

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

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

• кодирование проблемы в виде генов;
• выведение первоначального поколения;
• вычисление оценок для индивидов;
• скрещивание;
• мутация;

Рассмотрим ГА на примере задачи раскроя.

Кодирование задачи

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

Инициализация первого поколения

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

Оценка индивидов

Оценку результата можно проводить различными способами. Можно, к примеру, ввести некоторую оценочную функцию. Рассматривая задачу раскроя, за оценку можно взять занятую фигурами площадь. Далеко необязательно использовать какой-то один фактор, например, если индивид характеризуется парой , где ‒ число размещённых фигур, а ‒ высота раскроя, то можно взять за оценку данную пару. Тогда то, что индивид лучше, чем индивид можно записать через следующее отношение : . Тоже самое можно записать с помощью функции , тогда достаточно сравнивать числовые значения функций. Выбранная функция будет принимать большее значение при лучшем варианте раскроя. Вообще говоря, можно использовать любую функцию, исходя из условий задачи.

Скрещивание

• К п. 2.: Почему это стабильная часть? Что это вообще такое? Каков критерий стабильности? В чём нестабильность остального? -- АтрашкевичАндрей
• К п. 5.: В чём смысл? Наоборот от чего? В обратном порядке? От второго к первому? -- АтрашкевичАндрей

Рассмотрим скрещивание на следующем примере:

1. Выберем двух индивидов, например {5 2 3 7 6 1 4} и {4 6 2 1 3 5 7}.
2. Выберем не изменяющуюся часть первого родителя случайным образом {5 2 [3 7] 6 1 4}.
3. Удалим эти элементы из второго родителя {4 6 2 1 [3] 5 [7]}.
4. Первого потомка получим путём копирования генов второго родителя в первого {4 6 3 7 2 1 5}.
5. Повторим действия 1-3 поменяв родителей местами.
6. Второго потомка получим путём копирования генов первого родителя во второго {5 3 2 1 7 6 4}.

• Нужно что-то вроде: оценочная функция будет иметь большее значение при лучшем раскрое (если формально говорить, то монотонное неубывание по «качеству» раскроя). -- АтрашкевичАндрей

Мутация

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

Отбор

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