A Very Simple Genetic Algorithm Written in Swift 3

gen.swift

#!/usr/bin/env xcrun swift

/*
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.
"""
*/

import Foundation

let OPTIMAL = "Hello, World"
let DNA_SIZE = OPTIMAL.characters.count
let POP_SIZE = 50
let GENERATIONS = 100
let MUTATION_CHANCE = 100

// HELPERS

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

/*
    extenstion to convert a character to ascii value
*/
extension Character {
    var asciiValue: UInt32? {
        return String(self).unicodeScalars.filter{$0.isASCII}.first?.value
    }
}

/*
    helper function to return a random character string
*/
func randomChar() -> String {
    
    let letters : NSString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ,."
    let len = UInt32(letters.length-1)
    
    let rand = arc4random_uniform(len)
    return String(Character(UnicodeScalar(letters.character(at: Int(rand)))!))
    
    // NOTE: above solution is faster
    //return String(letters[letters.index(letters.startIndex, offsetBy: Int(rand))])
}

// END HELPERS

/*
    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:String, optimal:String) -> Int {
    
    var fitness = 0
    let dnaLetters = dna.characters.map { String($0) }
    let optimalLetters = optimal.characters.map { String($0) }
    for c in 0...dna.characters.count-1 {
        fitness += abs(Int(Character(dnaLetters[c]).asciiValue!) - Int(Character(optimalLetters[c]).asciiValue!))
    }
    return fitness
}

/*
    randomly mutate the string
*/
func mutate(dna:String, mutationChance:Int, dnaSize:Int) -> String {
    var outputDna = ""
    
    let dnaLetters = dna.characters.map { return String($0) }
    
    for i in 0..<dnaSize {
        let rand = Int(arc4random_uniform(UInt32(mutationChance)))
        if rand == 1 {
            let ranchar = String(randomChar())!
            outputDna += ranchar
        } else {
            outputDna += dnaLetters[i]
        }
    }

    return outputDna
}

/*
    combine two parents to create an offspring
    parent = xy & yx, offspring = xx, yy
*/
func crossover(dna1:String, dna2:String, dnaSize:Int) -> (dna1:String, dna2:String) {
    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 (dna1.substring(to: dna1Index1) + dna2.substring(from: dna2Index1), dna2.substring(to: dna2Index1) + dna1.substring(from: dna1Index1))
}


/*
returns a random population, used to start the evolution
*/
func randomPopulation(populationSize: Int, dnaSize: Int) -> [String] {
    
    let letters : NSString = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ,."
    let len = UInt32(letters.length)
    
    var randomString = ""
    
    var pop = [String]()
    
    for _ in 0..<populationSize {
        var dna = ""
        for _ in 0..<dnaSize {
            let rand = arc4random_uniform(len)
            var nextChar = letters.character(at: Int(rand))
            dna += NSString(characters: &nextChar, length: 1) as String
        }
        pop.append(dna)
    }
    return pop
}


/*
function to return random canidate of a population randomally, but weight on fitness.
*/
func weightedChoice(items:[(item:String, weight:Double)]) -> (item:String, 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:[String] = randomPopulation(populationSize: POP_SIZE, dnaSize: DNA_SIZE)
    // print("population: \(population), dnaSize: \(DNA_SIZE) ")

    var fittestString = ""

    for generation in 0...GENERATIONS {
        print("Generation \(generation) with random sample: \(population[0])")
        
        var weightedPopulation = [(item:String, 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)
            
            var pair = ("",0.0)
            if fitnessValue == 0 {
                pair = (individual, 1.0)
            } else {
                pair = (individual, 1.0/Double(fitnessValue))
            }
            
            weightedPopulation.append(pair)
        }
        
        population = []
        
        // create a new generation using the individuals in the origional population
        for i in 0...POP_SIZE/2 {
            let ind1 = weightedChoice(items: weightedPopulation)
            let ind2 = weightedChoice(items: weightedPopulation)
            
            var 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))
        }
        
        let fitnessString = population[0]
        let minFitness = calculateFitness(dna: fitnessString, optimal: OPTIMAL)
        
        // parse the population for the fittest string
        for indv in population {
            let indvFitness = calculateFitness(dna: indv, optimal: OPTIMAL)
            if indvFitness > minFitness {
                fittestString = indv
                let minFitness = indvFitness
            }
        }
    }
    print("fittest string: \(fittestString)")
}

main()