Abstract

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.

Introduction

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.

Description

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

generation.

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

individuals.

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.

Methodology

applied to our problem

In

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