STANFORD “ANTNET”: LE FORMICHE LAVORANO COME INTERNET

"Apparentemente le formiche e Internet non hanno molto in comune, tuttavia due ricercatori di Stanford hanno scoperto che invece il sistema usato dalle formiche per raccogliere il cibo è concettualmente uguale agli algoritmi usati per il funzionamento di Internet.

Deborah Gordon, docente di Biologia dell’università, studia le formiche da oltre 20 anni e per capire in che modo le formiche determinano quante formiche servono per trasferire una fonte di cibo, ha contattato Balaji Prabhakar, docente di informatica ed esperto nel trasferimento dei dati.

Grazie a questa singolare collaborazione, è stato possibile determinare la somiglianza tra il sistema adoperato dalle formiche e il protocollo TCP (Transmission Control Protocol), ovvero quella serie di regole che determinano come devono essere trasferiti i dati su Internet... 

Continua a leggere questa notizia su pianetatech.it. "

Read More

Online AntNet Simulator

http://w3.ualg.pt/~pcardoso/antnet_simulator/main.html

Read More

Examples of the algorithm Reviewed AntNet: Data Structures

Routing Table
For any one destination d, and for each neighbor node n, is likely Pnd, which represents the "trend" to choose the node n as part of the path to the destination d.
Local Traffic Statistics
Contains information about the distribution of traffic across the network.

AntNet: Description of the algorithm
At each time interval t, at each node n is created an ant (Forward Ant), with a pseudo-random target (dependent on traffic patterns).
The goal of each ant is to find a path from origin to destination, and let each node visited, useful information for future ants. Each Forward Ant saves in its memory, which we visited and the time spent between each one.

Read More

Artificial ants (AntNet)

AntNet is an algorithm to adapt the best effort routing in IP networks.
AntNet's design is based on ant colony optimization (ACO), which explores the mechanisms behind the behavior of ants, using the shortest way to define a meta-heuristic inspired by nature for combinatorial optimization.
The ACO is characterized by a multi-agent using estigmergia communication between agents (distributed transactions), using a stochastic policy decision to build solutions, estigmergia learning the parameters of the policy decision. It has been successfully applied to a variety of combinatorial problems. AntNet was the first algorithm
ACO for routing in packet-switched networks. This work is based on the work of Dr. Gianni Di Caro in AntNet, under the supervision of Prof. Marco Dorigo.
AntNet, as well as most other algorithms based on ACO, displays a series of interesting properties: it works in a fully distributed, it is highly adaptable to changing network and traffic, uses lightweight mobile agents (called ants) for sampling path assets, is robust to failures of the agent, has several routing paths, and automatically takes care of loading data from spreading.

The performance of AntNet has been extensively tested in simulations, considering the different networks and traffic patterns, and compared to various routing algorithms (state-of-the-art). In the vast majority of situations, AntNet far surpassed all its competitors, showing excellent adaptability and robustness. AntNet has also been tested in small physical networks, confirming the good results and performance in real world tests.

Read More

Real ants

The behavior in search of food in many societies of ants is based on indirect communication based on pheromones.
While walking from the nest to food sources and vice versa, ants leave a chemical trail (pheromone) forming a trail for other ants.

Read More

Metrics and goals of the routing

The metrics can be defined as delay in the delivery of packets (seconds), service quality, speed at which packets are sent (bits / second), the network resources used. Have the goals may be too much load, increase the amount of packets sent on the same average delay, with low (decreasing the average delay of each packet).

Read More

ACO - Algorithm Routing in Networks

The routing algorithm is distributed throughout the network, you must choose the best path to take the packages to your destination and avoid congestion. Most algorithms using data structures in the nodes (Routing Tables), these structures are both databases and local models of global state, the information such as store and update depends on the algorithm used.

Read More

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

Gianni Di Caro publication about AntNet implementation for NS-2

Gianni Di Caro ,senior researcher at Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), in Lugano, Switzerland says [ Software implementations of AntNet ] "Lavina Jain made an implementation of AntNet for NS-2 (that can be also downloaded here). Starting from Jain's code, Richardson Lima has released a revised and updated version of AntNet for NS-2.33. Since I'm not an NS-2 user, I haven't checked these implementations, but I guess the Lima's implementation can be used as a good starting point. If you plan to use Lima's code, please feel free to contact me to check/improve the quality of the implementation."

Read More

AntNet Algorithm Source Code on github

https://github.com/richardsonlima/antnet

Read More

AntNet Algorithm on ENSC427: COMMUNICATION NETWORKS SPRING 2011

"One of the implementations for routing in MANET is Antnet, first developed by Lavina Jain and later updated by Richardson Lima[1]. Inspired by the foraging behaviour of ants when they search for food and the swarm intelligence to the optimized path between a food source and colony, each node in a MANET stores routing information for the neighbouring nodes and their usage as pheromone values and routes incoming packets to the path with the highest pheromone value. However, during initialization and route discovery phase, all the pheromone values are set equal and nodes route incoming packets randomly until the pheromone value converges to the optimum values. " http://www.sfu.ca/~ela6/ProjectReport.pdf

Read More