You are here

Implementing the Traveling Salesman Problem

    So far, we have discussed the basic principles of genetic algorithms and how they are used. Now it is time to examine a C# example. In this section, you will be shown a complete application that is capable of finding solutions to the TSP. As this program is examined, you will be shown how the user interface is constructed, and also how the genetic algorithm itself is implemented.

Using the Traveling Salesman Program

    The traveling salesman program itself is very easy to use. This program displays the cities, shown as dots, and the current best solution. The number of generations and the mutation percentage are also shown. As the program runs, these values are updated. The final output from the program is shown in Figure 6.2.

Figure 6.2: The traveling salesman program.

The traveling salesman program.

    As the program is running, you will see white lines change between the green cities. Eventually, a path will begin to emerge. The path currently being displayed is close to the shortest path in the entire population.

    When the program is nearly finished, you will notice that new patterns are not introduced; the program seems to stabilize. Yet, you will also notice that additional generations are still being calculated. This is an important part of the genetic algorithm—knowing when it is done! It is not as straightforward as it might seem. You do not know how many steps are required, nor do you know the shortest distance.

    Termination criteria must be specified, so the program will know when to stop. This particular program stops when the optimal solution does not change for 100 generations. Once this has happened, the program indicates that it has found a solution after the number of generations indicated, which includes the 99 generations that did not change the solution. Now that you have seen how this GA program works, we will examine how it was constructed. We will begin by examining the user interface.

Overall Structure

    The traveling salesman program uses five C# classes. It is important to understand the relationship between the individual classes that make up the traveling salesman program. These classes, and their functions, are summarized in Table 6.3.

Table 6.3: Classes Used for the GA Version of the Traveling Salesman

Class Purpose
City This class stores individual city coordinates. It also contains methods that are used to calculate the distance between cities.
GeneticTravelingSalesman This class implements the user interface and performs general initialization.
TSPChromosome This class implements the chromosome. It is the most complex class of the program, as it implements most of the functionality of the genetic algorithm.
TSPGeneticAlgorithm This class implements the genetic algorithm. It is used to perform the training and process the chromosomes.
WorldMap This class assists the GeneticTravelingSalesman class by drawing the map of cities.

    Most of the work is done by the TSPChromosome class. This class is covered in the next section.

Traveling Salesman Chromosomes

    When implementing a genetic algorithm using the classes provided in this book, you must generally create your own cost calculation method, named CalculateCost, as well as your own mutation function, named Mutate. The signature for the traveling salesman problem's CalculateCost method is shown here:

override public void CalculateCost()  

    Calculating the cost for the traveling salesman problem is relatively easy; the distance between each of the cities is summed. The program begins by initializing a running cost variable to zero and looping through the entire list of cities.

double cost = 0.0;
for (int i = 0; i < this.cities.Length - 1; i++) 
{

    For each city, the distance between this city and the next is calculated.

 double dist = this.cities[GetGene(i)]
  .proximity(this.cities[GetGene(i + 1)]);

    The distance is added to the total cost.

 cost += dist;
}

    Finally, the cost is saved to an instance variable.

this.Cost = cost;

    A Mutate method is also provided. The signature for the Mutate method is shown here:

override public void Mutate() 

    First, the length is obtained and two random cities are chosen to be swapped.

Random rand = new Random();
int length = this.Genes.Length;
int iswap1 = (int) (rand.NextDouble() * length);
int iswap2 = (int)(rand.NextDouble() * length);

    The two cities are then swapped.

int temp = GetGene(iswap1);
SetGene(iswap1, GetGene(iswap2));
SetGene(iswap2, temp);		

    The preceding code shows you how the generic genetic algorithm provided in this book was extended to solve a general problem like the traveling salesman. In the next section, classes will be provided that will allow you to use the generic algorithm to train a neural network using training sets in place of backpropagation.

Position: 

Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer