Swarm Optimization

1. INTRODUCTION

1.1 SWARM INTELLIGENCE

It is a type of artificial intelligence which focuses on the collective behavior of decentralized and self-organized systems. This idea was developed by Gerardo Beni and Jing Wang in 1989, in the setting of cellular robotic systems. These systems are generally made up of a group of simple agents that are interacting with one another as well as with their environment locally. Algorithms are designed or problem-solving techniques are developed by taking inspiration from the collective behavior of agents (social insect colonies and other animal societies). The rules followed by these agents are very simple and there is no controlling structure which tells how an individual agent should behave and interact.

1.2 PARTICLE SWARM OPTIMIZATION

Particle swarm optimization (PSO) is an algorithm based on swarm intelligence which helps to find a solution to an optimization problem in a search space, or model. Also, it can be considered as a technique using artificial intelligence which helps in finding out an approx. solution of difficult or rather impossible numeric maximization and minimization problem.

1.3 ANT COLONY OPTIMIZATION

The ant colony optimization algorithm (ACO), is a probabilistic approach which is used to solve problems of computations which can find good paths through graphs. In swarm intelligence procedure, this algorithm is a segment of ant colony algorithms, the first algorithms goal was to search for a best path in a graph, based on the behaviour of ants searching a path between their colony and the position of food. The original idea had been varied to solve a wider range of numerical problems, and as a result, several problems have appeared, depicting on various features of the action of ants.

2. OBJECTIVES

• Suggest an easy way to the Ant Colony Algorithm, with suitable terminology and definitions, as well as details about its behaviour.

• Establish a Java application which demonstrate the working of the algorithm and gives a better knowledge.

• Give an easy reasoning of the studies on Ants-based Routing Algorithms and their implementations that have been done.

28

3. THE CAUSE OF IDEA: THE ANTS

Ant as a single individual has a very finite effectiveness. But as a group of a well-organized colony, it becomes one powerful operator, working for the betterment of the colony. The ant exists for the colony and lives only as a part of it.

Each ant is capable to communicate, acquire information, coordinate and all together they are able to colonise a large area and establish themselves. They maintain such great achievements by being exceptionally well organised and increasing the number of individuals. The self-organising rule that they are using allow a highly cooperative behaviour of the colony.

A French entomologist, Pierre Paul Grassé, was one of the first researchers who examine the social behaviour of insects. He found that these insects are able to react to what he called “significant stimuli” that initiate a reaction that is genetically encoded. He noticed that the consequences of these reactions can perform as new significant stimuli for both the insect that generated them and for the other insects in the colony. The term stigmergy is used by Grassé to define the specific type of indirect interaction in which the workers are encouraged by the performance they have achieved.

Stigmergy is described as a technique of indirect communication in a self-organizing developing system where its individuals communicate with one another by altering their local environment.

Ants lays down pheromones along their ways which helps them to converse to one another, so where ants go inside and around their ant colony is a stigmergic system. Many ants while walking from or to a food source, deposit on the ground an element called pheromone. Other ants can smell this pheromone, and its occurrence directs their choice of the path, as they have a tendency to follow strong pheromone concentrations. The pheromone placed on the ground forms a pheromone track, which lets the ants to find good traces of food that have been previously recognized by other ants.

With random walks and pheromones within a ground having one nest and one food source, the ants will leave the nest, find the food and come back to the nest. Sometime later, the way being used by the ants will converge to the quickest and shortest path.

4. THE DOUBLE BRIDGE EXPERIMENT

The ants start by walking arbitrarily. They have a very limited view of what is around them, they cannot see the ground. Therefore, they will just wander and take random decision at each crossroads, if the ground has not been discovered yet.

After a certain time, the places around the nest will be all discovered. The ants will get to know that by the marking done by the previous ants. Certainly, they will leave behind them the pheromones and notify the other ants that the way is already explored.

Fig. 1. Ants and pheromones

The quantity of pheromones varies on the number of ants who took the way, the more ants taking the way, the more pheromones.

The procedure is as shown in figure 1: the nest of a colony of ants is linked to the food via two bridges of the same length. In such a setting, ants begin to discover the surroundings of the nest and ultimately reach the

...