Ant Colony Optimization for infrastructure routing (1.0.0)
As is usual in an ACO, the agents are the ants looking for food sources (the consumer nodes) by a semi-random walk. If they have reached a food source, they are allowed to return to the nest (the source node) immediately. On their return they are attracted by the scent spread by the nest, and the pheromone that fixed network paths emit. When ants reach the existing network, they will only follow existing network patches until they reach the nest. The ant keeps track of the patches it follows back to the nest. When an ant returns to the nest, the observer calculates the additional costs of adding this path to the existing network and the observer stores the path if it is the cheapest so far.
The network connection between the nest and this food source is built when a specified number of ants have returned from the same food source without finding a cheaper alternative. When a network connection is built, the patches that are part of the new connection store the network capacity for this food source. If the patch was already part of the network, the capacity is increased accordingly. After this, the ant will look for food again. The pheromones that the network emits evaporates and diffuses according to the respective parameter settings. Even though the ants are allowed to walk through the no-go area, the no-go area is not attractive for various reasons.
There the evaporation rate of pheromones is immediate and the building cost for a no-go patch is one thousand times higher than on an allowed patch. Therefore, when the ant returns to the nest it is unlikely to follow a pheromone scent across a no-go area and any path containing a no-go patch is very unlikely to be the cheapest. The run stops when all consuming nodes, i.e. the food sources, are connected to the source (the ant nest).
Release Notes
Version used to accompany publication in JASSS
Associated Publications
Ant Colony Optimization for infrastructure routing 1.0.0
Submitted by
Igor Nikolic
Published Mar 24, 2018
Last modified Mar 24, 2018
As is usual in an ACO, the agents are the ants looking for food sources (the consumer nodes) by a semi-random walk. If they have reached a food source, they are allowed to return to the nest (the source node) immediately. On their return they are attracted by the scent spread by the nest, and the pheromone that fixed network paths emit. When ants reach the existing network, they will only follow existing network patches until they reach the nest. The ant keeps track of the patches it follows back to the nest. When an ant returns to the nest, the observer calculates the additional costs of adding this path to the existing network and the observer stores the path if it is the cheapest so far.
The network connection between the nest and this food source is built when a specified number of ants have returned from the same food source without finding a cheaper alternative. When a network connection is built, the patches that are part of the new connection store the network capacity for this food source. If the patch was already part of the network, the capacity is increased accordingly. After this, the ant will look for food again. The pheromones that the network emits evaporates and diffuses according to the respective parameter settings. Even though the ants are allowed to walk through the no-go area, the no-go area is not attractive for various reasons.
There the evaporation rate of pheromones is immediate and the building cost for a no-go patch is one thousand times higher than on an allowed patch. Therefore, when the ant returns to the nest it is unlikely to follow a pheromone scent across a no-go area and any path containing a no-go patch is very unlikely to be the cheapest. The run stops when all consuming nodes, i.e. the food sources, are connected to the source (the ant nest).
Release Notes
Version used to accompany publication in JASSS