Ant Colony Optimization
Ant Colony Optimization (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.
Also, ACO is a meta-heuristic approach. A meta-heuristic is a higher-level procedure or heuristic designed to find, generate, or select heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete or imperfect information or limited computation capacity.
HISTORY
In 1992, Marco Dorigo proposed the first version of ACO, which searches for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food.
STEPS
1. A trail of ants goes from their colony in random directions searching for a food source.
2. While walking, ant leaves "Pheromone" along with its path.
3. When finding a food, an ant comes back to the colony, but it walks in the path with higher pheromone level.
4. The probabilities of other paths being chosen will converge to the strangest reinforced path.
FORMAL REPRESENTATION
A model P = (S, Ω, f)
S is a search space defined over a finite set of discrete decision variables;
Ω is a set of constraints among the variables; and
f: S→R+0 is an objective function to be minimized (as maximizing over f is the same as minimizing over −f, every COP can be described as a minimization problem).
Algorithm (pseudo code):
Set parameters, initialize pheromone trails SCHEDULE_ACTIVITIES ConstructAntSolutions DaemonActions {optional} UpdatePheromones END_SCHEDULE_ACTIVITIES
Example:
One of the most important problems that can be solved using ACO is the Traveling Salesperson Problem (TSP).
Problem Statement:
Given a set of cities and the distances between each pair of cities, what is the shortest possible tour that visits each city exactly once, and returns to the starting city?
Here is an excellent Jupyter Notebook contains the implementations of different techniques by Peter Norvig
Applications:
NP-hard combinatorial optimization problems
Classification
Games
Routing in telecommunication networks