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

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

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

/*
 helper function to return a random character string
 */
func randomValue() -> UInt8 {
    
    let letters : [UInt8] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ,.".asciiArray

    let len = UInt32(letters.count - 1)
    let rand = Int(arc4random_uniform(len))
    return letters[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:[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 = [UInt8]()
    
    for i in 0..<dnaSize {
        let rand = Int(arc4random_uniform(UInt32(mutationChance)))
        if rand == 1 {
            let ranchar = randomValue()
            outputDna.append(ranchar)
        } else {
            outputDna.append(dna[i])
        }
    }
    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))
    )
}


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


/*
 returns a random population, used to start the evolution
 */
func randomPopulation(populationSize: Int, dnaSize: Int) -> [[UInt8]] {
    
    let letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ,.".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 fittestString = [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)
            
            var pair = ([UInt8](), 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 _ 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))
        }
        
        let fitnessString = population[0]
        var 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
                minFitness = indvFitness
            }
        }
    }
    print("fittest string: \(String(bytes: fittestString, encoding: .ascii)!)")
}

main()

$ swiftc -o gen -O gen.swift
$ time ./gen > /dev/null

real 0m0.553s
user 0m0.538s
sys 0m0.009s

Without -O, takes ~9.9 sec