Wednesday, October 21, 2009

Свойства кроссовера по Рэдклиффу в рамках теории Моральо

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

Первое, что может быть замечено общего в этих двух теориях, так это такое свойство как "respect" в аналилзе форм и "геометричность" в, так скажем, анализе геометричности. Еще в своей диссертации [1] Рэдклифф вводит понятие множества подобия (similarity set) для пары хромосом, которое является ничем иным как выпуклой оболочкой этой пары.

Вообще говоря, в рамках теории Моральо [2] понятие геометричности кроссовера, или respectful кроссовера по Рэдклиффу, является центральным. В тоже время свойство "respect" в теории Рэдклиффа является одним из целого списка свойств [1].

Следующий вопрос: как такие свойства кроссовера как "assortment", "strict transmission" могут быть сформулированы на языке выпуклых оболочек.

1. Radcliffe N. J. Genetic Neural Networks on MIMD Computers. - University of Edinburgh, 1990.
2. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.

Friday, October 2, 2009

Толковая статья о сходимости метаэвристик

Найдена статья по сходимости метаэвристик, достаточно четко расставляющая все точки над i.

W. J. Gutjahr Convergence Analysis of Metaheuristics // Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, Springer, 2009. Качать здесь.

Число перестановок порядка n с k инверсиями и вопрос об эффективности мутации

Каким образом может быть оценена эффективность мутации? Мутация является невыпуклым оператором в эволюционном алгоритме [1, с. 322, Theorem 15.4.4.]. При условии, что остальные операторы являются выпуклыми, только оператор мутации может ввести решения за выпуклой оболочкой текущей популяции в следующую популяцию. Тогда возникает вопрос о том, насколько же эффективен в этой своей функции оператор мутации. Если взять пространство генотипов, с введенной на нем метрикой, то вероятность, большую нуля, выхода за пределы выпуклой оболочки текущей популяции имеют только точки на границе выпуклой оболочки. Таким образом, вопрос может быть поставлен следующим образом: какова вероятность того, что как минимум m точек выйдет за границу выпуклой облочки. Следует учесть, что текущая популяция может как содержать, так и не содержать все точки на границе своей выпуклой оболочки.

1. Moraglio A. Towards a geometric unification of evolutionary algorithms. - University of Essex, 2007.