The main task of each artificial ant, similarly to their natural counterparts, is to find a shortest path
between a pair of nodes on a graph on which the problem representation is suitably mapped.
Let G = (N , E) be a connected graph with n=|N| nodes. The simple ant colony optimization algoirhtm can be used to find a solution to the shortest path problem defined on the graph G, where a solution is a path on the graph connecting a source node s to a destination node d, and the path length is given by the number of hopes in the path.
To each arc ( i , j ) of the graph is associated a variable Tij called artificial pheromone trail.
Pheromone trails are read and written by ants. The amount (intensity) of pheromone trail is proportional to the utility, as estimated by the ants, of using that are to build good solutions.
Each ant applies a step-by-step constructive decision policy to build problem's solutions. At each node local information, maintained on the node itself and/or on its outgoing arcs, is used in a stochastic way to decide the next node to move to.
The decision rule of an ant k located in node i uses the pheromone trails Tij to compute the probability with which it should choose node j e Ni as the next node to move to where Ni is the set of one-step neighbors of node i:
P1
Pij = Tij if j e Ni
= 0 if j# Ni
A the beginning of the search process, a same small amount of pheromone To is assigned to all arcs.
While building a solution ants deposit pheromone information as the arcs they use. In aco ants deposit a constant amount of delta T of pheromone.
Consider an ant that at time t moves from node i to node j. It will change the pheromone value Tij as follows:
Tij (t) <------ Tij(t) + delta T
By this rule, which simulates real ants pheromone depositing an arc (i , j), an ant using the arc connecting node i to node j increases the probability that ants will use the same arc in the future. As in the case of real ants, auto catalysts and differential path length are at work to favor the emergence of shots paths.
To avoid a quick convergence of all the ants towards a sub optimal path, an exploration mechanism is added : similarly to real pheromone trails, artificial pheromone trails "evaporate".
In this way pheromone intensity decreases automatically, favoring the exploration of different arcs during the whole search process. The evaporation is carried out in a simple way, T <--------- (1 - p) T , p e (0 ,1] at each iteration of the algorithm.
Preliminary experiments run with ACO using a simple graph modeling the experimental apparatus P1 have shown that the algorithm effectively finds the shortest path between the simulated aest and food services.Experimets have also shown that if we increase the complexity of the search graph, for example by connecting the nest to the food sources by means of morethan two possible paths, the behaviour of the algorithm tends to become less stable and the value given to parameters becomes critical.
ACO must therefore be taken for what it is: a didactic example that, because of its simplicity, has a number of limitations.
Another important point is that it should be desirable to enlarge the class of problems that can be attacked by aco algorithms.
ACO can be applied only to shortest path problems without additional constraints: if we want to use it to find a shortest hamiltonian path on a graph, that is , a path which visits all the nodes only once, we need to give our ants a least some limited form of memory.
Follow this link for illustration : Swam Intelligence
Let G = (N , E) be a connected graph with n=|N| nodes. The simple ant colony optimization algoirhtm can be used to find a solution to the shortest path problem defined on the graph G, where a solution is a path on the graph connecting a source node s to a destination node d, and the path length is given by the number of hopes in the path.
To each arc ( i , j ) of the graph is associated a variable Tij called artificial pheromone trail.
Pheromone trails are read and written by ants. The amount (intensity) of pheromone trail is proportional to the utility, as estimated by the ants, of using that are to build good solutions.
Each ant applies a step-by-step constructive decision policy to build problem's solutions. At each node local information, maintained on the node itself and/or on its outgoing arcs, is used in a stochastic way to decide the next node to move to.
The decision rule of an ant k located in node i uses the pheromone trails Tij to compute the probability with which it should choose node j e Ni as the next node to move to where Ni is the set of one-step neighbors of node i:
P1
Pij = Tij if j e Ni
= 0 if j# Ni
A the beginning of the search process, a same small amount of pheromone To is assigned to all arcs.
While building a solution ants deposit pheromone information as the arcs they use. In aco ants deposit a constant amount of delta T of pheromone.
Consider an ant that at time t moves from node i to node j. It will change the pheromone value Tij as follows:
Tij (t) <------ Tij(t) + delta T
By this rule, which simulates real ants pheromone depositing an arc (i , j), an ant using the arc connecting node i to node j increases the probability that ants will use the same arc in the future. As in the case of real ants, auto catalysts and differential path length are at work to favor the emergence of shots paths.
To avoid a quick convergence of all the ants towards a sub optimal path, an exploration mechanism is added : similarly to real pheromone trails, artificial pheromone trails "evaporate".
In this way pheromone intensity decreases automatically, favoring the exploration of different arcs during the whole search process. The evaporation is carried out in a simple way, T <--------- (1 - p) T , p e (0 ,1] at each iteration of the algorithm.
Preliminary experiments run with ACO using a simple graph modeling the experimental apparatus P1 have shown that the algorithm effectively finds the shortest path between the simulated aest and food services.Experimets have also shown that if we increase the complexity of the search graph, for example by connecting the nest to the food sources by means of morethan two possible paths, the behaviour of the algorithm tends to become less stable and the value given to parameters becomes critical.
ACO must therefore be taken for what it is: a didactic example that, because of its simplicity, has a number of limitations.
Another important point is that it should be desirable to enlarge the class of problems that can be attacked by aco algorithms.
ACO can be applied only to shortest path problems without additional constraints: if we want to use it to find a shortest hamiltonian path on a graph, that is , a path which visits all the nodes only once, we need to give our ants a least some limited form of memory.
Follow this link for illustration : Swam Intelligence