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()

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!