A Very Simple Genetic Algorithm Written in Swift 3

gen.swift

#!/usr/bin/env xcrun swift -O

/*
gen.swift is a direct port of cfdrake's helloevolve.py from Python 2.7 to Swift 3
-------------------- https://gist.github.com/cfdrake/973505 ---------------------
gen.swift implements a genetic algorithm that starts with a base
population of randomly generated strings, iterates over a certain number of
generations while implementing 'natural selection', and prints out the most fit
string.
The parameters of the simulation can be changed by modifying one of the many
global variables. To change the "most fit" string, modify OPTIMAL. POP_SIZE
controls the size of each generation, and GENERATIONS is the amount of
generations that the simulation will loop through before returning the fittest
string.
This program subject to the terms of The MIT License listed below.
----------------------------------------------------------------------------------
Copyright (c) 2016 Blaine Rothrock
Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in the
Software without restriction, including without limitation the rights to use, 
copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the 
Software, and to permit persons to whom the Software is furnished to do so, subject
to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
"""
*/

/*
 --- CHANGELOG ---
 
 - 11/11/16: updated fittest loop based on suggestions from @RubenSandwich 
             & @RyanPossible
 - 11/11/16: simpilfied the weighted calculation based on suggestion from @nielsbot
 - 11/11/16: completed did away with string manipulation, to only use [UInt] base 
             on fork from @dwaite: https://gist.github.com/dwaite/6f26c970170e4d113bf5bfa3316e2eff
             *huge runtime improvement*
 - 11/15/16: mutate function optimization from @dwaite
 */


import Foundation

// HELPERS
/*
    String extension to convert a string to ascii value
*/
extension String {
    var asciiArray: [UInt8] {
        return unicodeScalars.filter{$0.isASCII}.map{UInt8($0.value)}
    }
}

/*
    helper function to return a random character string
*/
func randomChar() -> UInt8 {
    
    let letters : [UInt8] = " !\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~".asciiArray
    let len = UInt32(letters.count-1)
    
    let rand = Int(arc4random_uniform(len))
    return letters[rand]
}

// END HELPERS


let OPTIMAL:[UInt8] = "Hello, World".asciiArray
let DNA_SIZE = OPTIMAL.count
let POP_SIZE = 50
let GENERATIONS = 5000
let MUTATION_CHANCE = 100

/*
    calculated the fitness based on approximate string matching
    compares each character ascii value difference and adds that to a total fitness
    optimal string comparsion = 0
*/
func calculateFitness(dna:[UInt8], optimal:[UInt8]) -> Int {
    
    var fitness = 0
    for c in 0...dna.count-1 {
        fitness += abs(Int(dna[c]) - Int(optimal[c]))
    }
    return fitness
}

/*
    randomly mutate the string
*/
func mutate(dna:[UInt8], mutationChance:Int, dnaSize:Int) -> [UInt8] {
    var outputDna = dna
    
    for i in 0..<dnaSize {
        let rand = Int(arc4random_uniform(UInt32(mutationChance)))
        if rand == 1 {
            outputDna[i] = randomChar()
        }
    }

    return outputDna
}

/*
    combine two parents to create an offspring
    parent = xy & yx, offspring = xx, yy
*/
func crossover(dna1:[UInt8], dna2:[UInt8], dnaSize:Int) -> (dna1:[UInt8], dna2:[UInt8]) {
    let pos = Int(arc4random_uniform(UInt32(dnaSize-1)))
    
    let dna1Index1 = dna1.index(dna1.startIndex, offsetBy: pos)
    let dna2Index1 = dna2.index(dna2.startIndex, offsetBy: pos)
    
    return (
        [UInt8](dna1.prefix(upTo: dna1Index1) + dna2.suffix(from: dna2Index1)),
        [UInt8](dna2.prefix(upTo: dna2Index1) + dna1.suffix(from: dna1Index1))
    )
}


/*
returns a random population, used to start the evolution
*/
func randomPopulation(populationSize: Int, dnaSize: Int) -> [[UInt8]] {
    
    let letters : [UInt8] = " !\"#$%&\'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~".asciiArray
    let len = UInt32(letters.count)

    var pop = [[UInt8]]()
    
    for _ in 0..<populationSize {
        var dna = [UInt8]()
        for _ in 0..<dnaSize {
            let rand = arc4random_uniform(len)
            let nextChar = letters[Int(rand)]
            dna.append(nextChar)
        }
        pop.append(dna)
    }
    return pop
}


/*
function to return random canidate of a population randomally, but weight on fitness.
*/
func weightedChoice(items:[(item:[UInt8], weight:Double)]) -> (item:[UInt8], weight:Double) {
    var weightTotal = 0.0
    for itemTuple in items {
        weightTotal += itemTuple.weight;
    }
    
    var n = Double(arc4random_uniform(UInt32(weightTotal * 1000000.0))) / 1000000.0

    for itemTuple in items {
        if n < itemTuple.weight {
            return itemTuple
        }
        n = n - itemTuple.weight
    }
    return items[1]
}

func main() {

    // generate the starting random population
    var population:[[UInt8]] = randomPopulation(populationSize: POP_SIZE, dnaSize: DNA_SIZE)
    // print("population: \(population), dnaSize: \(DNA_SIZE) ")
    var fittest = [UInt8]()

    for generation in 0...GENERATIONS {
        print("Generation \(generation) with random sample: \(String(bytes: population[0], encoding:.ascii)!)")
        
        var weightedPopulation = [(item:[UInt8], weight:Double)]()
        
        // calulcated the fitness of each individual in the population
        // and add it to the weight population (weighted = 1.0/fitness)
        for individual in population {
            let fitnessValue = calculateFitness(dna: individual, optimal: OPTIMAL)
            
            let pair = ( individual, fitnessValue == 0 ? 1.0 : 1.0/Double( fitnessValue ) )
            
            weightedPopulation.append(pair)
        }
        
        population = []
        
        // create a new generation using the individuals in the origional population
        for _ in 0...POP_SIZE/2 {
            let ind1 = weightedChoice(items: weightedPopulation)
            let ind2 = weightedChoice(items: weightedPopulation)
            
            let offspring = crossover(dna1: ind1.item, dna2: ind2.item, dnaSize: DNA_SIZE)

            // append to the population and mutate
            population.append(mutate(dna: offspring.dna1, mutationChance: MUTATION_CHANCE, dnaSize: DNA_SIZE))
            population.append(mutate(dna: offspring.dna2, mutationChance: MUTATION_CHANCE, dnaSize: DNA_SIZE))
        }
        
        fittest = population[0]
        var minFitness = calculateFitness(dna: fittest, optimal: OPTIMAL)
        
        // parse the population for the fittest string
        for indv in population {
            let indvFitness = calculateFitness(dna: indv, optimal: OPTIMAL)
            if indvFitness < minFitness {
                fittest = indv
                minFitness = indvFitness
            }
        }
        if minFitness == 0 { break; }
    }
    print("fittest string: \(String(bytes: fittest, encoding: .ascii)!)")
}

main()

This is a direct port of @cfdrake's helloevolve.py written in Python 2.7.

To Run

This is written as a swift script and can be ran by changing the permissions of the file chmod +x gen.swift then ./gen.swift.

Customize

Update the following constants to yield different results:

• OPTIMAL: The string with the highest fitness
• DNA_SIZE: Length of OPTIMAL, do not change
• POP_SIZE: Number of individuals in a population
• GENERATIONS: Number of generations created before calculating fitness on a population
• MUTATION_CHANCE: Chance that the string will mutate with each generation, 1/MUTATION_CHANCE

Hey, I played around with the code for pulling out the fittest string:

for indv in population {
  let indvFitness = calculateFitness(dna: indv, optimal: OPTIMAL)
  if indvFitness < minFitness {
    fittestString = indv
    minFitness = indvFitness
  }
}

I was able to get the optimal string in <1000 generations with this for loop. I believe that is because of two changes:

1. Updating the minFitness variable.
2. Checking for a lower value for fitness. The lower the fitness value, the more closer the string is to being optimal, I think.
   Does this work for you?

Edit: I cannot Markdown...

Er, never mind. Looks like yours is working fine.

I'm a bit confused by line 231; where you are creating a new minFitness but never use it. Do you mean to update the minFitness you created at line 224?

Thanks @RubenSandwich & @RyanPossible, few mistakes on my part in that loop. Updated!

There is a difference between this and the python version in that you are using non-unicode strings in python and unicode strings in Swift - but this makes sense given swift doesn't have non-unicode strings.

Created a version using [UInt8] at https://gist.github.com/dwaite/6f26c970170e4d113bf5bfa3316e2eff - compiled with optimizations it takes about 0.5 sec on my 2013 MBP

I think this

var pair = ("",0.0)
if fitnessValue == 0 {
    pair = (individual, 1.0)
} else {
    pair = (individual, 1.0/Double(fitnessValue))
}

could be simply

let pair = ( individual, fitnessValue == 0 ? 1.0 : Double( fitnessValue ) )

Also, if you want to keep the first form, you don't have to assign anything to pair. It can be a let as long as you assign a value to it only once:

let pair:(String, Double)
if fitnessValue == 0 {
    pair = (individual, 1.0)
} else {
    pair = (individual, 1.0/Double(fitnessValue))
}

On line 107, I think you don't need the return statement, this works too:

let dnaLetters = dna.characters.map { String($0) }

On line 146

for _ in 0..<populationSize {

You could also use this form which eliminates the _... (not sure if it's prefereable)

(0..<populationSize).forEach {

• thanks @nielsbot, updated!
• also, @dwaite good stuff, I'll definitely take a look at it when I have some heads down time.

Hah! Didn't expect to see my name when I clicked this link :P Nice work from a fellow Swift fan.

@blainerothrock Since you're explicitly restricting this algorithm to ASCII, you're likely to find String.utf8CString to be more performant than your asciiArray extension :)

thanks to @dwaite this is now much faster! The above runs with logging in 1.757s on my early 2015 MBP.

@cfdrake, so awesome you found this! What a world.

Thanks for all the help everybody!

One more easy optimization, the mutate function currently has to create DNA_SIZE intermediate uint8 arrays as it appends each character. Instead, you can have it just create new arrays for the mutations:

/*
 randomly mutate the string
 */
func mutate(dna:[UInt8], mutationChance:Int, dnaSize:Int) -> [UInt8] {
    var outputDna = dna
    
    for i in 0..<dnaSize {
        let rand = Int(arc4random_uniform(UInt32(mutationChance)))
        if rand == 1 {
            let ranchar = randomChar()
            outputDna[i] = ranchar
        }
    }
    
    return outputDna
}

thanks again @dwaite -- no noticeable runtime differences, but definitely cleaner code!