Swiftvolution

I had an idea, which is that it might be interesting to develop an evolution model for bots that can play pong. I imagined that the strategy would be evolved and eventually, you would get a more or less perfect player. Leaving aside the fact that this requires me to develop or reuse a pong game and the internals of how a pong bot would work – or at least one that could be evolved, job one is build an evolution engine.

I found a nice simple framework, written in Java in the Watchmaker project. It also has good API documentation and a nice tutorial. Development so far has been done by following the tutorial but implementing everything in Swift.

Source code can be found at https://bitbucket.org/jeremy-pereira/swiftvolution. I am using the Apache 2.0 licence because, although I did not copy any code from the Watchmaker project, I have shamelessly copied the design.

An Example

In what follows, we use the “Hello World” example from the Watchmaker User Manual. We start with a population of ten random strings of eleven upper case letters and space and we evolve generations of new strings using two transformations:

1. the cross over – take two random strings, take a random spot, cut both strings at that spot and then splice the left half of the first string with the right half of the second string and vice versa. This is roughly analogous to recombination in real genetics.
2. the random mutation – with a low probability, randomly mutate a string by replacing one of its letters with another random letter.

Selection of the transformed strings is done on the basis of how many letters match the string “HELLO WORLD”.

The Evolution Engine

This section is loosely based on The Evolution Engine in chapter 2 of the Watchmaker User Guide.

The heart of an evolution simulation is the evolution engine.  I first defined a protocol. This is so that users of the framework can implement their own engines.

public protocol EvolutionEngine
{
    /// The type of thing that the engine will be evolving.
    associatedtype EvolveType

    /// Run an evolution simulation
    ///
    /// - Parameters:
    ///   - populationCount: Number of individuals in the population
    ///   - eliteCount: Number of elite individuals
    ///   - seeds: List of seed individuals
    ///   - terminator: Conditions under which evolution will stop
    /// - Returns: The fittest individual when evolution stops.
    func evolve(populationCount: Int,
                     eliteCount: Int,
                          seeds: [EvolveType],
                     terminator: TerminationCondition<EvolveType>) -> EvolveType

    /// Add an observer. The observer will b e called each time a new set of
    /// population data is compiled.
    ///
    /// - Parameter observer: The observer to be called.
    mutating func addObserver(observer: @escaping EvolutionObserver<EvolveType>)
}

At this time, we only have two functions one to run an evolution and one to add observers so that we can see what is going on (more on this later). Note that the protocol places no constraints at all on what kinds of things can be evolved.

The framework defines a generic type that conforms to the above protocol. This means you do not have to write your own engine. Here’s how to instantiate it:

        let engine = GenerationalEvolutionEngine<HelloFactory>(
            candidateFactory: factory,
           evolutionOperator: { crossover.apply(parents: $0, rng: $1) } | { mutate.apply(parents: $0, rng: $1) },
            fitnessEvaluator: { SwiftvolutionTests.evaluateHello(candidate: $0, population: $1, target: factory.target) },
           selectionStrategy: SelectionStrategy.rouletteWheel,
                         rng: rng)

We’ll talk in detail about all of this in later posts. However:

• The candidateFactory is an object that creates the initial population. It must conform to the CandidateFactory protocol and the type of thing it returns determines the type of thing that GenerationalEvolutionEngine evolves.
• The evolutionOperator is a function that transforms one population into a new population. The pipe operator in the above code pipelines two evolution operators together so that the output population of the first operator is piped as the input population of the second operator. This is a major point of departure from the Watchmaker design: I have recast several of their single member interfaces as closures.
• The fitnessEvaluator is a function that evaluates candidates prior to selection.
• The selectionStrategy determines how candidates are selected to survive into the next generation.
• The rng is a the random number generator used to provide necessary randomness.

That’s it for now. In the next post, I’ll talk about the candidate factory.