Weasel Program - Go Version

One more implementation of the Weasel Program. (See previous two posts.) Then I'll get into the simulation issues.

I really like the ideas behind Go. Based on the still largely theoretical arguments for it being created (not much data yet) I hope it becomes popular for the type of programming problems it's designed for. It's very C-like mostly, which I think is good. But unfortunately, this little simulation doesn't allow it to show off any of the advantages it has over C.

I don't have very much experience in Go and so am taking every opportunity I can to see what it can do.

My bug rate per line of code has always been pretty consistent regardless of language. Go seems no different. Performance wise, for this particular problem, Go split the difference in execution time between the program written in Python and the program written in C.

/* Weasel Program -- evolutionay simulation demonstration

A simple computer simulation demonstrating 
that the process that drives natural selection
(based on random variation combined with non-random selection)
is qualitatively different from results based on pure random selection.

See Wikipedia for more info on Weasel Program.

Given:
    Genome as string representing list of genes modelled as chars.
    Target genome is a fixed string of chars.
    Fixed mutation probability.
    Fixed number of children per generation.

Basic algorithm:
    Generate children from single parent keeping most fit as new parent
    for next generation.

    Stop when child genome = target genome

    Note: to save space, child is discarded immediately if not most fit
    in generation so far.

*/
package main

import (
    "fmt"
    "math/rand"
    "time"
)

// Adjust the following to see how they affect number of generations and
// time to convergence. (Convenient to define here, visible and easy to
// change.
var targetGenome = []byte("METHINKS IT IS LIKE A WEASEL!")
var genes = []byte(" ABCDEFGHIJKLMNOPQRSTUVWXYZ!")
var mutationProbability float32 = 0.05
var numChildrenPerGeneration int = 100

// Useful to define globally
var genomeLen, perfectFitnessScore, numGenes int
var parentGenome, childGenome, survivingChildGenome []byte

func init() {
    rand.Seed(time.Now().UTC().UnixNano())

    genomeLen = len(targetGenome)
    perfectFitnessScore = len(targetGenome)
    numGenes = len(genes)

    // First generation parent is just a random set of genes.
    parentGenome = make([]byte, genomeLen)
    for i := range parentGenome {
        parentGenome[i] = genes[rand.Intn(numGenes)]
    }

    childGenome = make([]byte, genomeLen)
    survivingChildGenome = make([]byte, genomeLen)
}

func calcFitness(genome []byte) (fitness int) {
    for i, targetGene := range targetGenome {
        if genome[i] == targetGene {
            fitness++
        }
    }
    return
}

func createChild() {
    for i, parentGene := range parentGenome {
        if rand.Float32() < mutationProbability {
            childGenome[i] = genes[rand.Intn(numGenes)]
        } else {
            childGenome[i] = parentGene
        }
    }
}

func main() {

    var i, generation, fitness, maxFitness int

    startTime := time.Now()
    // Let user know how we started.
    maxFitness = calcFitness(parentGenome)
    fmt.Printf("%3d %3d %s\n", generation, maxFitness, string(parentGenome))

    // Evolve.  Loop each generation.
    for maxFitness < perfectFitnessScore {
        generation++
        maxFitness = 0
        for i = 0; i < numChildrenPerGeneration; i++ {
            createChild()
            fitness = calcFitness(childGenome)
            if fitness >= maxFitness {
                maxFitness = fitness
                copy(survivingChildGenome, childGenome)
            }
        }
        copy(parentGenome, survivingChildGenome)
    }
    fmt.Printf("%3d %3d %s\n", generation, maxFitness, string(parentGenome))
    elapsedTime := time.Since(startTime)
    fmt.Printf("Elapsed time: %v\n", elapsedTime)
}

No comments:

Post a Comment