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.
- · Converted all ints to float so that I can store the relative fitness.
- · 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.)
- · Remove the weakest Individual
- · Confirmed that assignment is making a deep copy instead of passing a reference around.
- · Using reflect deep equal to make sure individuals in crossovers are different
- · Go has no WHILE LOOP :o, just an endless for loop
- · Limitations, population size has to be an even number due to structure of for loops. (loop unrolling)
- · Introduce a count limiter on the off chance that every member of the population is the same.
- · Interesting link between mutation rate and time to convergence
- · Current issue is returning a value when population no longer changes much.
- · Uniform crossover does not converge (possible rand problem, rand is not random enough)