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 ³significant stimuli," signals that activate a genetically encoded reaction. He observed that the effects of these reactions can act as new significant stimuli for both the insect that produced them and for the other insects in the colony. Grassé used the term stigmergy to describe this particular type of indirect communication in which ³the workers are stimulated by the performance they have achieved´. Stigmergy is defined as a method of indirect communication in a self-organizing emergent system where its individual parts communicate with one another by modifying their local environment. Ants communicate to one another by laying down pheromones along their trails, so where ants go within and around their ant colony is a stigmergic system. In many ant species, ants walking from or to a food source, deposit on the ground a substance called pheromone. Other ants are able to smell this pheromone, and its presence influences the choice of their path, that is, they tend to follow strong pheromone concentrations. The pheromone deposited on the ground forms a pheromone trail, which allows the ants to find good sources of food that have been previously identified by other ants. Pheromones represent in some ways the common memory. The fact that it is external and not a part of the ants / agents, confers to it an easy access for everyone. The memory is saved in without regarding the configuration of the ground, the number of ants, etc. It is totally independent, and still remains extremely simple. In our implementation we will see that two different types of pheromones are used. The first one is represented in red and is let by the ants which do not carry the food. We will call it the Away pheromone, as it means that the ant is going away from the nest. Oppositely, the ants which carry the food to bring it back to the nest let a blue trace behind them, the Back pheromone. Pheromones just proceed to one task: nature will take care of it in the real life, although it is a simple process in algorithms. In course of time, a global reduction of the pheromones by a certain factor is applied, simulating the evaporation process. Thus the non-succeeding path will see their concentration of pheromones reduced, although good solutions will stay full of pheromones as the ants keep using it.
Ants communicate information by leaving pheromone tracks. A moving ant leaves, in varying quantities, some pheromone on the ground to mark its way. While an isolated ant moves essentially at random, an ant encountering a previously laid trail is able to detect it and decide with high probability to follow it, thus reinforcing the track with its own pheromone. The collective behavior that emerges is thus a positive feedback: where the more the ants following a track, the more attractive that track becomes for being followed; thus the probability with which an ant chooses a path increases with the number of ants that previously chose the same path. This elementary ant's behavior inspired the development of ant colony optimization by Marco Dorigo in 1992, constructing a meta-heuristic stochastic combinatorial computational methodology belonging to a family of related meta-heuristic methods such as simulated annealing, Tabu search and genetic algorithms. This book covers in twenty chapters state of the art methods and applications of utilizing ant colony optimization algorithms. New methods and theory such as multi colony ant algorithm based upon a new pheromone arithmetic crossover and a repulsive operator, new findings on ant colony convergence, and a diversity of engineering and science applications from transportation, water resources, electrical and computer science.
No comments:
Post a Comment