Содержание
Генетические алгоритмы.
Генетический алгоритм — один из методов оптимизации, основанный на эвристике. Для получения оптимального решения применяют случайный подбор, комбинирование и вариацию искомых параметров с использованием эволюционных механизмов. Данный алгоритм состоит из нескольких частей: * кодирование проблемы в виде генов; * выведение первоначального поколения; * вычисление оценок для индивидов; * скрещивание; * мутация;Пример
Рассмотрим генетический алгоритм на примере задачи раскроя. В качестве генома целесообразно рассматривать только номер фигуры в последовательности. Допустим уже имеется два различных индивида — две различные последовательности раскроя, тогда генетический алгоритм будет выглядеть следующим образом:
- Выберем двух индивидов, например $\{5\ 2\ 3\ 7\ 6\ 1\ 4\}$ и $\{4\ 6\ 2\ 1\ 3\ 5\ 7\}$.
- Выберем стабильную часть первого родителя $\{5\ 2\ [3\ 7]\ 6\ 1\ 4\}$.
- Удалим эти элементы из второго родителя $\{4\ 6\ 2\ 1\ [3]\ 5\ [7]\}$.
- Первого потомка получим путём копирования генов второго родителя в первого $\{4\ 6\ 3\ 7\ 2\ 1\ 5\}$.
- Повторим действия 1-3 наоборот.
- Второго потомка получим путём копирования генов первого родителя во второго $\{5\ 3\ 2\ 1\ 7\ 6\ 4\}$.