Travelling Salesman Problem

This attempts to solve the Travelling Salesman Problem using a Genetic Algorithm. It is not guaranteed to produce an optimal solution, but with suitable values of MaxIter and PopulationSize, it can, given time and a bit of luck, find the optimal path of length 1989, when all 25 towns are specified. [Try the goal: towns25(Iterations, Length, Route).]

/* tsp(MaxIter, PopulationSize, Towns, Expected, Iters, Length, Route)     */
/*   performs a GA search with a population size of PopulationSize for the */
/*   given Towns.  The search will terminate when either MaxIter           */
/*   iterations have been performed, or when the Expected path length is   */
/*   reached.  In either case, Route is the best route found during the    */
/*   search, Length its length, and Iters the total number of iterations.  */
/*   If the Expected path length is unknown, it can be replaced by 0.      */
/* e.g. tsp(100, 100, [leeds,dover,york,london,cardiff,hull], 0, I, L, R). */
tsp(MaxIter, PopulationSize, Towns, Expected, Iters, Length, Route):-  
  abolish(town/2),
  abolish(e/3),
  towns_integers(Towns, 1),
  forall((member(Town1, Towns), member(Town2, Towns), d(Town1, Town2, D)), 
         (town(Town1, I), town(Town2, J), assert(e(I, J, D)))),
  length(Towns, NumberOfTowns),
  population(PopulationSize, NumberOfTowns, Population),
  asserta(args(0, MaxIter, PopulationSize, NumberOfTowns, Population,
               Expected, c(32767,[]))),
  tsp_1,
  retract(args(Iters, _, _, _, _, _, c(Length,Route0))), !,
  integers_towns(Route0, Route).

tsp_1:-
  args(Imax, Imax, _, _, _, _, _), 
  !. 
tsp_1:-
  args(_, _, _, _, _, Expected0, c(Expected,_)), 
  Expected =< Expected0,
  !. 
tsp_1:-
  retract(args(I, Imax, PopSize, NumberOfTowns, Pop0, Expected, Best)),
  !,
  crossover(PopSize, NumberOfTowns, Pop0, Pop1),
  mutation(I, PopSize, NumberOfTowns, Pop1, Pop),
  best(Pop, Best1),
% debug(Best, Best1),
  I1 is I + 1,
  asserta(args(I1, Imax, PopSize, NumberOfTowns, Pop, Expected, Best1)),
  tsp_1.

debug(c(L,_), c(M,_)):-M >= L, !.
debug(_, C):-write(C), nl.

towns25(Iterations, Length, Route):-
  Towns=[aberdeen, aberystwyth, brighton, birmingham, bristol, cambridge,
         cardiff, carlisle, dover, edinburgh, exeter, glasgow, hull, leeds,
         liverpool, manchester, newcastle, nottingham, oxford, penzance,
         portsmouth, sheffield, swansea, york, london],
  tsp(32767, 200, Towns, 1989, Iterations, Length, Route).

/* population(M, N, List) is true if the List contains M elements, each    */
/*   element being a structure c(Length, Towns), where Towns is a pseudo-  */
/*   random permutation of the integers 1 to N, and Length is the length   */
/*   of the tour represented by this permutation.                          */
population(0, _, []):-!.
population(M, N, [c(Length,Perm)|Perms]):-
  M > 0,
  perm_rand(N, Perm),
  distance(Perm, Length),
  M1 is M - 1,
  population(M1, N, Perms).
  
/* Crosses over two routes chosen by select/4 and replaces the two worst   */
/*   tours in the population by the two new tours.                         */
/* 
   1 2 3|4 5 6 7 8 Route1
   2 4 6|8 1 3 5 7 Route2
   ---------------
   4 6 8 5 7|3 2 1 New1
   1 3 5 7 8|2 4 6 New2
*/   
crossover(PopulationSize, NumberOfTowns, Population0, Population):-
  SelectionCount is 1 + PopulationSize // 4,
  select(SelectionCount, PopulationSize, Population0, Route1),
  select(SelectionCount, PopulationSize, Population0, Route2),
  rand_int(NumberOfTowns, PrefixLength),
  prefix_n(PrefixLength, Route1, Prefix1),
  reverse(Prefix1, ReversedPrefix1),
  union(Route2, ReversedPrefix1, New1),
  prefix_n(PrefixLength, Route2, Prefix2),
  union(Route1, Prefix2, New2),
  distance(New1, L1),
  distance(New2, L2),
  worst(Population0, Worst1),
  efface(Population0, Worst1, Population1),
  worst(Population1, Worst2),
  efface(Population1, Worst2, Population2),
  Population=[c(L1,New1),c(L2,New2)|Population2].

/* Selects the best of N pseudo-randomly-chosen routes.                    */
select(N, PopulationSize, Population, Route):-
  select_1(N, PopulationSize, Population, c(32767,[]), c(_,Route)).
  
select_1(0, _, _, Tour, Tour):-!.
select_1(N, PopulationSize, Population, Tour0, Tour):-
  member_rand(Population, PopulationSize, Tour1),
  better(Tour0, Tour1, Tour2),
  N1 is N - 1,
  select_1(N1, PopulationSize, Population, Tour2, Tour).
  
/* Mutates (swaps two towns in) a route chosen by select/4 and replaces    */
/*   the worst tour in the population by the new tour.                     */
mutation(L, _, _, Population, Population):-
  L mod 100 =\= 0, !. /* Do a mutation every 100 iterations */
mutation(_, PopulationSize, NumberOfTowns, Population0, Population):-
  SelectionCount is 1 + PopulationSize // 20,
  select(SelectionCount, PopulationSize, Population0, Route),
  rand_int(NumberOfTowns, Town1),
  repeat,
    rand_int(NumberOfTowns, Town2),
  Town1 \= Town2, !, /* The following code could fail if Town1=Town2 */
  subst(Route, Town1, 0, Route1),
  subst(Route1, Town2, Town1, Route2),
  subst(Route2, 0, Town2, NewRoute),
  distance(NewRoute, Length),
  worst(Population0, Worst),
  efface(Population0, Worst, Population1),
  Population=[c(Length,NewRoute)|Population1].

/* best(List, Best) is true if Best is the best element in the List        */
/*   according to the predicate better/2.                                  */
best([X|Xs], Best):-best_1(Xs, X, Best).

/* best_1(List, Element, Best) is true if Best is the best element in the  */
/*   list [Element|List].                                                  */
best_1([], Best, Best).
best_1([Y|Ys], X, Best):-better(X, Y, Better), best_1(Ys, Better, Best).

/* better(X, Y, Better) is true if Better is the better of X and Y.        */
better(c(L,X), c(M,_), Z):-L < M, !, Z=c(L,X).
better(_, Chromo, Chromo).

/* worst(List, Worst) is true if Worst is the worst element in the List    */
/*   according to the predicate worse/2.                                   */
worst([X|Xs], Worst):-worst_1(Xs, X, Worst).

/* worst_1(List, Element, Worst) is true if Worst is the worst element in  */
/*   the list [Element|List].                                              */
worst_1([], Worst, Worst).
worst_1([Y|Ys], X, Worst):-worse(X, Y, Worse), worst_1(Ys, Worse, Worst).

/* worse(X, Y, Worse) is true if Worse is the worse of X and Y.            */
worse(c(L,X), c(M,_), Z):-L > M, !, Z=c(L,X).
worse(_, Chromo, Chromo).

/* This is the data from LPA Win-Prolog Examples\Salesman.pl */
d( aberdeen,    aberystwyth, 427 ).
d( aberdeen,    birmingham,  403 ).
d( aberdeen,    brighton,    547 ).
d( aberdeen,    bristol,     480 ).
d( aberdeen,    cambridge,   443 ).
d( aberdeen,    cardiff,     484 ).
d( aberdeen,    carlisle,    206 ).
d( aberdeen,    dover,       573 ).
d( aberdeen,    edinburgh,   115 ).
d( aberdeen,    exeter,      555 ).
d( aberdeen,    glasgow,     142 ).
d( aberdeen,    hull,        336 ).
d( aberdeen,    leeds,       306 ).
d( aberdeen,    liverpool,   327 ).
d( aberdeen,    manchester,  326 ).
d( aberdeen,    newcastle,   221 ).
d( aberdeen,    nottingham,  370 ).
d( aberdeen,    oxford,      464 ).
d( aberdeen,    penzance,    663 ).
d( aberdeen,    portsmouth,  550 ).
d( aberdeen,    sheffield,   338 ).
d( aberdeen,    swansea,     502 ).
d( aberdeen,    york,        299 ).
d( aberdeen,    london,      488 ).
d( aberystwyth, birmingham,  114 ).
d( aberystwyth, brighton,    249 ).
d( aberystwyth, bristol,     121 ).
d( aberystwyth, cambridge,   211 ).
d( aberystwyth, cardiff,     108 ).
d( aberystwyth, carlisle,    219 ).
d( aberystwyth, dover,       284 ).
d( aberystwyth, edinburgh,   312 ).
d( aberystwyth, exeter,      196 ).
d( aberystwyth, glasgow,     313 ).
d( aberystwyth, hull,        216 ).
d( aberystwyth, leeds,       166 ).
d( aberystwyth, liverpool,   100 ).
d( aberystwyth, manchester,  126 ).
d( aberystwyth, newcastle,   254 ).
d( aberystwyth, nottingham,  154 ).
d( aberystwyth, oxford,      156 ).
d( aberystwyth, penzance,    304 ).
d( aberystwyth, portsmouth,  218 ).
d( aberystwyth, sheffield,   154 ).
d( aberystwyth, swansea,      75 ).
d( aberystwyth, york,        190 ).
d( aberystwyth, london,      212 ).
d( birmingham,  brighton,    159 ).
d( birmingham,  bristol,      86 ).
d( birmingham,  cambridge,    97 ).
d( birmingham,  cardiff,     100 ).
d( birmingham,  carlisle,    198 ).
d( birmingham,  dover,       181 ).
d( birmingham,  edinburgh,   291 ).
d( birmingham,  exeter,      162 ).
d( birmingham,  glasgow,     292 ).
d( birmingham,  hull,        122 ).
d( birmingham,  leeds,       109 ).
d( birmingham,  liverpool,    99 ).
d( birmingham,  manchester,   80 ).
d( birmingham,  newcastle,   198 ).
d( birmingham,  nottingham,   48 ).
d( birmingham,  oxford,       63 ).
d( birmingham,  penzance,    271 ).
d( birmingham,  portsmouth,  141 ).
d( birmingham,  sheffield,    75 ).
d( birmingham,  swansea,     125 ).
d( birmingham,  york,        125 ).
d( birmingham,  london,      110 ).
d( brighton,    bristol,     136 ).
d( brighton,    cambridge,   106 ).
d( brighton,    cardiff,     183 ).
d( brighton,    carlisle,    354 ).
d( brighton,    dover,        81 ).
d( brighton,    edinburgh,   432 ).
d( brighton,    exeter,      165 ).
d( brighton,    glasgow,     448 ).
d( brighton,    hull,        224 ).
d( brighton,    leeds,       250 ).
d( brighton,    liverpool,   250 ).
d( brighton,    manchester,  240 ).
d( brighton,    newcastle,   328 ).
d( brighton,    nottingham,  178 ).
d( brighton,    oxford,       96 ).
d( brighton,    penzance,    277 ).
d( brighton,    portsmouth,   49 ).
d( brighton,    sheffield,   216 ).
d( brighton,    swansea,     236 ).
d( brighton,    york,        250 ).
d( brighton,    london,       52 ).
d( bristol,     cambridge,   151 ).
d( bristol,     cardiff,      44 ).
d( bristol,     carlisle,    276 ).
d( bristol,     dover,       187 ).
d( bristol,     edinburgh,   369 ).
d( bristol,     exeter,       76 ).
d( bristol,     glasgow,     370 ).
d( bristol,     hull,        206 ).
d( bristol,     leeds,       195 ).
d( bristol,     liverpool,   163 ).
d( bristol,     manchester,  161 ).
d( bristol,     newcastle,   284 ).
d( bristol,     nottingham,  141 ).
d( bristol,     oxford,       71 ).
d( bristol,     penzance,    184 ).
d( bristol,     portsmouth,   97 ).
d( bristol,     sheffield,   161 ).
d( bristol,     swansea,      89 ).
d( bristol,     york,        211 ).
d( bristol,     london,      116 ).
d( cambridge,   cardiff,     177 ).
d( cambridge,   carlisle,    260 ).
d( cambridge,   dover,       125 ).
d( cambridge,   edinburgh,   330 ).
d( cambridge,   exeter,      216 ).
d( cambridge,   glasgow,     354 ).
d( cambridge,   hull,        124 ).
d( cambridge,   leeds,       143 ).
d( cambridge,   liverpool,   185 ).
d( cambridge,   manchester,  159 ).
d( cambridge,   newcastle,   226 ).
d( cambridge,   nottingham,   82 ).
d( cambridge,   oxford,       80 ).
d( cambridge,   penzance,    329 ).
d( cambridge,   portsmouth,  126 ).
d( cambridge,   sheffield,   116 ).
d( cambridge,   swansea,     216 ).
d( cambridge,   york,        149 ).
d( cambridge,   london,       54 ).
d( cardiff,     carlisle,    277 ).
d( cardiff,     dover,       232 ).
d( cardiff,     edinburgh,   370 ).
d( cardiff,     exeter,      119 ).
d( cardiff,     glasgow,     371 ).
d( cardiff,     hull,        227 ).
d( cardiff,     leeds,       209 ).
d( cardiff,     liverpool,   164 ).
d( cardiff,     manchester,  176 ).
d( cardiff,     newcastle,   298 ).
d( cardiff,     nottingham,  162 ).
d( cardiff,     oxford,      106 ).
d( cardiff,     penzance,    227 ).
d( cardiff,     portsmouth,  141 ).
d( cardiff,     sheffield,   175 ).
d( cardiff,     swansea,      45 ).
d( cardiff,     york,        232 ).
d( cardiff,     london,      161 ).
d( carlisle,    dover,       373 ).
d( carlisle,    edinburgh,    93 ).
d( carlisle,    exeter,      352 ).
d( carlisle,    glasgow,      94 ).
d( carlisle,    hull,        149 ).
d( carlisle,    leeds,       117 ).
d( carlisle,    liverpool,   118 ).
d( carlisle,    manchester,  120 ).
d( carlisle,    newcastle,    58 ).
d( carlisle,    nottingham,  187 ).
d( carlisle,    oxford,      260 ).
d( carlisle,    penzance,    455 ).
d( carlisle,    portsmouth,  338 ).
d( carlisle,    sheffield,   148 ).
d( carlisle,    swansea,     284 ).
d( carlisle,    york,        112 ).
d( carlisle,    london,      302 ).
d( dover,       edinburgh,   451 ).
d( dover,       exeter,      246 ).
d( dover,       glasgow,     467 ).
d( dover,       hull,        243 ).
d( dover,       leeds,       269 ).
d( dover,       liverpool,   269 ).
d( dover,       manchester,  260 ).
d( dover,       newcastle,   347 ).
d( dover,       nottingham,  197 ).
d( dover,       oxford,      128 ).
d( dover,       penzance,    355 ).
d( dover,       portsmouth,  130 ).
d( dover,       sheffield,   235 ).
d( dover,       swansea,     271 ).
d( dover,       york,        269 ).
d( dover,       london,       71 ).
d( edinburgh,   exeter,      445 ).
d( edinburgh,   glasgow,      44 ).
d( edinburgh,   hull,        221 ).
d( edinburgh,   leeds,       195 ).
d( edinburgh,   liverpool,   211 ).
d( edinburgh,   manchester,  213 ).
d( edinburgh,   newcastle,   104 ).
d( edinburgh,   nottingham,  258 ).
d( edinburgh,   oxford,      357 ).
d( edinburgh,   penzance,    548 ).
d( edinburgh,   portsmouth,  435 ).
d( edinburgh,   sheffield,   229 ).
d( edinburgh,   swansea,     377 ).
d( edinburgh,   york,        184 ).
d( edinburgh,   london,      380 ).
d( exeter,      glasgow,     446 ).
d( exeter,      hull,        282 ).
d( exeter,      leeds,       271 ).
d( exeter,      liverpool,   239 ).
d( exeter,      manchester,  237 ).
d( exeter,      newcastle,   360 ).
d( exeter,      nottingham,  217 ).
d( exeter,      oxford,      136 ).
d( exeter,      penzance,    112 ).
d( exeter,      portsmouth,  126 ).
d( exeter,      sheffield,   237 ).
d( exeter,      swansea,     165 ).
d( exeter,      york,        287 ).
d( exeter,      london,      172 ).
d( glasgow,     hull,        243 ).
d( glasgow,     leeds,       211 ).
d( glasgow,     liverpool,   212 ).
d( glasgow,     manchester,  214 ).
d( glasgow,     newcastle,   148 ).
d( glasgow,     nottingham,  281 ).
d( glasgow,     oxford,      355 ).
d( glasgow,     penzance,    549 ).
d( glasgow,     portsmouth,  433 ).
d( glasgow,     sheffield,   242 ).
d( glasgow,     swansea,     378 ).
d( glasgow,     york,        206 ).
d( glasgow,     london,      396 ).
d( hull,        leeds,        58 ).
d( hull,        liverpool,   122 ).
d( hull,        manchester,   90 ).
d( hull,        newcastle,   117 ).
d( hull,        nottingham,   90 ).
d( hull,        oxford,      164 ).
d( hull,        penzance,    396 ).
d( hull,        portsmouth,  242 ).
d( hull,        sheffield,    65 ).
d( hull,        swansea,     266 ).
d( hull,        york,         37 ).
d( hull,        london,      172 ).
d( leeds,       liverpool,    73 ).
d( leeds,       manchester,   41 ).
d( leeds,       newcastle,    89 ).
d( leeds,       nottingham,   72 ).
d( leeds,       oxford,      170 ).
d( leeds,       penzance,    378 ).
d( leeds,       portsmouth,  248 ).
d( leeds,       sheffield,    34 ).
d( leeds,       swansea,     229 ).
d( leeds,       york,         23 ).
d( leeds,       london,      198 ).
d( liverpool,   manchester,   35 ).
d( liverpool,   newcastle,   162 ).
d( liverpool,   nottingham,  100 ).
d( liverpool,   oxford,      165 ).
d( liverpool,   penzance,    343 ).
d( liverpool,   portsmouth,  243 ).
d( liverpool,   sheffield,    70 ).
d( liverpool,   swansea,     166 ).
d( liverpool,   york,         96 ).
d( liverpool,   london,      198 ).
d( manchester,  newcastle,   130 ).
d( manchester,  nottingham,   71 ).
d( manchester,  oxford,      143 ).
d( manchester,  penzance,    344 ).
d( manchester,  portsmouth,  221 ).
d( manchester,  sheffield,    38 ).
d( manchester,  swansea,     188 ).
d( manchester,  york,         64 ).
d( manchester,  london,      189 ).
d( newcastle,   nottingham,  155 ).
d( newcastle,   oxford,      253 ).
d( newcastle,   penzance,    468 ).
d( newcastle,   portsmouth,  331 ).
d( newcastle,   sheffield,   123 ).
d( newcastle,   swansea,     318 ).
d( newcastle,   york,         80 ).
d( newcastle,   london,      276 ).
d( nottingham,  oxford,       98 ).
d( nottingham,  penzance,    322 ).
d( nottingham,  portsmouth,  176 ).
d( nottingham,  sheffield,    38 ).
d( nottingham,  swansea,     173 ).
d( nottingham,  york,         80 ).
d( nottingham,  london,      126 ).
d( oxford,      penzance,    250 ).
d( oxford,      portsmouth,   78 ).
d( oxford,      sheffield,   136 ).
d( oxford,      swansea,     145 ).
d( oxford,      york,        178 ).
d( oxford,      london,       57 ).
d( penzance,    portsmouth,  242 ).
d( penzance,    sheffield,   348 ).
d( penzance,    swansea,     273 ).
d( penzance,    york,        398 ).
d( penzance,    london,      281 ).
d( portsmouth,  sheffield,   214 ).
d( portsmouth,  swansea,     186 ).
d( portsmouth,  york,        256 ).
d( portsmouth,  london,       72 ).
d( sheffield,   swansea,     196 ).
d( sheffield,   york,         52 ).
d( sheffield,   london,      164 ).
d( swansea,     york,        248 ).
d( swansea,     london,      200 ).
d( york,        london,      198 ).

/* e.g. towns_integers([leeds,bristol,york,london,hull], 1).               */
towns_integers([], _).
towns_integers([Town|Towns], I):-
  assert(town(Town, I)),
  I1 is I + 1,
  towns_integers(Towns, I1).

/* e.g. integers_towns([3,1,5,2,4], Towns).                                */
integers_towns([], []).
integers_towns([I|Is], [Town|Towns]):-
  town(Town, I),
  !,
  integers_towns(Is, Towns).
  
dist(X, Y, D):-e(X, Y, D), !.
dist(X, Y, D):-e(Y, X, D), !.

/* distance(Towns, Length) is true if Length is the length, as defined by  */
/*   dist/3, of the route going through all the Towns (including returning */
/*   to the first town from the last town).                                */
distance([Start|Towns], Length):-  
  distance_1(Towns, Start, Start, 0, Length).

distance_1([], End, Start, Length0, Length):-
  dist(End, Start, Length1),
  Length is Length0 + Length1.
distance_1([Town|Towns], Town0, Start, Length0, Length):-
  dist(Town0, Town, Length1),
  Length2 is Length0 + Length1,
  distance_1(Towns, Town, Start, Length2, Length).

/* efface(Xs, Y, Zs) is true if Zs is the result of deleting the first     */
/*   occurrence of the element Y from the list Xs.                         */
efface([Y|Xs], Y, Xs):-!.
efface([X|Xs], Y, [X|Zs]):-efface(Xs, Y, Zs).

/* member_rand(Xs, M, X) is true if X is the N-th (base 1) element of the  */
/*   list Xs, where N is a pseudo-random number between 1 and M.           */
member_rand(Xs, M, X):-
  rand_int(M, N),
  member_rand_1(Xs, X, 1, N).

member_rand_1([X|_], X, N, N):-!.
member_rand_1([_|Xs], X, N0, N):-
  N1 is N0 + 1,
  member_rand_1(Xs, X, N1, N).
  
/* perm_rand(N, Perm) is true if Perm is a pseudo-random permutation of    */
/*   the integers 1 to N inclusive.                                        */
perm_rand(N, Perm):-
  N >= 0,
  perm_rand_1(N, N, [], Perm).

perm_rand_1(0, _, Perm, Perm):-!.
perm_rand_1(M, N, Perm0, Perm):-
  repeat,
    rand_int(N, Rand),
  \+ member(Rand, Perm0), !,
  M1 is M - 1,
  perm_rand_1(M1, N, [Rand|Perm0], Perm).

/* prefix_n(N, List, Prefix) is true if Prefix is the leading prefix of    */
/*   length N of the List.                                                 */
prefix_n(0, _, []):-!.
prefix_n(N, [X|Xs], [X|Ys]):-
  N1 is N - 1,
  prefix_n(N1, Xs, Ys).

/* subst(Ls, X, A, Ms) is true if the list Ms is the same as the list Ls   */
/*   except that the first occurrence of the element X is replaced by A.   */
subst([X|Ms], X, A, Ns):-!, Ns=[A|Ms].
subst([L|Ls], X, A, [L|Ms]):-subst(Ls, X, A, Ms).
 
/* rand_int(I, J) is true if J is a pseudo-random integer in the range     */
/*   1 to I.                                                               */
rand_int(I, J):-J is int(rand(I)) + 1.

/* union(Xs, Ys, Zs) is true if Zs is the list of the set of elements in   */
/*   the union of the sets of elements in lists Xs and Ys.                 */
union([], Ys, Ys).
union([X|Xs], Ys, Zs):-member(X, Ys), !, union(Xs, Ys, Zs).
union([X|Xs], Ys, [X|Zs]):-union(Xs, Ys, Zs).

LPA Index     Home Page

Valid HTML 4.01 Strict