Genetic Algorithm in CoffeeScript

genetic.js.coffee

# Add some useful features to array prototypes
Array::fold     = (initial, fn) -> initial = fn initial, x for x in @; initial
Array::sum      = -> @fold 0, (memo, i) -> memo + i
Array::mean     = -> @sum() / @length
Array::max      = -> Math.max.apply {}, @
Array::min      = -> Math.min.apply {}, @
Array::median   = -> if @length % 2 is 0 then (@[@length/2-1]+@[@length/2])/2 else @[Math.ceil @length/2]
Array::variance = -> avg = @mean(); @fold(0, (memo, i) -> memo + Math.pow i-avg, 2) / @length
Array::std_dev  = -> Math.sqrt @variance()

# Give us an easy random integer
RANDOM_INT = (n = 100, m = 0) ->
  [max, min] = if n > m then [n, m] else [m, n]
  Math.floor(Math.random() * (max - min + 1) + min)

# Constants
GENE_LENGTH = 64
MUTATION_RATE = 0.05

# Alphabet
BASES = ['C', 'A', 'G', 'T']

# Give us a random base from our alphabet
RANDOM_BASE = -> BASES[RANDOM_INT BASES.length-1]

# Organism with perfect fitness
MODEL_SPECIMEN = 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'

class Individual

  # Create an individual with specified 'genes', or randomly generate genes if none are provided
  constructor: (@genes = @random_gene GENE_LENGTH) ->

  # Give us a random gene
  random_gene: (length) -> (RANDOM_BASE() for i in [0...GENE_LENGTH]).join ''

  # Use Levenschtein distance algorithm to calculate fitness
  # Fitness ranges from 0-100
  fitness: (solution = MODEL_SPECIMEN) ->
    matrix = []
    for i in [0..GENE_LENGTH]
      matrix[i] ?= []
      matrix[i][0] = i
    for i in [0..GENE_LENGTH]
      matrix[0][i] = i

    for i in [1..GENE_LENGTH]
      for j in [1..GENE_LENGTH]
        matrix[i] ?= []
        if @genes[i-1] is solution[j-1]
          matrix[i][j] = matrix[i-1][j-1]
        else
          matrix[i][j] = Math.min matrix[i-1][j] + 1, matrix[i][j-1] + 1, matrix[i-1][j-1] + 1

    100 - (matrix[GENE_LENGTH][GENE_LENGTH] / (GENE_LENGTH / 100))

  # Mate an individual with another individual
  # Sometimes mutates genes (according to MUTATION_RATE)
  # Returns a child
  # :: Individual -> Int -> Individual
  mate: (other, uniform_rate = 0.5) ->
    s = ''
    for i in [0...GENE_LENGTH]
      s += if Math.random() <= MUTATION_RATE
        RANDOM_BASE()
      else if Math.random() <= uniform_rate
        @genes[i]
      else
        other.genes[i]
    new Individual s

class Population

  # Create a population of a certain size
  constructor: (@target_size = 10) ->
    @pop = (new Individual for i in [0...@target_size])
    @is_dirty = yes

  size: -> @pop.length

  # Get a random individual from the population
  random_individual: -> @pop[RANDOM_INT @pop.length-1]

  # Get the fittest of the bunch
  fittest: -> @pop.fold @pop[0], (memo, i) -> if i.fitness() > memo.fitness() then i else memo

  # Get all the fitnesses in an array.  Caches them so I don't recalculate them
  # whenever I calculate a statistic
  fitnesses: ->
    if @is_dirty
      @_fitnesses = new Array
      @_fitnesses.push individual.fitness() for individual in @pop
      @is_dirty = no
    @_fitnesses

  # Evolves the population in a 'natural' way.
  # More fitness = increased chance of mating, less chance of dying and vice versa
  # Doesn't work that great
  evolve: ->
    [@is_dirty, i] = [yes, i]
    while i < @pop.length

      fitness = @pop[i].fitness()

      mate_chance  =  0.9 * fitness + 5
      death_chance = -0.9 * fitness + 5
      overcrowding_bonus = 75

      death_chance += overcrowding_bonus if @pop.length > @target_size

      # Mating
      if RANDOM_INT() <= mate_chance and @pop.length > 1

        # Get a random individual's index until it isn't this individual's index
        loop if (mate_idx = RANDOM_INT @pop.length-1) isnt i then break
        
        # Mate them and add to population
        @pop.push @pop[i].mate @pop[mate_idx]

      # Kill the individual by removed it from the population
      if RANDOM_INT() <= death_chance then @pop.splice i, 1

      i += 1

  # Evolves better.  Kills everyone less than a Std Dev above mean fitness, refills population
  # by mating the rest randomly.
  super_evolve: ->
    @is_dirty = yes

    # Kill subpar individuals (create new array with only 'fit' individuals)
    @pop = (p for p in @pop when p.fitness() > @fitnesses().mean() + @fitnesses().std_dev())

    # Mate randomly until we fulfill our target size
    @pop.push @random_individual().mate @random_individual() while @pop.length < @target_size

  to_s: ->
    """
    Pop Size  : #{@size()}
    Max       : #{@fitnesses().max()}
    Min       : #{@fitnesses().min()}
    Mean      : #{@fitnesses().mean()}
    Median    : #{@fitnesses().median()}
    Variance  : #{@fitnesses().variance()}
    Std Dev   : #{@fitnesses().std_dev()}
    Fittest:  : #{@fittest().genes}
"""

pop1 = new Population 100
pop2 = new Population 100

print_pops = (gen_number) ->
  console.log """
  Generation #{gen_number}

  Population 1
  ---
  #{pop1.to_s()}
  ---

  Population 2
  #{pop2.to_s()}
  ---

"""
evolve_pops = (n) -> (pop1.evolve(); pop2.super_evolve()) for i in [0...n]

print_pops(0)

evolve_pops(10)
print_pops(10)

evolve_pops(10)
print_pops(20)

evolve_pops(10)
print_pops(30)