Genetic Algorithm using Java
This article is focused on simple implementation of Genetic
Algorithm(GA) using Java. If you want to learn more on GA, you can start from
here.In the implementation, I will be discussing 3 major operators
which are Selection, Crossover and Mutation. Each operator will be discussed separately.
Population
Initially we have to generate a random population of chromosomes
in order to continue with above mentioned operators. Size of the initial
generation should be defined based on the problem that we are going to solve
using GA.
Selection
Purpose of this operator is to select best chromosomes out
of entire population in order to generate a new population. Selection will be
done based on the Fitness value. Fitness value is the factor we use to measure
the strength of each gene and it will be calculated using a Fitness
Function which is totally based on the problem we are dealing with. There
are couple of selection approaches available which based on fitness value. This article will focus on Tournament
Selection mechanism when selecting parent chromosomes.
Crossover
Crossover is performed on two best chromosomes. Best chromosome
parents are selected on the fitness value. Each parent chromosome will donate a
part from itself to create a new child chromosome. This part of each parent can
be selected based on couple of methodologies. Single Point crossover, Multi-point
crossover or Uniform crossover. This article will be using Single point
crossover to keep this simple and easy to understand. In the implementation,
there is one more value that we need to consider which is Crossover probability. This indicates the ratio of how many
chromosomes couples to be selected in the population. More details on these can
be found in here.
Mutation
Mutation is performed on chromosome by flipping one or more
gene values. This is done in order to maintain the genetic diversity among the
population. It helps to avoid the algorithm from getting stuck in local optimum
solution and move towards the global maximum. Mutation Probability is another factor like Crossover Probability
which indicates how many genes to be mutated in a chromosome. There are few
methods of performing mutation on a chromosome but this article will be focusing
only on bit inverting approach. More details on mutation methods can be found here.
Java Implementation
Evolution (Main Class)
Comments
Post a Comment