Implementing the fitness functions

The rosenbrock function

 

Turns out there was no problem with the rosenbrock function. I confirmed this by working through the mathematics by hand. And also adding some test print statements in the program. Here is the output for the last run. The function behaves as expected.

 

 

I then run this function for a two variable problem with a range between -16 and 16 and it was able to converge to a solution of 1,1 for both variables. Proving that the function behaved as expected.

 

 

Note: In the above screen capture, each chromosome is represented in binary with the first value representing the signed bit and the other four representing the floating point value.

The reason it had trouble converging before was because I was running it within the range from -2048 to 2048 then dividing by 1000 in order to search the defined search space between -2.048 to 2.048 .

 

I also changed the chromo2float function so that it takes in a decimal value count. So now it can basically return to you the decimal representation of a chromosome accurate to the number of decimal places you have passed through.

 

 

 

Problems implementing algorithms

The first major problem that held me back for a whole evening was due to the simple fact that my calculator was set to degrees and Go returns values for sin, cos and tan in radians. After setting my calculator to radians and checking that the results for simple calculations matched up between my calculator and Go. I went ahead to start implementing more of the test optimisation algorithms.

The Griewank function

 

 

The Griewank function was proving troublesome as its output after a calculation did not match up with what I got from my paper calculations. I added a debug line (line 26) to see what was going on.

 

 

As can be seen in the above screenshot, “tempProd” which we are using for the dot product is not changing. Additionally, the last line starting with the word “completed”, we can see that the chromosome evaluates to 0 for that chromosome which should return 0 from the griewank function, wet we get a fitness of 1?

Well the problem is on line 15 in the griewank function. Once tempProd has been initialised to 0, any number we multiply it with on line 21 will evaluate to 0. The solution is to set it to 1:

 

 

 

The Rosenbrock function (a problem, that wasn’t a problem)

The rosenbrock function was the next function to pose an implementation challenge as it refused to converge for large dimensions and got stuck at local optima. So the first step in solving this challenge was to grossly simplify the problem. A single loop of optimisation with an unsigned binary chromosome length of 10 bits per variable using only 2 total variables. So our total chromosome length is 20, 10 for each of the two variables. This gives us a huge search space but the binary values are divided by 1000 after they are converted to floats for decimal precision of up to 3 places. This is what the function currently looks like:

 

 

 

We are also limiting the size of our population to 2 individuals for debugging purposes, Here is the output of the function:

 

 

 

As can be seen, this is wrong since the first chromosome represents (0.541,0.518) and should output  5.287546. How do I know this? Pen, paper and a calculator!. The second individual has simply been replaced by the first due to the relative fitness functions behaviour and it’s cloning behaviour.

So the next step is to throw in some debug print statements and see what’s happening in the function!

 

 

So as expected, the loop is only iterating once for each individual as expected from the test setup. So the problem lies within the core of the algorithm. Okay, lets calculate the output for this function using those values. Guess what, the fitness value for the first individuals should be 59.08797; which is the exact same as the programmed function has output for the values of 0.037 and 0.764. And the second values fitness is being correctly evaluated too. So why are we failing to converge? This only leaves one suspect, the only thing that’s different in this function in comparison to others is that we are using the chromo2float function to handle conversion including automating the decimal place precision process.

So let’s convert the two individuals chromosomes to floats by hand and figure out if this assumption is valid. So the first individuals chromosome evaluates to (0.656,0.253) not (0.037, 0.764) as the chromo2float function is currently returning.

Let’s add some more debug print statements and reconfirm that there is no problem with the rosenbrock fitness method:

 

 

 

As you can see, the floating point values returned for X do not match their chromosome.

 

Off to the chromo2float function

So the problem may be originating somewhere in here:

 

 

 

Well looking at the chromo2float function, it becomes clear what the problem was. I was reading the chromosome the wrong way round (left to right) rather than how we had implemented (right to left)

So that’s how I spent a whole morning debugging a problem, that was not a problem.

 

Test Optimisation functions completed and manually tested:

1.       Griewank function

2.       De Jong’s 1st (Sphere) function

3.       Rosenbrock function

4.       Rastrigin function

5.       Axis parallel hyper-ellipsoid function

6.       Rotated hyper-ellipsoid function

7.       Moved axis hyper-ellipsoid function

8.       Schwefel function

9.       Ackley’s function

10.   Bukin’s 6th function

11.   Schwefel’s 7th function

12.   Gramacy and Lee’s function

13.   Levy’s function

14.   Trid function

15.   Sum of different powers function

16.   Zakharov function

17.   MichaleWicz function

18.   Dixon-Price function

19.   Styblinski-Tang function

20.   Matyas function

21.   Branin function

 

Notes:

·         When I was implementing the Levy function, I tried to clear a slice but it turns out the Go has no clear or empty slice function. This issue is covered on stackoverflow.

·         My algorithm re-orders the whole population. Does ‘i’ the incrementer need to remain constant?

·         One of the reasons answers from the functions are different is because Golang cos and sin return radians while my calculator is in degrees. – Make sure to mention that I manually checked the functions by hand, with a pen and paper and discovered this issue.

·         Problem with some algorithm converging if you decide to increase search resolution by returning high resolution floats from the chromo2float function.

·         Possible further flexibility and possible performance improvement if we have a function that returns the slice of floating point values which the chromosome represents. It may even make more sense to add a field for the floating point representation of the chromosome to the individual struct. This is very useful for debugging and readability of code. A much needed future improvement

 

 

Comments   

0 #2 Jon Kerridge 2014-03-25 13:22
Progress has been made in that HFC is well on the way to working.
Next stage is to do lots of runs of the different algorithms and then produce an analysis.

Could even think of parallelising.

Need a poster

Need a detailed map of what you want to write and why. You need to construct a story line
Quote
0 #1 jon kerridge 2014-03-18 13:44
Most impressed lots of functions tested and determined correct by off-line validation using pen paper and calculator.
After discussion with Emma we decided to do the HFC algorithm as a matter of urgency.
I also suggested that he create a set of scripts to automate the data collection process.
Quote

Add comment


Security code
Refresh