Basic neural network with genetics

NeuralNet.swift

//
//  NeuralNet.swift
//  BestColor
//
//  Created by Stevie Hetelekides on 9/15/15.
//  Copyright (c) 2015 Expetelek. All rights reserved.
//

import Foundation

enum NeuralError: ErrorType
{
    case InputWeightMismatch
}

class Neuron
{
    var bias: Double = 0
    var weights: [Double] = [ ]
    
    init(weights: [Double])
    {
        self.weights = weights
    }
    
    init(inputs: Int, bias: Double = 0)
    {
        // initialize random weights
        for _ in 0..<inputs
        {
            self.weights.append(Double.random(min: -1, max: 1))
        }
        
        self.bias = bias
    }
    
    func computeOutput(inputs: [Double]) throws -> Double
    {
        // make sure inputs (+1 for bias) == number of weights
        if inputs.count != self.weights.count
        {
            throw NeuralError.InputWeightMismatch
        }
        
        // compute sum
        var sum: Double = 0
        for (index, input) in inputs.enumerate()
        {
            sum += input * self.weights[index]
        }
        
        // add bias
        sum += self.bias
        
        // return sigmoid of sum
        return sigmoid(sum)
    }
}

class NeuronLayer
{
    private(set) var neurons: [Neuron] = [ ]
    
    init(neurons: Int, inputsPerNeuron: Int)
    {
        for _ in 0..<neurons
        {
            self.neurons.append(Neuron(inputs: inputsPerNeuron))
        }
    }
    
    func getWeights() -> [[Double]]
    {
        var weights: [[Double]] = [ ]
        for neuron in self.neurons
        {
            weights.append(neuron.weights)
        }
        
        return weights
    }
    
    func updateWeight(newWeights: [[Double]])
    {
        for (neuronIndex, newNeuronWeights) in newWeights.enumerate()
        {
            self.neurons[neuronIndex].weights = newNeuronWeights
        }
    }
}

class NeuralNetwork
{
    private typealias BackpropagationValues = (gradients: [Double], neuronError: Double)
    
    private(set) var numberOfInputs: Int
    private(set) var numberOfOutputs: Int
    
    private(set) var layers: [NeuronLayer] = [ ]
    
    init(inputs: Int, outputs: Int, hiddenLayers: Int, neuronsPerHiddenLayer: Int)
    {
        self.numberOfInputs = inputs
        self.numberOfOutputs = outputs
        
        // create layers
        if (hiddenLayers < 1)
        {
            let singleLayer = NeuronLayer(neurons: self.numberOfOutputs, inputsPerNeuron: self.numberOfInputs)
            self.layers.append(singleLayer)
        }
        else
        {
            for i in 0..<hiddenLayers
            {
                let inputNeurons = (i > 0) ? self.layers[i - 1].neurons.count : self.numberOfInputs
                let layer = NeuronLayer(neurons: neuronsPerHiddenLayer, inputsPerNeuron: inputNeurons)
                self.layers.append(layer)
            }
            
            let outputLayer = NeuronLayer(neurons: self.numberOfOutputs, inputsPerNeuron: self.layers.last!.neurons.count)
            self.layers.append(outputLayer)
        }
    }
    
    func updateWeights(newWeights: [[[Double]]])
    {
        for (layerIndex, newLayerWeights) in newWeights.enumerate()
        {
            self.layers[layerIndex].updateWeight(newLayerWeights)
        }
    }
    
    func compute(inputs: [Double]) throws -> [Double]
    {
        return try forwardPropogate(inputs: inputs).last!
    }
    
    func compute(inputs: [Double], expectedOutputs: [Double]) throws -> (outputs: [Double], cost: Double)
    {
        let outputs = try self.compute(inputs)
        
        var cost: Double = 0
        
        // calculate cost
        // cost function = (1/2n) * sum of all (expected - actual)^2)
        for (index, expectedOutput) in expectedOutputs.enumerate()
        {
            cost += pow(expectedOutput - outputs[index], 2)
        }
        cost *= 1 / (2 * Double(outputs.count))
        
        return (outputs: outputs, cost: cost)
    }
    
    func compute(inputs: [[Double]], expectedOutputs: [[Double]]) throws -> (outputs: [[Double]], cost: Double)
    {
        var totalCost: Double = 0
        var outputs: [[Double]] = [ ]
        
        for (index, miniBatchInputs) in inputs.enumerate()
        {
            // compute this batch's output
            let miniBatchResult = try self.compute(miniBatchInputs, expectedOutputs: expectedOutputs[index])
            
            // add to our outputs array, update the cost
            outputs.append(miniBatchResult.outputs)
            totalCost += miniBatchResult.cost
        }
        
        return (outputs: outputs, cost: totalCost)
    }
    
    private func forwardPropogate(inputs startingInputs: [Double]) throws -> [[Double]]
    {
        var inputs: [Double] = startingInputs
        var outputs: [[Double]] = [ ]
        
        for layer in self.layers
        {
            // create array for new outputs
            var currentLayerOutputs: [Double] = [ ]
            
            // for each neuron, compute the output
            for neuron in layer.neurons
            {
                let neuronOutput = try neuron.computeOutput(inputs)
                currentLayerOutputs.append(neuronOutput)
            }
            
            // add current layer outputs to outputs
            outputs.append(currentLayerOutputs)
            
            // update inputs for next iteration
            inputs = currentLayerOutputs
        }
        
        return outputs
    }
    
    private func computeErrors(inputs: [Double], outputs: [[Double]], desiredOutputs: [Double]) throws -> [[Double]]
    {
        // array to hold errors for each layer
        var layerErrors: [[Double]] = [ ]
        
        // compute output layer errors
        // output error = cost function derivative * activation function derivative = (desired - computed) * (computed * (1 - computed))
        var outputErrors: [Double] = [ ]
        for (neuronIndex, output) in outputs.last!.enumerate()
        {
            let desired = desiredOutputs[neuronIndex]
            let outputError = (desired - output) * sigmoid_derivative(output)
            
            outputErrors.append(outputError)
        }
        
        // add to output layer error to errors array
        layerErrors.insert(outputErrors, atIndex: 0)
        
        // compute hidden layer errors
        for layerIndex in (outputs.count - 2).stride(through: 0, by: -1)
        {
            var currentLayerErrors: [Double] = [ ]
            for neuronIndex in 0..<self.layers[layerIndex].neurons.count
            {
                var error: Double = 0
                
                // this looks tricky but really isn't. It's just getting the weights that go FROM the current neuron TO the next layer
                // it's not setup well (structurally), that's why this looks so hacky
                for (nextLayerNeuronIndex, weights) in self.layers[layerIndex + 1].getWeights().enumerate()
                {
                    error += weights[neuronIndex] * layerErrors[0][nextLayerNeuronIndex]
                }
                
                // compute error
                let output = outputs[layerIndex][neuronIndex]
                error *= sigmoid_derivative(output) * (1 - sigmoid_derivative(output))
                
                // add to this layers errors
                currentLayerErrors.append(error)
            }
            
            // add to errors array
            layerErrors.insert(currentLayerErrors, atIndex: 0)
        }
        
        return layerErrors
    }
    
    private func computeGradient(inputs: [Double], desiredOutputs: [Double]) throws -> [[BackpropagationValues]]
    {
        // compute all outputs
        var outputs = try forwardPropogate(inputs: inputs)
        
        // compute all errors
        let layerErrors = try computeErrors(inputs, outputs: outputs, desiredOutputs: desiredOutputs)
        
        // insert inputs into output layer
        outputs.insert(inputs, atIndex: 0)
        
        // represents the gradients of every weight for every neuron for every layer in the network
        /* structure:
            [
                // LAYER 1
                [
                    [ NEURON 1 GRADIENTS ],
                    [ NEURON 2 GRADIENTS ],
                    etc...
                ],

                // LAYER 2
                [
                    [ NEURON 1 GRADIENTS ],
                    [ NEURON 2 GRADIENTS ],
                    etc...
                ],

                etc...
            ]
        */
        var networkGradients: [[BackpropagationValues]] = [ ]
        
        // compute layers' neurons' decents
        for (layerIndex, errors) in layerErrors.enumerate()
        {
            let layer = self.layers[layerIndex]
            
            // represents the gradients of every weight for every neuron in this layer
            /* structure:
                [
                    [ NEURON 1 GRADIENTS],
                    [ NEURON 2 GRADIENTS],
                    etc...
                ]
            */
            var layerGradients: [BackpropagationValues] = [ ]
            
            // loop through each neuron
            for (neuronIndex, neuron) in layer.neurons.enumerate()
            {
                // get the error for this neuron
                let neuronError = errors[neuronIndex]
                
                // represents the gradients of every weight for this neuron
                /* structure:
                    [ WEIGHT 1 GRADIENT, WEIGHT 2 GRADIENT, etc... ]
                */
                var neuronGradients: [Double] = [ ]
                
                // go through each weight
                for weightIndex in 0..<neuron.weights.count
                {
                    // get the input for this weight
                    let inputToThisWeight = outputs[layerIndex][weightIndex]
                    
                    // calculate the gradient (error * the activation of the neuron pointing to this neuron of the previous layer)
                    // the activation is also the "input to this weight", which is easier for me to grasp, so that's what
                    // the variable will be anmed
                    let weightGradient = inputToThisWeight * neuronError
                    
                    // add to our neuron gradient array
                    neuronGradients.append(weightGradient)
                }
                
                // add this neuron to the layer gradients array
                layerGradients.append(BackpropagationValues(gradients: neuronGradients, neuronError: neuronError))
            }
            
            // add this layer to the network gradients array
            networkGradients.append(layerGradients)
        }
        
        return networkGradients
    }
    
    func train(inputs: [[Double]], desiredOutputs: [[Double]], learningRate: Double = 1) throws
    {
        // holds all the gradients
        // I know an array in an array in an array in an array is probably bad programming practice, but whatever
        // to comprehend what's happening here, see the "computeGradient" function's comments
        var allNetworkGradients: [[[BackpropagationValues]]] = [ ]
        
        // loop through ever "mini batch" (set of inputs with desired outputs)
        for miniBatchIndex in 0..<inputs.count
        {
            let batchInputs = inputs[miniBatchIndex]
            let batchDesiredOutputs = desiredOutputs[miniBatchIndex]
            
            let miniBatchNetworkGradient = try computeGradient(batchInputs, desiredOutputs: batchDesiredOutputs)
            allNetworkGradients.append(miniBatchNetworkGradient)
        }
        
        // start with the first batch
        var networkGradientsSums = allNetworkGradients[0]
        
        // loop through every batch
        for (networkIndex, networkGradients) in allNetworkGradients.enumerate()
        {
            // see if it's our first / last
            let firstNetwork = networkIndex == 0
            let lastNetwork = networkIndex == allNetworkGradients.count - 1
            
            // loop through each neuron / weight
            for (layerIndex, layerGradients) in networkGradients.enumerate()
            {
                for (neuronIndex, backpropValues) in layerGradients.enumerate()
                {
                    // if it's not the first network, add it to the sum
                    // (the first is already included)
                    if !firstNetwork
                    {
                        networkGradientsSums[layerIndex][neuronIndex].neuronError += backpropValues.neuronError
                    }
                    
                    // if it's the last network, update the bias
                    if lastNetwork
                    {
                        let averageError = networkGradientsSums[layerIndex][neuronIndex].neuronError / Double(layerGradients.count)
                        self.layers[layerIndex].neurons[neuronIndex].bias += learningRate * averageError
                    }
                    
                    // sum / update weight gradients
                    for (weightIndex, gradient) in backpropValues.gradients.enumerate()
                    {
                        // if it's not the first network, add it to the sum
                        // (the first is already included)
                        if !firstNetwork
                        {
                            networkGradientsSums[layerIndex][neuronIndex].gradients[weightIndex] += gradient
                        }
                        
                        // if this is the last network, update the weight
                        if lastNetwork
                        {
                            // compute the average (by dividing by the total number of networks)
                            let averageGradient = networkGradientsSums[layerIndex][neuronIndex].gradients[weightIndex] / Double(allNetworkGradients.count)
                            
                            // update the weight
                            self.layers[layerIndex].neurons[neuronIndex].weights[weightIndex] += learningRate * averageGradient
                        }
                    }
                }
            }
        }
    }
}

func sigmoid(input: Double) -> Double
{
    return 1 / (1 + exp(-input))
}

func sigmoid_derivative(input: Double) -> Double
{
    let sigmoidOuput = sigmoid(input)
    return sigmoidOuput - pow(sigmoidOuput, 2)
}

RandomNumberExtensions.swift

//
//  NumberExtensions.swift
//  BestColor
//
//  Created by Stevie Hetelekides on 9/15/15.
//  Copyright (c) 2015 Expetelek. All rights reserved.
//

import Foundation

public extension Int
{
    public static func random(upperBound: Int) -> Int
    {
        return Int(arc4random_uniform(UInt32(upperBound)))
    }
    
    public static func random(min min: Int, max: Int) -> Int
    {
        return Int(arc4random_uniform(UInt32(max - min + 1))) + min
    }
}

public extension Double
{
    public static func random() -> Double
    {
        return Double(arc4random()) / 0xFFFFFFFF
    }
    
    public static func random(min min: Double, max: Double) -> Double
    {
        return Double.random() * (max - min) + min
    }
}

public extension CGFloat
{
    public static func random() -> CGFloat
    {
        return CGFloat(arc4random()) / 0x7FFFFFFF
    }
    
    public static func random(min min: CGFloat, max: CGFloat) -> CGFloat
    {
        return CGFloat.random() * (max - min) + min
    }
}

Sex.swift

//
//  Sex.swift
//  BestColor
//
//  Created by Stevie Hetelekides on 9/15/15.
//  Copyright (c) 2015 Expetelek. All rights reserved.
//

import Foundation

class Genome : Comparable
{
    var fitness: Double = 0
    private(set) var weights: [Double]
    private(set) var inputs: Int?
    private(set) var outputs: Int?
    private(set) var hiddenLayers: Int?
    private(set) var neuronsPerHiddenLayer: Int?
    
    init(weights: [Double])
    {
        self.weights = weights
    }
    
    convenience init(inputs: Int, outputs: Int, hiddenLayers: Int, neuronsPerHiddenLayer: Int)
    {
        var numberOfWeights = 0
        var neuronsInPreviousLayer = inputs
        for _ in 0..<hiddenLayers
        {
            numberOfWeights += (neuronsPerHiddenLayer + 1) * (neuronsInPreviousLayer + 1)
            neuronsInPreviousLayer = neuronsPerHiddenLayer
        }
        
        numberOfWeights += (neuronsPerHiddenLayer + 1) * outputs
        
        self.init(numberOfWeights: numberOfWeights)
        
        self.inputs = inputs
        self.outputs = outputs
        self.hiddenLayers = hiddenLayers
        self.neuronsPerHiddenLayer = neuronsPerHiddenLayer
    }

    init(numberOfWeights: Int)
    {
        self.weights = [ ]
        
        for _ in 0..<numberOfWeights
        {
            self.weights.append(Double.random(min: -1, max: 1))
        }
    }
}

class Population
{
    var crossOverProbability: Double = 0.7
    var mutatationProbability: Double = 0.05
    var mutationAmount: Double = 10
    var fittestCopies = 1
    
    private(set) var generation: Int = 1
    private(set) var genomes: [Genome] = [ ]
    
    init(size: Int, numberOfWeightsPerGenome: Int)
    {
        for _ in 0..<size
        {
            // generate a new genome
            let genome = Genome(numberOfWeights: numberOfWeightsPerGenome)
            self.genomes.append(genome)
        }
    }
    
    init(genomes: [Genome])
    {
        self.genomes = genomes
    }
    
    func computeWorstAverageBest() -> (worst: Double, average: Double, best: Double)
    {
        var best: Double = 0
        var worst: Double = 0xFFFFFFFFFFFFFFFF
        var sum: Double = 0
        
        // calculate worst, best, average
        for genome in self.genomes
        {
            if genome.fitness < worst
            {
                worst = genome.fitness
            }
            
            if genome.fitness > best
            {
                best = genome.fitness
            }
            
            sum += genome.fitness
        }
        
        let average = sum / Double(self.genomes.count)
        return (worst, average, best)
    }
    
    private func rouletteSelectGenome() -> Genome
    {
        let maxFitness = self.genomes.maxElement()!.fitness
        
        while true
        {
            // generate threshold
            let randomIndex = Int.random(self.genomes.count)
            let threshold = self.genomes[randomIndex].fitness / maxFitness
            
            // if the random value is greater than the threshold, return
            if (Double.random() < threshold)
            {
                return self.genomes[randomIndex]
            }
        }
    }
    
    private func crossOver(parent1: Genome, parent2: Genome) -> [Genome]
    {
        // check pre conditions
        let sameParent = parent1 == parent2
        let amountOfWeightsDontMatch = parent1.weights.count != parent2.weights.count
        let shouldPerformCrossOver = Double.random() <= self.crossOverProbability
        
        if (sameParent || amountOfWeightsDontMatch || shouldPerformCrossOver)
        {
            return [ Genome(weights: parent1.weights), Genome(weights: parent2.weights) ]
        }
        
        // get number of weights (both parents are the same), get random point
        let numberOfWeights = parent1.weights.count
        let crossOverPoint = Int.random(min: 1, max: numberOfWeights - 1)
        
        // execute cross over
        var babies = [ Genome(numberOfWeights: numberOfWeights), Genome(numberOfWeights: numberOfWeights) ]
        for i in 0..<crossOverPoint
        {
            babies[0].weights[i] = parent1.weights[i]
            babies[1].weights[i] = parent2.weights[i]
        }
        
        for i in crossOverPoint..<numberOfWeights
        {
            babies[0].weights[i] = parent2.weights[i]
            babies[1].weights[i] = parent1.weights[i]
        }
        
        return babies
    }
    
    private func mutateGenome(genome: Genome)
    {
        for index in 0..<genome.weights.count
        {
            // see if we should mutate this chromosome
            if (Double.random() <= self.mutatationProbability)
            {
                // mutate it +- mutationAmount * random
                genome.weights[index] += Double.random(min: -1, max: 1) * self.mutationAmount
            }
        }
    }
    
    func mutatePopulation()
    {
        let originalGenomeCount = self.genomes.count
        
        // copy the fittest genome
        let fittestGenome = self.genomes.maxElement()!
        if fittestGenome.fitness == 0
        {
            let weightsPerGenome = self.genomes[0].weights.count
            self.genomes.removeAll(keepCapacity: true)
            
            for _ in 0..<originalGenomeCount
            {
                // generate a new genome
                let genome = Genome(numberOfWeights: weightsPerGenome)
                self.genomes.append(genome)
            }
            
            ++self.generation
        }
        else
        {
            for _ in 0..<self.fittestCopies
            {
                self.genomes.append(fittestGenome)
            }
            
            // create new genome
            var newGenomes: [Genome] = [ ]
            while newGenomes.count < originalGenomeCount
            {
                // select parents
                let parent1 = self.rouletteSelectGenome()
                let parent2 = self.rouletteSelectGenome()
                
                // make babies
                let babies = self.crossOver(parent1, parent2: parent2)
                
                // mutate babies
                self.mutateGenome(babies[0])
                self.mutateGenome(babies[1])
                
                newGenomes.append(babies[0])
                newGenomes.append(babies[1])
            }
            
            // update current genome
            self.genomes = newGenomes
            ++self.generation
        }
    }
}

func ==(left: Genome, right: Genome) -> Bool
{
    return left.fitness == right.fitness
}

func <=(left: Genome, right: Genome) -> Bool
{
    return left.fitness <= right.fitness
}

func >=(left: Genome, right: Genome) -> Bool
{
    return left.fitness >= right.fitness
}

func >(left: Genome, right: Genome) -> Bool
{
    return left.fitness > right.fitness
}

func <(left: Genome, right: Genome) -> Bool
{
    return left.fitness < right.fitness
}