Friday, October 2, 2009

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

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

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

No comments:

Post a Comment