Go language implementation of genetic algorithm example code

Before I introduce the text, I would like to add some basic knowledge and examples of go language.

Go Language tutorial

Go is an open source programming language that makes it easy to build simple, reliable, and efficient software.

Go was developed by Robert Griesemer, Rob Pike, Ken Thompson at the end of 2007. Later, Ian Lance Taylor, Russ Cox and others were added. Go was finally open source in November 2009 and stable version of Go 1 was released in early 2012. Go is now fully open for development and has an active community.

Go language features

Simple, fast and safe
Parallel, fun, open source
Memory management, v array security, fast compilation

Go language USES

The Go language is designed as a system programming language for use with Web servers, storage clusters or similar giant central servers.

Go is undoubtedly more efficient than most other languages in the field of high-performance distributed systems. It offers massive parallelism, which is great for game server development.

The first Go program

Next, let's write the first Go program, hello.go (the extension of the Go language source file is.go), as follows:

The instance

package main
import "fmt"
func main() {
  fmt.Println("Hello, World!")
}

Execute the above code output

$ go run hello.go 
Hello, World!

All right, here we go.

For fun, I decided to learn 1 Go. I think the best way to learn a new language is to study deeply and make as many mistakes as possible. While this may be slow, it ensures that compilation errors never occur again later in the process.

Go is different from any other language I'm used to. Go prefers its own implementation, while other languages like Java prefer inheritance. There is no inheritance at all in Go because there is no object. C, for example, has structures but no classes. But then it can still have common ideas and design patterns like "constructors" (1) the way structures are produced in order in this case.

The Go language, which is strongly pro-composition (composition) and strongly anti-inheritance, has generated a lot of discussion on the Internet and caused people to rethink the direction of language development. So, from this perspective, the Go language may not be that different from other languages.

This paper will focus on how to implement genetic algorithm with Go language. If you haven't participated in GoLang Tour, I also suggest you take a quick look at the introduction to the language.

Without further ado, let's start with the code! The first example is very similar to what I've done before: find a minimum twice.

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{})
}

I immediately defined a set of Settings to be used in the algorithm that I started later.

GeneticAlgorithmRunner in Part 2 this looks a little strange. GeneticAlgorithmRunner is an interface that asks how to generate the initial population, perform corssovers and mutataions, and sort the answers to keep the best individuals in Population so that the next generation will be better. I think this seems strange, because "interfaces" are usually used in object-oriented languages, and usually require objects to implement certain features and methods. There's no difference here. This little piece of code is actually saying that it's asking for something to define the details of these methods. Here's what I did:

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))
 })
}

Even stranger, I never mentioned the interfaces to these methods. Remember, there are no objects and no inheritance. The QuadraticGA structure is a blank object that implicitly ACTS as GeneticAlgorithmRunner. Each required method is bound to the structure in parentheses, like "@override" in Java. Now, the structure and Settings need to be passed to the module running 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)))
}

Simple, right? #63; "QuadraticGA {}" simply creates a new instance of the structure, and the Run() method does the rest. This method returns search results and any errors that occur because Go does not believe try/catch - another war author took a strict design stance.

Now let's calculate the performance of each item, so as to find a new method of 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
}

Now that the interface has been created for the two implementations, GA itself needs to be done:

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
}

Much like before, a new population is created, members of which will mate for generations, and their offspring may carry mutations. The better a person performs, the more likely they are to mate. Over time, the algorithm converges to the best answer, or at least a fairly good answer.

So when it runs, what does it return? #63;

Best: x: 3.072833 y: -6.994695

Not bad! Since the population size is only 5 or 20 generations and the input range is limited to [0, 100], the 1 search is nailed to the top.

Now, you might wonder why I've defined all the interface methods to return "interface {}". This is just like Go and generics1. There is no object, so no object type is returned, but data with no size described can still be passed on the stack. This is essentially what this return type means: it passes objects of some known and similar type. With this "generic", I can move GA to its own package and move the same code to multiple different types of data.

We have two inputs of 3D quadratic equation instead of a single input of a two-dimensional quadratic equation. Interface methods require only minor changes:

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 float64s everywhere, the Quad3D entry is available everywhere; Each one has an X and an Y value. For each entry created, contructor makeNewQuadEntry is used. None of the code in the Run() method has changed.

When it runs, we get this output:

Best: x: 3.891671 y: 4.554884 z: -12.787259

That's close!

Oh, I forgot to say fast! When you do this in Java, even with the same Settings, there is a noticeable wait time. Solving quadratic equations over a relatively small range is not very complicated, but it is worth noting for one person.

Go is compiled locally, such as C. As base 2 executes, it seems to spit out an answer right away. Here is a simple way to measure the execution time per 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 say how glad I am that we are a developer community that has moved on from the mistakes of the past and built the integrated time modules and packages into a language? Java 8 + owns them, Python owns them, and owns them. It makes me happy.

Current output:

Best: x: 3.072833 y: -6.994695
136,876
Best: x: 3.891671 y: 4.554884 z: -12.787259
4,142,778

That "almost instant" feeling is what I want to convey, and now we have hard Numbers. 136,876 looks big, but report the time in nanoseconds.

Once again: nanoseconds. Not milliseconds, we're all used to the Internet age and other lingua franca like Python and Java; A nanosecond. 1/1000000 of a millisecond.

This means that in less than a millisecond we have found an answer to a quadratic equation that USES a genetic algorithm to search for the answer. The phrase, "the damn moment" seems appropriate, doesn't it? This includes printing to the terminal.

Now, what about counting something denser? Before I show you one way to find a good fantasy soccer lineups, I use Fanduel. This includes reading data from spreadsheets, making and filtering lineups, and making more complex crossings and mutations. Forcing the search for the best solution may take more than 75,000 years (at least using the Python I was using).

I don't need to go through all the details, you can look at the code yourself, but I'll show the output here:

$ go run hello.go 
Hello, World!

0

Oh, yes! Now it looks like a good squad! It only takes 16 milliseconds to find it.

Now, the genetic algorithm can be improved. As with C1, when an object is passed to a method, the object is copied on the stack (the data is read). As objects grow in size, it is best not to copy them repeatedly, but to create them in the heap and pass Pointers around. At present, I will take it as my future work.

Go was also written with native support for coroutines and channels, using multiple cores to solve a single problem, which was a huge advantage over other languages of the single-core era. I would like to enhance the algorithm to use these tools, but that too must be left to future work.

I really enjoy the learning process. It's hard for me to think about engineering solutions in terms of composition rather than inheritance because I'm used to 8 + years and that's how I learned to program. But each language and approach has its own advantages and disadvantages; Each language is a different tool in my toolkit. For anyone worried about trying, don't. There's a hump (more like a speed bump), but you'll soon get over it and on the road to success.

There are a few other things I like, and I like other languages, mainly a set of basic functional methods to manipulate data. I need an lambda function and method to map, reduce, and filter arrays or portions of data. Designers objected to functional implementations because the code should always be simple, easy to read, and write, and this was achievable with the for loop. I think mapping, filtering, and reducing are often easier to read and write, but this is an argument that is already raging in war.

Go is a really good language, although I disagree with some developers and I have to think about different ways to solve problems. I encourage you to try again after you've learned one or two languages. It quickly became one of the most popular languages, and there are many reasons why. I look forward to using it more in the future.

conclusion