Genetic crossover with Go slices

Attempting to do genetic crossovers in Go proved to be a challenge that requires a little ingenuity. The key is to remember that Go is based on C, so deal with such problems as if programming in a CSP version of C. The challenge with the genetic crossover is also partially due to the inexperience in Go thus far. Anyway so how did we do the crossover.

The first attempt:

The first failed attempt was fairly straight forward:

 

This attempt failed due to the fact that the copy function in Go is not exactly as straightforward as it seems. What is actually being passed to ‘tempSlice’ is a reference to the ‘pop’ elements. Since this isn’t a deep copy, line 40 overwrites the values held in ‘tempSlice1’ with the values of ‘tempSlice2’. And gives us the following output:

As can be seen, this behaviour result in only one of the parents swapping it’s genes.

The second attempt:

This attempt failed simply failed due to newbie inexperience. It turns out that you can’t assign to a subsection of a slice.

 

The third attempt:

In the third attempt, we attempted to use append which failed with a strange error.

Turns out that in order to append multiple items to a slice, the addition of three dots to the second parameter in the append function is necessary.

And this appears to work in a sense, but let’s actually do a crossover instead of reconstructing the individuals and see what happens.

We are now taking the genes from the second individual and appending them to tempGene1 and vice versa. Yet the behaviour of the output appears quite strange.

This appears quite strange, FChromo are the children of Chromo yet as it can clearly be seen, we have lost values for Fchromo 1 as it should ‘11100’. Additionaly, Chromo 2 and its child FChromo 2 are exactly the same.

 

To investigate this behaviour, lets change the encoding back into decimal values and add some debug comments.

After analysing the output of the program, it becomes painfully clear what the problems is.

Hey remember the problem in attempt 1, well its manifested itself again in some strange form. It seems that append also passes a reference around which means that even if we cleanly initialise and assign the temp variables (line 37 and 38), it seems like the next assignments on lines 40 and 41 pass a reference to a sub-slice of the original individuals which then causes a mess when appending. If we look at the output from the original ‘Chromo’ values which we have not directly manipulated (last line in the above screenshot), it can be seen that they have changed proving that our hypothesis about what is going on is correct.

More evidence for this can be seen below, we have also changed the assignment to see if it has any effect and made the debug messages clearer:

Output:

As can be seen, the parent values are linked directly to the children’s values due to the internal referencing system.

This leaves us with few options, last one being having to build our own deep copying function for this genetic algorithm. So let’s first exhaust our options.

The fourth attempt:

As can be seen above, lines 37, 38 initialise and assign the tempGene variables to empty slices with the capacity to hold the number of values needed to represent each individual’s chromosome.

Output:

 We finally have the initial desired behaviour from the crossover function. Next challenge!!

Note: This solution only works for the particular type of crossover whereby you swap all of the elements after a certain point between parents. A deep copy mechanism may be required for more complex crossover functions such as when values of the chromosome between two parents are swapped at multiple points stochastically. We have prototyped a method for this crossover technique that may prove to be more efficient than all previous attempts (see below).

 

Comments   

0 #1 Jon Kerridge 2014-01-26 21:40
wow that was exhaustive and will make good content for the report as you have all the code and output to show what you tried. well done!
Quote

Add comment


Security code
Refresh