Getting to a working prototype

From int to float chromosomes

Since the fitness value is a decimal number between 0 and 1. I had to convert the chromosome to a float32 since there is no decimal type (apparently this was intentional decided during the design of the language). The other option was to multiply every value by 100 but there is a good chance that similar chromosomes may get similar  fitness values for the first 2-4 decimal places. Float32 on the other hand allows for greater precision and requires little change to the current code base. This inadvertently caused an issue with ‘newGeneMat’, the population generation function and all other functions that took in values to create slices and/or matrices. This is because slices and subsequently slices of slices (or matrices) require an integer value to create them, so floats cause errors.

This was solved by removing the type value from the values being passed in, then go seems to do some inference and conversions to the types needed by different functions.

 

 

Roulette Wheel Selection

In order to implement the roulette wheel selection process, during the fitness evaluation we select the fittest and least fit individuals in the population. Then we replace the least fit individual with the fittest one, increasing the chances of the fittest genes being distributed across the population.

Additionally, we had to confirm that  the line 76 assignment was actually passing the values of the of ‘maxIndividual’, to the weakest individual. We learnt previously (in the article ‘Genetic Crossover with Go Slices’) that Go likes to pass references around and doesn’t make deep copies. In this case, it seems to be passing the value around as the genetic crossover are affecting individuals in the population uniquely, even after the roulette wheel selection process.

As can be seen above, individual 1 is the fittest and its values are copied to individual 2’s values (remember this is 0 indexed). Yet in the last 5 lines, individual 1 and 2 have different values showing that go has made a copy of the values and isn’t passing memory address around.

 

The consequences of the roulette wheel selection

The loop that selects individuals for mating in our function is unrolled and deals with two subsequent individuals at a time. This method of mating means that our population has to always be an even number in terms of population size, otherwise the loop in which we select individuals for mating will throw an error when it tries to select an individual that does not exist.

Additionally, since we now have two copies of the fittest individual in the population, in order to prevent that individual from mating with itself, we have to check the population and ensure that the population is not ordered in a manner that will allow this. We carry out mating by picking two subsequent individuals and crossing their genes, so we have to make sure these individuals are different. To do this, we implemented the reflect package’s ‘DeepEqual’ method (line 100) which checks if slices, maps, and fields of structs are equal.

 

During this process, we also learned that Go has no While loop and instead we have to implement a while loop through an infinite for loop and a break statement (line 96 , 155 & 127). We also implemented an isClean (line 97) to ensure that the population is not ordered in a way that would allow for the mating of two individuals who are exact copies of each other. If we find such individuals next to each other, we move one copy to another location within the population, if that doesn’t work and isClean evaluates to false too many times, we reshuffle the whole list and if that does not work, we break out the infinite loop (we may have converged to some kind of solution). We will change this behaviour later on.

 

Mutation Rate and Crossover strategy

We discovered a few interesting behaviours of this implementation of the algorithm. Firstly, if the mutation rate is below 0.009, we take exponentially longer to converge to a solution. The population remains too diverse, even after 1000s of generations.  While a mutation rate of 0.03 will converge by the 50th generation. This will have to be investigated later.

 

We are currently using a single point crossover for mating, but when we tried to use a uniform crossover (the apparently better solution), we got a lot worse performance as the genetic algorithm does not converge to a solution or takes a very long time to do so. In single point crossover, we pick a location in the chromosome and swop all the genes after that point with the genes of the other parent. In uniform crossover (below), we randomly pick multiple different locations within the parents chromosome and swop the genes at those specific points.

This is supposed to offer better performance but instead drastically reduces it in this case. This could possibly be due to the Go random function or the way we have implemented this behaviour in code. This will have to also be investigated later on.

 

Notes:

  1. ·         Converted all ints to float so that I can store the relative fitness.
  2. ·         Select the individuals with the maximum and minimum fitness (we will drop one value at this point. In the HFC model, we keep all of them.)
  3. ·         Remove the weakest Individual
  4. ·         Confirmed that assignment is making a deep copy instead of passing a reference around.
  5. ·         Using reflect deep equal to make sure individuals in crossovers are different
  6. ·         Go has no WHILE LOOP :o, just an endless for loop
  7. ·         Limitations, population size has to be an even number due to structure of for loops. (loop unrolling)
  8. ·         Introduce a count limiter on the off chance that every member of the population is the same.
  9. ·         Interesting link between mutation rate and time to convergence
  10. ·         Current issue is returning a value when population no longer changes much.
  11. ·         Uniform crossover does not converge (possible rand problem, rand is not random enough)

 

 

Comments   

0 #4 Emmanuel K. 2014-02-18 00:55
Quoting Jon kerridge:
Just a quick thought on decimal float tribulations.

The joys of using a new language?!


I wouldn't class it as a joy in this instance. Well there is always a work around most issues.
Quote
0 #3 Jon Kerridge 2014-02-11 13:11
There is no post this week but we had an interesting discussion concerning the fact that GO does not seem to be able to completely consume all the CPU resource. Confirmed by comments on stackoverflow.
Hence it may be possible to use much lower level concurrency that had been initally expected.
There could eb some interesting experiments to see at what point for example you send a pair of chromosomes off in parallel to undertake any genetic operation. How many bits in the string make it worthwhile to run concurrently.

You have discovered things that the community is also just learning about that makes your work current and timely.

lots to do as you now seem to be a bit better having been a bit unwell at the end of last week.

You are building a package to do this and it has a minimal limiatiton that the population has to have an even number of individuals; that is not a real limitation in my view!!!
Quote
0 #2 Jon Kerridge 2014-02-04 13:24
We discussed parallelisation and the problems of the ratio of communication to computation and using multiple processors.
I advised in the first instance, given n is small, just parallelise for a single multi-core processor.
Then investigate larger n type applications where distribution could be helpful. Each level on a separate node and then use the cores to parallelise the internal of level processing.

May need to investigate how you can do distributed paralel in GO but this can wait!!
Quote
+1 #1 Jon kerridge 2014-02-03 12:25
Just a quick thought on decimal float tribulations.

The joys of using a new language?!
Quote

Add comment


Security code
Refresh