advertisement

OGTSP Travelling Salesman in ASM

25 %
75 %
advertisement
Information about OGTSP Travelling Salesman in ASM
Science-Technology

Published on May 8, 2009

Author: gstathis

Source: authorstream.com

advertisement

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

Add a comment

Related presentations

Related pages

Implementations | A.I. programming in Prolog and Assembler

Posts about Implementations written by ... ===== _apply_func.asm ... in Assembly Language for the Travelling Salesman ...
Read more

Bruteforce solver for the travelling salesman problem ...

... Bruteforce solver for the travelling salesman problem, ... Trinitek / BruteSolverOptimized. Code. ... salesman.asm: salesman.h: Status; API; Training ...
Read more

Genetic Algorithms and the Traveling Salesman Problem ...

ASM: Скачать ... Genetic Algorithms and the Traveling Salesman Problem using C# and ATL ... This project is about an application used by the ...
Read more

Travelling Salesman Again ! | CodeChef

Home » Compete » April 2010 Contest » Travelling Salesman Again ! ... A salesman is located at city 0. ... ASM, BASH, BF, C, C99 strict, CAML, ...
Read more

P. Polak and G. Wolansky - researchgate.net

THE LAZY TRAVELLING SALESMAN PROBLEM IN R2 ... salesman (TSP). ... squareofthepath’slength1 asm!1.Notealsothattheflrsttermin(5) ...
Read more

Ultra-Fast Hybrid Genetic Algorithm in Assembly Language ...

A.I. programming in Prolog and Assembler. ... Algorithm in Assembly Language for the Travelling Salesman ... omadeon.com/tsp/ogtsp.ppt;
Read more

traveling salesman | eBay

Find great deals on eBay for traveling salesman . ... August Traveling Drink Salesman Peculiar Contraption 1870 antique engraved print. £19.13. Was: £23.91
Read more

Local Meta-models for ASM-MOMA - ResearchGate

Local Meta-models for ASM-MOMA on ResearchGate, ... studies on software next release and travelling salesman problems. Xinye Cai, Xin Cheng, ...
Read more