Monday, September 7, 2009

Два класса кроссоверов: негеометрический лучше

Нашел статью [1], в которой говорится, что негеометрический кроссовер дает результаты лучше, чем такой представитель класса геометрических кроссоверов, как равномерный кроссовер (uniform crossover), причем как для однокритериальной, так и для двухкритериальной постановки. Тестирование проводилось на задаче о рюкзаке с бинарными переменным, т.е. в пространстве Хэмминга. Было бы интересно провести подобные "испытания" и для других пространств генотипов.

1. Ishibuchi H. Effects of the use of non-geometric binary crossover on evolutionary multiobjective optimization / Proceedings of the 9th annual conference on Genetic and evolutionary computation, 829--836, 2007.

5 comments:

  1. Что есть негеометрический кроссовер? Просто эта терминология геометрический-негеометрический без примера плохо воспринимается. Классический одноточечный кроссовер является негеометрическим?

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

    ReplyDelete
  2. Да, я тоже не понял из предыдущих постов в блоге, как отличить геометрический от нон-геометрического ))

    ReplyDelete
  3. Есть множество допустимых решений, пусть это будет множество бинарных строк. Введем на нем метрику Хэмминга. Пусть А и Б родители, В - потомок, полученный в результате геометрического кроссовера, а Д(x,y)-расстояние в метрике Хэмминга между x и y. Тогда, Д(А,В)+Д(Б,В)=Д(А,Б), т.е. в данном случае в метрике Хємминга, сумма расстояния между одним родителем А и потомком В, а также другим родителем Б и этим же потомком В, будет равна расстоянию между этими родителями А и Б. Все классические кроссоверы для бинарных строк являются геометрическими, в т.ч. n-точечные и равномерный.

    Эта же схема применима к любому другому множеству генотипов, например, множеству перестановок.

    ReplyDelete
  4. О том как отличить геометрический от негеометрического. Насколько я понял, просто посмотрев на оператор кроссовера, не получится с точностью сказать геометрический он или нет. Это требуется доказать. Для того, чтобы доказать, требуется найти метрику в которой данный кроссовер будет геометрическим. Один и тот же кроссовер может быть геометрическим в более чем одной метрике. Для того, чтобы доказать, что кроссовер негеометрический, нет смысла перебирать метрики. В этом случае, вы можете вомпользоваться, свойствами геом. кросс. независимыми от метрики, но присущими всем геом. кроссоверам. Например, свойство чистоты: скрещивание при помощи геом. кр-ра хромосомы с самой собой может дать только саму эту хромосому.

    ReplyDelete
  5. О примерах геометрических кроссоверов. Примеры могут быть найдены в диссертации A. Moraglio (см. предыдущие сообщения).

    ReplyDelete