Genetic Algorithms TSP

http://www.metivity.com/

The Traveling Salesman Problem TSP is defined as finding the minimum length of a cyclic path that runs through a list of known cities say n cities.
This problem is unfortunately NP-Complete which means there is no efficient algorithm that finds the shortest path except for the one that checks all or too many of the possible paths. It is very popular today to solve this problem by using genetic algorithms and many nice demos can be found over the internet. Problems begin when stochastic hillside climbing gets stuck because too many correct mutations need to appear in order to reach new solutions. This problem can only be partially solved by the use of Transposons or Retrotransposons (Jumping sequences of code or Jumping Genes) and by continuous reduction of the TSP problem to simpler TSP problems. This reduction is unmatched in Nature because multiple evolution environments in the presented model simultaneously exist. Moreover, it is evident that in one out of five simulations, large scale Transposon mutations are insufficient and more complex large scale mutations are required. These were called Insertion Rotation mutations.

here is some sample of using the regular GA vs. complex large scale mutations GA (GA1-GA2).

Category:

Science & Technology

Tags:

• genetic algorithms
• metivity
• artificial intelligence
• tsp
• genetic algorithm

[ravivyatom]

visual studio 6 c++

[georzal]

source in studio :-))

[ravivyatom]

: )

[txikiportu]

genetic-cumagic in C, solves the cumagic problem. Here in youtube.

[Frank4651]

which software did you use?

[Onafets94]

fantastic man!

[Danik112]

Or you could use an Ant Colony Optimization algorithm (ACO). It beats standard GA by far for the TSP, but I don't know how it compares to your method.

[kingrion]

Thats Awesome! What is a good resource for learning about the more complex mutations you mentioned?