12,625,402 members (36,186 online)
alternative version

546K views
202 bookmarked
Posted

# Genetic and Ant Colony Optimization Algorithms

, 26 Sep 2006 CPOL
 Rate this:
Genetic and Ant Colony Optimization Algorithms

## Introduction

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).

### Traveling Salesman Problem

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.

## Background

### The Algorithms Explained

#### Genetic Algorithm

The algorithm consists of the following fundamental steps:

1. Initialization: chromosomes are randomly created. At this point, it is very important that the population is diverse. Otherwise, the algorithm may not produce good solutions.
2. Evaluation: each chromosome is rated on how well the chromosome solves the problem at hand. A fitness value is assigned to each chromosome.
3. Selection: the fittest chromosomes are selected for propagation into the future generation based on how fit they are.
4. Recombination: individual chromosomes and pairs of chromosomes are recombined, modified and then put back into the population.

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: 35x21x4```

The following mapping is established.

```3 -> 2

4 -> 1```

Now 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: 25314```

Second iteration (mapping 4 with 1):

```Child 1: 43215

Child 2: 25341```

The 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)

#### Ant Algorithm

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(<city><place>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.

## Quick User Manual

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.

1. The top half shows a graphical view of the current performance of each algorithm.
2. The bottom half shows a graph of the current solution charted against the best know solution. In most demonstrations of the TSP, cities are placed at random. I chose to distribute the cities in a circular fashion. This allows an easy way to calculate the shortest path among the cities, as well as visually assess how far away the algorithm is from the optimal solution.

### A Simulation is Controlled by the Control Buttons

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:

• Epoch represents the number of times the simulation has run through each cycle of the simulation.
• Best So Far is the shortest tour so far.
• Best Possible represents the optimal solution to the current tour.
• Elapsed Time is the time spent inside the algorithm. This excludes the time spent "drawing" the solution to the screen. See below for further 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.

## Design and Implementation

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:

• Application framework applications are small and fast
• The Visual C++ tools reduce coding drudgery
• The framework is rich in features

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:

• CMemDC is a class used for double buffering. This is a technique used in computer animation to avoid screen flicker, which was a major problem due to the fact that the screen is updated (repainted) several times each second. The technique used here is to create an off-screen buffer to which the image is drawn. The final image is then copied to the screen.
• CAutoFont is a class used for font manipulation.
• CChart is a class used for charting.
• CPerfTimer is used for timing.
• `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:

1. Big, difficult to manage class definition file.
2. Diminished reusability: you could reuse one big `CView` descendant or nothing.
3. Hard to maintain (what if you want to modify or add a new "look" to the document?).
4. Wasted memory: some variables (objects) will exist in memory and won’t be used.” (Lodos,1999)

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.

## Performance

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.

## Conclusion

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.

## References

• Buckland, M., 2002, AI Techniques for Game Developers, Premier Press, United States of America.
• Dorigo ,M., & Gambardella, L. M (1997) Ant colonies for the traveling salesman problem. BioSystems, 43 ,73-81
• Jearakul, C.,1999 2D and 3D Watefall Chart Control, [Online], Available: http:/www.codeguru.com.controls/Waterfall.shtml [Accessed 3/9/2003]
• Jones, M., 2003, AI Application Programming, Publisher: David Pallali.
• Lodos, J, 1999 Replacing a view in a doc-view application, [Online], Available: http:/www.codeguru.com/doc_view/ReplacingView.shtml [Accessed 2/9/2003]
• Nordmeyer, J., Automatic Font Handling Class, [Online], Available: http://www.codeproject.com/gdi/autofont.asp [Accessed 28/10/2003]
• Prosise, J, 1999,Programming Windows with MFC, 2nd Edition, Microsoft Press, Redmond Washington
• Rule,K..1999 Flicker Free Drawing in MFC, [Online], Available: http:/www.codeproject.com/gdi/flickerfree.asp [Accessed 24/9/2003]
• Wyant,D., 2002, CPerfTimer timer class, [Online], Available: http:/www.codeproject.com/datetime/perftimer.asp [Accessed 24/9/2003]

## Share

 Australia
No Biography provided

## You may also be interested in...

 First PrevNext
 Matlab source code for GA and ACO with simple c++ for job shop scheduling Member 1263226526-Jul-16 21:39 Member 12632265 26-Jul-16 21:39
 About Writing Ant Colony Algorithm Member 1245297911-Apr-16 19:43 Member 12452979 11-Apr-16 19:43
 ant colony optimization for an assignment problem Member 1051972829-May-15 6:32 Member 10519728 29-May-15 6:32
 Re: ant colony optimization for an assignment problem Member 105197284-Jul-15 15:54 Member 10519728 4-Jul-15 15:54
 ant colony optimization for query plan generation Member 1148900727-May-15 4:26 Member 11489007 27-May-15 4:26
 Ant colony implementation on resource constrained project scheduling Member 1122091520-May-15 22:13 Member 11220915 20-May-15 22:13
 how do i solve the scheduling Problem Using Aco Member 1146218418-Feb-15 11:35 Member 11462184 18-Feb-15 11:35
 Ant colony optimization in Matlab Member 112896255-Dec-14 10:49 Member 11289625 5-Dec-14 10:49
 Ant Colony Optimisation Code Member 1125266921-Nov-14 1:16 Member 11252669 21-Nov-14 1:16
 help please Member 1092676918-Jul-14 14:23 Member 10926769 18-Jul-14 14:23
 project Member 1023477327-Aug-13 0:44 Member 10234773 27-Aug-13 0:44
 Help for TSP problem and code Marija Ivanovic27-Jun-13 1:53 Marija Ivanovic 27-Jun-13 1:53
 coding for matlab Member 1000708623-Apr-13 1:40 Member 10007086 23-Apr-13 1:40
 Help me, please Member 1000619822-Apr-13 19:19 Member 10006198 22-Apr-13 19:19
 Help... ahora719-Feb-13 0:46 ahora7 19-Feb-13 0:46
 help for doing project shantha0829-Dec-12 22:43 shantha08 29-Dec-12 22:43
 sir im doing project using Artificial Bee Colony algorithm to maximize the lifetime for heterogeneous wireless sensor network and i need to prove ABC(Artificial Bee Colony) is bettter than ACO(Ant Colony Optimization)help me plz
 my opinion shidifen13-May-12 23:45 shidifen 13-May-12 23:45
 ACO udhayakuamr6-Apr-12 7:49 udhayakuamr 6-Apr-12 7:49
 ant colony optimization in disk scheduling Member 876510827-Mar-12 9:07 Member 8765108 27-Mar-12 9:07
 ant colony optimization technique in ad hoc network abhishek anand srivastava17-Feb-12 5:30 abhishek anand srivastava 17-Feb-12 5:30
 pls help me sir sandeepsany446-Jan-12 2:48 sandeepsany44 6-Jan-12 2:48
 hello sir ,regarding my project need ur help prashant gosavi24-Dec-11 3:23 prashant gosavi 24-Dec-11 3:23
 c code for my university project pushkarcdacnoida1123-Oct-11 22:30 pushkarcdacnoida11 23-Oct-11 22:30
 Master Zen napsterboyz29-Sep-11 2:24 napsterboyz 29-Sep-11 2:24
 bee colony genetic Algorithms scheduling multiprocessor e_live19-Sep-11 23:51 e_live 19-Sep-11 23:51
 please/// Help supasasi26-Aug-11 3:46 supasasi 26-Aug-11 3:46
 Re: source code for ACO algorithm and local search algorithm in java sailish17-Aug-11 5:47 sailish 17-Aug-11 5:47
 ant colony optimization code engriham21-Jul-11 6:53 engriham 21-Jul-11 6:53
 ant colony optimization hgzel7-Jul-11 10:11 hgzel 7-Jul-11 10:11
 ant colony matlab code hossein_6430-Apr-11 21:58 hossein_64 30-Apr-11 21:58
 ACO Member 781984224-Apr-11 3:54 Member 7819842 24-Apr-11 3:54
 the TSP solved here has been made some premise wxl24life31-Mar-11 16:35 wxl24life 31-Mar-11 16:35
 C# source code for ACO algorithm shahab zarei26-Feb-11 4:36 shahab zarei 26-Feb-11 4:36
 about Project saNdEep809915424222-Feb-11 8:07 saNdEep8099154242 22-Feb-11 8:07
 Ant Colony Optimization to solve the Shortest Path Problem (SPP) Yuni Ardita Sari Dewi19-Feb-11 22:24 Yuni Ardita Sari Dewi 19-Feb-11 22:24
 Implementation of routing algorithm using zone based ant colony optimization algorithm Shibhu200213-Feb-11 18:48 Shibhu2002 13-Feb-11 18:48
 Help me Donia suleman25-Jan-11 23:21 Donia suleman 25-Jan-11 23:21
 debug cann`t pass through PreCreateWindow function doityth77719-Dec-10 17:06 doityth777 19-Dec-10 17:06
 Dear respected sir bijay mahato8-Dec-10 19:30 bijay mahato 8-Dec-10 19:30
 ACO naghikhani19-Sep-10 21:42 naghikhani 19-Sep-10 21:42
 request for code bhuvanes10-Sep-10 16:05 bhuvanes 10-Sep-10 16:05
 ANT COLONY SOURCE CODE atikah.razi11-Aug-10 6:38 atikah.razi 11-Aug-10 6:38
 solving travelling salesman problem by using ant colony optimization amirah 'aisha13-Jul-10 20:42 amirah 'aisha 13-Jul-10 20:42
 ACO matlab sorce code elnaz65d11-Jul-10 21:19 elnaz65d 11-Jul-10 21:19
 Re: ACO matlab sorce code atikah.razi11-Aug-10 6:40 atikah.razi 11-Aug-10 6:40
 MMAS or HCF soheilasharifi5-Jun-10 21:29 soheilasharifi 5-Jun-10 21:29
 Last Visit: 31-Dec-99 19:00     Last Update: 5-Dec-16 2:07 Refresh 1234 Next »