11-02-2013, 12:56 PM
Zone Based Ant Colony Optimization in Mannet
Zone Based Ant Colony .docx (Size: 214.99 KB / Downloads: 29)
INTRODUCTION
Ant Colony Optimization (ACO) studies artificial systems that take inspiration from the behavior of real ant colonies and which are used to solve discrete optimization problems. In 1999, the Ant Colony Optimization Metaheuristic was defined by Dorigo, Di Caro and Gambardella.
The first ACO system was introduced by Marco Dorigo in his Ph.D. thesis (1992), and was called Ant System(AS). AS is the result of a research on computational intelligence approaches to combinatorial optimization that Dorigo conducted at Politecnico di Milano in collaboration with Alberto Colorni and Vittorio Maniezzo. AS was initially applied to the travelling salesman problem, and to the quadratic assignment problem.
Since 1995 Dorigo, Gambardella and Stützle have been working on various extended versions of the AS paradigm. Dorigo and Gambardella have proposed Ant Colony System (ACS), while Stützle and Hoos have proposed MAX-MIN Ant System (MMAS). They both have been applied to the symmetric and asymmetric travelling salesman problem, with excellent results. Dorigo, Gambardella and Stützle have also proposed new hybrid versions of ant colony optimization with local search.
Detailed view of Ant Colony Optimization
The original idea comes from observing the exploitation of food resources among ants, in which ants’ individually limited cognitive abilities have collectively been able to find the shortest path between a food source and the nest.
1. The first ant finds the food source (F), via any way (a), then returns to the nest (N), leaving behind a trail pheromone (b)
2. Ants indiscriminately follow four possible ways, but the strengthening of the runway makes it more attractive as the shortest route.
3. Ants take the shortest route; long portions of other ways lose their trail pheromones.
In a series of experiments on a colony of ants with a choice between two unequal length paths leading to a source of food, biologists have observed that ants tended to use the shortest route.
A model explaining this behavior is as follows:
1. An ant (called "blitz") runs more or less at random around the colony;
2. If it discovers a food source, it returns more or less directly to the nest, leaving in its path a trail of pheromone;
3. These pheromones are attractive; nearby ants will be inclined to follow, more or less directly, the track;
4. Returning to the colony, these ants will strengthen the route;
5. If there are two routes to reach the same food source then, in a given amount of time, the shorter one will be traveled by more ants than the long route;
6. The short route will be increasingly enhanced, and therefore become more attractive;
7. The long route will eventually disappear because pheromones are volatile;
8. Eventually, all the ants have determined and therefore "chosen" the shortest route.
Edge Selection in Manets
An ant is a simple computational agent in the ant colony optimization algorithm. It iteratively constructs a solution for the problem at hand. The intermediate solutions are referred to as solution states. At each iteration of the algorithm, each ant moves from a state to state , corresponding to a more complete intermediate solution. Thus, each ant computes a set of feasible expansions to its current state in each iteration, and moves to one of these in probability. For ant , the probability of moving from state to state depends on the combination of two values, viz., the attractiveness of the move, as computed by some heuristic indicating the a priori desirability of that move and the trail level of the move, indicating how proficient it has been in the past to make that particular move.
The trail level represents a posteriori indication of the desirability of that move. Trails are updated usually when all ants have completed their solution, increasing or decreasing the level of trails corresponding to moves that were part of "good" or "bad" solutions, respectively.
HOW ANT CAN MANAGE THEIR TASKS:
• Ants can explore vast areas without global view of the ground.
• They can find the food and bring it back to the nest.
• They will converge to the shortest path.
• By leaving pheromones behind them.
• Wherever they go, they let pheromones behind here, marking the area as explored and communicating to the other ants that the way is known.
• Consider four ants which were travelling for food from nest to the destination
• Initially, every ant finds its own route to reach the destination point (food).
• From destination point again it comes back to the starting point in the same way they went.
• To travel for another time, the ants checks that which ant had reached first from destination (food) to the source (nest).
• In second phase, more than two ants will follow the shortest path.
• In this way, all the ants will select their best way or optimized way to get their food.
• While they travel, they leave some pheromones behind them which evaporates very fast.
• The basic idea of the ant colony optimization This behavior of the ants can be used to find the shortest path in networks.
• Especially, the dynamic component of this method allows a high adaptation to changes in mobile ad-hoc network topology, since in these networks the existence of links are not guaranteed and link changes occur very often.
• Meta heuristic is taken from the food searching behavior of real ants.
Applications of Manets
Knapsack problem. The ants prefer the smaller drop of honey over the more abundant, but less nutritious, sugar.
Ant colony optimization algorithms have been applied to many combinatorial optimization problems, ranging from quadratic assignment to protein folding or routing vehicles and a lot of derived methods have been adapted to dynamic problems in real variables, stochastic problems, multi-targets and parallel implementations. It has also been used to produce near-optimal solutions to the travelling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches of similar problems when the graph may change dynamically; the ant colony algorithm can be run continuously and adapt to changes in real time. This is of interest in network routing and urban transportation systems.
ALGORITHMS IN ANT COLONY OPTIMIZATION
SHORTEST-PATH ALGORITHM:
With an ACO algorithm, the shortest path in a graph, between two points A and B, is built from a combination of several paths. It is not easy to give a precise definition of what algorithm is or is not an ant colony, because the definition may vary according to the authors and uses. Broadly speaking, ant colony algorithms are regarded as populated Metaheuristic with each solution represented by an ant moving in the search space. Ants mark the best solutions and take account of previous markings to optimize their search. They can be seen as probabilistic multi-agent algorithms using a probability distribution to make the transition between each iteration. In their versions for combinatorial problems, they use an iterative construction of solutions. According to some authors, the thing which distinguishes ACO algorithms from other relatives (such as algorithms to estimate the distribution or particle swarm optimization) is precisely their constructive aspect. In combinatorial problems, it is possible that the best solution eventually be found, even though no ant would prove effective.
Thus, in the example of the Travelling salesman problem, it is not necessary that an ant actually travels the shortest route: the shortest route can be built from the strongest segments of the best solutions. However, this definition can be problematic in the case of problems in real variables, where no structure of 'neighbors’ exists. The collective behavior of social insects remains a source of inspiration for researchers. The wide variety of algorithms (for optimization or not) seeking self-organization in biological systems has led to the concept of "swarm intelligence", which is a very general framework in which ant colony algorithms fit.
SUMMARY
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 (see Ant communication).
Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over more frequently, and thus the pheromone density becomes higher on shorter paths than longer ones. Pheromone evaporation also has the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained.