Particle Swarm Optimization

    The Partice Swarm Optimization (CLS), 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. The PSO algorithm consists of a set of potential solutions evolves to approach a convenient solution (or set of solutions) for a problem. Being an optimization method, the aim is finding the global optimum of a real-valued function (fitness function) defined in a given space (search space).

The social metaphor that led to this algorithm can be summarized as follows: the individuals that are part of a society hold an opinion that is part of a "belief space" (the search space) shared by every possible individual. Individuals may modify this "opinion state" based on three factors:

• The knowledge of the environment (its fitness value)
• The individual's previous history of states (its memory)
• The previous history of states of the individual's neighborhood

An individual's neighborhood may be defined in several ways, configuring somehow the "social network" of the individual. Several neighborhood topologies exist (full, ring, star, etc.) depending on whether an individual interacts with all, some, or only one of the rest of the population.

PSO is initialized with a group of random particles (solutions) and then searches for optima by updating generations. In every iteration, each particle is updated by following two "best" values. The first one is 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 population. This best value is a global best and called gbest. When a particle takes part of the population as its topological neighbors, the best value is a local best and is called lbest.

After finding the two best values, the particle updates its velocity and positions with following equation (a) and (b).

         v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
         present[] = persent[] + v[] (b)

v[] is the particle velocity, persent[] is the current particle (solution). pbest[] and gbest[] are defined as stated before. rand () is a random number between (0,1). c1, c2 are learning factors. usually c1 = c2 = 2.

 1 for each particle (solution): initialize particle(i)
 2 do
 3    for each particle(i): calculate fitness value.
 4    If the fitness value is better than the best fitness value (pBest) in history
 5       update current value as the new pBest.
 6     Choose the particle with the best fitness value in the neighborhood
 7     For each particle(i)
 8        Calculate particle velocity according equation (a)
 9        Update particle position according equation (b)
 10 While maximum iterations or minimum error criteria is not attained

This skeleton (PSO) requires the classes:

• Problem
• Solution

The class Problem corresponds to the definition of a problem instance. The skeleton filler must provide a complete definition of this class.

And finally, the class Solution corresponds to the definition of a particle (feasible or not) of a problem instance. The skeleton filler must provide a complete definition of the class Solution.

In adition, the user must configure the following algorithm parameters (in file PSO.cfg):

General parameters

• Number of independent runs.
• Number of generations.
• Swarm size.
• Particle size.
• Neighborhood size.

Binary pso parameters (for constriction factor)

• Delta max.
• Delta min.

Weight factors

• Individuality weight.
• Individuality minimum.
• Individuality maximum.
• Sociality weight.
• Sociality minimum.
• Sociality maximum.
• Maximum weight.
• Minimum weight.

Migration configuracion

• Migration frequency

Parallel configuracion

• Interval of generation to refresh global state
• Running mode (synchronized or asyncronized)
• interval of generations to check solutions from other populations

There are several basic steps to running a problem solve with PSO skeleton

1. Change to the problem directory

cd Mallba/rep/PSO/PSO-baseskeleton-problem

2. Compile skeleton.

make

3. Configure algorithm parameters (PSO.cfg file)
4. Run problem:
       4.1 Sequential Version:

make SEQ

        4.2 Parallel Version:
                     4.2.1 Configure pgfileLan (or pgfileWan) : machines where we run the program.
                     4.2.2 Run

make LAN
     or
make WAN

[Up]