The Code Files

[Ruby] Genetic String Evolver

Inspired by Richard Dawkins' weasel program, this is a genetic algorithm, written in Ruby, to evolve the same "METHINKS IT IS LIKE A WEASEL" string. It's really fun to experiment with changing the probability constants (mutation, reproduction) and the algorithm in Evolver#advance, which advances the population of strings to the next generation. Have fun!

The default algorithm works as follows:

Initialize a population of random strings.
Mutate each string with probability 'mutation_probability'.
Breed each string with another random string from the population with probability 'breed_probability', keeping the newborn population separate.
Kill random newborns until the number of newborns is less than 1/4 of the size of the main population.
Select a random half of the main population and replace its weakest (furthest from the target) members with the remaining newborns.
Go back to Step 2.

In about 5000-10000 generations, the strongest member of the population stabilizes to the target string.

The same algorithm can be applied to other problems, like finding the maximum of a mathematical function, by just modifying Weasel.rb.

Sample Output

The left column is the population's strongest member. The right column is the population's weakest member.

YAPXMLHQFORHPPNVWF DISTEBZEK -- vs. -- YZLHUURLMPKITAP ZYVTTSIZZCQV (Gen: 0)
YAPXMLHQFORHPPNVWF DISTEBZEK -- vs. -- CXZWQCVCUAZFDOUSZNRCXDQPNENR (Gen: 1)
YAEBXJFACES FVUTYWTLATTIACDY -- vs. -- CXZWQCVCUAZFDOUSZNRCXDQPNENR (Gen: 2)
YAEBXJFACES FVUTYWTLATTIACDY -- vs. -- J ICBDLWUGASSNRS YENZDLVBJ V (Gen: 3)
YAEBXJFACES FVUTYWTLATTIACDY -- vs. -- NJQPSUPJUBEUQGNEBPRCMHIVBJ V (Gen: 4)
YAEBXJFACES FVUTYWTLATTIACDY -- vs. -- NJQPSUPJUBEUQGNEBPRCMHIVBJ V (Gen: 5)
YAEBXJFACES FVUTYWTLATTIACDY -- vs. --  RQPSUPJUBEUQWSFJTJ OWHRTKIM (Gen: 6)
MDLDIGLMBUJPTV LWEC W FMNINL -- vs. -- ZXZNNKDUGWIVLKARQLMDKCIZ FGW (Gen: 7)
MDLDIGLMBUJPTV LWEC W FMNINL -- vs. -- ZXZNNKDUGWIVLKARQLMDKCIZ FGW (Gen: 8)
...
MDPXKNIS MVHXZ LHCC W ODACEL -- vs. -- MDLDMFQS MVHCZ LHCCGW IQACDY (Gen: 100)
MDPXKNIS MVHXZ LHCC W ODACEL -- vs. -- MDJDIFVS M DAS HHXC W TSACEL (Gen: 101)
MDPXKNIS MVHXZ LHCC W ODACEL -- vs. -- MDJDMNQS MVGXZ LHCC W FQACDL (Gen: 102)
MADIMNQS MVDXZ LHCE W ODACEL -- vs. -- MDJDMNQS MVGXZ LHEC W FMACIL (Gen: 103)
MDPXKNQS MVDAS HHCE W ODACEL -- vs. -- MDJDMNQS MVGXZ LHEC W FMACIL (Gen: 104)
MDPXKNQS MVDAS HHCE W ODACEL -- vs. -- MAPXYNCM MVHXZ LHTC D DQACIL (Gen: 105)
...
METHINIS ITHIS LHKE A VMAQEL -- vs. -- METHINIS IVHWS LHKEXA VMAQEL (Gen: 400)
METHINIS ITHIS LHKE A VMAQEL -- vs. -- METHINIS RVHIS LHKEEA VMAQEL (Gen: 401)
METHINIS ITHIS LHKE A VMAQEL -- vs. -- METHINIS RVHIS LHKEEA VMAQEL (Gen: 402)
METHINIS ITHIS LHKE A VMACEL -- vs. -- METHINIS IVHWS LHKEXA VMAQEL (Gen: 403)
METHINIS ITHIS LHKE A VMAQEL -- vs. -- METHFNIS RVHIS LHKE A VMAQEL (Gen: 404)
METHINIS ITHIS LHKE A VMAQEL -- vs. -- METHFNIS RRHIS LHKE A VMAQEL (Gen: 405)
...
METHINIS IV IS LHKE A WMAQEL -- vs. -- MVTHINIS IV IS QHKE AMVMAQEL (Gen: 800)
METHINIS IV IS LHKE A WMAQEL -- vs. -- METUINIS IV IS LHKE AMVMEQEL (Gen: 801)
METHINIS IV IS LHKE A WMAQEL -- vs. -- METUINIS IV IS LHKE AMVMEQEL (Gen: 802)
METHINIS IV IS LHKE A WMAQEL -- vs. -- METUINIS IV IS LHKE AMVMEQEL (Gen: 803)
METHINIS IV IS LHKE A WMAQEL -- vs. -- METHINIS IVQISKLHKE A VMAQEL (Gen: 804)
METHINIS IV IS LHKE A WMAQEL -- vs. -- METCINIS IV RS LHKK A WMAQEL (Gen: 805)
...
METHINKS IT IS LIKE A WEAWEL -- vs. -- ROTHINKS IT IS LIKE A WEAHEL (Gen: 5106)
METHINKS IT IS LIKE A WEAWEL -- vs. -- MOTHINKS ITSIS VIKE A WEAWEL (Gen: 5107)
METHINKS IT IS LIKE A WEAWEL -- vs. -- MOTHINKS ITSIS VIKE A WEAWEL (Gen: 5108)
METHINKS IT IS LIKE A WEAWEL -- vs. -- METHINKSOIT IS LIKE A WEAWEL (Gen: 5109)
METHINKS IT IS LIKE A WEASEL -- vs. -- METHINKSOIT IS LIKE A WEAWEL (Gen: 5110)

Main.rb

require './Evolver.rb'
require './Weasel.rb'

evolver = Evolver.new( Weasel )
evolver.setup

i = 0
while 1
  print "#{evolver.best} -- vs. -- #{evolver.worst} (Gen: #{i}) \r"
  evolver.advance
  i += 1
end

Evolver.rb

# WARNING: I have never even read `On the Origin of Species` so do not mistake
# this horrible code to be anything like what happens in nature.

class Evolver

  attr_reader :population
  attr_accessor :population_size, :mutation_probability, :breed_probability

  def initialize( klass )
    @entity = klass
    @population = []
    @population_size = 100
    @mutation_probability = 0.07
    @breed_probability = 0.3
  end

  def setup
    @population_size.times do |i|
      @population << @entity.random
    end
  end

  def advance
    @population.each do |subject|
      if rand() <= @mutation_probability
        subject.mutate
      end
    end

    newborns = []
    @population.each do |subject|
      if rand() <= @breed_probability
        newborns << subject.breed( @population[rand(population.length)] )
      end
    end

    # Limit the number of newborns to at most 1/4 of the population size.
    if newborns.length * 4 > @population.length
      newborns.shuffle!
      newborns = newborns.first( @population.length / 4 )
    end

    # Select a random half of the population to be candidates for dying.
    killed = @population.shuffle.first( @population.length / 2 )
    # Sort them by goodness value in increasing order.
    killed.sort! do |a,b|
      if a.goodness < b.goodness
        -1
      elsif b.goodness > a.goodness
        1
      else
        0
      end
    end

    # Replace the weakest death candidates with the newborns.
    newborns.each_with_index do |subj,k|
      idx = @population.index( killed[k] )
      @population[idx] = subj
    end
  end

  def best
    @population.inject do |a,b|
      ( a.goodness > b.goodness ) ? a : b
    end
  end

  def worst
    @population.inject do |a,b|
      ( a.goodness > b.goodness ) ? b : a
    end
  end

end

Weasel.rb

class Weasel
  attr_reader :str

  ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
  TARGET = "METHINKS IT IS LIKE A WEASEL"

  def self.random
    str = ""
    TARGET.length.times do |i|
      str << ALPHABET[rand(ALPHABET.length)]
    end
    return Weasel.new( str )
  end

  def initialize( str )
    @str = str
  end

  def mutate
    @str[rand(@str.length)] = ALPHABET[rand(ALPHABET.length)]
  end

  def breed( organism )
    split = rand(@str.length)
    front = @str[0...split]
    back = organism.str[split...organism.str.length]
    return Weasel.new( front + back )
  end

  def goodness
    hamming = 0
    0.upto( @str.length - 1 ) do |i|
      hamming += (@str[i].ord ^ TARGET[i].ord).to_s(2).count("1")
    end
    return -hamming
  end

  def to_s
    @str
  end

end

social