I have recently become very interested in the area of genetic algorithms and Ant Colony Optimization techniques. I was determined to write a complete program demonstrating these two techniques. In particular I wanted to compare the efficiency of these two approaches in the area of finding solutions to the Traveling Salesman Problem (TSP).
Buckland (2002, pp. 118) succinctly summarizes the problem as, �Given a collection of cities, the traveling salesman must determine the shortest route that will enable him to visit each city precisely once and then return back to his starting point.�
He goes on to explain that this is an example of what mathematicians call NP-Complete problems. As more cities are added, the computational power required to solve the problem increases exponentially. An algorithm implemented on a computer that solves the TSP for fifty cities would require an increase in computer power of a thousand-fold just to add an additional ten cities. The following table demonstrated the problem:
Clearly, a "brute force" way becomes impossible for a large number of cities and alternate algorithms need to be employed if a solution is to be found for this problem.
The algorithm consists of the following fundamental steps:
I am not going to discuss the details of genetic algorithms, as these are better explained elsewhere, apart from discussing the mechanisms used to produce valid crossover operators and Roulette Wheel Selection. Each chromosome is encoded as a possible tour. For example, a tour of five cities might be encoded as 3,4,0,1,2. A difficulty with the TSP is that a simple crossover will not work. Consider the following situation where crossover occurs at position 3.
| Parent 1 | 1 2 3 4 5 |
| Parent 2 | 3 5 2 1 4 |
| Child 1 | 1 2 3 1 4 |
| Child 2 | 3 5 2 4 5 |
A problem that has occurred here is that Child 1 has visited city 1 two times, which is not allowed, and Child 2 has not visited city 1 at all. A defacement encoding must be used in order to make sure that only valid tours are produced. A well-known and perhaps the simplest to understand crossover operator is called the Partially Matched Crossover. Buckland (2002, pp. 130-132) explains this technique as follows:
A crossing region is picked.
Parent 1: 12x34x5 Parent 2: 35x21x4The following mapping is established.
3 -> 2 4 -> 1Now we cycle through each parent gene and swap the genes wherever a gene is found that occurs in the above mapping.
First iteration (mapping 3 with 2):
Child 1: 13245 Child 2: 25314Second iteration (mapping 4 with 1):
Child 1: 43215 Child 2: 25341The final crossed-over genes are valid permutations with no duplicates.
Roulette Wheel Selection is a technique of choosing members from the population of chromosomes in a way that is proportional to their fitness. Buckland illustrates, �Imagine that the population�s total fitness score is represented by a pie chart or roulette wheel. Now you assign a slice of the wheel to each member of the population. The size of the slice is proportional to that chromosome�s fitness score: the fitter a member is, the bigger the slice of pie it gets. Now, to choose a chromosome, all you have to do is spin the wheel, toss in the ball and grab the chromosome that the ball stops on.� Buckland (2002, pp. 100)
This algorithm is inspired by observation of real ants. Individually, each ant is blind, frail and almost insignificant. Yet, by being able to co-operate with each other, the colony of ants demonstrates complex behavior. One of these is the ability to find the closest route to a food source or some other interesting landmark. This is done by laying down special chemicals called "pheromones." As more ants use a particular trail, the pheromone concentration on it increases, hence attracting more ants. In our example, an artificial ant is placed randomly in each city and, during each iteration, chooses the next city to go to. This choice is governed by the following formula, as described by Dorigo (1997):
Each ant located at city i hops to a city j selected among the cities that have not yet been visited according to the probability:
where:
is the probability that ant k in city i will go to city j.
is the set of cities that have not yet been visited by ant k in city i.
is the relative importance of the pheromone trail.
is the relative importance of the distance between cities.
Therefore the probability that a city is chosen is a function of how close the city is and how much pheromone already exists on that trail. It is further possible to determine which of these has a larger weight by tweaking with the and parameters. Once a tour has been completed (i.e. each city has been visited exactly once by the ant), pheromone evaporation the edges is calculated. Then each ant deposits pheromone on the complete tour by a quantity which is calculated from the following formula (Dorigo 1991):
if
, where:
multiplies the pheromone concentration on the edge between cities i and j by p(
RHO), which is called the "evaporation constant." This value can be set between 0 and 1. The pheromone evaporates more rapidly for lower values. is the amount of pheromone an ant k deposits on an edge, as defined by
which is the length of the tour created by this ant. Intuitively, short tours will result in higher levels of pheromone deposited on the edges.
At the heart of the application lies the two algorithms which are used to solve the traveling salesman problem. Each algorithm is brought into a view by selecting it from a toolbar of the main frame. A view is a window which is presented to the user. The genetic algorithm view is shown below:
Each view is divided into two horizontal sections.
Each button is self-explanatory. The Start button is used to start the application and the Stop button is used to stop the simulation. The Reset button resets the simulation while the Step button is used to step through the simulation. The text information shows the following information:
Graph of the above information:
The blue line is a plot of Epoch vs. the shortest distance found by the algorithm to date. The green line represents the shortest possible tour (optimal solution). When the two lines converge, a solution has been found.
I choose C++ as the language to program this application in. A compiled program will always be faster than an interpreted program. Both of the algorithms are computationally quite expensive and so is the process of visualization. Potentially C would be faster still, but by choosing this language the benefits of object orientation are lost. Other possible languages were Delphi, Visual Basic and C#, but I don�t have enough experience in any of these languages to attempt a project of this size. I chose to use the Microsoft Foundation Classes (MFC) application framework. The benefits of using this are:
One of the main disadvantages is that it takes a long time to understand the complexity of the underlying model. Also, once the developer tries to move away from wizard-generated code, it is very easy to get lost in the code with the debugger. The project was developed and compiled using Visual Studio .NET Academic Version 7.1.3088. The code used to implement the genetic algorithm is based on the work of Mat Buckland (2002) in his book "AI Techniques for Game Programming." The code for the ACO algorithm is partially based on the work of M Jones (2003) in his book "AI Application Programming." Several other code sources were also used:
CSideBannerWnd is used to display the panel on the left-hand side of the window.Initially I thought that the document would hold information common to both algorithms, including the number of cities, city position and shortest possible tour. However, as the project progressed, I realized that each algorithm is sufficiently different to warrant its own data structure. What was needed was a way to switch between different views (derived from a common ancestor).
�Sometimes the way a document is being visualized needs to be significantly changed. For example, in PowerPoint, you can see the slides in a WYSIWYG form or view only the text in a text edit window. In the MFC world, one can find an amazingly large quantity of programs that implement this behavior, defining one CView descendant and making it responsible for all visualization changes. This path has several disadvantages:
CView descendant or nothing. The author then goes on to explain how this is possible and gives an example of code that defines different Views and how to switch between them.
The following sequence diagram shows the basic interaction between the CACOView and CAntSystem classes.
The following sequence diagram shows the basic interaction between the CGAView and CGASystem classes.
I next turned my attention to the ACO and looked at how certain parameters in the algorithm affect performance.
Parameters used here are City No: 40, alpha: 1, beta: 1 and rho: 0.6. These findings suggest that it might be possible to write a genetic algorithm that would optimize the parameters. This might make an interesting project somewhere down the track.
This has been both a rewarding and difficult project. I previously had little knowledge of MFC programming and thought that it would be relatively easy to master. It turns out that I was wrong and it took me a very long time to get the program up and running. Despite the steep learning curve, I was thrilled to actually produce a working program and learned a lot along the way about genetic algorithms and ant colony optimization algorithms. I am very grateful for all the people who have contributed to this fantastic site. I have found many of the articles very useful in this project. Keep up all the good work, guys.
| You must Sign In to use this message board. | |||||
|
|||||
|
|||||
