This paper will describe the effects
of the crossover operator in a simple genetic algorithm and how they affect the
performance in an optimization problem. A comparison of different types of the
crossover operator will be applied to a population in order to obtain the
fittest values after a number of generations. After the comparison is made we
will evaluate which type of crossover operator can provide higher performance
values than the other crossover operators.
Genetic algorithms (GA) came into
existence with the adaptation of developed biological processes to the computer
environment (Kaya, 2010). A genetic algorithm
is a high-level procedure used to generate quality solutions to optimization and
search problems, this procedure is inspired by the natural process called
natural selection. The basic elements of genetic algorithm were introduced in
“Machine Learning” by Holland (Holland, 1975).They were proved to
be practical by one of his students, when he performed a study on gas pipes. GA
studies in engineering are generally the optimizations of topology, shape, and
dimension (Goldberg, 1989).
Optimization problems will be faster
solved with a computer and the genetic algorithm is faster than traditional
optimization methods because the units stored in the computer`s memory can
behave in the same way as those in a natural population (Kaya, 2010).
The genetic algorithm like any other
algorithms has phases. These are: initial population, fitness function,
selection, crossover, mutation and termination. The selection, crossover and
mutation will also be the operators of this kind of algorithm. These operators
will determine if the algorithm is good or not for finding the best solution to
a problem. For example, if we had a search problem, all the solutions can be
gathered in a set and considered a population on which the operators will
perform different actions. After all the operators have performed on the
initial population, a final population will be formed, this population will
show the best solution to the problem.
Any genetic algorithm is influenced by
their operators, such as crossover, selection and mutations. The performance is
mainly affected by crossover and mutation, which makes them the most important
part of the GA (Obtiko, 2017). Therefore, the
effects of these operators were the subject of different experiments and the
effect of the crossover operator was investigated on the behaviour of genetic
algorithms (S. Rajeev, 1992). Producing different
results is not possible if the same type of crossover is used and this lead to
discovery that there are more types of crossover. The crossover operator has
several types such us: single point crossover, two-point crossover, uniform
crossover and arithmetic crossover.
In this paper the effect of crossover
operators will be investigated on a genetic algorithm in order to find which
type of crossover is going to be the most efficient on different sizes of the
initial population. Genetic algorithms are very used for parametric
optimisation problems and it can be explored how different crossover operators
influences the performance of the genetic algorithm.
of the Genetic Algorithm
A genetic algorithm procedure needs to
be applicated to a population because is based on Charles Darwin’s theory of
natural evolution (Mallawaarachchi, 2017). The natural
selection process is the most similar procedure, where the fittest individuals
are selected for reproduction, to produce the next generation.
Genetic algorithms are often
represented by strings of binary values like in the image above.
Natural selection starts with the
selection of individuals from a population. An individual is characterized by a
set of parameters (variables) known as Genes (Mallawaarachchi, 2017). Genes will form the chromosome when they are
joined into a string. The new generation will inherit the genes
that can give them a better chance of survival. This procedure keeps repeating
until the population has converged, this means that there are no new
generations with significantly different genes. This process can be applied to optimize problem
in order to produce a better solution, because the better solution is like a
new generation, inherits genes that will give it a better chance of survival.
The genetic algorithm is going to have
five different stages: initial population, fitness function, selection,
crossover and mutation.
The process starts with a set of
solutions to a given problem, these solutions can be called individuals and the
set of individuals a population.
The fitness function will show if an
individual is fit in comparation with other individuals. Each individual will
have a fitness score, the one with highest score will be selected for
reproduction. Also, the least fit ones will die and make space for the new
Selection is the phase where the
fittest individuals are selected to pass their genes to the next generation.
Then crossover happens, for each pair
of parents a crossover point is chosen randomly from their genes and the
offspring is created by exchanging genes from the parents until the crossover
point is reached. After this, the new offspring is added to the set of
Mutation appears only in some of the
new offsprings because some of their genes can be the subject of a mutation,
but this has a very low probability. This means that some bits in the bit
string can be changed.
The algorithm terminates when the
population has converged. This means the algorithm has provided a new optimised
set of solutions to our problem.
applied to our problem
this particular case we will be using a population of 100 to show how the
crossover operator will influence the optimization of a problem. After
experimenting with different population sizes like 1000 and 100, that will be
visible in the graphs below. The number 100 for the population was chosen
because it is big enough to