Basics of Genetic Algorithm
Before the solution, I will try to explain basics of genetic algorithm using an example, humans.
A child typically has characteristics from its parents say the child has hair color of the mother and hair texture from father. But there will be certain traits which may not be from any of the parents and will be a new trait. If you notice very carefully you will find enough instances and that is how we evolved. The child getting mixed traits from parents is crossover and getting a new trait is mutation.
Now each trait is identified by a DNA and that forms the basis of a genetic algorithm too. Let us represent a DNA with a string of numbers of length 30.
Now when the child inherits the traits from mother and father it is a crossover. For example the point at which the crossover happens is index 12 in the DNA, then the child's DNA will be:
Mother's DNA: 345691254789453680427438234624
Father's DNA: 834623623523473295730945734114
Child's DNA: 345691254789 473295730945734114
When a new trait is created it is a mutation. It happens when a gene in the DNA changes giving it new properties. For example in mother's DNA gene at index 15 changed. Below is an example:
345691254789454680427438234624
A genetic algorithm progresses identical to the process of evolution. The algorithm generates a population and selects the fittest, this keeps on repeating over generations. In a similar way, a genetic algorithm has following phases.
Now as the generations pass and selecting of the best parents in each generation, the algorithm progresses towards a solution. So the genetic algorithm might give a solution or it may
be somewhere close to the solution ?? depending on the number of generations. The solution here evolves as the generations progress.
If you think about evolution in nature you can understand it better. Lets consider an actual problem.
A large number of metal sheets are available in all shapes and sizes. The company needs to cut pieces from that sheet so that there is minimum wastage.
Depending on the number of generations we create, we will get a more optimized solution.
So to write a genetic algorithm we need to define a DNA, the number of crossover and mutation, the number of generations, the population size to be generated.
This is the hardest thing. Lets us define DNA in our case. Robot can see five squares, the square Robot is in, and four square adjacent to it. So the total possible combination of surrounding the Robot can encounter is
3 ^ 5 = 243. So our DNA will have 243 genes.
What is a Gene?Gene is the action Robot performs given a surrounding situation.Robot after inspecting surrounding, he can take following actions. Go north, south, east, west or pick a coin i.e. five different actions, so a gene would have five states numbered from 0 to 4. 0 means go north, 1 means go south, 2 means go east, 3 means go west, 4 means pick coin.
Understanding with an example
Lets us analyze with a sample DNA below. It has 243 genes.
Let us take a sample surrounding situation, it is shown in picture below.

Imagine Robot is center, this is what he sees. North view=1, SouthView=1, EastView=0, WestView=0, CurrentView=0. So to calculate index of gene in DNA we would use following formula
Gene Index = NorthView * 3^4 + SouthView * 3^3 + EastView * 3^2 + WestView * 3^1 + CurrentView * 3^0
So in our case it would be 108, and gene would be “0” ( marked in italics and red color below)
Please read the solution twice as it may not be clear by reading it once.
P.S.
I did one more test run, it found out 852 different solutions . I tried one to verify in simulator. That is correct solution!!
Before the solution, I will try to explain basics of genetic algorithm using an example, humans.
A child typically has characteristics from its parents say the child has hair color of the mother and hair texture from father. But there will be certain traits which may not be from any of the parents and will be a new trait. If you notice very carefully you will find enough instances and that is how we evolved. The child getting mixed traits from parents is crossover and getting a new trait is mutation.
Now each trait is identified by a DNA and that forms the basis of a genetic algorithm too. Let us represent a DNA with a string of numbers of length 30.
Crossover and Mutation with Example
Now when the child inherits the traits from mother and father it is a crossover. For example the point at which the crossover happens is index 12 in the DNA, then the child's DNA will be:
Mother's DNA: 345691254789453680427438234624
Father's DNA: 834623623523473295730945734114
Child's DNA: 345691254789 473295730945734114
When a new trait is created it is a mutation. It happens when a gene in the DNA changes giving it new properties. For example in mother's DNA gene at index 15 changed. Below is an example:
345691254789454680427438234624
A genetic algorithm progresses identical to the process of evolution. The algorithm generates a population and selects the fittest, this keeps on repeating over generations. In a similar way, a genetic algorithm has following phases.
- Define DNA
- Generate parents randomly
- Repeat below steps for number of generation ( 1000 or 10000)
- Crossover and mutate parents randomly to produce a population of children ( 1000 or 10000 children)
- Use fitness function to find strength of each child, associate a score.
- select best two children, they will be parents for next generation, go to step 3
- Display children having best score.
Now as the generations pass and selecting of the best parents in each generation, the algorithm progresses towards a solution. So the genetic algorithm might give a solution or it may
be somewhere close to the solution ?? depending on the number of generations. The solution here evolves as the generations progress.
If you think about evolution in nature you can understand it better. Lets consider an actual problem.
A large number of metal sheets are available in all shapes and sizes. The company needs to cut pieces from that sheet so that there is minimum wastage.
Depending on the number of generations we create, we will get a more optimized solution.
So to write a genetic algorithm we need to define a DNA, the number of crossover and mutation, the number of generations, the population size to be generated.
Problem Solution
This is the hardest thing. Lets us define DNA in our case. Robot can see five squares, the square Robot is in, and four square adjacent to it. So the total possible combination of surrounding the Robot can encounter is
3 ^ 5 = 243. So our DNA will have 243 genes.
What is a Gene?
Understanding with an example
Lets us analyze with a sample DNA below. It has 243 genes.
342030244240140423344044033144111142243143112322432133012140140214212323222400311042242221140243044040311001022213131110331132244201223042244434044212010303132320243030304220103244304122003214343114122422112343123043340113314440210323031021321
Let us take a sample surrounding situation, it is shown in picture below.
Imagine Robot is center, this is what he sees. North view=1, SouthView=1, EastView=0, WestView=0, CurrentView=0. So to calculate index of gene in DNA we would use following formula
Gene Index = NorthView * 3^4 + SouthView * 3^3 + EastView * 3^2 + WestView * 3^1 + CurrentView * 3^0
So in our case it would be 108, and gene would be “0” ( marked in italics and red color below)
34203024424014042334404403314411114224314311232243213301214014021421232322240031104224222114024304404031100102213131110331132244201223042244434044212010303132320243030304220103244304122003214343114122422112343123043340113314440210323031021321
And what action Robot should take when gene is “0”. As outlined above 0 means go north, 1 means go south, 2 means go east, 3 means go west, 4 means pick coin. So Robot will North, which is logical thing to do looking at the surrounding as there gold coin in north direction!! ( refer picture above).
Please read the solution twice as it may not be clear by reading it once.
P.S.
I did one more test run, it found out 852 different solutions . I tried one to verify in simulator. That is correct solution!!
No comments:
Post a Comment