Estigmergia

Term introduced by the French zoologist Pierre-Paul Grasse in 1959.
Estigmergia: Greek stigma (mark, sign) + ergon (action, work), the term refers to the notion that an action of a particular agent ceases signals in the environment, and this signal can be perceived by other agents (usually the same species) in order to incite or determine its subsequent actions. In real ants, this signal (or communication) is made by deposition of pheromone in the environment.
The shortest paths emerge from the collective behavior through:
A choice location and probability of each ant on where to move, and most likely paths that have more pheromones.
An indirect way of communication (Estigmergia), when the ants leave a trail of pheromone, modify how the next ants shall go see the local terrain, influencing the choice of the next way forward ants.
When reading / writing the pheromone chemical signal in a local ants are communicating indirectly via the environment

Read More

ACO: Pseudo-code

1: Initialize parameters
2: Initialize array heuristic
3: Initialize the pheromone matrix
4: while stopping conditions not satisfied do
5: to build solutions
6: Apply Local Search (optional)
7: Pheromone Update
8: end while
9: View best solution
10: Stop

Read More

Introduction ACO AntNet

Currently, researchers around the world propose new methods to solve classical problems or complex, so simple and / or efficient.
A simple proof of this are the new optimization techniques based on swarm intelligence, where through cooperation between individuals, directly or indirectly, can be a better adaptation of the environment.
An example of a swarm intelligence technique is the ant colony optimization (ACO), inspired by the behavior of agents (artificial ants) in search of alimento.A ant colony optimization, originally described by Dorigo (1992), has idea primarily as indirect communication among its subjects, through the path made by each ant during the exploration of the search space. This track is made using a kind of artificial pheromone, which acts as an attraction for them, serving as information perceived by the ants which is modified to reflect your current search experience.

The motivation of this work is to implement and evaluate the feasibility of a new target for heuristic called Ant Colony Optimization (ACO - Ant Colony Optimization), in solving routing problem in IP networks. Inspired by the behavior of some species of ants the analogy of the problem is that the ants would seek the best path with lower cost and time (effort) for moths acceptable computational routes.

The whole context was simulated by me using the NS-2 algorithm with AntNet integrated three topologies were adopted, 3x4 mesh networks, ring topology using three nodes and an arbitrary topology using 12 nodes

Read More

ACO

I present this site, a stochastic meta-heuristic inspired by nature, based on Ant Colony Optimization for (ACO), originally formulated for combinatorial optimization problems, and a Genetic Algorithm (AntNet) to solve the problem of routing in IP networks. Solving the problem of routing in IP networks is complex because it involves a search in a huge search space that grows as the number of nodes, making it impractical to use exact methods. The proposed algorithm is Antnet to obtain good results, so as to circumvent the question of the complexity of the problem.
The ant colony optimization (ACO) is a new meta-heuristic that mimics the behavior of a population of agents (ants) in search of food. Through the use of cooperation mechanisms and adaptation, this technique emulates nature so as to obtain promising solutions with simple ideas.
With this, the ACO is proving to be a competitive approach in relation to other strategies presented in the literature. Regarding the application of this technique, the same can be applied in a wide range of problems, being among the best known, for example, the problem of vehicle routing, restoration of electrical power systems, routing in IP networks.

Read More

Antnet abstract

AntNet

AntNet is an algorithm for adaptive best-effort routing in IP networks. AntNet’s design is based on the Ant Colony Optimization (ACO) framework, which exploits the mechanisms behind the shortest path behavior observed in ant colonies to define a Nature-inspired metaheuristic for combinatorial optimization. ACO features a multi-agent organization, stigmergic communication among the agents, distributed operations, use of a stochastic decision policy to construct solutions, stigmergic learning of the parameters of the decision policy, and so on. It has been applied with success to a large variety of combinatorial problems. AntNet has been the first ACO algorithm for routing in packet-switched networks. My first work on AntNet dates back to 1997. AntNet, as well as most of the other ACO routing algorithms designed after AntNet, exhibits a number of interesting properties: it works in a fully distributed way, is highly adaptive to network and traffic changes, uses lightweight mobile agents (called ants) for active path sampling, is robust to agent failures, provides multipath routing, and automatically takes care of data load spreading. AntNet’s performance has been extensively tested, considering different networks and traffic patterns, and compared to several state-of-the-art routing algorithms. In the great majority of the considered situations, AntNet has largely outperformed all its competitors, showing excellent adaptivity and robustness.

More information

Read More

Download AntNet

Download the Antnet Algorithm

https://github.com/richardsonlima/antnet/downloads

Read More

AntNet Algorithm on Google+

AntNet is an algorithm for adaptive best-effort routing in IP networks.

https://plus.google.com/b/108902716282114833896/108902716282114833896/posts

Read More