Travelling salesman problem solved by using genetic algorithms

This problem finds the shortest path for a given graph

In the following exemple I used the algorithm on the berlin52 dataset with the following parameters :

• Population size : 100
  
• Mutation factor : 30%
  
• Number of generations : 1000
  

The shortest path had the cost : 7713.506772189631

And the following paths had this cost sum:

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631

Chromosome: [11, 27, 26, 25, 46, 12, 13, 51, 10, 50, 3, 24, 23, 47, 36, 39, 37, 4, 5, 14, 42, 32, 9, 8, 7, 40, 18, 44, 31, 48, 38, 35, 34, 33, 45, 15, 43, 0, 21, 30, 17, 2, 16, 20, 22, 19, 49, 28, 29, 41, 6, 1] --- fit: 7713.506772189631