Genetic Algorithms And Evolutionary Learning .*;

Traveling Salesman Problem Example 1

This is a rendition of the classic Traveling Salesman Problem, where the shortest tour needs to be found among all cites without visiting the same one twice.  The algorithm works out the minimum Cartesian distance through eight cities named 0, 1, 2, 3, 4, 5, 6 and 7.  There are 108 (or, 100,000,000) possible combinations, but this algorithm can find them in less than 103, and sometimes less than 102!

The cities' locations are (30, 5), (40, 10), (40, 20), (29, 25), (19, 25), (9, 19), (9, 9), (20, 5).  This is roughly a circle; something easy to see on a graph and check the algorithm's solutions with.

This is what is known as a permutation problem where the chromosomes cannot contain any duplicate values, so instead of swapping genes between parents, the genes must be swapped within each parent.  The kind of crossover for this example is called "partially-mapped crossover".  All manner of combinations using eight digit strings of 0 through 7 are explored to find the one that represents the shortest distance (i.e.; 01234567).  By hand, I've found the solution to be about 86.6299, which is the target value of the algorithm.

To simplify this example, there is no starting or ending point, and it doesn't matter which direction the tour travels in (i.e.; forward or backward).  For instance, a solution that looks like 34567012 is valid because it travels forward from 3 and around to 2.  The solution 76543210 is equally valid, it just goes backward from 7 to 0.

Selection is implemented with the Roulette Wheel method.  One offspring at a time is produced between two parents.

You can adjust:

  • StartSize - population size at start.
  • MaxInputs - the number of chromosomes in the population.
  • MaxEpochs - arbitrary number of test cycles.
  • rRate - probability of two chromosomes mating.
  • mRate - mutation rate.
  • MinSelect - minimum parents allowed for selection.
  • MaxSelect - maximum parents allowed for selection.
  • oRate - new offspring created per generation.
  • MinShuffles and MaxShuffles - for randomizing starting chromosomes.
  • ShowVerboseResults - setting this to False will only print out the first and last generations, and definitely speed up the program!

 

Example Results 1

With StartSize = 25, MinSelect = 10, MaxSelect = 50, and oRate = 20.

Epoch: 175
54321706; Dist = 105.738036217805; at 84%
23547601; Dist = 118.913145300258; at 73%
65430127; Dist = 109.57192798241; at 81%
23546701; Dist = 106.378564843438; at 84%
65430127; Dist = 109.57192798241; at 81%
52107634; Dist = 121.175565376182; at 72%
65340127; Dist = 121.591077237066; at 71%
34506712; Dist = 122.681595056773; at 70%
01236754; Dist = 122.872404747027; at 70%
67023145; Dist = 117.885457090191; at 74%
25643701; Dist = 122.996139189615; at 70%
32456710; Dist = 118.857535229016; at 74%
07321456; Dist = 122.861196090306; at 70%
74532106; Dist = 118.913145300258; at 73%
70432156; Dist = 118.893195088479; at 74%
12346507; Dist = 116.805395294044; at 75%
23456107; Dist = 120.941414489326; at 72%
76543120; Dist = 99.9954353154684; at 89%
17650432; Dist = 122.467557361677; at 71%
76432105; Dist = 116.879400778939; at 75%
01234756; Dist = 112.470422396791; at 79%
54123706; Dist = 122.861196090306; at 70%
31075642; Dist = 120.123950322633; at 73%
70312456; Dist = 113.579696477572; at 78%
63542107; Dist = 122.627086700385; at 70%
01254367; Dist = 121.175565376182; at 72%
56430127; Dist = 122.877780360878; at 70%
07654231; Dist = 106.818097944165; at 83%
57021346; Dist = 113.301287693936; at 78%
41023765; Dist = 122.396433939413; at 71%
64531207; Dist = 119.744010597403; at 73%
31207564; Dist = 113.301287693936; at 78%
76453120; Dist = 119.744010597403; at 73%
35670214; Dist = 116.420045106989; at 76%
76012354; Dist = 118.913145300258; at 73%
24536701; Dist = 122.627086700385; at 70%
24536701; Dist = 122.627086700385; at 70%
05432176; Dist = 122.681595056773; at 70%
64320175; Dist = 118.57912644538; at 74%
54321076; Dist = 86.6299895615037; at 100%
Done.
5, 4, 3, 2, 1, 0, 7, 6, 
Completed 175 epochs.
Encountered 3 mutations in 2085 offspring.

 

Example Results 2

With StartSize = 25, MinSelect = 20, MaxSelect = 75, and oRate = 40.

Epoch: 270
21074563; Dist = 110.562770995016; at 80%
57601234; Dist = 105.812041702701; at 84%
13245670; Dist = 106.818097944165; at 83%
13245670; Dist = 106.818097944165; at 83%
31207654; Dist = 99.9954353154684; at 89%
76542310; Dist = 106.818097944165; at 83%
12365470; Dist = 110.562770995016; at 80%
70213456; Dist = 99.9954353154684; at 89%
23476501; Dist = 110.231929094562; at 81%
07645321; Dist = 106.378564843438; at 84%
65470123; Dist = 110.562770995016; at 80%
72103456; Dist = 109.57192798241; at 81%
65423107; Dist = 106.818097944165; at 83%
01243567; Dist = 105.352685960963; at 85%
12345760; Dist = 105.812041702701; at 84%
70123654; Dist = 110.562770995016; at 80%
36547012; Dist = 110.562770995016; at 80%
12345607; Dist = 105.738036217805; at 84%
23456701; Dist = 86.6299895615037; at 100%
Done.
2, 3, 4, 5, 6, 7, 0, 1, 
Completed 270 epochs.
Encountered 6 mutations in 5161 offspring.

 

Example Results 2b

Sometimes it gets stuck in local minima, even with these same settings...

Epoch: 501
67021345; Dist = 99.9954353154684; at 100%
51234076; Dist = 118.893195088479; at 83%
65012347; Dist = 110.231929094562; at 91%
45607213; Dist = 116.640537353861; at 85%
65012347; Dist = 110.231929094562; at 91%
64531207; Dist = 119.744010597403; at 82%
34576021; Dist = 119.177487456665; at 82%
65401237; Dist = 111.387126181992; at 89%
67021345; Dist = 99.9954353154684; at 100%
54632107; Dist = 117.210242679394; at 84%
12075643; Dist = 113.301287693936; at 88%
10746532; Dist = 113.036945537529; at 88%
10746532; Dist = 113.036945537529; at 88%
65432017; Dist = 105.273274066912; at 95%
34675012; Dist = 116.879400778939; at 84%
67013245; Dist = 106.818097944165; at 94%
76021345; Dist = 119.177487456665; at 82%
32156704; Dist = 118.893195088479; at 83%
54213076; Dist = 113.579696477572; at 87%
70213456; Dist = 99.9954353154684; at 100%
53401276; Dist = 121.591077237066; at 80%
45670312; Dist = 113.579696477572; at 87%
47601235; Dist = 118.913145300258; at 83%
32017654; Dist = 105.273274066912; at 95%
65012347; Dist = 110.231929094562; at 91%
21073456; Dist = 117.667724283448; at 84%
01234765; Dist = 110.231929094562; at 91%
23407651; Dist = 118.893195088479; at 83%
45632107; Dist = 110.562770995016; at 90%
21037654; Dist = 118.090673326794; at 83%
46532107; Dist = 113.036945537529; at 88%
30456712; Dist = 118.915586617621; at 83%
07654132; Dist = 117.885457090191; at 83%
01234765; Dist = 110.231929094562; at 91%
10756342; Dist = 116.184363796918; at 85%
45670132; Dist = 106.818097944165; at 94%
65341207; Dist = 116.420045106989; at 85%
54321067; Dist = 105.812041702701; at 95%
01235647; Dist = 113.036945537529; at 88%
10756342; Dist = 116.184363796918; at 85%
07654231; Dist = 106.818097944165; at 94%
01234576; Dist = 105.812041702701; at 95%
61072345; Dist = 120.941414489326; at 81%
01234765; Dist = 110.231929094562; at 91%
56703214; Dist = 111.281609869633; at 90%
12456730; Dist = 118.090673326794; at 83%
16543270; Dist = 120.941414489326; at 81%
12345607; Dist = 105.738036217805; at 95%
37654012; Dist = 111.387126181992; at 89%
45610723; Dist = 120.941414489326; at 81%
32017654; Dist = 105.273274066912; at 95%
76542103; Dist = 118.090673326794; at 83%
35674012; Dist = 118.699107605162; at 83%
70213465; Dist = 113.301287693936; at 88%
46570123; Dist = 99.9358419399716; at 100%
60123457; Dist = 105.812041702701; at 95%
60123457; Dist = 105.812041702701; at 95%
65421037; Dist = 118.090673326794; at 83%
63452107; Dist = 121.175565376182; at 80%
57602134; Dist = 119.177487456665; at 82%
43012765; Dist = 109.57192798241; at 91%
54372106; Dist = 121.151514203083; at 80%
04567123; Dist = 118.915586617621; at 83%
56321074; Dist = 110.562770995016; at 90%
56321074; Dist = 110.562770995016; at 90%
67012435; Dist = 105.352685960963; at 95%
32456701; Dist = 106.818097944165; at 94%
60712345; Dist = 105.738036217805; at 95%
43215670; Dist = 118.893195088479; at 83%
12304567; Dist = 118.915586617621; at 83%
31245670; Dist = 113.579696477572; at 87%
56321074; Dist = 110.562770995016; at 90%
65071234; Dist = 116.805395294044; at 84%
27653401; Dist = 121.591077237066; at 80%
10754632; Dist = 117.210242679394; at 84%
60123547; Dist = 118.913145300258; at 83%
76534210; Dist = 105.352685960963; at 95%
43120675; Dist = 119.177487456665; at 82%
54032176; Dist = 118.915586617621; at 83%
06754312; Dist = 119.177487456665; at 82%
76543201; Dist = 105.273274066912; at 95%
21043567; Dist = 121.591077237066; at 80%
43657012; Dist = 116.184363796918; at 85%
57012436; Dist = 116.184363796918; at 85%
76534012; Dist = 121.591077237066; at 80%
56712034; Dist = 112.034872600319; at 89%
42130765; Dist = 113.579696477572; at 87%
12356740; Dist = 118.699107605162; at 83%
67012543; Dist = 121.175565376182; at 80%
34210756; Dist = 116.184363796918; at 85%
34210756; Dist = 116.184363796918; at 85%
34210756; Dist = 116.184363796918; at 85%
23456107; Dist = 120.941414489326; at 81%
56012347; Dist = 112.470422396791; at 88%
54327016; Dist = 120.941414489326; at 81%
54327016; Dist = 120.941414489326; at 81%
57102346; Dist = 118.57912644538; at 83%
57102346; Dist = 118.57912644538; at 83%
65401237; Dist = 111.387126181992; at 89%
10746532; Dist = 113.036945537529; at 88%
46702135; Dist = 119.744010597403; at 82%
56701243; Dist = 105.352685960963; at 95%
34567210; Dist = 109.57192798241; at 91%
70214356; Dist = 116.420045106989; at 85%
47560123; Dist = 112.470422396791; at 88%
36457012; Dist = 117.210242679394; at 84%
65071234; Dist = 116.805395294044; at 84%
43567021; Dist = 116.420045106989; at 85%
73456012; Dist = 121.151514203083; at 80%
06543127; Dist = 116.640537353861; at 85%
46571023; Dist = 118.57912644538; at 83%
46571023; Dist = 118.57912644538; at 83%
15670432; Dist = 118.893195088479; at 83%
07654231; Dist = 106.818097944165; at 94%
65701234; Dist = 99.9358419399716; at 100%
67023145; Dist = 117.885457090191; at 83%
34012765; Dist = 121.591077237066; at 80%
76021345; Dist = 119.177487456665; at 82%
64321075; Dist = 99.9358419399716; at 100%
Done.
Completed 501 epochs.
Encountered 8 mutations in 7672 offspring.

 

Example Results 3

With StartSize = 25, MinSelect = 10, MaxSelect = 50, and oRate = 20.  This time, the mRate (mutation rate) is set to 0.01 instead of 0.001 (maybe more mutations might shake it out of local minima).

Epoch: 209
21706543; Dist = 105.738036217805; at 84%
70132456; Dist = 106.818097944165; at 83%
32017654; Dist = 105.273274066912; at 85%
21706543; Dist = 105.738036217805; at 84%
12345607; Dist = 105.738036217805; at 84%
12345607; Dist = 105.738036217805; at 84%
32107456; Dist = 110.562770995016; at 80%
12346570; Dist = 99.9358419399716; at 89%
74563210; Dist = 110.562770995016; at 80%
07654312; Dist = 99.9954353154684; at 89%
23457601; Dist = 105.812041702701; at 84%
70654321; Dist = 105.738036217805; at 84%
32106754; Dist = 105.812041702701; at 84%
06754321; Dist = 105.812041702701; at 84%
23456710; Dist = 105.273274066912; at 85%
21076453; Dist = 106.378564843438; at 84%
75643210; Dist = 99.9358419399716; at 89%
01234765; Dist = 110.231929094562; at 81%
10234567; Dist = 105.273274066912; at 85%
32106754; Dist = 105.812041702701; at 84%
21056743; Dist = 110.231929094562; at 81%
01234765; Dist = 110.231929094562; at 81%
70213456; Dist = 99.9954353154684; at 89%
01236547; Dist = 110.562770995016; at 80%
65430127; Dist = 109.57192798241; at 81%
65430127; Dist = 109.57192798241; at 81%
65430127; Dist = 109.57192798241; at 81%
02134567; Dist = 99.9954353154684; at 89%
67013245; Dist = 106.818097944165; at 83%
42310765; Dist = 106.818097944165; at 83%
64321075; Dist = 99.9358419399716; at 89%
23456701; Dist = 86.6299895615037; at 100%
Done.
2, 3, 4, 5, 6, 7, 0, 1, 
Completed 209 epochs.
Encountered 41 mutations in 4144 offspring.

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}