Это старая версия (1.49) ГенетическиеАлгоритмы.

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

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

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

Пример

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

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}.

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

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

Отбор

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

Отбор для скрещивания

---

КатегорияМетодыОптимизации