Travelling Salesman in Assembly Language

The “Omadeon Genetic TSP Algorithm”combines Simulated Annealing techniques with state-of-the-art Genetic Algorithms. This algorithm was first implemented in LPA Win-Prolog and C++. It was then converted to pure X86 Assembly Language and finally re-linked (to LPA WIN-Prolog) as a DLL-library. : 

The “Omadeon Genetic TSP Algorithm”combines Simulated Annealing techniques with state-of-the-art Genetic Algorithms. This algorithm was first implemented in LPA Win-Prolog and C++. It was then converted to pure X86 Assembly Language and finally re-linked (to LPA WIN-Prolog) as a DLL-library. NOTE: This is a first and very informal presentation of O.G.T.S.P. More demos may follow, with detailed statistics. However, some important benchmarks are already included in this demo. Demo of the “OMADEON Genetic TSP algorithm”

Slide 2: 

Demo of the “OMADEON Genetic TSP algorithm” (LPA Prolog + Assembly DLL)…

A “Simulated Annealing Algorithm” is used, to find an almost optimum path, through 70 points. The problem is solved, after 43.5 seconds; Path-cost (or distance) = 3565. : 

A “Simulated Annealing Algorithm” is used, to find an almost optimum path, through 70 points. The problem is solved, after 43.5 seconds; Path-cost (or distance) = 3565.

Now the “OMADEON Genetic TSP algorithm” solves the same problem, a path through 70 points, but... 435 times faster, i.e. in only 0.1 second! Also at a lower cost: 3372! : 

Now the “OMADEON Genetic TSP algorithm” solves the same problem, a path through 70 points, but... 435 times faster, i.e. in only 0.1 second! Also at a lower cost: 3372!

And now for something more ambitious: -An optimum path through 150 points… : 

And now for something more ambitious: -An optimum path through 150 points…

The OMADEON Genetic TSP algorithm finds an optimum path through 150 points…in about a third of a second (0.35 sec.)! (forget other algorithms; they’re too slow!) : 

The OMADEON Genetic TSP algorithm finds an optimum path through 150 points…in about a third of a second (0.35 sec.)! (forget other algorithms; they’re too slow!)

The “OMADEON Genetic TSP algorithm”, applied repeatedly (30 times) to 150 points, finds an even better solution (of a cost = 6747 instead of 6951) in only 3.38 seconds!... : 

The “OMADEON Genetic TSP algorithm”, applied repeatedly (30 times) to 150 points, finds an even better solution (of a cost = 6747 instead of 6951) in only 3.38 seconds!...

The “OMADEON Genetic TSP algorithm”, applied repeatedly (100 times) to 150 points, shows that the previous solution (when running it 30 times) was already quite optimal… : 

The “OMADEON Genetic TSP algorithm”, applied repeatedly (100 times) to 150 points, shows that the previous solution (when running it 30 times) was already quite optimal…