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

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

Рассмотрим общую схему работу Генетического алгоритма(ГА)

Ш.1 Формирование начального поколения

Ш.2 Отбор и применение ГА операторов для нового поколения

Ш.3 Проверка условия останова. Если не выполняется перейти к Ш.2

Ш.4 Лучшая особь выбирается как найденное решение.

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

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

В данном случае решения задачи теории расписания минимаксный критерий будет являться оптимизационной функцией, а условием останова неизменность лучшего решения в течение поколений.

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

Рассмотрим подробнее Ш.2 алгоритма

Проставить формулы

Ш.2.1 На вход шага поступает исходный вектор особей (хромосом), каждая из особей представляет какое-то расписание с соответствующим ему Tmax и соотвественно приспособленностью особи.

Ch1=[0(S:48), 1(S:41), 2(S:32), 3(S:42), 4(S:37), 5(S:47), 6(S:26), 7(S:37), 8(S:37), 9(S:31)] Новое поколение должно быть записано в новый вектор Ch2, который на следующем шаге послужит исходным.

Ш.2.2 Если используется механизм элитных особей, то лучшие Nособей переходят в новое поколение без изменений (обычно ограничиваются одной особь).

Ш.2.3 В цикле по всем особям, за исключением элитных производят применение ГА операторов.

Ш.2.4 iтая особь переходит в следующее поколение, если к ней не применятся какие-либо операторы, то она сохранится в следующем поколении без изменений.

Ш.2.5 Выполняется оператор кроссовера с заданной вероятностью к примеру 0.95. Простым способом задать такую вероятность является получение случайногоо числа в интервале [0..1] R=RND(), и проверка условия R<0.95. Для применения оператора кроссовера необходимо выбрать две особи, например с помощью двоичного турнирного отбора.

Ш.2.6 Выполняется оператор мутации с заданной вероятностью.

Ш.2.7 Если i<N перейти к шагу Ш.2.4

Ш.2.8 Сформировано поколение Ch2. После проверки условия останова в Ш.3 оно послужит начальным вектором для шага Ш.2.1.

Попробуем найти решение для параметров задачи указанных выше и следующими параметрами ГА

Вероятность кроссовера: 0.95

Вероятность мутации: 0.05

Кол-во особей: 10

Лимит останова

Использование Элиты: 1 особь

Ш.1 Начальное поколение

Поколение №0

Особи: SumF:378 0(S:48, ), 1(S:41, ), 2(S:32, ), 3(S:42, ), 4(S:37, ), 5(S:47, ), 6(S:26, ), 7(S:37, ), 8(S:37, ), 9(S:31, )

Лучшей особью является

Особь #6 Tmax: 26

[1 r:0] summ:26/26 4(4) 5(22)

[2 r:0] summ:22/22 2(15) 3(7)

[3 r:0] summ:20/20 0(5) 1(10) 6(5)

Поколение №1

Особи: SumF:361 1000(S:26, ), 1001(S:31, ), 1002(S:37, ), 1003(S:27, ), 1004(S:51, ), 1005(S:30, ), 1006(S:41, ), 1007(S:44, ), 1008(S:37, ), 1009(S:37, ),

Видно что в новом поколении лучшая особь не изменилась, но суммарная присобленность (SumF) улучшилась, что говорит о начале сходимости алгоритма вокруг лучшего решения.

…Пропускаем до 37 поколения

Поколение №37

Особи: SumF:264 1000(S:26, ), 1001(S:26, ), 1002(S:26, ), 1003(S:26, ), 1004(S:24, ), 1005(S:26, ), 1006(S:26, ), 1007(S:26, ), 1008(S:26, ), 1009(S:32, )

Лучшей особью является

Особь #1004 Tmax: 24

[1 r:1] summ:22/22 5(22)

[2 r:2] summ:24/24 2(15) 4(4) 6(5)

[3 r:3] summ:22/22 0(5) 1(10) 3(7)

Поколение №38

Особи: SumF: 267 0(S:24, ), 1(S:26, ), 2(S:30, ), 3(S:26, ), 4(S:26, ), 5(S:26, ), 6(S:31, ), 7(S:26, ), 8(S:26, ), 9(S:26, )

…Пропускаем до 87 поколения. Останов алгоритма.

Особи: SumF: 263 1000(S:24, ), 1001(S:24, ), 1002(S:27, ), 1003(S:24, ), 1004(S:24, ), 1005(S:24, ), 1006(S:44, ), 1007(S:24, ), 1008(S:24, ), 1009(S:24, )

Любая из особей с Tnax:24 может быть выбрана как решение.

Особь #1004 Tmax: 24

[1 r:1] summ:22/22 5(22)

[2 r:2] summ:24/24 2(15) 4(4) 6(5)

[3 r:3] summ:22/22 0(5) 1(10) 3(7)

Графически процесс решения можно увидеть на след графике.