Wednesday, August 26, 2009

Вопрос о двух классах кроссоверов на перестановках

Могут быть выделены два класса кроссоверов на решениях, представленных перестановками. Первый класс описывается следующим образом. Дано две хромосомы и управляющая бинарная последовательность по длине равная длине хромосомы. Управляющая она в том смысле, что в зависимости от того какой бит занимает рассматриваемую позицию, такой аллель (значение элемента перестановки) переходит в хромосому потомка. При этом, если некоторый аллель переходит к потомку, то он удаляется как у родителя-источника, так и у второго родителя.
Во второй класс кроссоверов на перестановках отнесем все такие, которым вышеуказанное описание не подходит. Эти кроссоверы, вообще говоря, являютя первыми, которые были предложены для работы с перестановками, в т.ч. частично-соответствующий кроссовер (partially-mapped crossover)[1].
Вопрос стоит таким образом: можно ли доказать превосходство одного класса кроссоверов над другим?

1. Goldberg D.E. Alleles, loci, and the traveling salesman problem // D.R. Goldberg, R. Lingle / Proceedings of the of the International Conference on Genetic Algorithms and Their Applications, 1985. - pp.162-164

2 comments:

  1. Похожие вопросы в данный момент интересуют и меня.

    ReplyDelete
  2. Смотря по какому критерию мы будем сравнивать два класса и на каких задачах (в блоге у vankina я уже высказывал свои мысли на этот счёт). А вообще, качество эволюционных алгоритмов доказывается вычислительными экспериментами и анализом результатов. Или необходимо доказать именно математически? В таком случае условия и вопрос требуется детализировать и, возможно, сузить.

    ReplyDelete