Мы реализуем представление пути, чтобы решить нашу задачу коммивояжера, используя генетический алгоритм.Тем не менее, мы задавались вопросом, как решить вопрос о том, что могут быть идентичные туры у наших людей, но которые признаются путевым представлением как разные люди.Пример:
Каждый индивид состоит из массива, в котором элементами являются города, посещенные в порядке.
Individual 1:
[1 2 3 4 5]
Individual 2:
[4 5 1 2 3]
Вы можете видеть, что тур в 1 и 2 фактически идентичен, отличается только «начальное» местоположение.
Мы видим некоторые решения этой проблемы, , но мы былиинтересно, какой из них был бы лучшим, или есть ли лучшие методы для преодоления этой проблемы из литературы / экспериментов / ....... 1016 *
Решение 1
Sort each individual to see if the individuals are identical:
1. pick an individual
2. shift the elements by 1 element to the right (at the end of the array, elements are placed at the beginning of the array)
3. check if this shift now matches an individual
4. if not, repeat steps 3 to 4
Решение 2
1. At the start if the simulations, choose a fixed starting point of the cities.
2. If the fixed starting point would change (mutation, recombination,...) then
3. Shift the array so that chosen starting point is back on first index.
Решение 3
1. Use the adjacency representation to check which individuals are identical.
2. Pass this information on to the path representation.
3. This is used to "correct" the individuals.
Решение 1 и 2 кажется трудоемким, хотя для 2, вероятно, потребуетсягораздо меньше вычислительного времени.Решение 3 должно будет постоянно переключаться с одного представления на другое.
Тогда существует также проблема, заключающаяся в том, что в нашем примере тур можно прочитать двумя способами:
[1 2 3 45]
- это то же самое, что и
[5 4 3 2 1]
Опять-таки, есть ли лучшие практики для решения этой проблемы?