25-02-2013, 11:55 AM
APPLICATION OF ANT COLONY OPTIMIZATIONTECHNIQUE FOR MANETS
APPLICATION OF ANT COLONY.pdf (Size: 1.24 MB / Downloads: 82)
ABSTRACT
All networks tend to become more and more complicated. They can be wired, with lots of
routers, or wireless, with lots of mobile nodes… The problem remains the same: in order to get
the best from the network, there is a need to find the shortest path. The more complicated the
network is, the more difficult it is to manage the routes and indicate which one is the best.
The Nature gives us a solution to find the shortest path. The ants, in their necessity to find food
and brings it back to the nest, manage not only to explore a vast area, but also to indicate to their
peers the location of the food while bringing it back to the nest. Thus, they know where their nest
is, and also their destination, without having a global view of the ground. Most of the time, they
will find the shortest path and adapt to ground changes, hence proving their great efficiency
toward this difficult task.
The purpose of this project is to provide a clear understanting of the Ants-based algorithm, by
giving a formal and comprehensive systematization of the subject. The simulation developed in
Java will be a support of a deeper analysis of the factors of the algorithm, its potentialities and its
limitations.
INTRODUCTION
SWARM INTELLIGENCE
Swarm intelligence (SI) is a type of artificial intelligence based on the collective behavior of
decentralized, self-organized systems. The expression was introduced by Gerardo Beni and Jing
Wang in 1989, in the context of cellular robotic systems.[1].
SI systems are typically made up of a population of simple agents or boids interacting locally
with one another and with their environment. The agents follow very simple rules, and although
there is no centralized control structure dictating how individual agents should behave, local, and
to a certain degree random, interactions between such agents.
PARTICLE SWARM OPTIMISATION
Particle swarm optimization (PSO) is a swarm intelligence based algorithm to find a solution to
an optimization problem in a search space, or model.
ANT COLONY OPTIMISATION
The ant colony optimization algorithm (ACO), is a probabilistic technique for solving
computational problems which can be reduced to finding good paths through graphs.
This algorithm is a member of ant colony algorithms family, in swarm intelligence methods,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 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.
OBJECTIVES
§ Propose an easy approach to the Ant Colony Algorithm, with appropriated vocabulary and
global explanation, as well as details about its behaviour.
§ Develop a Java application which shows the working of the algorithm and gives a better
understanding.
THE SOURCE OF INSPIRATION: THE ANTS
Ant as a single individual has a very limited effectiveness. But as a part of a well-organised
colony, it becomes one powerful agent, working for the development of the colony. The ant lives
for the colony and exists only as a part of it.
Each ant is able to communicate, learn, cooperate, and all together they are capable of develop
themselves and colonise a large area. They manage such great successes by increasing the
number of individuals and being exceptionally well organised. The self organising principles
they are using allow a highly coordinated behaviour of the colony.
Pierre Paul Grassé, a French entomologist, was one of the first researchers who investigate the
social behaviour of insects. He discoveredi that these insects are capable to react to what he
called