Monday, September 14, 2009

Pure Crossovers

В работе [1] описываются функции трех основных операторов эволюционного алгоритма: отбора, рекомбинации и мутации. Говорится, что, в чистом виде, каждый из них выполняют уникальную функцию. Отбор отвечает за сходимость популяции, мутация - за расходимость, а кроссовер - за смешивание генетического материала. При этом, только рекомбинация может выполнять также функцию селекции и мутации. Чистыми, при этом, называются кроссоверы, выполняющие только свою функцию. Под чистотой при этом понимается, говоря о примере в пространстве Хэмминга, постояноство в популяции пропорций схем первого порядка. Если говорить с позиции определений, независимых от представления (representation-independent), то чистыми кроссоверами являются:

Класс кроссоверов, сохраняющих отрезки (segment-preserving crossovers), с замещением родителей. При этом кроссоверы являются фиксированными по отношению к соответствующему им множеству полупространств. Это подкласс геометрических кроссоверов.

Практическая значимость таких кроссоверов заключается в том, что в таком случае за сходимость и расходимость отвечают исключительно отбор и мутация, т.е. условия эксперимента становится контролированными.

С точки зрения теории, применение таких кроссоверов дает возможность точнее изучить эффекты всех трех операторов: рекомбинативный, селективный и мутационный.

1. Cervantes, J., Moraglio, A. , "Pure Crossovers: definition, their relation to Geiringer's theorem for finite populations and practical value", Technical Report, Universidad Autónoma Metropolitana, Mexico, 2008

2 comments:

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

    Не хочу излишне упрощать, но, к примеру, есть у меня 10 одинаковых кухонных стульев. Стулья-то вроде и хорошие, но с ножками у них беда — на заводе не рассчитали с их толщиной, сделали слишком тонкими, а я, допустим, человек немаленьких размеров и стулья подо мной начали раз за разом ломаться. При том, что у меня есть 10 одинаковых стульев, сижу я только на одном — он у меня любимый — и каждый раз, когда ломается очередная ножка, я просто выкручиваю одну из все еще целых ножек у одного из остальных 9-ти стульев. Но вот наступает момент, когда «запасных» целых ножек уже не осталось, а посидеть на стуле очень хочется, тогда я беру ножовку, иду в ближайшую посадку и спиливаю там молодое деревце, которое после грубой обработки и становится очередной ножкой моего стула.

    Ну в общем к чему я все это? Мне кажется, что реализация кроссовера во многих задачах напоминает выпиливание этой самой ножки, когда рекомбинация (в данном случае древесная) осуществляется, но мало что в ней напоминает эти классические генетические алгоритмы с двоичным кодированием решений-хромосом.

    ReplyDelete
  2. Класс чистых кроссоверов распространяется на все те представления, на которые распространяется класс геометрических кроссоверов. А пример с бинарными последовательностями приведен исключительно для легкости восприятия.

    ReplyDelete