Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Rubik's Cubes and Genetic Algorithms In Swift

Javier Soto
November 08, 2016

Rubik's Cubes and Genetic Algorithms In Swift

Genetic Algorithms are a fascinating way of solving problems in computer science which lie in between programming and biology. I implemented one in Swift to solve Rubik's Cubes, and you won't believe what happened next.

Javier Soto

November 08, 2016
Tweet

More Decks by Javier Soto

Other Decks in Programming

Transcript

  1. RUBIK'S CUBES AND GENETIC ALGORITHMS IN SWIFT @JAVI 1 —

    "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  2. EVOLUTION BY NATURAL SELECTION 1. ? 2. Random mutations in

    genome 3. Survival of the fittest 4. (Rinse and repeat) 5 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  3. GENETIC ALGORITHMS - EXAMPLE 1. GOAL: FIND A NUMBER 'X'

    2. START WITH 0000000000000000 3. MUTATE EACH RANDOMLY, BIT BY BIT 4. CALC FITNESS COMPARING WITH X'S BITS 8 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  4. GENETIC ALGORITHMS - EXAMPLE final class Individual { let number:

    UInt init(number: UInt) { self.number = number } } 9 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  5. GENETIC ALGORITHMS - EXAMPLE typealias Fitness = Int extension Individual

    { func fitness(withGoal goal: UInt) -> Fitness { return Fitness(self.number.numberOfBitsEqual(in: goal)) } } 10 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  6. GENETIC ALGORITHMS - EXAMPLE extension Individual { let likelyhoodOfMutatingBit =

    5 func mutate() -> Individual { let mutatedBits = self.number.bits.map { bit -> Bool in let shouldMutate = Bool.random(percentage: likelyhoodOfMutatingBit) return shouldMutate ? !bit : bit } return Individual(number: UInt(bits: mutatedBits)) } } 11 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  7. GENETIC ALGORITHMS - EXAMPLE final class GeneticSolver { var population:

    [Individual] init(numberToSolve: UInt, populationSize: Int) func runGeneration() { // 1: Natural selection (survival of the fittest) population.removeLast(Int(Double(population.count) * 0.8)) // 2: Random mutations population += population.map { $0.mutate() } // 3: Sort by fitness population.sort { $0.fitness(towards: numberToSolve) > $1.fitness(towards: numberToSolve) } } } 12 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  8. RubikSwift struct Cube { struct Pieces { var edges: EdgePieceCollection

    var corners: CornerPieceCollection } var pieces: Pieces } 19 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  9. RubikSwift enum EdgeLocation { case topRight, topFront, topLeft, topBack... }

    struct EdgePiece { enum Orientation { case correct case flipped } var location: EdgeLocation var orientation: Orientation } 20 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  10. RubikSwift struct CornerPiece { enum Orientation { case correct case

    rotatedClockwise case rotatedCounterClockwise } var location: CornerLocation var orientation: Orientation } 22 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  11. RubikSwift struct Cube { struct Pieces { var edges: EdgePieceCollection

    var corners: CornerPieceCollection } var pieces: Pieces } 23 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  12. RubikSwift enum Face { case top, bottom, left, right, front,

    back } struct Move { enum Magnitude { case clockwiseQuarterTurn case halfTurn case counterClockwiseQuarterTurn } let face: Face let magnitude: Magnitude } 24 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  13. RubikSwift extension Cube { mutating func apply(_ move: Move) }

    26 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  14. RubikSwift final class Individual { let moves: [Move] init(moves: [Move])

    { self.moves = moves } } 27 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  15. RubikSwift typealias Fitness = Int extension Individual { func fitness(solvingCube

    cube: Cube) -> Fitness { var cubeAfterApplyingMoves = cube cubeAfterApplyingMoves.apply(self.moves) return cubeAfterApplyingMoves.numberOfSolvedPieces } } extension Cube { // Number of pieces in the correct location and orientation var numberOfSolvedPieces: Int } 28 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  16. RubikSwift extension Individual { func mutate() -> Individual { var

    moves = self.moves let randomMoves = Move.randomMoves(count: Int.random(in: 5...20)) moves += randomMoves return Individual(moves: moves) } } 29 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  17. RubikSwift final class Solver { private(set) var population: [Individual] init(scrambledCube:

    Cube, populationSize: Int) func runGeneration() { population.removeLast(Int(Double(population.count) * 0.8)) population += population.map { $0.mutate() } population.sort { $0.fitness(solvingCube: scrambledCube) > $1.fitness(solvingCube: scrambledCube) } } } 30 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi
  18. RubikSwift Cube: R' F' B D2 L' R' D2 R'

    F2 B2 D F L' R2 F' U2 R' U' D F 1: New best: B2 (3.0) 3: New best: B2 U D' U2 F2 D2 B U2 D R B' [...] (6) 7: New best: B2 L2 U2 L' B2 F' U' U' D L2 [...] (7) 100 (avg fitness 3.6012, 23806 algs/sec, 0 min elapsed) 3465: New best: B2 D2 U R2 B2 U2 B' F2 D [...] (13) 10000 (avg fitness 6.462, 11217 algs/sec, 74 min elapsed) 25781: New best: L' D' B2 L2 B' D R2 F R' [...] (**16**) 80800 (avg fitness 9.2612, 7676 algs/sec, 877 min elapsed) 32 — "Rubik's Cubes and Genetic Algorithms In Swift" - @Javi