: The “OMADEON Genetic TSP Algorithm”(O.G.T.S.P) for T.S.P. (Travelling Salesman Problems)combines “Simulated Annealing”with (State-of-the-Art) “Genetic Algorithms”…


: This unusual “Hybrid Algorithm” (O.G.T.S.P.) was initially conceived and implemented in LPA Win-Prolog. This algorithm seemed to perform far better than ALL other algorithms attempted - at the time. However, its very good performance seemed hard to verify for larger problem-sizes (e.g. finding the best path passing through 100+ points)…


: Some critical parts of the Algorithm were then translated into ‘C’ and eventually (in April 2009) the entire O.G.T.S.P Algorithm was rewritten in hand-optimized Assembly Language. The resulting speed-improvements were ominous: Typically 10x/100x faster than the fastest algorithms E.g. 430+ times faster than “Simulated Annealing” …..and (above all)…. Almost Linear Complexity (instead of “NP-complete”)


Slide 4:O.G.T.S.P was finally compiled As an external DLL-library for LPA Win-Prolog (www.lpa.co.uk) (…or any other programming language) This presentation is a first informal Demo of O.G.T.S.P. (with comparative timings and benchmarks)


Slide 5: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…