0

Genetic Algorithm

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:-

• Gene
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.

• Chromosome
It has a series of genes that forms the solution.

• Individual
Individual is same as chromosome.

• Population
Population is the number of individuals that has the same length of chromosome.

• Fitness
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
Mutation is to randomly change the gene in an individual.

• Selection
Selection is a process to choose the individuals in order to create the next generation.

facebooktwittergoogle_plusredditpinterestlinkedinmailby feather
1 Star2 Stars3 Stars4 Stars5 Stars (No Ratings Yet)
Loading ... Loading ...

chin yee

Leave a Reply

Your email address will not be published. Required fields are marked *

Current day month ye@r *

What is 13 + 3 ?
Please leave these two fields as-is:
IMPORTANT! To be able to proceed, you need to solve the following simple math (so we know that you are a human) :-)