Genetic Algorithms for TSP

Started by
11 comments, last by QuinnJohns 12 years, 6 months ago
I did a project for college a few years back, it has an option to solve TSP using a GA.

Here are the binaries and the source, I hope it helps:
http://www.mediafire.com/file/jc0yka96f63b05x/TSP-Genetic.rar

UI is in Croatian but it shouldn't be too hard to figure out. Code is in English.

I didn't find GA too useful for TSP, it was mostly included as a proof of concept.
Advertisement

[color=#1C2837]So crossovers turned out to be useful and diversity is used in the fitness function in order to avoid premature convergence (= genetic drift in GA terminology), such as illustrated below:
[color="#1c2837"]


I think the GA is just used as a diversification mechanism here: an alternative meta-heuristic that picks new neighbourhoods to search in. IIRC the local search itself is using an exchange operator that ranks edges based on how close they are to being part of the Minimum Spanning Tree of all cities.

[quote name='Franck Dernoncourt' timestamp='1318406659' post='4871766']
[color="#1C2837"]So crossovers turned out to be useful and diversity is used in the fitness function in order to avoid premature convergence (= genetic drift in GA terminology), such as illustrated below:


I think the GA is just used as a diversification mechanism here: an alternative meta-heuristic that picks new neighbourhoods to search in. IIRC the local search itself is using an exchange operator that ranks edges based on how close they are to being part of the Minimum Spanning Tree of all cities.
[/quote]

Anyways, it took me a little less than two days to write the GA, mutations, crossovers, etc. Pretty excited about the results. Thanks for the input everyone.
[size="2"][size="1"][size="2"]- Quinn
[size="2"][size="1"][size="2"]Software Developer, Mintrus

This topic is closed to new replies.

Advertisement