A Framework for Parallel Ant Colony Optimization | Jin Wang
| | Abstract | With this thesis, we implemented a parallel ant colony optimization framework in Java and studied its performance by a series of experiments. The thesis consists of five chapters.
The first chapter contains some background knowledge. Beginning with the origin of the evolutionary algorithm (EA), an existent island model, the parallel (1+1) EA with migration, was introduced. Then the ant colony optimization (ACO) and the MAX-MIN ant system (MMAS) which is an instance of ACO are covered.
In the second chapter, the detailed parallel ant colony optimization, namely the MMAS* island model, is defined after introducing the MMAS* algorithm and a general parallel ACO algorithm with migration. Then the migration topologies and benchmark problems which will be used in MMAS* island algorithm is presented.
The third chapter shows the implementation of the whole algorithm in Java. The implementation contains a graphical user interface (GUI) which allows the user to set common parameters including all topologies and problems mentioned in second chapter. The whole process of the algorithm can be observed in a graphical representation. In addition, it is also possible to set up and run experiments. The program will collect statistics from the result automatically.
The fourth chapter deals with the experiments regarding the performance of the parallel ACO. The first two experiments are on the LEADINGONESLEADINGZEROS problem which is a synthetic problem that designed to show the benefit of parallel evolution strategies. The experimental result shows that it is likely that low evaporation rate has a same effect with low migration interval on the success rate. The third experiment is an attempt of different evaporation rates on different islands on ONEMAX problem. It shows that the disadvantage on late generations ruins the advantage on early generations.
Finally, the conclusion chapter gives a summary of the whole study. | | Type | Master's thesis [Academic thesis] | | Year | 2013 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science / DTU Co | | Address | Matematiktorvet, Building 303B, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | M.Sc.-2013-66 | | Note | DTU supervisor: Carsten Witt, cawi@dtu.dk, DTU Compute | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|