Survey Paper on Swarm Intelligence

Survey Paper on Swarm Intelligence

Sanjay M P Department Of ISE New Horizon College

Of Engineering, Bangalore India.

Vignesh D Department Of ISE New Horizon College

Of Engineering, Bangalore India.

S.Keerthi Department Of ISE New Horizon College

Of Engineering, Bangalore India.

Krupashree.B Department Of ISE New Horizon College

Of Engineering, Bangalore India

Abstract:- In this paper we are discussing regarding the Swarm Intelligence and there some of the examples. Anything in group is said to a swarm. Intelligent behaviour from a large number of Simple Individuals is called as Swarm Intelligence. It is a collective Behaviour from the local interactions of the individuals with the each other. Individual co-ordinate from the decentralized control and self-organization. We can find swarm in colonies of ants, school of fishes, flocks of birds etc. In this paper we are seeing the examples of Swarm and their behaviour. we also see the various Swarm Intelligence models such as the Ant colony Optimization where is describes about the movement of ants, their behaviour, and how do it overcome the obstacles, in birds we see about the Particle swarm optimization it is based on the swarm intelligence and how the positions has to be placed based on the three principles. Next is the Bee colony optimization that deals with the behaviour of the bees, their interactions, also describes about the Movement and how they work in Swarm. Some of the techniques and algorithms are discussed in this paper.

Keywords: Swarm, Swarm Intelligence, Stigmergy, Pheromone.

1. INTRODUCTION

Swarm Intelligence (SI) is a group of homogeneous individual agents, interact among themselves and with the environment. A Swarm is a collection of homogeneous, individual agents which interacts among them locally within the environment without centralization. Swarm Intelligence concept was first introduced by G. Beni, Hackwood and J. Wang in 1989. The context of cellular robotics systems was strictly used [6] [10][33]. This field of study focuses on the collective behaviour those results from the local interactions of the people with each other and with their surrounding conditions [1]. There is an arise to the smart systems which is able to perform complex tasks in various fields like robotics, computer science and software applications. SI is a simple local behaviour which leads to global intelligent behaviour. SI represents the idea to control and monitor complex systems interacting among the entities. Distributed forms of control can be more efficient, effective and scalable. The main aim of Swarm Intelligence is to increase the performance and robustness

[6][9]. Swarm algorithms are fast, robust solution to solve complex problems. SI is a new branch of artificial intelligence that is used as collective behaviour of swarms in nature, such as colonies of ants, flocking of birds, honey bees. Agents are simple with limited capabilities; by interacting with other agents of their own kind they achieve the task. The agent follows very simple rules. The social interactions among individual swarms can be either direct or indirect. Direct interactions here the agents interact with each other through audio or video. Example is birds where they interact with each other through sound (audio) and bees interact with each other through waggle dance. Indirect interactions here the agents interact with the environment i.e., one agent changes the environment and other agents respond to the change. This indirect type of communication is called as stigmergy which is interaction through environment [7]. For example, the pheromone trail lay by the ants during the search of food. SI algorithms are inspired by nature to solve real life problems. Social collective behaviour of swarms helps to solve the real life problems by observing how swarms have survived to take challenges to solve complex problems in nature [8][12]. The swarm system is characterized in terms of individuals, interactions and environment.

ANTS

The ants are considered to be one of the best natural examples of the swarm. The ants follow the indirect interaction. Ants live in colonies and are almost blind individuals, they lay pheromone (i.e., volatile chemical substance) on the way from the nest when they go in search of food source. The term pheromone was introduced by

P. Karlson and M.Luscher in 1959, based on Greek word Pherin which means transport and hormone means to stimulate. Marco Dorigo and colleagues in 1991 as introduced ant colony optimisation algorithm to demonstrate the food foraging behaviour of the ant colonies. This algorithm was developed by the observation. ACO is one of the first optimization algorithm used to solve the problems like Sequential ordering problem, scheduling problem, graph colouring, vehicle routing. Ants

live in a group and their problem goal is group survival rather than an individual survival. Ants communicate with each other through pheromones. [11][12]

ANT COLONY OPTIMIZATION

Ant colony optimization (ACO) was proposed by Macro Darigo in 1991 in his PhD thesis the first algorithm was to search for optimal path based on the behaviour of ants finding the shortest path in search of food source. ACO algorithm is used to solve complex problems like optimization problems, sequential ordering problems, scheduling problems, graph colouring, assembly line balancing, vehicle routing problems. Multi objectives areas used are data mining, telecommunication networking and bioinformatics. ACO is widely used in swarm intelligence it is a class of algorithms which inspires the foraging behaviour of ants. ACO is almost same as motivated behaviours in order to solve optimization problems. Since it has been introduced there are several different versions to the original optimization algorithms. So we limit our focus to Ant Systems (AS), the original ACO algorithms were introduced. Pheromone levels are updated by all the ants which build a solution to the iteration which is the main characteristics of AS. Foraging behaviour of ants is the best example for explaining the ability of ant colonies. [15]

Foraging behaviour of ants is as follows:

1. Individual ants go in search of food; they wander randomly around colonies in search of food source as shown in figure 1.

2. Ants cannot directly communicate with each other; indirect communication is called as stigmergy.

3. When the ants find their food source they immediately come back near the nest on its way back it leaves a chemical substances called as pheromone. These pheromones are volatile in nature they keep evaporating.

4. Ants are capable of sensing this pheromone and the route is attracted by other ants, they move on the same track. And each ant leaves their chemical substances and thickness the track so that if any other ants are in the source then they can follow the pheromone thickness and find their food source.

5. If other ant has found shortest paths for the same food source, then that shortest path can be followed by many other ants and this route becomes more attractive as increase in the concentration of pheromone.

6. If there is any obstacle in the route then it will move randomly in the beginning but later they will find the shortest path.

   Figure: Ants stigmergic behaviour in finding the shortest path between the food and nest.

   The algorithm of an ant colony optimisation

   1. Procedure ACO met heuristic

   2. Schedule activities

   3. Construct ants solutions

   4. Update pheromones

   Daemon actions % optional

   5. End-schedule activities

   6. End procedure[16][17]

BEES

Honey bees are one of the examples of swarm, in nature which has been used as an efficient and intelligent distributed system. Honey bee swarms are dynamic and intelligent they are capable of dividing various tasks among the other bees. The daily tasks that Bees perform like foraging, storing, retrieving and distributing honey, collecting pollen, communication, and adapting themselves to the changes in the environment in a collective manner without any central control. [39][40] There are various algorithms that have been using intelligent behavior of bees to design distributed systems. Foraging in bee swarms is different than that in ant swarms. Well-organized colonies and do not require hibernation. [19][21][22]

Bees in nature are very organized, the bees categorized into different ways based on their work, the bees which can be called as scout bees look for different sources or targets, this bees search their source which are flowers based on various constraint and after finding the appropriate sources they have to display it to the other bees in the hive, so they return to the hive and there is something called as dance floor in the hive where these scout bees do waggle dance, by this dance they can communicate to other bees about the location of the food source. The worker bees decide the best path of the source based on the dance. And all the worker bees go to the appropriate location which is flower and they collect the nectar from it and reach to the hive in the same path taken, by this way they come back to the hive and gives the nectar to the food store bees which collects the nectar from the worker bees and then they process the nectar and then they store it in the comb, the selection of the food source is based on the quantity of the food and can also be the distance. This behaviour of bees

can be used for many optimization problems and also for the best path technique.[20]

There are two types of worker bees named as scouts and foragers. At first the scout bees are sent out in search for food source. These bees move randomly from one flower to another and keep exploring other flowers in order to find the best food until they are tired. And after they have found a flower they deposit their nectar or pollen and then they move to the dance floor and perform a dance to communicate about the flower or food to the other bees. This information helps the colony to send its bees to flower patches precisely, without using guides or maps. Each individuals knowledge of the outside environment is purely based on the waggle dance. This dance enables the colony to evaluate the different flower patches according to both the quality of the food they provide and the amount of energy needed. After waggle dancing inside the hive, the dancer or the scout bee goes back to the flower with follower bees that were inside the hive. More follower bees are sent to best patches. This allows them to gather food quickly and efficiently. The bees monitor its food level. This is necessary to decide upon the next waggle dance when they return to the hive. If the patch is still good enough as a food source, then it will be advertised in the waggle dance and more bees will be sent to that source.[24][25]

EXISTING ALGORITHM IN BEES:

The Bees Algorithm is based on the foraging behaviour of the bees. This finds the optimal solution.

Algorithm

1. Population of the bees is initialized.

2. Populations fitness has to be calculated.

3. While (condition (stopping criteria) not met)

4. Select certain spots to search.

5. Select more bees for the new spot and calculate the fitness.

6. Determine the fittest bees.

7. Other bees have to be assigned randomly for the search. 8. End While. [19][21]

   BCO

   BCO is the SI system where the low level agent to the system is the bee. BCO is the name given to the total foraging behaviour of honey bees. Bee system is a standard example of organized team work, well coordinated interaction, coordination, labour division, simultaneous task performance, specialized individuals, and well-knit communication. Typically bee colony optimization has different types of bees. There is a queen bee, many male drone bees and thousands of worker bees.

   Types of bees:

   1. Queen bees are responsible of laying eggs so that new colonies of bees can be formed.

   2. Drones are male bees which are responsible to mate with the queen. This is their sole role in the hive. They are discarded from the colony during their down fall.

   3. Worker bees are the female bees of the hive. The main building blocks of the hive are worker bees. They build the honey bee comb, clean, maintain, guard and feed the queen and drones. The main job of this worker bee is to collect rich food. [19][22]

There are two types of worker bees namely scout bees and forager bees. Both of them are collectively responsible for collecting food but they all play different roles in the hive. Based on the behaviour of bees the BCO is designed. In the BCO there are many agents which works collectively to solve the problem in the optimization method.BCO is a little different from the actual bee colony. Initially before BCO there were two algorithms that are ecological algorithm and bee system algorithm which was based on the collective intelligence of bees behaviour and latter is of the genetic algorithm.BCO can be related to the travelling salesman problem. Yonezava and Kikuchi were the first to describe the collective intelligence of bees. Lucic and Teodorovic used the principles of the collective intelligence to solve the optimization problem. BCO can also be called as the population algorithm because it finds the optimal solution. One of its applications is Ride matching problem can be solved using BCO. It is met heuristic and it is motivated by the foraging behaviour of bees. BCO is not used widely to solve real life problems. BCO has two vital process that is recruiting and information exchange.

Fig: Flowchart for Basic BCO Steps.

Algorithm: The general scheme of the ABC algorithm is as follows:

Initialization Phase REPEAT

Employed Bees Phase Onlooker Bees Phase Scout Bees Phase

Memorize the best solution achieved so far

UNTIL (Cycle=Maximum Cycle Number or a Maximum CPU time) [25]

Initialization Phase: Food sources are initialized by the Scout bees and control parameters are set.

Employed Bees Phase: Employed bees search for new food sources having more nectar within the neighbourhood of the food source in their memory. They find a neighbour food source and then evaluate its profitability (fitness).

Onlooker Bees Phase:Employed bees share their food source information with onlooker bees waiting in the hive and then onlooker bees probabilistically choose their food sources depending on this information. In ABC, an onlooker bee chooses a food source depending on the probability values calculated using the fitness values provided by employed bees. [27]

BIRDS

A flock is a group of birds or mammals assembled or herded together. Boids was developed by Craig Reynolds in 1986. Boids is an artificial life program which simulates the flocking behaviour of birds. The name boid means bird-oid object which refers to bird-like object. Boids are similar to particle systems but have orientation and geometrical in shape which is used for rendering. Boids is a behavioural based motion. Age, Sex and Body size plays a major role in the formation of the V-shaped pattern. In a group of birds of adults and young birds, juveniles usually do not lead the group since they are unable to maintain high speed in lead position and hence would slow down. The entire flock down according to the study of Swedish researchers published in January 2004 issue of journal behaviour Ecology. [29][30]

p>Researchers also decided that pelicans that fly in group formation beat their wings less often and have lower heart rates than those birds that fly alone. In this way the birds that fly in v-formation conserve less energy during their long and difficult journey and to avoid predators. This v- formation also helps in communication and coordination within the flock, allowing birds to improve orientation and follow their route more directly. From the swarm behaviour is a collective motion of large number of self-entities. From the mathematical model perspective, it is emergent behaviour arising from the simple rules that are followed by the individual.

The simple mathematical model of animal swarms follows three rules. They are

1. Neighbours move in the same directions.

2. Closely remain to their neighbours.

3. In all direction they avoid collisions.

The movement of Boids can be in order or disorder. Disorder means splitting groups and wild behaviour. Splitting flocks and reuniting after avoiding obstacles are few unexpected behaviours and these can be considered as newly formed or newly independent. Boids simulation specifies each individual bird behaviour. [32][44]

PARTICLE SWARM OPTIMISATION

Particle swarm optimization is a method which works on the basis of swarm intelligence. Particle swarm optimization was introduced by Doctor Kennedy and E Berhart in 1995. PSO was developed from swarm intelligence and the research is based on birds and fish behaviour. While searching for food the birds get scattered or they go together in search of food while searching for food source from one place to another, there is always a bird that can smell the best food source easily and go in search of that source i.e., the bird is perceptible of the food source and supply the information to all other birds. Birds have good communication, co operation and positive thinkers. The particle without quality and volume will serve as individuals and their behaviours are controlled by each particle to show their complexity. PSO is an experience based thinking optimization which is based on swarm intelligence. [35]

PSO will be mainly concentrated on the following:

1. The maths basic theory- it analyze the stability of the condition where the particle can move stably.

2. Particle swarm topology- Research on the topology of new pattern of particle swarm which can perform the function better. Different particle swarms are based on the intimation of different societys foe neighbouring topology. In order to enable PSO and to have best property and perform research on the suitable ranges of different topologies the algorithms should select the proper topology.

3. Blending with other intelligent optimization algorithm- it means merging the PSO advantages with the other intelligent optimization algorithm

   advantages to create the compound algorithm that has practical value.

4. Develop the application area of algorithm- it is important to explore the developing area since the PSO algorithm has been used widely.

Algorithm for boids

Boids program structure:

1. Initialize position( )

2. Loop

3. Draw boids( )

4. Move all boids to new position( )

5. End loop

All the boids are initialized at a starting position and initialization is done at random locations. All the boids will fly towards the middle of the screen when simulation starts. One frame of animation is drawn with all boids being in their current positions. Moving all boids to new position involves simple vector operations on boids positions.

Consider vector A1, A2, A3 for Boid c For each boid c

1. A1=rule1(c)

2. A2=rule2(c)

3. A3=rule3(c)

4. c.velocity =c.velocity+A1+A2+A3

5. c.position =c.position+c.velocity 6. end [36]

CONCLUSION

In this paper, the main ideas and principles of swarm, swarm intelligence is presented with the particular focus on three most popular and successful SI optimization techniques: Ant Colony Optimization, bee colony optimization and Particle Swarm Optimization. The examples of swarm are the colonies of ants, flocks of birds, schools of fishes. We also describe about the various Swarm Intelligence models such as the Ant Colony Optimization model that deals with the behaviour of the ants, their interactions, algorithm. Particle Swarm Optimization it describes the behaviour and the principles of movements of birds in swarm. The bee colony deals with the behaviour of bees how do they work in group together and there interaction with each other. These swarm examples all solve complex problem.

REFERENCES

1. Principles and applications of swarm intelligence for adaptive routing in telecommunications networks, Frederick Ducatelle, Gianni A. Di Caro, Luca M. Gambardella, DalleMolle Institute for Articial Intelligence Studies (IDSIA) Galleria 2, 6928 Manno, Switzerland e-mail: {Frederick, gianni,luca}@idsia.ch

2. A Study on Swarm Artificial Intelligence by Dr. Ajay Jangra, AdimaAwasthi, Vandana Bhatia U.I.E.T,K.U, India

3. An Ant Colony Optimization Algorithm for Solving Travelling Salesman Problem Krishna H. Hingrajiya, Ravindra Kumar Gupta, Gajendra Singh Chandel , University of Rajiv Gandhi ProudyogikiVishwavidyalaya, Bhopal (M. P.)

4. Evolutionary Dynamics of Ant Colony Optimization HaithamBouAmmar, Karl Tuyls, and Michael Kaisers Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands

5. Swarm Based Truck-Shovel Dispatching System in Open Pit Mine Operations YassiahBissiri, W. Scott Dunbar and Allan Hall Department of Mining and Mineral Process Engineering University of British Columbia, Vancouver, B.C., Canada Email:bissiri@mining.ubc.ca

6. http://www.slideshare.net/smashingrohit/swarm-intelligence- an-introduction

7. Beekman M, Sword G A, and Simpson S J, 2008, Biological foundations of swarm intelligence, In C. Blum and D. Merkle (eds.) Swarm Intelligence. Introduction and Applications, Springer, Berlin, Germany, pp. 3-41.

8. BijayaKetanPanigrahi, Yuhui Shi et al, 2011, Handbook of Swarm Intelligence, Springer 2011.

9. Foundations of Swarm Intelligence: From Principles to Practice Mark Fleischer Institute for Systems Research University of Maryland College Park, Maryland 20742

10. Swarm-based information retrieval Automatic knowledge- acquisition using MAS, SI and the Internet Harvard Rykkelid

11. http://www.slideshare.net/idforjoydutta/ant-colony- optimization-23180597?related=2

12. Swarm Intelligence: Concepts, Models and Applications Technical Report 2012-585 Hazem Ahmed Janice Glasgow School of Computing Queen's University Kingston, Ontario, Canada K7L3N6 {hazem, janice}@cs.queensu.ca

13. Bee Colony Optimization A Cooperative Learning Approach to Complex Transportation Problems Duan Teodorovi1, 2, Mauro Dell Orco3

14. The Bees Algorithm A Novel Tool for Complex Optimisation Problems D.T. Pham, A. Ghanbarzadeh, E. Koç,

    S. Otri , S. Rahim , M. Zaidi Manufacturing Engineering Centre, Cardiff University, Cardiff CF24 3AA, UK

15. Honey Bees Inspired Optimization Method: The Bees Algorithm BarisYuce 1,*, Michael S. Packianather 2, Ernesto Mastrocinque