Michael Kalochristianakis


FT: the problem with facts
why facts don't change our minds
'father of internet' joins tech leaders in condemning repeal plan





code == knowledge
|programs| < |problems|

optimization of the travelling salesman problem using a genetic approach

given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization. TSP is a special case of the travelling purchaser problem and the vehicle routing problem. The decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (perhaps, specifically, exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1% (wikipedia).

input

number of nodes

distance matrix

population size

number of iterations

elite children percentage




April, 2004