Ant colony optimization
Introduction:
Ant colony optimization (ACO) is a metaheuristic that belongs to the research field, swarm intelligence, which studies algorithms motivated by the observation of swarms. ACO was proposed by Dorigo and colleagues [1,3] for the resolution of hard combinatorial optimization problems.
In real life, swarms members cooperate without any central control or any direct communication between one another. These swarm algorithms consist of simple individuals that collaborate through self-organization.
Biological phenomenon:
The investigation of the behavior of the insects was first started by Pierre-Paul Grasse, a French entomologist during the decades of 1940 and 1950. By observing termites he found out[3] that they reacted to certain signals that make the termites change their behavior. This so called stimulus provokes reactions on both the termite that produces it and the rest of the swarm. This indirect type of communication was named stigmergy [2]. This term is derived from the Greek words stigma (mark, sign) and ergon (work, action) and captures the notion that an agent’s actions leave signs in the environment, signs that it and other agents sense and that determine and incite their subsequent actions [1].
In colonies of ants it can be observed examples of stigmergy. In many species of ants, they drop an essence called pheromone on the ground when they come back to the nest from a source of food. This pheromone can be smelled by others ants and therefore, it can influence on them when it comes to choose the path. The ants tend to follow those paths with stronger concentrations of pheromones. These pheromone tracks that are formed by the pheromones laid on the ground, help the ants to locate good sources of food.
Deneubourg et al. [8] carried out an experiment called “binary bridge experiment” to study this pheromone dropping. The experiment consisted of an ant nest connected to a source of food by two equal length paths. Initially, there are no pheromones deposited on the paths and the ants are free to choose one of them. After some time, due to random variations there will be a heavier concentration of pheromones on one the paths and, since the ants prefer to follow the trail with more pheromones, the path with stronger concentration of pheromones will attract more ants. Consequently, the colony of ants converges towards to follow one of the paths.
In another similar experiment performed by Goss et al. [9] where the paths aren’t equally long, else one of them is notably longer, the ants that choose by chance the shorter path, go back to nest earlier and hence, pheromones are dropping quicker on this path than the other. Probabilistically, the shorter path is followed by more ants and the convergence tends towards it. By probabilistically, it means that the path with larger amount of pheromones is more likely to be chosen as the probability of an ant of following a path lies on both randomness and pheromones.
The next section explains how the optimization were created from the study of the results of these experiments
Development of the ACO algorithms:
Basing on these results, Goss et al. [9] created a model to explain the behavior of the ants in the “binary bridge experiment”. Calling t to the units of time passed since the beginning of the experiment, m1 to the ants that chose the first path and m2 to the ants that chose the second one, the probability for the (n+1)th ant to choose the first path can be set by:
p1(n+1) = (n1 + k)h
(n1 + k)h + (n2 + k)h
Where k and h are needed to fit the experimental data. The probability that the same ant (n+1)th follows the second path is:
p2(n+1) = 1
p1(n+1)
The design of artificial ants can be drawn from this model to solve optimization problems that are defined along the same lines. Whereas real ants drop pheromones on the way back to the nest when they find food, artificial ants can simulate this pheromones lying by modifying certain variables associated to the optimization problem and having local access to them.
ACO’s basic idea is very close to the biological inspiration and hence, these two types of ants, real and artificial, have many features in common. Both colonies are composed by a group of individuals that jointly collaborate to achieve a specific goal.
In the case of real ants their main objective is to find food, whereas in the case of artificial ones it’s to find a good solution to a specific optimization problem. In both cases, an individual ant is capable of finding food although only through cooperation they can find a good solution/source of food.
The most important differences between real and artificial ants are:
The world where they move/live. Artificial ants live in a discrete world and move sequentially through the states of the problem
Sometimes, artificial ants don’t drop pheromones unless they have found a solution
There exist some implementations of artificial ants that use extra methods to complete the solution and which are not carried out by real ones.
The Metaheuristic
Before going through the description of the ACO metaheuristic, the next section will explain a very basic algorithm based on ants to exemplify the basic behavior of the ACO metaheuristic.
A Simple ACO algorithm
Similarly to real ants, the main task of an artificial ant is o find the shortest path between two nodes on a graph that represents the optimization problem.
Let G = (V,E) be a connected graph with v = |V| vertices. S-ACO can be used to find the shortest path between two vertices on the graph G, where the solution is a path that connects the source s with the destination d and the length of the path is the number of vertices (hops) between them.
Each edge (i,j) carries a variable tij that represents the amount of pheromone on that edge which is proportional to the quality of the solution to build.
The ants build their individual solutions step by step by deciding stochastically at each vertex where to move next and basing this decision on the local information that every vertex keeps.
The decision rule that determines the probability to go from the vertex i to the vertex j can be modeled as follows:
tij if j Î Ni
P kij =
0 if j ÏNi
Where k signifies the ant, i and j the source and destination respectively, and Ni represents the set of neighbors of i.
When an ant reaches the destination, it starts building the solution in which the ant drops pheromones all along the complete path from the source to the destination as shown:
tij (t) = tij (t) + Dt
Where Dt stands for a constant amount of pheromone. By this rule, an ant using the edge connecting vertices i and j raises the probability of that edge to be chosen by future ants.
To avoid local optimums, which means a convergence of all the ants towards this path, a “pheromone evaporation” rule is applied. In reality this evaporation takes longer and doesn’t affect the search significantly however, in the case of the artificial ants, this evaporation plays a more important role since it is carried out at each iteration of the algorithm. This evaporation is exponential and performed in a simple way:
t = (1 - r)t r Î (0,1]
When the graph becomes more complex, and there are several trails from the source to the destination, the behavior of the ants become less stable and the value given to the parameters becomes critical. It is because of that, that S-ACO should be taken as a didactic example as due to its simplicity it has limitations. In the next sections it is presented other types of algorithms that derivate from S-ACO. These algorithms are enriched with additional capabilities in order to meet complex problems difficulties, for instance:
The amount of pheromone could be proportional to the quality of the solution
The pheromones could be produced by the ant so it can lead the other ants search
To use local the information of the vertices
To give some sort of memory to the ants so they can, for example, avoid visiting the same vertex more than once, or cycles.
The ACO metaheuristic
Artificial ants used in ACO algorithms construct the solution stochastically by adding elements to partial solutions. When building the solution, they take into account the following information:
Heuristics on the problem, if existing
Pheromones trails that are dynamically updated that show the acquired search experience of the ants.
Thanks to the stochastic element, ants are able to explore a much larger number of solutions whereas the heuristic factor can guide the ants towards the better solutions.
Also, the ants’ search experience can influence the construction of the solution in future iterations.
The ACO algorithms are instances of the ACO metaheuristic that can be explained by the next algorithm. This algorithm has been made out from discrete optimization problems models.
1: procedure ACO_metaheuristic()
2: while (termination_criterion_not_satisfied)
3: schedule_activities
4: ants_generation_and_activity();
5: pheromone_evaporation();
6: daemon_actions(); {optional}
7: end_schedule_activities
8: end while
9: end procedure
1: procedure ants_generation_and_activity()
2: while (available_resources)
3: schedule_the_creation_of_a_new_ant();
4: new_active_ant();
5: end while
6: end procedure
1: procedure new_active_ant() {ant lifecycle}
2: initialilze_ant();
3: M = update_ant_memory();
4: while (current_state ¹ target_state)
5: A = read_local_ant_routing_table();
6: P = compute_transition_probabilitites (A, M,Ω);
7: next_state = apply_ant_decision_ploicy(P, Ω);
8: move_to_next_state(next_state);
if (online-step-by-step_pheromone_update)
9: deposit_pheromone_on_the_visited_edge();
10: update_ant-routing_table();
end if
11: M = update_internal_state();
12: end while
if (online_delayed_pheromone_update)
13: foreach visited_edge Î Y do
14: deposit_pheromone_on_the_visited_edge();
15: update_ant_routing_table();
16: end foreach
end if
17: die();
18: end procedure
ACO metaheuristic in pseudocode
Where:
M = memory of the ant
,A, = local data structure
P = set of probabilities calculated
Ω, = finite set of constraints
Y = solution found
Main types of ACO
Although there are several variants of ACO in the literature, only the three most successful ones will be presented. The first implementation was Ant System (AS) followed by its first successors, MAX─MIN Ant System (MMAS) and Ant Colony System (ACS).
Ant System
AS was the first ACO algorithm and was developed by Dorigo, Maniezzo and Colorni in 1991. In fact, AS was originally a set of three algorithms, called ant-cycle, ant-density and ant-quantity., proposed in Dorigo’s doctoral dissertation[29]. In ant-density and ant-cycle, the pheromones are update while the ants construct their solutions with the difference that in ant-density , the amount of pheromone deposited is constant whereas in the ant-quantity depends on the desirability of the transition heuristics hij. The updating of the pheromones in ant-cycle is carried out a posteriori, that is, after the settlement was complete. This latter variant of AS was to obtain better results and hence, it is known as AS.
The main characteristic of AS is that pheromones are updated by all the ants that have finished the tour, as follows:
tij¬(1-r) · tij + åmk=1 Dtijk
Where r is the evaluation rate, m is the number of ants and Dtijk is the quantity of pheromone deposited by the k-th ant.
When the ant has to choose its next move, the decision is made probabilistically according to: include formula (3.1) Maria Arsuaga thesis, page 20.
|tij|a · |hij |b
Pijk = å
Where Nik is the set of neighbors of the kth ant when it is on the node i. The parameters a and b Î Â control the importance of the pheromones versus the heuristic information.
Regarding the parameters a and b, their function is: If a = 0, the ant will focus more on the heuristic information, whereas if b = 0 the ant will base its decision exclusively on traces of pheromones.
MAX─MIN Ant System
Stützle and Hoos [16], introduced this variant of ACO that is an improvement of the original AS. It presents a number of changes where the most important are the following:
The best ant is the only one that updates pheromones
The amount of pheromones that can be deposited is limited between a minimum and a maximum value.
The update pheromones equation from the Ant-System (put number of equation) becomes:
Equation (25.10) from an introduction to ant colony optimization, page 10
Where Dtijbest is the pheromone update value.
As said above, the possible values of pheromones are limited to the rank [tmin,tmax] hence ,the probability of a deadlock in the algorithm drops in order to give a probability, yet small, to each edge, if it’s chosen.
Unlike the AS where the edges are initially set with small traces of pheromones, in this algorithm, these initial values are an estimation of the maximum value allowed to a trail.
MMAS sometimes uses re-initialization of the pheromones values on the trails in order to support the exploration of new solutions
Ant Colony System
There are three main aspects that differs ACS (Dorigo and Gambardella,1997) with the Ant-System.
The transition rule offers a direct way to balance the exploration of new paths and exploitation of the accumulated knowledge about the problem.
The global updating rule is applied only to those edges that belong to the best ant trail
A local pheromone updating rule is applied while ants are constructing their solutions.
The above mentioned transition rule is called proportional rule pseudorandom where the next node is chosen randomly by the following probability distribution:
If (q <= q0)
Equation (3.5) Maria Arsuaga page 22
else if (q > q0 )
Equation (3.6) Maria Arsuaga page 22
Where q is a random number uniformly distributed in [0..1], q0 Î[0..1] . This algorithm helps transitions to go towards nodes connected by short edges with large number of pheromones. The parameter q0 establishes the importance of exploitation versus exploration. When deciding the next node, the ant creates a random number Î[0..1].
If (q <= q0) the ant chooses the best edge, exploiting the knowledge available. However, when it’s otherwise, the algorithm behaves like Ant-System (biased exploration).
The pheromones updating is performed only by the globally best ant, that is, the ant the constructed the shortest path from the beginning of the experiment. This choice, along with the pseudo random proportional rule is supposed to make the search more directed.
The global updating is done after all the ants have completed their tours according to the updating rule:
t(i,j)¬(1-a)×t(i,j)+a×Dt(i,j)
In this equation, a represents the pheromone decay parameter .
In the local updating rule, ants visit edges and change their pheromone level according to the equation:
t(i,j)¬(1-r)×t(i,j)+r×D t(i,j)
Where r Î(0..1) is a parameter.
In these three implementations of ACO, it is of vital importance to choose wisely the parameters a and b, that determines whether the ant will follow only pheromones, heuristics or a combination of both. For instance, in the case of the ACS algorithm, experiments have shown that when b = 0, that is to base the decision on the pheromones, the performance worsens. Also, if the ants neither deposit pheromones nor sense them, the performance is significantly poorer.
Ants, pheromones and solutions evaluation
Some of the most significant aspects of ACO algorithms will be discussed within this section, particularly the evaluation of the solutions generated by ants, the way these solutions are used to direct the ant’s search and the importance of using a colony of ants.
Implicit and explicit solution evaluation. There are two mechanisms to generate solutions in ACO algorithms by ants to provide feedback to lead the search of the forthcoming ants. The first one, which is common to all ACO algorithms, consists of an explicit solution evaluation. In this case, the amount pheromones deposited it’s decided according to the quality of the solution generated. The second one is a sort of implicit solution evaluation. In this case, ants exploit the effect of the differential path length (DPL), described as: When an ant chooses a shorter path, it will deposit pheromones earlier than others that choose longer paths and will bias the search of the next ants
The most natural way to implement ACO algorithms in combinatorial optimization algorithms is by ant colonies of synchronized ants, which means that the ants build their solutions by synchronously adding elements to this solution. It is possible, in principle to have asynchronous ants but the problem is the computational inefficiencies that the computational overheads takes to have independent and asynchronous ants may worsen the gains due to the exploitation of the DPL effect.
Explicit solution evaluation and pheromone laying. A problem that arises in a problem where the characteristics of itself change unpredictably when building the solution is that there isn’t exist an easy way to estimate the quality of the solution and consequently how much pheromones the ants should deposit. A possible solution could be to program the ants to find out, in online mode, the network status, which can be used to evaluate the quality of the solutions found
Number of ants. This parameter that, most of the times, has to be set experimentally. Is it worth it to use a colony of ants instead of just one ant?. One ant is capable of building a solution but, taking into consideration the efficiency, it is more desirable to use a colony of ants. In distribution problems specially, because the differential length effect, it’s only arisen when using a colony of ants.
However, in the case of optimization problems, to use n ants to build y solutions is the same than to use one ant that builds n·y solutions. Nevertheless, it’s been proved in experiments that in optimization problems, the use of a colony of ants instead of only one ant, increase the performance.
References:
[1] Dorigo, M., Maniezzo, V., and Colorni, A., Positive Feedback as a Search
Strategy, Technical report 91-016, Dipartimento di Elettronica, Politecnico
di Milano, Italy, 1991.
"Definitions of stigmergy. " From a special Issue of Artificial Life on Stigmergy. Volume 5, Issue 2 / Spring 1999. http://www.stigmergicsystems.com/stig_v1/stigrefs/article1.html
Grass¶e, P.-P., La reconstruction du nid et les coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp. La th¶eorie de la stig-
mergie: essai d'interpr¶etation du comportement des termites constructeurs,
Insectes Sociaux, 6, 41, 1959.
[3] Grass¶e, P.-P., Recherches sur la biologie des termites champignonnistes
(Macrotermitina), Ann. Sc. Nat., Zool. Biol. anim., 6, 97, 1944.
[8] Deneubourg, J.-L., Aron, S., Goss, S., and Pasteels, J.-M., The self-
organizing exploratory pattern of the Argentine ant, J. Insect Behav., 3,
159, 1990.
[9] Goss, S., Aron, S., Deneubourg, J.-L., and Pasteels, J.-M., Self-organized
shortcuts in the Argentine ant, Naturwissenschaften, 76, 579, 1989.
[10] Pasteels, J.M., Deneubourg, J.-L., and
[29] M.Dorigo, Optimization, learning and Natural Algorithms (in Italian). PhD thesis, Dipartamento di Elettronica, Politecnico di Milano, Italy, 1992. pp 140.
[16] StÄutzle, T. and Hoos, H.H., MAX-MIN Ant System, Future Generation
Comput. Syst., 16(8), 889, 2000.
Mention An introduction to ant colony optimization
The ant colony optimization meta-heuristic
Aco algorithms, applications and advances
We provide a professional essay writing service that thousands of our customers use as an effective way of improving their grades, improving their research and saving them lots of time.
