Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Very Simple Genetic Algorithm Written in Swift 3
#!/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()
@blainerothrock

This comment has been minimized.

Copy link
Owner Author

@blainerothrock blainerothrock commented Nov 11, 2016

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
@RyanPossible

This comment has been minimized.

Copy link

@RyanPossible RyanPossible commented Nov 11, 2016

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...

@RyanPossible

This comment has been minimized.

Copy link

@RyanPossible RyanPossible commented Nov 11, 2016

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

@RubenSandwich

This comment has been minimized.

Copy link

@RubenSandwich RubenSandwich commented Nov 11, 2016

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?

@blainerothrock

This comment has been minimized.

Copy link
Owner Author

@blainerothrock blainerothrock commented Nov 11, 2016

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

@dwaite

This comment has been minimized.

Copy link

@dwaite dwaite commented Nov 11, 2016

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

@nielsbot

This comment has been minimized.

Copy link

@nielsbot nielsbot commented Nov 11, 2016

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

This comment has been minimized.

Copy link

@nielsbot nielsbot commented Nov 11, 2016

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 {
@blainerothrock

This comment has been minimized.

Copy link
Owner Author

@blainerothrock blainerothrock commented Nov 11, 2016

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

This comment has been minimized.

Copy link

@cfdrake cfdrake commented Nov 11, 2016

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

@xwu

This comment has been minimized.

Copy link

@xwu xwu commented Nov 12, 2016

@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 :)

@blainerothrock

This comment has been minimized.

Copy link
Owner Author

@blainerothrock blainerothrock commented Nov 12, 2016

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!

@dwaite

This comment has been minimized.

Copy link

@dwaite dwaite commented Nov 15, 2016

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
}
@blainerothrock

This comment has been minimized.

Copy link
Owner Author

@blainerothrock blainerothrock commented Nov 15, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment