Genetic Algorithm

    A Genetic Algorithm is an evolutionary computation technique inspired by the principles of natural selection to search a solution space. It evolves a population of individuals encoded as chromosomes by creating new generations of offsprings through an iterative process until some convergence criteria or conditions are met. The best chromosome generated is then decoded, providing the corresponding solution. The underlying reproduction process is mainly aimed at improving the fitness of individuals, a measure of profit, utility or goodness to be maximized (or minimized) while exploring the solution space. The algorithm applies stochastic operators such as selection, crossover, and mutation, on an initially random population in order to compute a new generation of individuals. The whole process is sketched in the following figure.

 1 t = 0
 2 initialize P(t)
 3 evaluate structures in P(t)
 4 while not end do
 5    t = t + 1
 6    select C(t) from P(t-1)
 7    recombine structures in C(t) forming C'(t)
 8    mutate structures in C'(t) forming C''(t)
 9    evaluate structures in C''(t)
10    replace P(t) from C''(t) and/or P(t-1)

It can be seen that the algorithm comprises three major stages: selection, reproduction and replacement. During the selection stage, a temporary population is created in which the fittest individuals (those corresponding to the best solutions contained in the population) have a higher number of instances than those less fit (natural selection). The reproductive operators are applied to the individuals in this population yielding a new population. Finally, individuals of the original population are substituted by the new created individuals. This replacement usually tries to keep the best individuals deleting the worst ones. The whole process is repeated until a certain termination criterion is achieved (usually after a given number of iterations).

The Genetic Algorithm skeleton (newGA) requires the classes:

• Problem
• Solution
• Crossover
• Mutation
  

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

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

The class Crossover corresponds to the definition of a crossover operator. The skeleton filler must provide a complete definition of this class.

And finally, the class Mutation corresponds to the definition of a mutation operator. The skeleton filler must provide a complete definition of this class.

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

• number of independent runs.
• number of generations.
• size of population.
• size of offsprings in each generation.
• replace mode (if replaces parents for offsprings, or only offsprings may be new parents).
• Selection operators parameters (selection of parents and selection of offsprings parameters).
• Intra operators parameters (crossover and mutation parameters).
• Inter operators (operators to apply between sub-populations) parameters: operator number, operator rate, number of individuals and selection of individual to send and replace.
• Parallel Configuracion: interval of generation to refresh global state, running mode (synchronized or asyncronized) and interval of generations to check solutions from other populations.

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

1. Change to the problem directory

cd Mallba/rep/newGA/problem

2. Compile skeleton.

make

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

make SEQ
     or
MainSeq newGA.cfg_path instance_path res_file_path

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

make LAN
     or
make WAN

[Up]