Modified particle swarm algorithm and swarm intelligence
summer project pal|
Active In SP
Joined: Jan 2011
29-01-2011, 07:52 PM
Modified particle swarm algorithm and swarm intelligence
Irene Antony Tharayil
Department of Computer Science & Engineering
College of Engineering Trivandrum
Kerala - 695016
Swarm intelligence (SI) is emerged with collective intelligence of groups of simple agents. SI
oers an alternative way of designing intelligent system, in which autonomy, emergence and
distributed functioning replaces control, preprogramming and centralization systems.Particle
Swarm Optimization (PSO) incorporates swarming behaviors observed in
ocks of birds, schools
of sh, or swarms of bees, and even human social behavior, from which the idea is emerged.
PSO is a population-based optimization tool, which could be implemented and applied easily
to solve various function optimization problems, or the problems that can be transformed to
function optimization problems.In the MPSA, which is Modied Particle Swarm Algorithm,
the update rule of the best agent in swarm is based on a proportional control concept and the
tness of each agent is evaluated on-line. In this scheme, each agent self organizes to
the best agent in swarm and migrate to a moving target while avoiding collision between the
agent and the nearest obstacle /agent.
Modified particle swarm algorithm and swarm intelligence.pdf (Size: 224.31 KB / Downloads: 72)
The computer revolution changed human societies to a large extend.It helped man to tackle
problems in many areas zas communication, transportation, industrial production, administra-
tion, writing etc. However, some problems cannot be tackled with traditional hardware and
software.Drawback of traditional techniques is Computing tasks have to be well-dened,fairly
predictable,computable in reasonable time with serial computers.
Hard problems as problems as intelligent human-machine interaction, natural language un-
derstanding, Hardly predictable and dynamic problems as real-world autonomous robots are
yet to be solved.Simulation of biological systems,Bio computing etc are some approaches for
it.Swarm Intelligence is emergent technology that make use above methods.
Swarm Intelligence (SI) is an innovative distributed intelligent paradigm for solving optimiza-
tion problems that originally took its inspiration from the biological examples by swarming,
ocking and herding phenomena in vertebrates. Particle Swarm Optimization (PSO) incorpo-
rates swarming behaviors observed in
ocks of birds, schools of sh, or swarms of bees, and even
human social behavior, from which the idea is emerged. PSO is a population-based optimiza-
tion tool, which could be implemented and applied easily to solve various function optimization
problems, or the problems that can be transformed to function optimization problems. As an
algorithm, the main strength of PSO is its fast convergence.MPSA is a rst attempt that the
PSO concept is adapted to self-organization for swarm systems. In this scheme, the MPSA
which enables a conventional PSO concept to be used in dynamic environment is proposed and
Keywordswarm intelligence, particle swarm optimization, modied particle swarm algo-
2 Swarm Intelligence
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 exam-
ple, for a bird to participate in a
ock, it only adjusts its movements to coordinate with the
movements of its
ock mates, typically its neighbors that are close to it in the
ock. A bird in
ock simply tries to stay close to its neighbours, but avoid collisions with them. Each bird
does not take commands from any leader bird since there is no lead bird. Any bird can
the front, center or 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
searching for food (as each bird is essentially exploiting the eyes of every other bird).
The size and task distribution of the swarm can change dynamically when needs change or
part of the swarm is damaged. The self-learning units are able to control almost all the parts
of the system task and thus resemble a living tissue or an individual in an ant nest. Swarm-
intelligent systems can be applied to such businesses and environments where automation has
not proved protable. Fault tolerance is a basic property of the system. A swarm intelligent
system can be integrated easily into dierent machines, structures and furniture and it increases
their intelligence. Swarm-intelligent systems give the small companies in intelligence technology
new competitiveness alongside with larger companies and opportunities to completely new kinds
of technological applications in cooperation.
Swarm intelligence emerged from inspiration of the collective intelligence in social animals
such as birds, ants, sh and termites. These social animals require no leader. Their collective
behaviours emerge from interactions among individuals, in a process known as self-organisation.
Each individual may not be intelligent, but together they perform complex collaborative be-
haviours.In swarm intelligence, the models of social animals are used to create software agents
cooperating to solve complex problems. Typical uses of swarm intelligence are to assist the
study of human social behaviour by observing other social animals and to solve a variety of
Swarm-intelligent systems are common throughout nature. Examples are bacteria colonies,
social insects, and
ocks/herds of vertebrates. In addition, humans have produced a variety
of (articial) swarm systems ranging from swarmbased optimization algorithms to sensor net-
works, swarms of robots, and smart materials. In each of these natural or articial systems,
populations of agents change their spatiotemporal conguration (in computational space or the
real world) solely based on the agents' local interactions with each other and the environment.
2.1 Swarm Problem Solving
Swarm problem solving is a bottom-up approach to controlling and optimizing distributed
systems. It is a mindset rather than a technology that is inspired by the behavior of social
insects that has evolved over millions of years. Peterson suggests that swarms calculate faster
and organize better. Swarm systems are characterized by simple agents interacting through
the environment using signals that are spatially (and temporally) distributed. By simple,it
means that the agents possess limited cognition and memory; sometimes no memory at all.
Furthermore, the behavior of individual agents is characterized by a small number of rules.
In this document consider the complexity (or simplicity) of an agent to be a function of the
number of rules that are required to explain its behavior.
2.2 How can we design SI systems?
A swarm based system can be designed by following principles.
1. Agents are independent, they are autonomous. They are not simply functions as in the
case of a conventional object oriented system
2. . Agents should be small, with simple behaviors. They should be situated and capable of
dealing with noise. In fact, noise is a desirable characteristic.
3. . Decentralized - do not rely on global information. This makes things a lot more reliable.
4. .Agents should be behaviorally diverse - typically stochastic.
5. .Allow information to leak out of the system; i.e. introduce disorder at some rate.
6. .Agents must share information - locally is preferable.
7. .Planning and execution occur concurrently - the system is reactive
The principles outlined above come from Parunak.This can be applied for almost all swarm
based algorithms as particle swarm optimization algorithm,ant colony optimization algorithm
etc. More recently, the importance of gradient creation and maintenance has been stressed and
that digital pheromones can be made to react in the environment, thereby creating new signals
of use to other swarm agents.
2.3 Advantages and Disadvantages of SI
Swarm based systems has got advantages and disadvantages as well.
The advantages are:
1. .There are several advantages:
2. .Agents are not goal directed; they react rather than plan extensively.
3. .Agents are simple, with minimal behavior and memory.
4. .Control is decentralized; there is no global information in the system.
5. .Failure of individual agents is tolerated; emergent behavior is robust with respect to
6. .Agents can react to dynamically changing environments.
7. . Direct agent interaction is not required.
There are certain disadvantages:
1. .Collective behavior cannot be inferred from individual agent behaviour. This implies
that observing single agents will not necessarily allow swarm-defeating behavior to be
chosen. (This can be viewed as an advantage too from an aggressive point of view).
2. .Individual behavior looks like noise as action choice is stochastic.
3. .Designing swarm-based systems is hard. There are almost no analytical mechanisms for
4. .Parameters can have a dramatic eect on the emergence (or not) of collective behavior
3 Particle Swarm Optimization
Particle Swarm Optimization (PSO) was invented by Kennedy and Eberhart in the mid
1990s while attempting to simulate the choreographed, graceful motion of swarms of birds as
part of a sociocognitive study investigating the notion of collective intelligence in biological
populations. In PSO, a set of randomly generated solutions (initial swarm) propagates in the
design space towards the optimal solution over a number of iterations (moves) based on large
amount of information about the design space that is assimilated and shared by all members of
the swarm. PSO is inspired by the ability of
ocks of birds, schools of sh, and herds of animals
to adapt to their environment, nd rich sources of food, and avoid predators by implementing
an information sharing approach, hence, developing an evolutionary advantage.
The particle swarm algorithm can be described generally as a population of vectors whose
trajectories oscillate around a region which is dened by each individuals previous best success
and the success of some other particle. Various methods have been used to identify some other
particle to in
uence the individual. Eberhart and Kennedy called the two basic methods as
gbest model and lbest model . In the lbest model, particles have information only of their own
and their nearest array neighbors best (lbest), rather than that of the entire group.
In the gbest model, the trajectory for each particles search is in
uenced by the best point
found by any member of the entire population. The best particle acts as an attractor, pulling
all the particles towards it. Eventually all particles will converge to this position. The lbest
model allows each individual to be in
uenced by some smaller number of adjacent members of
the population array. The particles selected to be in one subset of the swarm have no direct
relationship to the other particles in the other neighborhood. Typically lbest neighborhoods
comprise exactly two neighbors.When the number of neighbors increases to all but itself in
the lbest model, the case is equivalent to the gbest model. Some experiment results found
that gbest model converges quickly on problem solutions but has a weakness for becoming
trapped in local optima, while lbest model converges slowly on problem solutions but is able
ow around local optima, as the individuals explore dierent regions. The gbest model is
recommended strongly for unimodal objective functions, while a variable neighborhood model
is recommended for multimodal objective functions.
The basic PSO algorithm consists of three steps, namely, generating particles positions and
velocities, velocity update, and nally, position update. Here, a particle refers to a point in the
design space that changes its position from one move (iteration) to another based on velocity
updates. First, the positions, xi(k), and velocities, vi(k) , of the initial swarm of particles are
randomly generated.The second step is to update the velocities of all particles at time (k +1)
using the particles objective or tness function values which are functions of the particles current
positions in the design space at time k . The tness function value of a particle determines
which particle has the best global value in the current swarm,pg , and also determines the best
position of each particle over time, pi , i.e. in current and all previous moves. The velocity
update formula uses these two pieces of information for each particle in the swarm along with
the eect of current motion, vi(k) , to provide a search direction, vi(k + 1) , for the next
iteration. The velocity update formula includes some random parameters, represented by the
uniformly distributed variables, rand , to ensure good coverage of the design space.The position
of each agent is represented by x - y axis position and the velocity is modied by PSO.
Figure 1: New Position
Modication of the agent position is realized by the position and velocity information. An
optimization technique based on the above concept can be described as follows namely, a colony
of insects optimizes a certain objective function. Each agent knows its best value so far and its
position. Moreover, each agent knows the best value so far in the group among their own best
values. Each agent tries to modify its position
The objective function is denoted by the tness function Fi. The tness function is the
distance of the best agent from the target, computed as:
Fi(k) = (xd(k)