Wednesday, September 9, 2009

Анализ кроссоверов на основании форм Рэдклиффа

1. В статье [1] на задаче flow shop с критерием длины расписания проводится исследование того, какая интерпретация перестановки дает результаты лучше. Интересно то, что методика может быть распространена и на другие задачи. Для этого используется такое обощение схем Холланда (Holland's schemata) (другие варианты: шаблоны, шимы) как формы Рэдклиффа (Radcliffe's formae) или предикаты Воуза (Vose's predicates).

Формами называют классы эквивалентности, порожденные некоторым отношением эквивалентности, заданным на, например, множестве допустимых решений задачи Джонсона (flow shop с критерием длины расписания).

Под интерпретацией перестановки понимается то, какое отношение эквивалентности мы хотим, чтобы потомок унаследовал от своих родителей (не обязательно от обоих). А наследовались в данной статье четыре отношения:
- предшествования(Пр);
- порядка(П);
- смежности(С);
- совпадения блоков(Б).
Лучшее же из этих четырех по критерию дисперсии фитнесса внутри формы оказалось Б, затем П, Пр и С. Следует заметить, что этот результат относится к задаче Джонсона.

Для существующих в литературе кроссоверов было описано какие формы они передают от родителей потомкам. Лучшим оказался частично-соотвествующий кроссовер (PMX). Затем были предложены новые кроссоверы, которые оказались не хуже, а некоторых индивидуальных задачах и превзошли его.

Ставится вопрос следующий: каким образом могут быть объединены теория геометрических кроссоверов и анализ кроссоверов на основании форм Рэдклиффа?

1. C. Cotta and J.M. Troya. Genetic forma recombination in permutation flowshop problems. Evolutionary Computation, 6(1):25–44, 1998.

No comments:

Post a Comment