ANT COLONY OPTIMIZATION
By using Ant Colony Optimization (ACO) and swarm intelligence the best/optimal/shortest path can be found for solving computational problems. There are many methods to solve computational problems, but taking the optimal and shortest method is very helpful and consumes less time. The shortest-path algorithm calculates the shortest path from a start node to each node of a connected graph. Marco Dorigo in his ph. D introduced ant colony optimization (ACO) in 1992. Ant-colony optimization is one of the probabilistic techniques for finding optimal paths. Ants are tiny insects which live in colonies. Ants roam around their colonies in search of food and deposit an organic substance called pheromone (a chemical substance i.e., carriers of information between individuals within the species) on the ground. Other ants reach their destination with the smell of pheromones, however the strength of pheromone will reduce due to the process of evaporation. Most ants follow the path of greater pheromone levels. When ants take different paths to reach a destination, the pheromone level will be higher on the shortest path. Depending on the rate of evaporation and the frequency with which the ants pass there, the path, initially chosen at random, starts to be known as the best path to food. The pheromone imprint grows stronger over time and cannot be overcome by the evaporation event.The applications of ant colony optimization are used to examine potential paths on the graphs in order to solve graph problems.
Code Description & Execution for Ant Colony Optimization
There are three main phases :
- Phase 1 : The calculation of probability of each route
The above formula is used to calculate the pheromone between the two nodes. The result of this equation will inform the probability that a particular route analysed will have to be chosen.
- Phase 2: Choosing the route based on probability results.
To choose the route roulette mechanism is used as it generates random routes. But the results of the probability calculations obtained in phase one are not ignored.
The above formula is used to add the cumulative sum of each visit made by an ant to the available routes. Here the delta ‘Δ’ is used to know the amount of pheromone released by an ant between ‘i’ and ‘j’ points. ‘lk’ is the amount of pheromone that should be deposited. The above formula will suffer loss due to evaporation
The higher the pheromone the lower the route being chosen again so to generate the inverse effect the alpha exponent used in the pheromone process was defined as negative. After calculating the probabilities, the values are informed to the random choice system.
- Phase 3 :According to the information, the definition of fitness is the key to selecting the best option.
There are five main codes for execution of project :
- aco.m : this is the ACO algorithm code
- createColony.m : it is used to create routes based on pheromone amount
- fittnessFunction.m : this code is used to choose the best path
- main.m : this is the main file which is to be runned
- rouletteWheel.m : used to generate random routes
Note: Matlab file or codes are saved in .m and .mat format
(Don’t worry if you don’t know the basics of the MATLAB Click here to watch our video about MATLAB software.
Steps to Execute the Code
- Download the zip file of this project and unzip it.
- Open matlab and click on the ‘browse for folder’ icon as shown below
3. A pop up window appears from which we can select the folder
4. Add all .m files in that folder as shown below.
5. Run aco.m file, a blank graph will pop up
6. Finally run the main.m file. The code will be executed and the output will be displayed.
Result For Ant Colony Optimization
When aco.m file is executed a blank graph will be displayed.
When the main.m file is executed then different optimal paths will be plotted on the graphs.
The shortest path’s points will be highlighted. The way to reach from source to destination will be estimated.
- There is no need to run createColony.m, fitnessFunction.m, rouletteWheel.m files as they are the functions of aco.m file and main.m file.