Page 1

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

31

A Profound Survey on Swarm Intelligence

Manish Mahant

1

, Bharat Choudhary

2

, Abhishek Kesharwani

3

, Kalyani Singh Rathore

4

Department of CSE1, 2, 3, 4

manishmhnt@gmail.com1

hi.bharat2002@gmail.com2

abhishek.keshar@gmail.com3

kalyani.rathore@gmail.com4

Abstract

Swarm Intelligence (SI) is the collective behavior of

decentralized, self-organized systems, natural or

artificial. The concept is employed in work on

artificial intelligence. The inspiration often comes

from nature, especially biological 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 their environment. The

agents follow very simple rules, and although there

is no centralized control structure dictating how

individual agents should behave, local, and to a

certain degree random, interaction between such

agents lead to the emergence of “intelligent” global

behavior, unknown to the individual agents. Swarm

Intelligence is a relatively new paradigm being

applied in a host of research settings to improve the

management and control of large numbers of

interacting entities such as communications,

computer and sensor networks, satellite

constellations and more. Attempts to take advantage

of this paradigm and mimic the behavior of insect

swarms however often lead to many different

implementations of SI. Natural examples of SI

include ant colonies, bird flocking, animal herding,

bacterial growth and fish schooling. This article

provides a set of general principle of Swarm

Intelligence.

Index Terms

Swarm intelligence, SI, self-organized, agents, ANN,

GSA, IWD

1. Introduction

A long time ago, people discovered the variety of the

interesting insect or animal behaviors in the nature. A

flock of birds sweeps across the sky. A group of ants

forages for food. A school of fish swims, turns, flees

together, etc. We call this kind of aggregate motion

“swarm behavior”. Recently the biologists and

computer scientists in the field of artificial life have

studied how to model biological swarms to

understand how such “social animals” interact,

achieve goals, and evolve. Moreover, engineer are

increasingly interested in this king of swarm behavior

since the resulting “Swarm Intelligence” can be

applied in optimization , robotics, traffic patterns in

transportation systems and military applications.

High level view of a swarm suggests that the N

agents in the swarm are cooperating to achieve some

purposeful behavior and achieve some goal. This

apparent “collective intelligence” seems to emerge

from what are often large groups of relatively simple

agents. The agents use simple local rules to govern

their actions and via the interactions of the entire

group, the swarm achieves its objectives. A type of

“self-organization” emerges from the collection of

action of the group. Swarm intelligence is the

emergent collective intelligence of groups of simple

autonomous agents. Here, an autonomous agent is a

subsystem that interacts with its environment, which

probably consists of other agents, but acts relatively

independently from all other agents. The autonomous

agent does not follow commands from a leader, or

some global plan. For example, for a bird to

participate in a flock, it only adjusts its movements to

coordinate with the movements of flock mates,

typically its “neighbor” that are close to it in the

flock. A bird in a flock simply tries to stay close to its

neighbors, but avoid collisions with them. Each bird

does not take commands from any leader bird since

there is no lead bird. Any bird can fly in the front,

center and back of the swarm. Swarm behavior helps

birds take advantage of several things including

protection from predators (especially for birds in the

middle of the flock), and searching for food

(essentially for birds in exploiting the eyes of every

other bird).

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

32

2. Swarm Behavior Diagram

Figure: 1 Swarm Behavior

The swarming behavior of ants, bees, termites, and

other social insects has implications far beyond the

hive. Swarm intelligence – the collective behavior of

independent agents, each responding to local stimuli

without supervision – can be used to understand and

model phenomena as diverse as blood clotting,

highway traffic patterns, gene expression, and

immune response, to name just a few swarm

technology is providing useful in a wide range of

applications including robotics and nanotechnology,

molecular biology and medicine, traffic and crowd

control, military tactics, and even interactive arts.

3. Particle Swarm Optimization

Particle swarm optimization (PSO) is a population

based stochastic optimization technique developed by

Dr. Eberhart and Dr. Kennedy in 1995, inspired by

social behavior of bird flocking or fish schooling.

PSO shares many similarities with evolutionary

computation techniques such as Genetic Algorithm

(GA). The system is initialized with a population of

random solutions and searches for optima by

updating generations. However, unlike GA, PSO has

no evolution operators such as crossover and

mutations. In PSO, the potential solutions, called

particles, fly through the problem space by following

the current optimu m part icles.

Each particle keeps track of its coordinates in the

problem space which are associated with the best

solution (fitness) it has achieved so far. (The fitness

value is also stored.) This value is called pbest.

Another "best" value that is tracked by the particle

swarm optimizer is the best value, obtained so far by

any particle in the neighbors of the particle. This

location is called lbest. When a particle takes all the

population as its topological neighbors, the best value

is a global best and is called gbest. The particle

swarm optimization concept consists of, at each time

step, changing the velocity of (accelerating) each

particle toward its pbest and lbest locations (local

version of PSO). Acceleration is weighted by a

random term, with separate random numbers being

generated for acceleration toward pbest and lbest

locations.

In past several years, PSO has been successfully

applied in many research and application areas. It is

demonstrated that PSO gets better results in a faster,

cheaper way compared with other methods.

Another reason that PSO is attractive is that there are

few parameters to adjust. One version, with slight

variations, works well in a wide variety of

applications. Particle swarm optimization has been

used for approaches that can be used across a wide

range of applications, as well as for specific

applications focused on a specific requirement.

a. Artificial neural network and

PSO

An artificial neural network (ANN) is an analysis

paradigm that is a simple model of the brain and the

back-propagation algorithm is the one of the most

popular method to train the artificial neural network.

Recently there have been significant research efforts

to apply evolutionary computation (EC) techniques

for the purposes of evolving one or more aspects of

artificial neural networks. Evolutionary computation

methodologies have been applied to three main

attributes of neural networks: network connection

weights, network architecture (network topology,

transfer function), and network learning algorithms.

Most of the work involving the evolution of ANN has

focused on the network weights and topological

structure. Usually the weights and/or topological

structure are encoded as a chromosome in GA. The

selection of fitness function depends on the research

goals. For a classification problem, the rate of mis-

classified patterns can be viewed as the fitness value.

The advantage of the EC is:

1. EC can be used in cases with non-differentiable PE

transfer functions and no gradient information

available.

The disadvantages are:

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

33

1. The performance is not competitive in some

problems.

2. Representation of the weights is difficult and the

genetic operators have to be carefully selected or

developed.

There are several papers reported using PSO to

replace the back-propagation learning algorithm in

ANN in the past several years. It showed PSO is a

promising method to train ANN. It is faster and gets

better results in most cases. It also avoids some of the

problems GA met.

Here we show a simple example of evolving ANN

with PSO. The problem is a benchmark function of

classification problem: iris data set. Measurements of

four attributes of iris flowers are provided in each

data set record: sepal length, sepal width, petal

length, and petal width. Fifty sets of measurements

are present for each of three varieties of iris flowers,

for a total of 150 records, or patterns.

A 3-layer ANN is used to do the classification. There

are 4 inputs and 3 outputs. So the input layer has 4

neurons and the output layer has 3 neurons. One can

evolve the number of hidden neurons. However, for

demonstration only, here we suppose the hidden layer

has 6 neurons. We can evolve other parameters in the

feed-forward network. Here we only evolve the

network weights. So the particle will be a group of

weights, there are 4*6+6*3 = 42 weights, so the

particle consists of 42 real numbers. The range of

weights can be set to [-100, 100] (this is just a

example, in real cases, one might try different

ranges). After encoding the particles, we need to

determine the fitness function. For the classification

problem, we feed all the patterns to the network

whose weights is determined by the particle, get the

outputs and compare it the standard outputs. Then we

record the number of misclassified patterns as the

fitness value of that particle. Now we can apply PSO

to train the ANN to get lower number of

misclassified patterns as possible. There are not many

parameters in PSO need to be adjusted. We only need

to adjust the number of hidden layers and the range

of the weights to get better results in different trials.

4. Applications

The applications of swarm principles to robots are

called swarm robotics, while swarm intelligence

refers to the more general set of algorithms.

A. Swarm Robots

Swarm robotics is currently one of the most

important applications areas for swarm intelligence.

Swarms provide the possibility of enhanced task

performance. High reliability (fault tolerance), low

unit complexity and decreased cost over traditional

robotic systems. They can accomplish some task that

would be impossible for a single robot to achieve.

Swarm robots can be applied to many fields, such as

manufacturing systems, spacecraft, inspection,

maintenance, construction, agriculture, and medicine

work.

Many different swarm models have been proposed.

Beni introduced the concept of cellular robotics

systems, which consists of collections of

autonomous, non-synchronized, non-intelligent

robots cooperating on a finite n-dimensional cellular

space under distributed control. Limited

communication exists only between adjacent robots.

These robots operate autonomously and cooperate

with others to accomplish predefined global tasks.

Swarm robots are more than just networks of

independent agents; they are potentially

reconfigurable networks of communicating agents

capable of coordinate sensing and interaction with the

environment. Considering the variety of possible

designs of group‟s mobiles robots. Dudek et al.

presents a swarm robot taxonomy of the different

ways in which such swarm robots can be

characterized. It helps to clarify the strengths,

constraints and tradeoffs of various designs. The

dimensions of the taxonomies axes are swarm size,

communication range, topology, bandwidth, swarm

reconfigurability, unit processing ability, and

compositions. For each dimension, there are some

key sample points. For instance, swarm size includes

the cases of single agent, pairs, finite sets, and finite

numbers. Communications ranges include none.

Close by neighbors, and “complete” where every

agent communicate with every other agent.

Swarm composition can be homogeneous or

heterogeneous (i.e. with al the same agents or mix of

different agents). We can apply this swarm taxonomy

to the above swarm models. For example, Hackwood

and Beni‟s model has multiple agents in its swarm,

nearby

communication

range,

broadcast

communication topology, free communication

bandwidth, dynamic swarm reconfigurability,

heterogeneous composition, and its agent processing

is Turing Machine equivalent.

B. Crowd Si mul ations

Artists are using swarm technology as a means of

creating complex interactive systems or simulating

crowds.

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

34

Stanley and Stella in: Breaking the Ice was the first

movie to make use of swarm technology for

rendering, realistically depicting the movements of

groups of fish and birds using the Boids system. Tim

Burton's Batman Returns also made use of swarm

technology for showing the movements of a group of

bats. The Lord of the Rings film trilogy made use of

similar technology, known as Massive, during battle

scenes. Swarm technology is particularly attractive

because it is cheap, robust, and simple.

Airlines have used swarm theory to simulate

passengers boarding a plane. Southwest Airlines

researcher Douglas A. Lawson used an ant-based

computer simulation employing only six interaction

rules to evaluate boarding times using various

boarding methods

C. ANT B ase d Routing

The use of Swarm Intelligence in Telecommunication

Networks has also been researched, in the form of

Ant Based Routing. This was pioneered separately by

Dorigo et al. and Hewlett Packard in the mid-1990s,

with a number of variations since. Basically this uses

a probabilistic routing table rewarding/reinforcing the

route successfully traversed by each "ant" (a small

control packet) which flood the network.

Reinforcement of the route in the forwards, reverse

direction and both simultaneously has been

researched: backwards reinforcement requires a

symmetric network and couples the two directions

together; forwards reinforcement rewards a route

before the outcome is known (but then you pay for

the cinema before you know how good the film is).

As the system behaves stochastically and is therefore

lacking repeatability, there are large hurdles to

commercial deployment. Mobile media and new

technologies have the potential to change the

threshold for collective action due to swarm

intelligence

5. Algorithm

By the beginning of swarm research, the researcher is

trying to make an algorithm which can make

effective swarm behavior. There are many algorithms

which have been proposed by researcher, and we will

some key algorithm of swarm.

a. ANT Colony Optimization

Ant colony optimization is a class of optimization

algorithms modeled on the action of ant colony, ACO

methods are useful in problems that need to find

paths to goals. Artificial „ants‟ –simulation agents-

locate optimal solutions by moving through a

parameter space representing all possible solutions.

Real ants lay down pheromones directing each other

to resource while exploring there environment. The

simulated „ants‟ similarly record their positions and

the quality of their solutions, so that in later

simulation iterations more ants locate better

solutions. One variation on this approach is the bee‟s

algorithm, which is more analogous to the forging

patterns of the honey bee.

b. Artificial BEE Colony Algorithm

Artificial bee colony (ABC) algorithm is a swarm

based meta-heuristic algorithm introduced by

Karaboga in 2005, and simulates the foraging

behavior of honey bees. The ABC algorithm has

three phases: employed bee, onlooker bee and scout

bee. In the employed bee and onlooker bee phases,

bees exploit the sources by local searches in the

neighborhood of the solutions selected based on

deterministic selection in the employed bee phase and

the probabilistic selection in the onlooker bee phase.

In the scout bee phase which is an analogy of

abandoning exhausted food sources in the foraging

process, solution that are beneficial anymore for

search progress are abandoned, and new solutions are

inserted instead of them to explore new regions in the

search space. The algorithm has a good-balanced

exploration and exploitations ability.

c. GSA

Gravitational search algorithm (GSA) is constructed

based on the law of gravity and the notion of mass

interactions. The GSA algorithm uses the theory of

Newtonian physics and its searcher agents are the

collection of masses. In GSA, there is an isolated

system of masses. Using the gravitational force,

every mass in the system can see the situation of

other masses. The gravitational force is therefore a

way of transferring information between different

masses. In GSA, agents are considered as objects and

their performance is measured by their masses. All

these objects attract each other by a gravity force, and

this force causes a movement of all objects globally

towards the objects with heavier masses. The heavy

masses correspond to good solutions of the problem.

The position of the agent corresponds to a solution of

the problem, and its mass is determined using a

fitness function. By lapse of time, masses are

attracted by the heaviest mass. We hope that this

mass would present an optimum solution in the

search space. The GSA could be considered as an

isolated system of masses. It is like a small artificial

world of masses obeying the Newtonian laws of

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

35

gravitation and motion. A multi-objective variant of

GSA, called Non-dominated Sorting Gravitational

Search Algorithm (NSGSA), was proposed by

Nobahari and Nikusokhan in 2011.

d. Intelligent Water Drop

Intelligent Water Drops algorithm (IWD) is a swarm-

based nature-inspired optimization algorithm, which

has been inspired by natural rivers and how they find

almost optimal paths to their destination. These near

optimal or optimal paths follow from actions and

reactions occurring among the water drops and the

water drops with their riverbeds. In the IWD

algorithm, several artificial water drops cooperate to

change their environment in such a way that the

optimal path is revealed as the one with the lowest

soil on its links. The solutions are incrementally

constructed by the IWD algorithm. Consequently, the

IWD algorithm is generally a constructive

population-based optimization algorithm.

e. River Formation Dynamics

River formation dynamics (RFD) is a heuristic

method similar to ant colony optimization (ACO). In

fact, RFD can be seen as a gradient version of ACO,

based on copying how water forms rivers by eroding

the ground and depositing sediments. As water

transforms the environment, altitudes of places are

dynamically modified, and decreasing gradients are

constructed. The gradients are followed by

subsequent drops to create new gradients, reinforcing

the best ones. By doing so, good solutions are given

in the form of decreasing altitudes. This method has

been applied to solve different NP-complete

problems (for example, the problems of finding a

minimum distances tree and finding a minimum

spanning tree in a variable-cost graph). The gradient

orientation of RFD makes it especially suitable for

solving these problems and provides a good tradeoff

between finding good results and not spending much

computational time. In fact, RFD fits particularly

well for problems consisting in forming a kind of

covering tree.

f. Stochastic Diffusion Search

Stochastic diffusion search (SDS) is an agent-based

probabilistic global search and optimization

technique best suited to problems where the objective

function can be decomposed into multiple

independent partial-functions. Each agent maintains a

hypothesis which is iteratively tested by evaluating a

randomly selected partial objective function

parameterized by the agent's current hypothesis. In

the standard version of SDS such partial function

evaluations are binary, resulting in each agent

becoming active or inactive. Information on

hypotheses is diffused across the population via inter-

agent communication. Unlike the stigmergic

communication used in ACO, in SDS agents

communicate hypotheses via a one-to-one

communication strategy analogous to the tandem

running procedure observed in some species of ant. A

positive feedback mechanism ensures that, over time,

a population of agents stabilizes around the global-

best solution. SDS is both an efficient and robust

search and optimization algorithm, which has been

extensively mathematically described.

6. Advantages of Swarm Intelligence

There are many advantages of swarm intelligence.

Such as,

1. Flexibility is a group that can be compatible

in a dynamic environment.

2. Robustness, is irrespective of individual

misbehavior or loss, the group can

accomplish its tasks.

3. Self-organization is inherent parallelism or

distributed action with little or no

supervision.

7. Conclusions

Swarm intelligence provides a distributive approach

to the problem solving mimicking the very simple

natural process of cooperation. According to survey

many solutions that had been previously solved using

AI approach like genetic algorithm neural network

are also solve able by this approach also. Due to its

simple architecture and adaptive nature like ACO has

it is more likely to be seen much more in the future.

References

[1] Beni, G., Wang, J. Swarm Intelligence in cellular

robotic systems, proceed. NATO Advanced workshop

on Robots and biological Systems, Tuscany, Italy,

June 26-30 (1989).

[2] Ant Colony Optimization by Macro Doriga and

Thomas Stutzle, MIT Press, 2004 ISBN 0-262-04219-

2.

[3] http://www.sciencedaily.com/release/2010/05/100527

2138616.htm

[4] E. Shaw, “the schooling of fishes”, Sci. Am, vol. 206,

pp. 128-138, 1962.

International Journal of Advanced Computer Research (ISSN (print): 2249-7277 ISSN (online): 2277-7970)

Volume 2 Number 1March 2012

36

[5] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm

Intelligence: from natural to artificial systems, NY:

Oxford Univ. Press, 1999.

[6] G. Flake, the computational beauty of nature.

Cambridge, MA: MIT press, 1999.

[7] M. Resnick, Turtles, Termites, and Traffic Jams:

Explorations in massively parallel microworld.

Cambridge, MA: MIT Press, 1994.

[8] A. Mogilner and L. Edelstein-Keshet, “A non-local

model for a swarm,” Journal of Mathematical Biology,

vol. 38. pp. 534-570, 1999.

[9] Yang X. S., (2008). Nature-inpired metaheuristic

algorithms. Frome: luniver press. ISBN 1905986106.

[10] Karaboga, Dervis (2010) artificial bee colony

algorithm scholarpedia, 5(3): 6915.

Manish Mahant is pursuing his M.Tech

from RGPV. Have a lifetime

membership of ISCA, IAENG and

ISTE. SCJP 1.5 and SCBCD 5.0 exam

passed. Have keen interest in cmc,

adhoc-wireless n/w, soft computing.

Bharat Choudhary is pursuing his

M.Tech from RGPV. His interesting

subjects are software engineering, data

mining, and data structures.

.Abhishek Kesharwani is pursuing his

M.Tech from CSVTU, Bhilai, (C.G.).

His area of interest are information

security, artificial intelligence, digital

image processing.

Kalyani Singh Rathore Lecturer (CSE)

in LCIT, Bilaspur, Chhattisgarh having

M.Tech and B.E. (Hons.). Her

interesting fields are soft computing,

software engineering and computer

networking.

Author‟s Photo

Author‟s Photo

Author‟s Photo