Several months ago, I read a blog regarding of the application of genetic programming that paints out a Mona Lisa painting (Referring to Roger Alsing Weblog – Genetic Programming: Evolution of Mona Lisa). I nearly forgot about this topic for more than one year since I graduated and that blog reminds me again with ‘Genetic Algorithm’. What is so special with Genetic Algorithm (GA) or Genetic Programming and why it brings such a remembrance to me? Genetic Algorithm was my final year project’s research topic and I have to apply this algorithm to develop a shift scheduling system.
What is Genetic Algorithm?
I certainly believe that the algorithm is being named in such way just because it works quite similar with human genetics and reproduction. Genetic Algorithm is also known as evolutionary algorithm and is based from Charles Darwin’s evolution theory. It is often used to solve large or complex problems because it chooses the best solution in the problem space that will result the reduction of search space. During the selection process, the best case will survive whereas the worst case will be eliminated or killed.
Important Terms of Genetic Algorithm
There are several important terms that need to know before it can be applied as part of the development. The important terms consist of:-
A gene is a part of the chromosome or the solution. For example, 12345 is a chromosome and 1, 2, 3, 4, and 5 are its genes.
It has a series of genes that forms the solution.
Individual is same as chromosome.
Population is the number of individuals that has the same length of chromosome.
Each individual has specific fitness values which based on the intimacy of the individual with the solution. The higher the fitness value, the better the solution that the individual contains.
• Breeding or Crossover
It involves the process of swapping the chromosomes from two fit individuals in order to create two new individuals. There are three common types of crossover which consists of one point, two point, and uniform.
One point crossovers is to split the parent chromosome into two parts and copy the left half with the right half of another parent chromosome to create a new generation. For example, if the crossover point is 2, the swapping of 11110000 and 11100011 will create two new individuals which are 11110011 and 11100000.
As for two point crossovers, it did the same thing with one point crossovers but it splits the parent chromosome into three parts. For example, if the crossover point is 3, the swapping of 11110000 and 11100011 will create two new individuals which are 11100011 and 11110000.
The uniform crossovers will randomly crossover the genes from each parent to create new chromosome. For example, the crossover of 11110000 and 11100011 will create two new individuals which are 11100000 and 11111100.
Mutation is to randomly change the gene in an individual.
Selection is a process to choose the individuals in order to create the next generation.