Particle Swarm Optimization, Genetic Algorithm, Ant Colony Optimization, Artificial Immune System, Decision Support System, Artificial Neural Network

Nature Inspired Algorithms




Nature  inspired algorithm is one of the Artificial Intelligence (AI) initiatives.  AI can be referred to this link. Many nature inspired algorithms was initiated or originated from the imitation of animals, human, plants, culture and many more.  One of the popular methods is swarm intelligence systems are typically made up of a population of simple agents interacting locally with one another and with their environment.


The agents follow very simple rules, and although there is no centralized control structure dictating how individual agents should behave, local interactions between such agents lead to the emergence of complex global behavior.Natural examples of SI include ant colonies, bird flocking, animal herding, bacterial growth, and fish schooling.

 GENETIC ALGORITHM

 Motivation

  •         GA is powerful and applicable stochastic search and optimization technique. 
  •          Few decades, it turns its attention to optimization problems in industrial design. 

About a Genetic Algorithm

  •            Developed: USA in the 1970’s
  •            Early names: J. Holland, K. DeJong, D. Goldberg
  •           Typically applied to discrete optimization
  •            Attributed features:  good heuristic for combinatorial problems
·             Special Features:
  •       Traditionally emphasizes combining information from good parents (crossover) e.g., reproduction models, operator
  •       Holland’s original GA is now known as the simple genetic algorithm (SGA)

Biological Background  – Chromosomes

• Genetic information is stored in the chromosomes
• Each chromosome is built of DNA
• Chromosomes in humans form pairs
• There are 23 pairs
• The chromosome is divided into parts: genes
• Genes code for properties
• The possibilities of the genes  for  one property is called: allele
• Every gene has a unique position  on the chromosome: locus


Simple GA Procedure

 Generate a population with N random individuals.
WHILE not happy with solution quality
 DO      
    Compute the fitness of every individual in the population.      
    Select better individuals.      
    Do crossover between pairs of selected individuals with probability Pc.      
     Mutate each gene with probability Pm.
  END WHILE

Lecture Notes for Genetic Algorithm : Click here!
PARTICLE SWARM OPTIMIZATION



• Particle Swarm Optimization (PSO) was introduced by Kennedy and Eberhart in the mid-1990s (1995) 

 • It is a population-based stochastic approach which has been grouped under a swarm intelligence (Kennedy, 2006; Engelbrecht, 2007; Parsopoulos & Vrahatis, 2007) and evolutionary computation (Trelea, 2003). 

 •PSO can be used to solve continuous and discrete problems. 

 •PSO was derived from a concept of a flock of birds which fly everywhere to find food.

 •Each bird is illustrated as a particle. 

  •         Each particle moves stochastically in the search space for a feasible solution. 


 •Each of the particles has its own velocity and position.
How it works?

 PSO is initialized with a group of random particles (solutions) and then searches for optima by updating generations. 

 Particles move through the solution space, and are evaluated according to some fitness criterion after each time step. 

 In every iteration, each particle is updated.


•Canonical PSO algorithm has been used to solve continuous problem. 

 •The algorithm starts with the initialization of the population of particles or swarm size, followed by the initialization of the inertia weight (W) and acceleration constants (C1 and C2). Step 4 and 5 initialize the minimum value (V (min)) and maximum value of velocity (V(max)) and minimum position (Dmin) and maximum value of the position (Dmax), respectively. 

 •Next is the calculation of Pbest and Gbest value for each particle. Step 9 calculates the new velocity value for each particle using equation 1. 

 •Step 10 updates the new position, D(new) using equation 2. Finally, Pbest (new) and Gbest (new) are determined based on the fitness value set for the problem. 

 รข€¢ Iteration starts from step 7 to step 13 to update the current velocity and position of each particle. 

 •This iteration will be done until it satisfies the stopping condition.

PSO Advantages
There has been an increasing amount of literature on PSO since 2002 (Muthuswamy, 2009). Many variants of PSO were developed and classified as a basic variant of PSO and modification variant of PSO (Rini et al., 2010). Basic variant is very much related to velocity clamping, inertia weight, and CF. Meanwhile modification variant involves discrete PSO, multi-objective PSO, and constraint optimization using PSO. The increase of the PSO research can be because of the many advantages of this algorithm in which easy to implement (Eberhart & Kennedy, 1995), computationally efficient (Eberhart & Kennedy, 1995; Li et al., 2006; Sevkli & Guner, 2006), and fast convergence (Banks et al., 2007). 

Canonical PSO algorithm

 Canonical PSO algorithm has been used to solve continuous problem. The algorithm is shown in figure below. The algorithm starts with the initialization of the population of particles or swarm size, followed by the initialization of inertia weight (W) and acceleration constants (C1 and C2). Step 4 and 5 initialize the minimum value (Vinitialize(min)) and maximum value of velocity (Vinitialize(max)) and minimum position (Dmin) and maximum value of position (Dmax), respectively. Next is the calculation of Pbest and Gbest value for each particle. Step 9 calculates the new velocity value for each particle using equation 2.1. Step 10 updates the new position, D(new) using equation 2.2. Finally, Pbest (new) and Gbest (new) are determined based on the fitness value set for the problem. Iteration starts from step 7 until step 13 to update the current velocity and position of each particle. This iteration will be done until it satisfies the stopping condition.

1.Begin
2.    Initialize number of particles
3.    Declare W, C1 and C2
4.    Initialize V (min) and V (max)
5.    Initialize Dmin and Dmax
6.    Calculate  Pbest and Gbest value for each particle
7.    Do
8.      For each particle
9.         Calculate new velocity value, V(new)
10.         Calculate new position, D(new)
11.         Calculate Pbest (new)
12.         Calculate Gbest (new)
13.   While (stopping condition is  reached)
14.End


ANT COLONY OPTIMIZATION


Ant Colony - Inspiration 

Inspired by foraging behavior of ants.
The ants find the shortest path to a food source from the nest.
Ants deposit pheromone along a traveled path which is used by other ants to follow the trail.
 This kind of indirect communication via the local environment is called stigmergy.
Has adaptability, robustness and redundancy.


Procedures in Ant Colony Optimization algorithm

The procedures in an ACO algorithm can be understood with an analogy of a real ant behavior (Socha & Dorigo, 2008).
Ants explore randomly in areas near to their nest for food
They carry food to the nest as they find a food source.
The ant has ability of producing pheromone, a chemical that gives the sense of smelling during travelling.
Pheromone enables ants to create a trail during return trips.
Others ants can follow the same path. Pheromone trails would be able to exploit the shortest path for the food source. 

ACO hows it works




APPLICATIONS

*Movie effects
*Tim Burton's Batman Returns was the first movie to make use of swarm technology for rendering, realistically depicting the movements of a group of penguins using the Boids system.
*Lord of the Rings - film trilogy made use of similar technology, known as Massive, during battle scenes.
*Network Routing
*ACO Routing
*Swarm Robotics
*Swarm bots

 More applications
  •        Bin packing problem
  •        Shortest path problem
  •        Location and allocation problem
  •        Design optimization
               ...... other real world optimization problem.

1 comment:

Subscribe to: Posts (Atom)