Evolving L-Systems as an intelligent design approach to ?nd classes of dicult-to-solve Traveling Salesman Problem instances

Select |




Print


Ahammed, Farhan; Pablo, Moscato


2011-04-27


Conference Material


European Conference on the Applications of Evolutionary Computation, 2011 (EvoApplications '11)


Torino, Italy


10


The technique of computationally analysing a program by searching for instances which causes the program to run in its worst-case time is examined. Concorde, the state-of-the-art Traveling Salesperson Problem (TSP) solver, is the program used to test our approach. We seed our evolutionary approach with a fractal instance of the TSP, defined by a Lindenmayer system at a fixed order. The evolutionary algorithm produced modifications to the L-System rules such that the instances of the modified L-System become increasingly much harder for Concorde to solve to optimality. In some cases, while still having the same size, the evolved instances required a computation time which was 30,000 times greater than what was needed to solve the original instance that seeded the search. The success of this case study shows the potential of Evolutionary Search to provide new test-case scenarios for algorithms and their software implementations.


Evolutionary Analysis of Algorithms, Memetic Design, fractals, L-Systems


http://evostar.dei.uc.pt/


nicta:4678


Ahammed, Farhan; Pablo, Moscato. Evolving L-Systems as an intelligent design approach to ?nd classes of dicult-to-solve Traveling Salesman Problem instances.[Conference Material]. 2011-04-27. <a href="http://hdl.handle.net/102.100.100/104524?index=1" target="_blank">http://hdl.handle.net/102.100.100/104524?index=1</a>



Loading citation data...

Citation counts
(Requires subscription to view)