The ant colony optimization algorithm

"In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs."

Swarm intelligence methods

"This algorithm is a member of the ant colony algorithms family, in swarm intelligence methods, and it constitutes some metaheuristic optimizations. Initially proposed by Marco Dorigo in 1992 in his PhD thesis."

The first algorithm

"the first algorithm was aiming to search for an optimal path in a graph, based on the behavior of ants seeking a path between their colony and a source of food."

The original idea

"The original idea has since diversified to solve a wider class of numerical problems, and as a result, several problems have emerged, drawing on various aspects of the behavior of ants."

In the natural world.

"In the natural world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food."

AntNet is an algorithm for adaptive best-effort routing in IP networks. AntNet's design is based on the Ant Colony Optimization (ACO) framework.

"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. 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." Dr. Gianni Di Caro is AntNet Creator and Currently senior researcher at Istituto Dalle Molle di Studi sull'Intelligenza Artificiale (IDSIA), in Lugano, Switzerland. The AntNet Algorithm for the Network Simulator NS-2 (www.isi.edu/nsnam/ns) is maintained by Richardson Lima .

Thursday, August 30, 2012

STANFORD “ANTNET”: LE FORMICHE LAVORANO COME INTERNET

7:28 AM    No comments

"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

Thursday, August 2, 2012

Online AntNet Simulator

5:53 PM    2 comments

Read More

Examples of the algorithm Reviewed AntNet: Data Structures

4:50 PM    No comments


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)

4:49 PM    No comments


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

4:49 PM    No comments


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

4:45 PM    No comments


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

4:44 PM    2 comments


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
Subscribe to: Posts (Atom)