fig. 9: The TSP application at design time
The components detailed in sections 4 - 12 were brought together in a simple application which solves the travelling salesman problem for random sets of cities. Figure 9 shows the main form for this application at design time and figure 10 shows the program running.
fig. 9: The TSP application at design time
fig. 10: Solving the TSP with 30 cities
The interface consists of three main display components and a set of controls on the right hand side which we can use to configure various parameters.
The main display component is our TTSPDisplay, which is used to display the cities and the routes between them. To the right of this is a list box which shows the fitnesses of the individuals in the population, with the best at the top. Clicking an individual in this list will display the associated route on the TSP Display component. Along the bottom of the form is a graph which shows the change in the fitness of the best individual in the population for each generation. This gives us an idea of how the EA is progressing.
Controls on the right of the main form allow the user to set up the problem by creating a random collection of cities and an initial population. We can also set up some EA parameters: The percentage of the population to be killed and probabilities for transposition and inversion.
Code and an executable can be downloaded - see the conclusion
Figures 11, 12 and 13 show the TSP for 500 cities. The number of possible solutions is 500! (500 factorial), which is a very large number. The fact that the EA system found a reasonable solution overnight illustrates its validity as a problem solving technique.
fig. 11: Solving the TSP with 500 cities - initial random route
fig. 12: Solving the TSP with 500 cities - after 2,000 generations (around 15 minutes)
fig. 13: Solving the TSP with 500 cities - a decent solution after 70,000 generations (around 9 hours)
| Back |
|
|
| Contents | ||
| Next | ||