GoAL - Go Artificial Life - Part I

A hobby of mine is Artificial Life. I grew up in what I’d call the Golden Age of AL.

Tamagotchi, SimAnt, and Creatures were all released during my formative years. In 2001 Black & White was released. Since then it feels like AL has been reserved to the realm of academia. I had hoped in the 22 years since Creatures 3 we’d have a better selection of AL games and experiments, but it remains a niche area of interest.

I’ve experimented with AL on a few occasions (perhaps most extensively with the Creatures Genetics Kit).
Creatures is a game that warrants its own write-up! I’d love to contribute to something comparable to Creatures, but our current goals are more modest.

This time I decided to dive into Genetic Algorithms, documenting the process as I go. I’ve previously used GA to create programs for an abstract machine called a URM. I want to get a feel for GAs, so there’s very few specific objectives here.

go-al is my playground repository for Artificial Life. In this series of posts, we’ll try to evolve a discount version of artificial life in our little world.

  1. Devise a simple genome that’s evolved with a genetic algorithm
  2. Increase the complexity of the DNA, and thus search space
  3. Explore ideas like co-evolution of organisms, and improvements to our approach

This post covers the first stage. We’ll build a skeleton project to start toying with.

Genetic Algorithms

Genetic Algorithms are machine learning algorithms inspired by their real-world counterparts. They typically begin by creating random genomes and evolving populations of them over many generations. New genomes are generated through crossover between two parents and random mutation, just like our own.

Implementing the core genetic algorithm is beyond the scope of this post. We want to get straight to the fun part.
I played around with a few alternatives, eventually settling on eaopt. eaopt is simple to get to grips with and seems fast enough for our needs. It can be instantiated in a few lines and supports several tuning parameters. It also sports parallel execution if our fitness function becomes hungry enough to require it.

Genetic Algorithms - Fun Fact

GAs have many interesting applications. For example, they have been successfully used to design antannae for highly specific purposes. This probably doesn’t come as a surprise, given that they’re a large factor in how life evolved on earth.

Utilities

We’ll define three entry points into our application:

$ ./ga evolve 10 # Evolves genomes with a fixed genome length, passed as the argument
$ ./ga parse ABA # Parses the given genome into a human-readable representation
$ ./ga ABA       # Evaluates the fitness of the given genome

func main() {
	args := os.Args[1:]

	if len(args) < 1 {
		usage()
		os.Exit(1)
	} else if args[0] == "evolve" {
		uintLen, _ := strconv.ParseUint(args[1], 10, 32)
		evolveGenomes(uintLen)
	} else if args[0] == "parse" {
		genome = args[1]
		parseGenomeString(genome)
	} else {
		genome = args[0]
		evaluateSingleGenome(genome)
	}
}

Defining a fitness function

Our organisms need a goal, and the GA needs a function to minimise. Let’s start with a rudimentary goal. Our organisms want to spawn as many children as possible. Let’s initialise our state.

type GenomeState struct {
    Children uint
}

func (G Genome) Evaluate() (fitness float64, err error) {
    g := GenomeState{Children: 0}
    return 1.0 - (float64(g.Children) / 1000.0)
}

A minimal genome

Now we need to define a genome. Let’s implement the parse method which will help serve as documentation of this structure.

func parseGenomeString(genome string) {
	codons := strings.Split(genome, "")
	for i := 0; i < len(codons); i++ {
		switch codons[i] {
		case "A":
			fmt.Println("Spawn child")
		case "B":
			fmt.Println("Nop")
		}

	}
}

That’s it. A string of A’s and B’s. When our simulation encounters an ‘A’ it will spawn a child. When it encounters a ‘B’ it will perform a no-op. We can now parse our genome!

➜  go-al git:(master) ✗ ./ga parse AB
Spawn child
Nop

We’ll have to define some boilerplate for our genome to work with eaopt, specifically Mutate and Crossover. These are the defining functions of a GA. We must also implement a Clone method. For now, we can lean on eaopt for most of the implementation.

MakeStrings allows the generation of random populations, an important starting point.

type Genome []string

var (
	corpus = strings.Split("AB", "")
)

func (G Genome) Mutate(rng *rand.Rand) {
	eaopt.MutUniformString(G, corpus, 1, rng)
}

func (G Genome) Crossover(Y eaopt.Genome, rng *rand.Rand) {
	eaopt.CrossGNXString(G, Y.(Genome), 2, rng)
}

func (G Genome) Clone() eaopt.Genome {
	var XX = make(Genome, len(G))
	copy(XX, G)
	return XX
}

func MakeStrings(rng *rand.Rand) eaopt.Genome {
	return Genome(eaopt.InitUnifString(genomeLength, corpus, rng))
}

Let’s revisit the Evaluate() function. We will treat our genome as a tape, reading left to right. Each genome runs for 1000 iterations before returning the calculated fitness.
When we reach the end of our DNA tape, we loop back to the beginning (we can revisit this another article).

func (G Genome) Evaluate() (fitness float64, err error) {
	index := 0

	g := GenomeState{}
	g.Children = 0

	for i := 0; i < 1000; i++ {
		codon := G[index]
		switch codon[0] {
		case 'A':
			g.Children += 1
			logWithFields(&g).Debug("Spawned a child")
		case 'B':
			logWithFields(&g).Debug("No Op")
		default:
			logWithFields(&g).Debug("Unexpected")
		}

        // Iterate through the genome, looping at the end
		index = (index + 1) % len(G)
	}

	return 1.0 - (float64(g.Children) / 1000.0), nil
}

Finally, let’s implement the command to start evolving. We initialise eaopt and set some basic options.
We’ve kept the number of generations and populations low because we’ll converge on an optimal solution incredibly quickly. We also define some regular feedback, printing to stdout whenever enough generations have passed or when a new best solution is discovered.

func evolveGenomes(len uint64) {
	genomeLength = uint(len)

	var ga, err = eaopt.NewDefaultGAConfig().NewGA()
	if err != nil {
		fmt.Println(err)
		return
	}

	ga.NGenerations = 10
	ga.NPops = 10
	ga.MigFrequency = 5
	ga.Migrator = eaopt.MigRing{NMigrants: 5}
	ga.ParallelEval = false

	winner := ""
	mutex := sync.Mutex{}

	// Periodically update progress, or when a new champion is found
	ga.Callback = func(ga *eaopt.GA) {
		mutex.Lock()
		defer mutex.Unlock()

		if ga.Generations%1 == 0 {
			fmt.Printf("%d)\n", ga.Generations)
		}

		var buffer bytes.Buffer
		for _, letter := range ga.HallOfFame[0].Genome.(Genome) {
			buffer.WriteString(letter)
		}

		if winner != buffer.String() {
			winner = buffer.String()
			fmt.Printf("%d) Result -> %s (%d children)\n", ga.Generations, buffer.String(), uint((1.0-ga.HallOfFame[0].Fitness)*1000.0))
		}
	}

	ga.Minimize(MakeStrings)
}

We can now trivially implement our last command, which evaluates this function for a single genome.
It provides debug output for a single execution, handy if we want to hand-craft or tailor our own solutions.

func evaluateSingleGenome(genomeString string) {
	g := Genome(strings.Split(genomeString, ""))
	fitness, _ := g.Evaluate() // Our genomes don't error... yet
	fmt.Println(fitness)
}

Let there be life?

Let’s run the fitness function against a hand-crafted genome.
We’ll spawn a child, perform a nop, rinse, and repeat - AB.

➜  go-al git:(master) ✗ ./ga AB
DEBU[0000] Spawned a child                               state="&{1}"
DEBU[0000] No Op                                         state="&{1}"
DEBU[0000] Spawned a child                               state="&{2}"
DEBU[0000] No Op                                         state="&{2}"
...
DEBU[0000] Spawned a child                               state="&{500}"
DEBU[0000] No Op                                         state="&{500}"
0.5

Our genome spawned 500 children and achieved a fitness of 0.5. The theoretical minimum (best) fitness is 0.0, i.e. spawning 1 child per iteration for a maximum of 1,000 children.

For a genome of size 2, the best solution is obviously AA.

➜  go-al git:(master) ✗ ./ga evolve 2
0)
0) Result -> AA (1000 children)
1)
...
10)

It was hardly a challenge for the GA to optimise this method. Only the first generation did any useful work. The remaining 9 generations found no better candidates.

What’s next

In the next post, we’ll add some complexity to our world and genomes. With enough complexity, we should start to see some novel constructs.

Resources

You can find the source here at v0.1.0

eaopt - The GitHub repository for eaopt
go-al master - The latest version of go-al