Genetic Algorithm example solving integer combination (depending on the work of Denny Hermawanto, http://arxiv.org/pdf/1308.4675)

ga_example.coffee

# a +2 b +3 c +4 d = 30

class Chromosome

  # ( a b c d ) -> chromosome

  factors: {
    a: 1
    b: 2
    c: 2
    d: 4   
  }

  equals: 30
  minValue: 0
  maxValue: 30
  # only to save index where (and if) the chromosome was operated
  crossoverPoint: null
  mutationPoint: null

  # array with gens
  code: null 

  constructor: ->
    @code = Array(Object.keys(@factors).length)
    for i in [[email protected]]
      @code[i-1] = @randomNumberForVariable()

  clone: ->
    c = new Chromosome()
    for key of @
      if Object.prototype.hasOwnProperty.call(@,key)
        c[key] = @[key]
    c.code = @code.slice()
    return c


  randomNumberForVariable: ->
    # we restrict here the number between 0 and 30
    return Math.round((Math.random()*@maxValue)+@minValue)

  evaluate: ->
    #F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30)
    sum = 0
    @code.forEach (value, i) =>
      factor = @factors[Object.keys(@factors)[i]]
      sum += value * factor
    return Math.abs(sum - @equals)

  fitness: ->
    # the fittest chromosomes have higher probability to be selected for the next generation
    return 1 / ( 1 + @evaluate() ) 

  toString: (marker = '', index = 0, offset = 0)  ->
    # returns a nicer to read function string
    # ↓
    code = @code.slice() # copy array
    if marker
      code.splice(index, 0, marker)
      "( #{code.join(' ')} )"
    else
      "( #{code.join(' ')} )"

  asObjectiveFunction: (usingNumericValues = true) ->
    sum = []
    i = 0
    for name of @factors
      value = if usingNumericValues then @code[i] else name
      sum.push("(#{@factors[name]} * #{value})")
      i++
    return "#{sum.join(' + ')} - #{@equals}"

  probability: (totalFitness) ->
    # P = Fitness / Total
    return @fitness() / totalFitness

  randomCrossoverPoint: (length = @code.length) ->
    # is between 1 and length-2
    # 'a' | 'b' | 'c' | 'd' | 'e'  -> | possible crossover point
    # between 0 and 2 for [a,b,c] 
    Math.round((Math.random()*(length)))

  createDescendantBySingleCrossoverPoint: (secondChromosome, k = null) ->
    if k is null
      k = @randomCrossoverPoint()
    code = @code.slice(0, k).concat(secondChromosome.code.slice(k))
    c = new Chromosome()
    c.code = code
    c.crossoverPoint = k
    return c
    #@createDescendantByCrossoverPoints(k, secondChromosome)

class SolvingCombinationWithGeneticAlgorithm

  numberOfChromosomes: 6

  population: []
  parents: []
  pairs: []
  selectedParentsIndex: []

  constructor: (options = {}) ->
    # apply options
    for attr of options
      @[attr] = options[attr]
    @population = []
    @parents = []
    @pairs = []
    @selectedParentsIndex = []
    return @


  initPopulation: ->
    @population = for i in [0..@numberOfChromosomes-1]
      c = new Chromosome()
      c.pos = i
      c
    return @

  evaluate: ->
    for chromosome in @population
      chromosome.evaluate()

  fitness: ->
    for chromosome in @population
      chromosome.fitness()

  totalFitness: ->
    @fitness().reduce (prev, curr, i, array) ->
      prev + curr

  probabilities: ->
    totalFitness = @totalFitness()
    for chromosome in @population
      chromosome.probability(totalFitness)


  cumulativeProbability: ->
    probabilities = @probabilities()
    probs = []
    probabilities.forEach (prob, i) ->
      cprob = if i>0 then probs[i-1] + prob else probabilities[0]
      probs.push(cprob)
    return probs

  selectNextGenerationByRouletteWheel: (randomNumbers = @randomNumbers()) ->
    nextGeneration = []
    cumulativeProbabilities = @cumulativeProbability()
    chromosomes = @population
    for randomProb, i in randomNumbers
      # initially select first
      winner = chromosomes[0]
      for j in [0..cumulativeProbabilities.length-2]
        if randomProb > cumulativeProbabilities[j] and randomProb <= cumulativeProbabilities[j+1]
          winner = chromosomes[j+1]
          break
      winner.pos = i
      nextGeneration.push(winner)
    nextGeneration

  selectPairsByCrossoverRate: (crossoverRate = 0.25) ->
    parents = []
    r = []
    rMap = {}
    pairs = []
    @selectedParents = []
    # R[1] = 0.191
    # R[2] = 0.259
    # R[3] = 0.760
    # …
    indexes = []
    for chromosome, i in @population
      randomR = Math.random() # between 0 and 1
      if randomR < crossoverRate
        parents.push(chromosome)
        # @selectedParentsIndex.push(i)
        @selectedParents.push(chromosome)
        r.push(randomR)
        rMap[randomR] = { chromosome, i }
    r.sort()
    @parents = parents
    parents = @parents.slice() # copy array
    j = @population.length
    for randomR in r
      #              parent#1          parent#2
      parent_1 = parents.shift()
      parent_2 = rMap[randomR].chromosome
      pair = [ parent_1, parent_2 ]
      pairs.push(pair)
      

    return @pairs = pairs

  singlepointCrossover: (pairs = @pairs) ->
    children = []
    children = for pair in pairs
      pair[0].createDescendantBySingleCrossoverPoint(null, pair[1])
    return children
      
  assignChildrenToPopulation: (children) ->
    for child in children
      @population[child.pos] = child
    @population

  mutatePopulation: (mutationRate = 0.1) ->
    totalGen = @population[0].code.length * @population.length
    numberOfMutations = mutationRate * totalGen
    for chromosome, i in @population
      for gene, j in chromosome.code
        rand = (Math.random()*(totalGen-1))+1
        if rand < numberOfMutations
          # which gene should be mutate?
          pos = Math.floor(Math.random()*chromosome.code.length)
          chromosome.mutationPoint = j
          chromosome.code[j] = chromosome.randomNumberForVariable()
    @population


  round: (number, decimal = 10000) ->
    Math.round(number*decimal)/decimal

  randomNumbers: ->
    for chromosome in @population
      Math.random()



#   calcabsoluteAbsoluteValue: (chromosome) ->
#     F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30)

# # f(x) = ((a + 2b + 3c + 4d) - 30)
# # minimizing
# # a,b,c,d e.o. {1,..,30}

log = (description = "", data = "") ->
  if data
    console.log(description, data)
  else
    console.log(description)

logStep = (msg) ->
  @__logStep__ ?= 0
  @__logStep__++
  log("\n#{@__logStep__}. #{msg}\n")


# a = new Chromosome()
# a.code = "abcdef".split('')
# b = new Chromosome()
# b.code = "ghijkl".split('')
# k = a.randomCrossoverPoint()
# console.log a.toString(), b.toString(), "k=#{k}"
# console.log a.createDescendantBySingleCrossoverPoint(b, k).toString()

# process.exit(0)

ga = new SolvingCombinationWithGeneticAlgorithm()
ga.initPopulation()

logStep """
  Initialization

  General objective function:
  f(x) = #{ga.population[0].asObjectiveFunction(false)}

  Generating #{ga.numberOfChromosomes} random chromosomes initially
"""

for iterationStep in [1..300]

  @__logStep__ = 0

  log "\n=> ITERATION ##{iterationStep}\n"

  log "[#{i}]:\t#{chromosome.toString()}" for chromosome, i in ga.population

  logStep """
    Evaluate
  """
  for chromosome, i in ga.population
    log "[#{i}]:\tAbs( #{chromosome.asObjectiveFunction()} )\t = #{chromosome.evaluate()}" 
    if chromosome.evaluate() is 0
      log "\n===>\tFound optimal solution with #{chromosome.toString()}:"
      log "\tAbs( #{chromosome.asObjectiveFunction()} )\t = #{chromosome.evaluate()}"
      log "Iterations: #{iterationStep}"
      process.exit(0)

  logStep """
    Selection
    Fitness for chromosomes
  """
  fitnesses = ga.fitness()
  log "[#{i}]:\t#{ga.round(fitness)}" for fitness, i in fitnesses


  totalFitness = ga.totalFitness()
  log """
    Sum of fitness:
    #{ga.round(totalFitness)}
  """
  probabilities = for chromosome in ga.population
    chromosome.probability(totalFitness)

  log "Probabilities:"
  log "[#{i}]:\t#{ga.round(prob)}" for prob, i in probabilities

  log "Cumulative Probability:"
  log "[#{i}]:\t#{ga.round(prob)}" for prob, i in ga.cumulativeProbability()
  #log "∑ = ", ga.cumulativeProbability().reduce (prev, curr, i, array) -> prev + curr

  randomNumbers = ga.randomNumbers()

  log "Random Numbers between 0 and 1:"
  log "[#{i}]:\t#{ga.round(rand)}" for rand, i in randomNumbers

  log "Selecting next generation by roulette-wheel"
  nextGeneration = ga.selectNextGenerationByRouletteWheel(randomNumbers)
  log "[#{i}]:\t#{chromosome.toString()}" for chromosome, i in nextGeneration

  ga.population = nextGeneration

  crossoverRate = 0.25
  log "Selecting parents, crossoverRate = #{crossoverRate}"
  pairs = ga.selectPairsByCrossoverRate(crossoverRate)
  parents = ga.parents
  log "[#{i}]:\t#{chromosome.toString()}" for chromosome, i in parents
  log "Mixing Pairs"
  log "#{pair[0]?.toString()}\t↔   #{pair[1]?.toString()}" for pair, i in pairs
  log "Singlepoint Crossover"

  children = for pair, i in pairs
    k = new Chromosome().randomCrossoverPoint() # just generate a random k
    child = pair[0].createDescendantBySingleCrossoverPoint(pair[1], k)
    child.pos = pair[0].pos
    log "[#{i}]\tk=#{child.crossoverPoint}\t→   #{child.toString('┇',child.crossoverPoint)}"
    #↓╳
    child

  ga.assignChildrenToPopulation(children)

  log "Result"
  log "[#{i}]:\t#{chromosome.toString()}" for chromosome, i in ga.population

  mutationRate = 0.1
  log "Mutate, mutationRate = #{mutationRate}"
  ga.mutatePopulation()

  for chromosome, i in ga.population
    if chromosome.mutationPoint
      c = chromosome.clone()

      c.code[c.mutationPoint] = "[#{c.code[c.mutationPoint]}]"
      log "[#{i}]:\t#{c.toString()} ←"
    else
      log "[#{i}]:\t#{chromosome.toString()}"