Sunday, July 31, 2011

Genetic Algorithm - Part 10 - Algorithm Correctness

How do you know that the genetic algorithm one has coded is correct. It is possible that the algorithm is arriving at a solution, but how one verifies that the algorithm is correct.

I have been rewriting the solution in C#, I have already created the basic structure for genetic algorithm using multithreading. Since I already had a SQL implementation of the same, I was importing the generated DNAs for a generation in C# and applying the fitness function on it in C#.
So the next step was to complete the full algorithm in C#. I coded the complete algorithm and ran it but the solution was not converging. The fitness score increased to 460 (maximum being 500 which is a solution) and it started coming down. I obviously cannot debug a genetic algorithm as I usually debug the code. I looked at the code for a couple of days but couldn't find the problem. So I need to try another way.

I already have a SQL version of the solution, so I exported the set of DNAs for the generation where the fitness score started coming down into SQL server. I realized that the DNAs in that generation had different parents which is incorrect. This was causing the solution not to converge.

I looked at the code and found that the multiple threads which were creating the DNAs for a generation, finds the DNAs with the best fitness score from each of its set of DNAs. Now in the common list used by main thread, the parents were getting overwritten which was causing the issue.

One criteria for the algorithm correctness is that the fitness score should always increase as the generations progress, that is by definition of evolution. And it is evolution what we are using in the algorithm.

So far i have successfully implemented a multi-threading solution for the problem. The next step is to have more realistic conditions in the algorithm which I will describe in the next post.

Tuesday, July 5, 2011

Genetic Algorithm – Part 9 - Optimum number of threads

How many threads one should create to get optimum performance? In my case how many child threads should I create on an given environment. I would be running this on different configurations. Some might have four processor core and some sixteen.

The logical answer is number of threads should be equal to number of processor cores. The idea is to keep all the processor cores busy at all times.Below are timings for tests done on 16 processor core machine, the code contains CPU intensive algorithm.

As we can see the best performance we get is when number of thread is slightly less than total number of cores i.e. between 12 to 16 threads. We need to keep couple of cores idle for other OS related threads.


In the application I would allow user to select number of child thread he wants to use. This would give user a chance to evaluate performance.

Genetic Algorithm – Part 8 - “Lock” can be expensive

I was doing multithreaded implementation of this this solution. I came out with two approaches.

Approach 1

There will be main thread and number of child thread ( number of child thread is equal to number of processor cores).
The main thread does following
  • Randomly selects cross over and mutation points for all children.
  • Selects top two children which would be parents for the next generation. 
  • Wait for all child threads to complete its tasks.
A Child thread does following
  • Creates new child from parents using cross over and mutation points.
  • Use fitness function to calculate score of child.
Looking back at the approach, I thought the main thread would do its work and wait for all the children to complete their work. To optimize I thought of other approach, which is summarized below.

Approach 2
There is no “designated” main thread, the child which complete its work first becomes main thread, it does task outlined in approach 1 for main thread and then transforms into child thread. I thought using this approach no thread would be significantly idle now. 

I had already used Approach 1, so I quickly but properly modified the code to use Approach 2. I took readings which I have outlined below.I was bit shocked. The time taken for Approach 2 was significantly higher (21%) than Approach 1. Below are the comparison.


I did some analysis to find out what went wrong. I ran the code for 10000 generations, instead of 1000 generations. Art of multithreading requires minimum use of  synchronization constructs between threads. In writing this implementation I have taken great pain to avoid “locks”, even main and child thread approach looked like producer and consumer pattern I had implemented it without “locks”. I will post the strategy for that in another post.

In Approach 2 however I had to use “one” additional “lock” statement so as to decide which child thread becomes main thread and it does main thread tasks while other “late” child thread waits. 

Below are the wait timings of child thread for both approaches which would reveal why Approach 2 took longer time.

Wait timings for child thread in Approach 1


















Wait timings for child thread in Approach 2


















In approach 1 average wait time was 22 secs which had become almost 1 minute 21 sec in approach 2, which accounts for the difference of timings. 

Remember take great care in adding “lock” in multithreaded code, even one additional synchronizing construct can your affect your applications scalability and performance.

In next post i will write about how many threads I should create on a given environment.

Sunday, July 3, 2011

Genetic Algorithm – Part 7 - Compare SQL and C# code

Now it is time to compare SQL and C# implementation. Below are the comparisons for 1000 generations.


The results are staggering the C# code is working way faster. There is couple of reason for that. First one uses of all processor cores. Picture below is for C# code, use can see all the processor cores being utilized properly.

(click on image to enlarge)


Below is the CPU utilisation for SQL code.






If you look at the CPU utilization in case C# all the cores are being used, while in case of SQL only one core is being used. If you look carefully in picture at the CPU usage percentage is 78.03 % for C#, while it is 8.77% for SQL.

Second reason is I have to represent DNA, board and other constructs as string in SQL and do manipulations, while I have data structure like arrays in C#, which has proved to be faster. Remember each code path runs one million times, so even slight benefit turns out to be significant gain in the end.

Friday, July 1, 2011

Genetic Algorithm – Part 6 - Benchmark multithreaded C# code

I did several runs on various machines and below are the reading and they speak for itself. First up comparison on 2 core and 16 core.



























Above reading might be puzzling to some who might have thought 16 core machine should have taken 9 sec. I have been part of discussions where software engineers have argued that if one thread takes X time then then eight thread should do work in X / 8 time.Apart from IO, memory bottlenecks that can happen between threads.Even before you can do multithreading the moment you have multiple processor there are bottlenecks.

When we have a system with just one processor, and if we add three more, we will not have four times the performance. This is because each time we add a processor, the time they dedicate to coordinate their work and the task assignment process increases. Table below summaries it best.



In next post I will compare performance between SQL and C#.

Genetic Algorithm – Part 5 - Multithreading bugs

I almost completed skeleton code for C# implementation and it was time to test. I did several round of testing with various configurations on different machines. I found a strange defect in code which took me almost 5 hours to resolve. Below is a screenshot where the application hangs as main thread waits for all child thread to complete. You can see the application stopped after 47 iterations.


The error was with following code.
Interlocked.Decrement(ref threadStartedCounter);
This is supposed to "Decrements (decreases by one) the value of the specified 32-bit variable as an atomic operation." but i figured out it was not on Windows XP when I had 16 threads on 2 core processor. I modified the code not to use Interlocked class and it was working fine.

If you are testing on XP (chances are high as when Vista was developed it was not Microsoft's finest hour) , you might have to apply patch below so that optimum use of cores takes place.
http://support.microsoft.com/kb/896256

Now I have to take readings which will be published in next post.

Wednesday, June 29, 2011

Genetic Algorithm – Part 4 - Benchmark existing solution

The first step was to benchmark performance for SQL server implementation. I did benchmark on two machines. Below are the readings for 1000 Generations. On both machines it takes 20 min. 


Remember the high end machine has 16 cores. However it is observed that SQL implementation is not able to take any advantage of huge processing power. Ironically there are only few products which scale to such huge processing power and one of the reasons for that is difficulty in re-writing existing software to use multiple cores effectively. Note also multithreaded programs are difficult to write and test. 

So now for C# implementation time to beat is 20 mins.

P.S.
One of the product which does fantastic use of multithreading is Metal Ray.

Sunday, June 19, 2011

Genetic Algorithm – Part 3 - Realising constraints of time and space

I had the original code for the problem in SQL Server and the solution takes 1-2 hrs to complete but it works. Since the solution takes so it looks that nobody would use it. I have just started and it was a big jolt. It is very important to make progress on idea, and to make progress one needs to work, one cannot think infinitely.

I will start writing the code in C# with multi-threading and see if I am able to improve the performance. Also,  I will work on creating a UI to show the actual evolution of the solution.

I started work on my first task "Convert into multi-threaded app, so as to use all the cores of processor" and soon found out to make optimum use of all cores of processor is not an easy ask. I found couple of solution, but somewhere knew they were not elegant. Frustration came and went, persistence is a good virtue to have and by day end I had a skeleton which would optimize for all cores.

I am making slow but steady progress.

Friday, June 17, 2011

Genetic Algorithm - Part 2 - The Solution

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.

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.
  1. Define DNA
  2. Generate parents randomly
  3. 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
  4. 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
    Defining DNA
    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.

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

    Thursday, June 16, 2011

    Genetic Algorithm - Part 1 - The Problem

    Below is the problem
    A robot has a board (like chess board) with some gold coins (50 coins on board of 10 X 10) in random squares. The red box is Robot, 0 means empty square, 1 means gold coin in square and there is walls surrounding the board.

    o 

    Robot can only see the current square he is in and four adjacent squares ( limited memory), so based on surrounding he can take following actions
    • Go in any of four directions
    • Bend and pick coin in the square he is in.
    However there is a catch, If robot moves into wall or he bends and tries to pick up gold in empty square he gets negative marks.

    The objective is to after studying the world he is in robot must
    • Come with a strategy to pick all the coins without scoring any negative points and that too in minimum moves i.e. if you score all 500 points in 100 moves its great.
    • Get all possible combination of strategy.
    Problem Explained
    The robot cannot go over all the squares one by one and pick up where there is a gold coin. Someone would think I would write nested for loop and I am done.

    We want you to come with what action robot will perform in a given surrounding.The robot has limited memory and the actions need to be defined for a robot. This implies:
    • At a certain position in a grid the robot is in, it has no idea which direction or from where it came to that position.
    • Given a surrounding, the robot will always take the same action.
    Just to give you idea how difficult it is to arrive at solution can be, consider scenario 1 below.
    Scenario 1
     Red square is where Robot is, now you decide to go left in this situation.You get scenario as below.
    Scenario 2
     Now if you decide that in this scenario robot move right, you get   scenario below which is same as first scenario and you are in deadlock!!
    Scenario 1 again

    Now try to find a solution iteratively or by working out a solution on paper to realize the complexity of the problem.

    If you wonder if this a complex problem worth discussing here. If we try to solve it iteratively, there are 7.074 e+169 combinations to find a solution from.

    So we will use genetic algorithm to solve the problem. Genetic algorithms are typically used for approximation/optimization problems.

    In my next post I will describe the solution to the problem.
    Genetic Algorithm - Part 2 - The Solution