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

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

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

Генетический алгоритм (ГА) — самый популярный из эволюционных алгоритмов. Он был изобретён Джоном Холландом в Университете Мичигана в 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}.

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

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

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

Отбор

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