evolve

Genetic Algorithm

This repository contains a simple implementation of a genetic algorithm for evolving arbitrary types. There's a double-buffering in place to prevent unnecessary allocations and a relatively simple API around it.

It also provides a binary package for evolving []byte genomes. Under the hood, it uses a simple random binary crossover and mutation to do the trick.

Usage

In order to use this, we first need to create a "phenotype" representation which contains the dna. In this example we're using the binary package in order to evolve a string. It should implement the Evolver interface which contains Genome() and Evolve() methods, in the example here we are creating a simple text which contains the binary representation of the text itself.

// Text represents a text with a dna (text itself in this case)
type text struct {
	dna evolve.Genome
}

// Genome returns the genome
func (t *text) Genome() []byte {
	return t.dna
}

// Evolve updates the genome
func (t *text) Evolve(v []byte) {
	t.dna = v
}

Next, we'll need a fitness function to evaluate how good a genome is. In this example we're creating a fitness function for an abritrary string which simply returns a func(Evolver) float32

// fitnessFor returns a fitness function for a string
func fitnessFor(text string) evolve.Fitness {
	target := []byte(text)
	return func(v evolve.Evolver) float32 {
		var score float32
		genome := v.Genome().(*binary.Genome)
		for i, v := range *genome {
			if v == target[i] {
				score++
			}
		}
		return score / float32(len(target))
	}
}

Finally, we can wire everything together by using New() function to create a population, and evolve it by repeatedly calling Evolve() method as shown below.

func main() {
	const target = "Hello World"
	const n = 200

	// Create a fitness function
	fit := fitnessFor(target)

	// Create a population
	population := make([]evolve.Evolver, 0, n)
	for i := 0; i < n; i++ {
		population = append(population, new(text))
	}
    
	// Create a population
	pop := evolve.New(population, fit, len(target))

	// Evolve over many generations
	for i := 0 ; i < 100000; i++ {
		pop.Evolve()
	}

	// Get the fittest member of the population
	fittest := pop.Fittest()
}

License

Tile is licensed under the MIT License.