Just for fun, I thought I’d try to learn Go (or Golang as some call it since it’s difficult to Google search ‘go’). I find the best way to learn a new language is to dive in and make as many mistakes as possible. Slowly but surely, the compilation errors die away.
What I discovered is that Go is different from other languages with which I’m accustomed. Go prefers composition whereas other languages, like Java, prefer inheritance. In fact, there is no such thing as inheritance in Go because there’s no such thing as objects. Like C, there are structs, but there are no classes. This doesn’t stop common ideas and design patterns like “constructors” (a way to generate structs in an orderly fashion in this case) from creeping in.
It’s the adoption and stance on composition as well as the resistance to generics in Go that has ignited online wars and has put the direction of the language into question. So, maybe Go isn’t that different.
For my try at the language, I wanted to mimic some of my previous work and create a generic Genetic Algorithm module to solve a variety of problems. If you’re not familiar with these types of algorithms, you read about them in my other posts. The scope of this post will focus on how to achieve a genetic algorithm in Go. I’d also recommend getting a quick introduction to the language if you haven’t already from GoLang Tour.
Let’s immediately dive into some code! The first example is similar to one I’ve done before: finding the minimum of a quadratic.
type GeneticAlgorithmSettings struct {
PopulationSize int
MutationRate int
CrossoverRate int
NumGenerations int
KeepBestAcrossPopulation bool
}
type GeneticAlgorithmRunner interface {
GenerateInitialPopulation(populationSize int) []interface{}
PerformCrossover(individual1, individual2 interface{}, mutationRate int) interface{}
PerformMutation(individual interface{}) interface{}
Sort([]interface{})
}
Right away, I’m defining a group of settings needed to start the algorithm later.
The second part may seem a bit stranger, the GeneticAlgorithmRunner. This is an interface asking for ways to generate the initial population, perform corssovers and mutataions, and to sort the answers so the search keeps the best individual in a population and makes progress over each generation. I say this seems strange because an “interface” is commonly used in object-oriented languages and usually ask objects down the line to implement certain features and methods. There’s little difference here. What this small block of code is essentially saying is that it’s requesting something down the line to define the specifics with these methods. Here’s how I did this:
type QuadraticGA struct {}
func (l QuadraticGA) GenerateInitialPopulation(populationSize int) []interface{}{
initialPopulation := make([]interface{}, 0, populationSize)
for i:= 0; i < populationSize; i++ {
initialPopulation = append(initialPopulation, makeNewEntry())
}
return initialPopulation
}
func (l QuadraticGA) PerformCrossover(result1, result2 interface{}, _ int) interface{}{
return (result1.(float64) + result2.(float64)) / 2
}
func (l QuadraticGA) PerformMutation(_ interface{}, _ int) interface{}{
return makeNewEntry()
}
func (l QuadraticGA) Sort(population []interface{}){
sort.Slice(population, func(i, j int) bool {
return calculate(population[i].(float64)) > calculate(population[j].(float64))
})
}
What’s even stranger here is that I never mention the interface with these methods. Just remember that, since there are no objects in Go, there’s also no inheritance. The QuadraticGA struct is a blank object that implicitly acts as a GeneticAlgorithmRunner. Each required method is bound to this struct in the parenthesis, like an ‘@Override’ in Java. Now that struct and the settings need to be passed to the module that runs the algorithm.
settings := ga.GeneticAlgorithmSettings{
PopulationSize: 5,
MutationRate: 10,
CrossoverRate: 100,
NumGenerations: 20,
KeepBestAcrossPopulation: true,
}
best, err := ga.Run(QuadraticGA{}, settings)
if err != nil {
println(err)
}else{
fmt.Printf("Best: x: %f y: %f\n", best, calculate(best.(float64)))
}
Pretty simple, right? “QuadraticGA{}” simply makes a new instance of that struct and the Run() method does the rest. The method returns the result of the search and any error that happened during, since Go doesn’t believe in try/catch – another war the authors took a strict design stance on.
And now to calculate the performance of each entry against the quadratic function to solve for as well as a way to create a new X value:
func makeNewEntry() float64 {
return highRange * rand.Float64()
}
func calculate(x float64) float64 {
return math.Pow(x, 2) - 6*x + 2 // minimum should be at x=3
}
So now that the interfaces have been created for the Quadratic implementation, the GA itself needs to be completed:
func Run(geneticAlgoRunner GeneticAlgorithmRunner, settings GeneticAlgorithmSettings) (interface{}, error){
population := geneticAlgoRunner.GenerateInitialPopulation(settings.PopulationSize)
geneticAlgoRunner.Sort(population)
bestSoFar := population[len(population) - 1]
for i:= 0; i < settings.NumGenerations; i++ {
newPopulation := make([]interface{}, 0, settings.PopulationSize)
if settings.KeepBestAcrossPopulation {
newPopulation = append(newPopulation, bestSoFar)
}
// perform crossovers with random selection
probabilisticListOfPerformers := createStochasticProbableListOfIndividuals(population)
newPopIndex := 0
if settings.KeepBestAcrossPopulation{
newPopIndex = 1
}
for ; newPopIndex < settings.PopulationSize; newPopIndex++ {
indexSelection1 := rand.Int() % len(probabilisticListOfPerformers)
indexSelection2 := rand.Int() % len(probabilisticListOfPerformers)
// crossover
newIndividual := geneticAlgoRunner.PerformCrossover(
probabilisticListOfPerformers[indexSelection1],
probabilisticListOfPerformers[indexSelection2], settings.CrossoverRate)
// mutate
if rand.Intn(101) < settings.MutationRate {
newIndividual = geneticAlgoRunner.PerformMutation(newIndividual)
}
newPopulation = append(newPopulation, newIndividual)
}
population = newPopulation
// sort by performance
geneticAlgoRunner.Sort(population)
// keep the best so far
bestSoFar = population[len(population) - 1]
}
return bestSoFar, nil
}
func createStochasticProbableListOfIndividuals(population []interface{}) []interface{} {
totalCount, populationLength:= 0, len(population)
for j:= 0; j < populationLength; j++ {
totalCount += j
}
probableIndividuals := make([]interface{}, 0, totalCount)
for index, individual := range population {
for i:= 0; i < index; i++{
probableIndividuals = append(probableIndividuals, individual)
}
}
return probableIndividuals
}
Very much like before, a new population is created, and members of the population will mate over generations while their offspring may carry mutations. The better an individual performs, the more likely it is to mate. Over time, the algorithm converges to the best answer, or at least a pretty good one.
So what does this return when it’s run?
Best: x: 3.072833 y: -6.994695
Not bad at all! With a population size of only 5, 20 generations, and the range of inputs being restricted to [0,100], this search about nailed the vertex.
Now, you may be wondering why I defined all of the interface methods to return “interface{}”. This is as close as Go has to generics. There are no objects so there are no object types to return, but data of a nondescript size can still be passed around on the stack. This is essentially what this return type means too: it’s passing some type of objects of a known and similar type back and forth. With this “generic”, I’m able to move the GA to its own package and the same code against multiple different types of data.
Say instead of a single input for a 2D quadratic we have two inputs for a 3D quadratic. Only small changes are needed for the interface methods:
type Quad3D struct {
x, y float64
}
func makeNewQuadEntry(newX, newY float64) Quad3D {
return Quad3D{
x: newX,
y: newY,
}
}
func calculate3D(entry Quad3D) float64 {
return math.Pow(entry.x, 2)- 6 * entry.x + math.Pow(entry.y, 2)- 6 * entry.y + 2
}
type Quadratic3dGA struct {
}
func (l Quadratic3dGA) GenerateInitialPopulation(populationSize int)[]interface{}{
initialPopulation := make([]interface{}, 0, populationSize)
for i:= 0; i < populationSize; i++ { initialPopulation = append(initialPopulation, makeNewQuadEntry(makeNewEntry(), makeNewEntry())) } return initialPopulation } func (l Quadratic3dGA) PerformCrossover(result1, result2 interface{}, mutationRate int) interface{}{ r1Entry, r2Entry := result1.(Quad3D), result2.(Quad3D) return makeNewQuadEntry((r1Entry.x + r2Entry.x) / 2, (r1Entry.y + r2Entry.y) / 2,) } func (l Quadratic3dGA) PerformMutation(_ interface{}) interface{}{ return makeNewQuadEntry(makeNewEntry(), makeNewEntry()) } func (l Quadratic3dGA) Sort(population []interface{}){ sort.Slice(population, func(i, j int) bool { return calculate3D(population[i].(Quad3D)) > calculate3D(population[j].(Quad3D))
})
}
func quadratic3dMain(){
settings := ga.GeneticAlgorithmSettings{
PopulationSize: 25,
MutationRate: 10,
CrossoverRate: 100,
NumGenerations: 20,
KeepBestAcrossPopulation: true,
}
best, err := ga.Run(Quadratic3dGA{}, settings)
entry := best.(Quad3D)
if err != nil {
println(err)
}else{
fmt.Printf("Best: x: %f y: %f z: %f\n", entry.x, entry.y, calculate3D(entry))
}
}
Instead of passing around float64s everywhere, Quad3D entries will be passed everywhere; each one holding an X and a Y value. For each entry that’s created, it’s created using the contructor, makeNewQuadEntry. None of the code in the Run() method changed.
Now when this is run, we get this output:
Best: x: 3.891671 y: 4.554884 z: -12.787259
Pretty close again!
Oh ya, did I forget to mention that Go is FAST!? When this is executed in Java, there’s a noticeable wait time even with the same settings. It’s not much since solving for a quadratic in a relatively small range is not that computationally exhaustive, but it is notable to an individual.
Go is natively compiled like C is. When the binary executes, it seems to spit out an answer damn near instantly! Here’s a simple way to measure the execution time of each run:
func main() {
beforeQuadTime := time.Now()
quadraticMain()
afterQuadTime := time.Since(beforeQuadTime)
fmt.Printf("%d\n", afterQuadTime)
before3dQuadTime := time.Now()
quadratic3dMain()
after3dQuatTime := time.Since(before3dQuadTime)
fmt.Printf("%d\n", after3dQuatTime)
}
Side note: can I just say I’m so happy we’re learning as a community of developers to move past the mistakes of the past and have comprehensive time modules and packages built into a language? Java 8+ has them, Python has them, and Go has them. This makes me happy.
Now here’s the output:
Best: x: 3.072833 y: -6.994695 136,876 Best: x: 3.891671 y: 4.554884 z: -12.787259 4,142,778
That “damn near instant” feeling I was trying to convey before, now we have hard numbers to it. 136,876 seems large, but Go reports time in nanoseconds.
Read that again: nanoseconds. Not milliseconds, which we’re all accustomed to in the age of the Internet or with other common languages like Python and Java; nanoseconds. 1/1,000,000 of a millisecond.
That means we found a close answer to the quadratic using genetic algorithms to search for the answer in less than a millisecond. The phrase, “Damn near instant” seems quite appropriate now, doesn’t it? And that includes the printout to the terminal.
Okay, so what about something more intensive to compute? Before I showed one way to find good fantasy football lineups for use in Fanduel. This involves reading data from a spreadsheet, making and filtering lineups, and conducting more complicated crossover and mutations. Brute forcing to find the best solution could take over 75,000 years (at least using the Python I had used at the time).
I don’t need to go over all of the details again – you can go look at the code yourself, but I’ll show the output here:
Best: 121.409960:, $58100 QB: Aaron Rodgers - 23.777778 RB: Latavius Murray - 15.228571 RB: DeMarco Murray - 19.980000 WR: Kelvin Benjamin - 11.800000 WR: Stefon Diggs - 14.312500 WR: Alshon Jeffery - 9.888889 TE: Connor Hamlett - 8.200000 D: Philadelphia Eagles - 10.777778 K: Phil Dawson - 7.444444 16,010,182
Oh yes! Now that looks like a good lineup! And it only took 16 milliseconds to find.
Now, this genetic algorithm could be improved. Like C, objects (read data) are copied on the Stack when they’re passed to a method. As objects grow in size, it’s best not to copy them over and over again but to create them in the Heap and pass pointers around instead. For the time being, I’m going to leave that as future work.
Go is also written with native support with coroutines and channels, making utilizing multiple cores to solve a problem much easier than they have been in the past and giving Go a huge advantage over other languages that came out of the single-core era. I’d like to enhance this algorithm to utilize these tools, but that will also have to be left for future work.
I’ve enjoyed learning Go overall. It was difficult for me to think of engineering solutions using composition instead of inheritance as the latter is what I’ve been accustomed to for over eight years and is the way I learned to program. But each language and way of doing things has their own pros and cons; each language is a different tool in my toolbelt. For anyone worried about giving it a try, don’t. There’s a hump (more like a speed bump), but you’ll quickly get over it and on to the road to success.
There are also a few things I miss in Go that I love in other languages, mostly a basic set of functional methods to manipulate data. I long for a lambda function and ways to map, reduce, and filter an array or slice of data. The argument the designers gave against the functional implementations is that code should always be simple and easy to read and write, and that this is accomplishable with for loops. I argue that mapping, filtering, and reducing is generally easier to read and write, but this is an argument in a war that’s already raging.
Despite my disagreements with some of the developers’ opinions and the different ways I had to think about solving problems, Go really is a nice language. I would encourage everyone to give it a try after you learn a language or two. It’s quickly becoming one of the most popular languages out there, and there are plenty of reasons to see why that is. I look forward to using it more in the future.
5280 In Code 
One thought on “Go with Genetic Algorithms”