Перекрестная операция в генетическом алгоритме для TSP

Here is a C# program approach for what you are looking for.

With regards to the interest (or lack thereof) of implementing cross-over, it all hinges on the particular selection logic your implementation will use (and/or the evaluation function itself, if for example it includes an evaluation of the speed of improvement). In many cases, cross-over operations will "rescue from the chopping block" some solutions that are effective/optimal in an area of the graph but somehow "stuck" in others. This is not to say that if the overall algorithm is slow-enough and covers a good percentage of the solution space the same solutions may not have been discovered anew, but cross-over may also increase these discoveries (and/or letting you stuck in another local minima ;-) )

Not directly related but of noteworthy interest to whomever looks into GA, is the original "ultimate" experiment in GA original "ultimate" experiment in GA by Prof. Alderman (of RSA fame), who used actual DNA molecules [into a C program - just kidding] to solve a related graph problem, that of hamiltonian graphs.

Edit: In re-reading the question I understand why you asked it or more precisely why you'd like a "No you don't want cross-over" reply ;-)
Your genonme is directly tied to the graph itself (nothing wrong with that, a priori), but this brings the impediment that most cross-over offsrpings will not be viable, since they may may have duplicate nodes (visit same city twice or more) and be missing nodes (failing to visit some cities)... Furthermore, viable cross-overs will affect similar graphs, and hence maybe merely incrementally expend the search, compared with what mutations would have discovered...
Хм ... Тогда, может быть, кроссовер, в этой конкретной реализации не очень поможет алгоритму (и действительно потребует много ресурсов процессора для создания, тестирования и часто отбрасывания перекрестных - по сравнению с потомками, ЦП, который лучше использовать, давая больше итераций и более низкую скорость охлаждения ...). Если только! Вы нашли умный способ выполнения перекрестных операций; -)

The purpose of crossover is to expand the evolutionary search space by bringing together novel genomic combinations.

The only real criteria required for the evolutionary process is that the product of crossover contains portions of both parents and represents a valid genome.

Only you know the validity rules for your algorithm so only you can specify a crossover method that will work (unless you want to share more details of the validation rules for you genome structure).

Когда я был на первом курсе в моем университете, я делал некоторые вычисления (которые занимали около 30 страниц) о влиянии различных операторов GA на сходимость решения. Насколько я помню, кроссовер - не лучшее решение для TSP, более подходящим решением является мутация, которая представляет собой инвертирование подпоследовательности вершин.

пример:

до: A BCDEF GH

после: A FEDCB GH

"Crossover" in genetic algorithms just refers to an arbitrary way of mixing two "genetic sequences", each of which represents a particular solution to a problem (how a sequence maps to a solution is up to you). So, for example, say you have a population that consists of the following two sequences:

AAAAAAAAAA
BBBBBBBBBB

One way to recombine these two "parent" sequences is to randomly pick a crossover point (say, position 3), resulting in these two "child" sequences:

AAABBBBBBB
BBBAAAAAAA

Or, you could randomly pick two crossover points (say, 3 and 8), resulting in these two sequences:

AAABBBBBAA
BBBAAAAABB

For fun and extra variability, you can also introduce the possibility of occasional point mutations:

AAABBBABAA
BBBAAAAABB

There aren't really any hard-and-fast rules regarding how you implement crossover in a genetic algorithm, just as there aren't really any hard-and-fast rules governing Evolution in the biological world. Whatever works, works.

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

Обычный подход не так хорошо работает для TSP, потому что функция приспособленности очень чувствительна к относительному положению различных городов в развитом маршруте, а не к их абсолютному положению. Например, если вы побывали во всех европейских столицах, кратчайший маршрут не пройдет. Это действительно зависит от того, побываете ли вы в Братиславе 1, 2 или 9. Что более важно, вы посетите его непосредственно перед или сразу после посещения Вены , а не посетите Хельсинки, Афины и 6 других столиц между ними.

Конечно, как mjv также указывает ], традиционный кроссовер также приведет к дублированию маршрута. Если у одного из родителей Париж находится в позиции 2, а у другого - Париж в позиции 14, переход может привести к тому, что один развитый маршрут посещает Париж дважды (и пропускает другой город), а другой развитый маршрут вообще не посещает его. Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

s более важно, чтобы вы посетили его непосредственно перед или сразу после посещения Вены , а не посещали Хельсинки, Афины и 6 других столиц между ними.

Конечно, как mjv также указывает ], традиционный кроссовер также приведет к дублированию маршрута. Если у одного из родителей Париж находится в позиции 2, а у другого - Париж в позиции 14, переход может привести к тому, что один развитый маршрут посещает Париж дважды (и пропускает другой город), а другой развитый маршрут вообще не посещает его. Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

s более важно, чтобы вы посетили его непосредственно перед или сразу после посещения Вены , а не посещали Хельсинки, Афины и 6 других столиц между ними.

Конечно, как mjv также указывает ], традиционный кроссовер также приведет к дублированию маршрута. Если у одного из родителей Париж находится в позиции 2, а у другого - Париж в позиции 14, переход может привести к тому, что один развитый маршрут посещает Париж дважды (и пропускает другой город), а другой развитый маршрут вообще не посещает его. Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

как mjv также указывает , традиционный кроссовер также добавит дубликаты в ваш маршрут. Если у одного из родителей Париж находится в позиции 2, а у другого - Париж в позиции 14, переход может привести к тому, что один развитый маршрут посещает Париж дважды (и пропускает другой город), а другой развитый маршрут вообще не посещает его. Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

как mjv также указывает , традиционный кроссовер также добавит дубликаты в ваш маршрут. Если у одного из родителей Париж находится в позиции 2, а у другого - Париж в позиции 14, переход может привести к тому, что один развитый маршрут посещает Париж дважды (и пропускает другой город), а другой развитый маршрут вообще не посещает его. Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.

Упорядоченный генетический оператор кроссовера не страдает этой проблемой. Он сохраняет элементы и изменяет порядок.