Mendel

Mendel - Swift miliframework for implementing evolutionary/genetic algorithms

Code Quality Rank: L5

Programming language: Swift

Tags: Utility    

README

Mendel

Mendel - Swift miliframework for implementing evolutionary/genetic algorithms. Or, you know, Gregor Mendel.

[Logo]([email protected])

This started out as an exercise in Swift and Functional Programming, but quickly turned into something bigger.

Intro

The framework provides an Engine protocol, describing the necessary interface for evolutionary/genetic computation using functions. Individual instantiation, population evaluation, selection, genetic operators (like mutation and crossover) and even termination conditions are all described as functions. This allows you to use techniques such as partial application and function composition to a great effect.

Here's a video showing the sample application that's build on top of Mendel in action.

Canned Functions

Mendel provides a number of canned implementations for some of those functions, see:

• [Selections](Mendel/Mendel/Selection.swift) for individual selection functions, such as RouletteWheel and StochasticUniversalSampling
• [Operators](Mendel/Mendel/Operators.swift) for genetic operators, such as Mutation and Crossover
• [TerminationConditions](Mendel/Mendel/Termination.swift) for termination conditions, such as terminating after a number of iterations (NumberOfIterations) or terminating when a given fitness threshold is reached (FitnessThreshold)

More on Genetic Operators

Genetic Operators can be easily piped using the >>> swift operator (which wraps the Pipe genetic operator). E.g. if you want to perform a crossover with probability 0.1 and then a mutation with probability 0.5, you can just pass Crossover(0.1) >>> Mutation(0.5) as your genetic operator.

The Split operator lets you split the genetic operator flow into two paths. E.g., if you want to perform a crossover(p=0.1) only on 30% of the population and a mutation(p=0.5) on the other 70% you can do Split(0.3, Crossover(0.1), Mutation(0.5)).

Using Pipe and Split together lets you build complex evolution schemes easily.

Additionally, there's a Parallel operator, which partitions the population in batches of batchSize and applies a genetic operator to those batches concurrently, returning only after all batches are processed.

Simple Engine

The framework provides a SimpleEngine class which implements the Engine protocol described below. It's a concrete implementation of a simple generational evolution engine and can be used out of the box. The two examples in the sample app were built using SimpleEngine.

//The Genetic Engine protocol
public protocol Engine {
    //The type that's being evolved
    typealias Individual : IndividualType
    //A collection of Individuals
    typealias Population = [Individual]
    //A collection of Individuals and their respective fitness scores
    typealias EvaluatedPopulation = [Score<Individual>]

    //MARK: Core function types

    //Used to instantiate a new arbitrary Individual
    typealias Factory = () -> Individual

    //Used to ge a fitness score for an Individual in a given Population
    typealias Evaluation = (Individual, Population) -> Fitness

    //Selection Function - used to select the next iteration's Population from
    //the current EvaluatedPopulation
    typealias Selection = (EvaluatedPopulation, FitnessKind, Int) -> Population

    //The Genetic Operator that is going to be called to modify the selected Population
    typealias Operator = Population -> Population

    //Termination predicate. When it returns yes, the evolution process is stopped
    typealias Termination = IterationData<Individual> -> Bool

    ////////////////////////////////////////////////////////////////////////////

    var fitnessKind: FitnessKind { get }

    var factory: Factory { get }

    var evaluation: Evaluation { get }

    var selection: Selection { get }

    var op: Operator { get }

    var termination: Termination? { get }

    //Called after each evolution step. Useful to update UI/inform user.
    var iteration: (IterationData<Individual> -> Void)? { get }

    //Starts the evolution process. This is a blocking call, it won't return until
    //`termination` returns true – make sure you aren't blocking UI.
    func evolve() -> Individual
}

Inspired by http://chriscummins.cc/s/genetics/ and the Functional Programming in Swift book. Hat tip to Watchmaker and Nacho Sotos' swift-genetics.