### 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.cfgfile)

4. Run problem:

4.1 Sequential Version:make SEQ

or

MainSeq newGA.cfg_path instance_path res_file_path4.2 Parallel Version:

4.2.1 ConfigureConfig.cfgfile.

4.2.2 ConfigurepgfileLan(orpgfileWan) : machines where we run the program.

4.2.3 Runmake LAN

or

make WAN