Переводит ли гены в хромосоме генетический алгоритм для комбинаторной функции, увеличивая разнообразие кандидатов?

Question

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

Переводить Я имею в виду хромосому с фенотипом ABCDE, переходящую на два на DEABC. Они были бы эквивалентными ответами и имели бы равную пригодность, но могли бы сделать более разнообразное потомство.

Стоит ли это в конечном итоге или просто тратит время на вычисление?

Answer 1

Цикл кроссовера (CX) основан на предположении, что важно сохранить абсолютное положение городов (город предпочтительно наследует свое положение от любого из родителей), а превентивный «перевод» противоречит духу CX.

В любом случае многочисленные исследования (например 1) показали, что для TSP ключ, чтобы сохранить относительное положение городов и краев.

Так что это может сработать, но вы должны поэкспериментировать. Другая форма мутации - еще одна возможность.

Возможно, если характеристики CX не удовлетворяют, то другой оператор перекрестного выбора является лучшим выбором: оставаясь с простыми операторами, одним из наиболее успешных является порядок кроссовера (например, 2).

---

1. L. Даррелл Уитли, Тимоти Starkweather, D'Ann Fuquay - Scheduling problems and traveling salesmen: The genetic edge recombination operator - 1989.
2. Пабло Moscato - On Genetic Crossover Operators for Relative Order Preservation.