Friday, September 11, 2009

Параллели между анализом форм и геометричностью кроссоверов

В 1990 Николасом Рэдклиффом [1] были предложены следующие принципы разработки кроссоверов:
1. Minimal redundancy. Одному фенотипу должно соответствовать как можно меньше генотипов.
2. Correlation within formae. Как можно больше форм, особенно низкой точности, должны содержать коррелированные решения.
3. Closure. Пересечение двух форм само должно быть формой.
4. Respect. Рекомбинация двух примеров любой формы дожна производить пример той же формы.
5. Proper assortment. Для примеров любых двух данных совместимых форм должны существовать такие параметры кроссовера, которые производят пример на пересечении этих форм.
6. Ergodicity. Должна существовать возможность конечным числом применений генетических операторов достигнуть любое решение в пространстве хромосом из произвольной популяции.

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

В [2] введен седьмой принцип:
7. Strict Transmission. При данном полном ортогональном базисе из множества отношений эквивалентности на пространстве поиска (множестве хромосом), для каждого отношения эквивалентности, каждый потомок, произведенный рекомбинацией, должен быть эквивалентен одному из своих родителей. Другими словами, каждый аллель потомок получает от одного из своих родителей.

Альберто Моральо и Риккардо Поли [3,4] были выведены следующие свойства геометрического кроссовера:
1. Свойство чистоты (Property of Purity). Рекомбинация родителя с самим собой производит этого родителя.
2. Свойство сходимости (Property of Convergence). Рекомбинация одного родителя с его потомком не может произвести другого родителя, если только этот другой родитель не совпадают.
3. Свойство разбиения (Property of Partition). Рекомбинация одного родителя со своим потомком и другого родителя с этим же потомком производит одинакового внука только в том случае, если он является этим потомком.

Свойства, прдложенные Рэдклиффом, являются с его точки зрения желательными для кроссоверов. В тоже время свойства геометрического кроссовера уже есть у него в наличии и логически выведены из его определения.

Обобщением схем для геометрического кроссовера являются метрические выпуклые множества. Потомок на замкнутом интервале между своими родителями принадлежит всем выпуклым множествам, общим для его родителей.

Моральо пишет, что, хотя и классы эквивалентности, и выпуклые множества, покрывают пространство целиком, в отличии от первых выпуклые множества не разбивают пространство поиска, поскольку они пересекаются. Следует заметить, что классы эквивалентности пересекаются, если они индуцированы разными отношениями эквивалентности. Такие классы эквивалентности (формы) Рэдклифф называет совместимыми.

Таким образом, если рассматривать дополнения выпуклых множеств относительно всего пространства поиска и сами соответствующие множества, как классы эквивалентности, индуцированные одним отношением, то мы получим то, что у Рэдклиффа называется отношением эквивалентности точности (precision - число индуцированных классов данным отношением) 2. Это значит, что теория геометрического кроссовера является частным случаем теории форм. Кроме того, не всякое отношение эквивалентности точности 2 может быть представлено как разбиение пространства поиска на выпуклое множество и его дополнение, поскольку последнее является частным случаем отношений такой точности.

1. Radcliffe N. Genetic neural networks on MIMD computers. - University of Edinburgh, 1990.
2. Radcliffe N. Forma analysis and random respectful recombination / Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 31–38, 1991.
3. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.
4. Moraglio A., Poli R. Inbreeding properties of geometric crossover and non-geometric recombinations / Proceedings of the European Conference on Artificial Intelligence - Italian worshop on Evolutionary Computation, 2006.

No comments:

Post a Comment