The purpose of this dissertation 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.
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. 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 centraized 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.
§ 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.
§ Give a straightforward analysis of the state-of-the-art studies on Ants-based Routing
Algorithms and the implementations which have been done.
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 significant stimuli," signals that activate a genetically encoded reaction. He observed thatthe 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.