A more flexible GA

Refactoring the fitness function

To ensure that the framework could handle any optimisation function thrown at it, I decided that I need to implement all the fitness functions and ensure that they all work as expected with just the plain GA before I implement the HFC structure. This also means that I can get the implementation of all the test algorithms out of the way before going any further.

The initial test algorithm summed the value of every  gene in a chromosome and returned it as the fitness of the individual. The original calcFitness() function implemented this behaviour.

 

 

This obviously meant that it’s hard to swap out functions as you have to always implement any algorithm under the calcFitness() function. First step was to make this scalable. So I implemented it as a function that returned the summed value of all the genes in a chromosome.

 

Then I simply retrieved the result and added it to a variable (popFitSum) for use in the relative fitness calculation. The calcFitness() function now looked like this.

 

It still looked messy and was not scalable so I converted the simpleFit function into a population method and added another attribute called ‘totalPopFit’ to the population struct to store the summed fitness of the population (for use in the relativefitness() function).

 

The relative function was also updated to use the totalPopFit attribute for its calculation making the relative fitness function very simple.

 

 

To call this was simple, under the calcfitness method, I simply called pop.simpleFit() before doing the relative fitness function.

 

This was still not scalable since you have to come into the actual framework code to change which fitness function being used. So I decided that it would make more sense to attach a generic fitness function field to the population struct that could then be assigned to any fitness function as required.

 

Attaching functions and methods to structs

Attaching functions and methods to structs would make it easy to distribute different populations to different machines with their own specific fitness functions to work on should the need arise in future. This also makes it possible to pass different functions to GA’s dynamically (note: although go pretends to be a dynamic programming language, it actually is not).

This task turned out to be more challenging than I expected. Firstly I wasn’t sure if it was possible. So the initial trials were essentially hacking to make something work. I added the following attribute to the population struct.

 

I was unsure if it would work because I am defining a function that takes in a population (or a method of type population), as a field within the population struct itself. I then assigned the simplefit() fitness function during the initialisation of the GA (line 32).

 

This didn’t work as I had expected, I started getting an error code 0 and 2

This error was basically complaining about the use of a field within the struct that takes in a pointer. After removing the pointer and defining a basic function as a struct field (line 42).

 

Error code 2 was no more and I had only error code 0 to deal with.

I then tried to assign it separately, after initialising the population.

 

This didn’t work either. After a couple of hours of hacking failure, I decided to stick the issue up on Stackoverflow using a pseudo-code example. I got voted down for ambiguity but managed to get an answer for this problem (Go Playground).

Turns out that I was making two simple mistake here. A function defined in the struct is inherently a method so it should be called like one and I shouldn’t be using the brackets when assigning a particular method to the pool object . Details on how structs work can be found here.

 

Once this was fixed, error code 0 disappeared. I then changed the calcfitness function to just call the structs fitness function.

 

And this will just run whatever fitness function is assigned to the population.  This now allows me to just define a fitness function and just assign it to the  GA during initialisation and it will just optimise it. To test this, I decided to implement a simple algorithm.

 

De Jong’s Function in the GA

 

The De Jong function is pretty straight forward.

 

Implementing a simple unimodal optimisation function such as De Jong’s Function lead to the addition of  the chromo2float function to the framework. It converts the binary chromosome into its floating point representation (reading from left to right) .

 

 

With this, the framework now allowed for the simple assignment of fitness functions easily.

And the GA would optimise it. The next thing was to change the optimisation options to allow for both maximisation and minimisation problems.

Maximisation and Minimisation GA by Bool

To allow the option to minimise or maximise a function. I added a boolean parameter to the population struct.

 

 This changed the sorting of individuals (high to low fitness or low to high fitness) for use with the relative fitness function depending on the optimisation criteria.

 

I then added a method to the framework that changes the sorting order for the population depending on the Boolean setting.

 

 

Binary or decimal encoding by Bool

The final step was to allow the choice between decimal and binary encoding for the chromosome (mostly because it is easier to debug problems with a decimal chromosome). This was fairly straightforward, I first added a boolean field to the population struct.

 

 

And then changed the population initialisation method to generate individuals using different chromosome encodings depending on whether the chromoDec bool is set to true. This also required an update to the mutation function so that it either mutated on a binary or decimal value.

 

 

Additional Info

Go raises a NaN flag for negative zero (-0). This has to be taken into account and chromo2float must be updated to not return a -0 at any time.

 

There also appears to be some strange behaviour going on with the mutation function in the algorithm.

 

It seems like the random number generator generates the same or similar ranging numbers over a period of time. And several generations could have evolved during that period.

 

Unrelated problem

I tried to push up the new code to the git repository only to be met with the following problem:

‘fatal: could not read Password for 'https://This email address is being protected from spambots. You need JavaScript enabled to view it.': No such file or directory’

There happens to be a bug in 1.8.5.2 msysgit. The solutions is to update Git to its latest version. The problem was also discussed on stackoverflow.

 

Future work:

Now that the basic GA is complete. These are the next things that will be done to the framework.

1.       Investigate the use of the log function for fitness calculation as some calculations may result in numbers that are way too large to be stored in a float64.

2.       Change all functions used directly by the GA to methods

3.       Restructure and distribute the code among different pages. (One page to deal with all algorithm stuff, another for the framework utilities, etc..)

4.       Implement all the test functions and ensure they work with the current framework.

5.       Ensure that the basic GA is working completely well

6.       Implement the HFC hierarchy

 

Notable Pages:

1.       Benchmarking functions for Genetic Algorithms , 2000 by J. G. DIGALAKIS and K. G. MARGARITISy

2.       Methods and slices of methods as struct fields : https://play.golang.org/p/Wz1b203-CI

3.       StackOverflow Question: https://stackoverflow.com/questions/22097142/go-slice-of-methods-and-methods-within-structs/22098940

4.       Test functions for optimization : https://en.wikipedia.org/wiki/Test_functions_for_optimization

5.       Test functions with visualisations : https://www.geatbx.com/docu/fcnindex-01.html

6.       Examples of objective functions : https://www.pg.gda.pl/~mkwies/dyd/geadocu/fcnindex.html

7.       Ensuring that a function returns a real number : https://golang.org/pkg/math/#IsNaN

8.       Page used to double check that chromo2float() worked correctly (reads from right to left, see explain answer button) : https://acc6.its.brooklyn.cuny.edu/~gurwitz/core5/nav2tool.html

9.       Structs and Interfaces : https://www.golang-book.com/9

10.   Initialising members in a struct : https://stackoverflow.com/questions/4498998/how-to-initialize-members-in-go-struct

11.   Go genetic algorithm library 1 : https://github.com/thoj/go-galib

12.   Go genetic algorithm library 2 : https://github.com/rrs/goga

13.   A deep copy function for Go : https://rosettacode.org/wiki/Deepcopy#Go

14.   Useful Code walk : https://golang.org/doc/codewalk/

15.   Some stuff I was dabbling in on converting ints to binary strings then back to ints : https://play.golang.org/p/b0pQMVyjig

 

 

Notes:

·         Figured out how to send functions to struct types. Can now assign a population with a unique fitness function.

·         Making code more readable too.

·         Framework now works with both binary and decimal encoding.

 

 

Comments   

0 #1 Jon Kerridge 2014-03-04 13:47
This was a most enjoyable read in terms of its content flow. I did not read the algorithmic detail.

You MUST capture this development in an appendix to show the sequence through which you went to obtain the final architecture.

This can then be referred to in the main body of the report where you describe the flexible GA architecture.

The list of tasks seems eminently sensible; just go away and do it.

The problem you have is assessing the use by GO of multi-cores. Assessing multi-thread (concurrency) will be perhaps easier.

How about writing it up for the go conference in August. "A Flexible Framework for Analysing Genetic Algorithms Using GO"
Quote

Add comment


Security code
Refresh