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

Содержание

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

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

Пример

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

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

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

Оценку результата можно проводить различными способами. Можно, к примеру, ввести некоторую оценочную функцию. Рассматривая задачу раскроя, за оценку можно взять занятую фигурами площадь. Далеко необязательно использовать какой-то один фактор, например, можно взять за оценку количество размещенных фигур и высоту раскроя. Тогда то, что индивид I sub 1 лучше, чем индивид I sub 2 можно записать через отношение порядка u+2228: I sub 1 ~ rho ~ I sub 2 = (N sub 1 > N sub 2 \\\[U+0048\] (N sub 1 = N sub 2 \\(and H sub 1 < H sub 2)

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



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