GAで"Hello, world!"

2013-06-01
#ruby

遺伝的アルゴリズムの入門として、Machine Learning: Introduction to Genetic Algorithms | Burak Kanber’s Blog がわかりやすかったので、Rubyで試してみた。

件の記事はHello, world!という文字列を遺伝的アルゴリズムで生成する、という内容。仕組みは、13個の文字(0~255のasciiコード)が遺伝情報。世代を進めるには、それぞれの個体の答えとの差の二乗和をコストとして計算する。コストが小さいトップの2つの個体同士を交配させ（それぞれの遺伝子を真ん中で分割して、つなぎ替える）、新しい子供2匹を誕生させる。そしてドベの2つを殺す。なので世代が進んでも全体の個数は保たれる。そしてすべての個体を50%の確率で突然変異（1文字をasciiコードで1増やす、または減らす）させる。

class Gene
  attr_reader :code, :cost

  def initialize(code = '')
    @code = code
    @cost = 10 ** 10
  end

  def random(length)
    @code = (0...length).map {rand(256).chr}.join
  end

  def calc_cost(compare_to)
    total = 0
    @code.length.times do |i|
      d = compare_to[i].ord - @code[i].ord
      total += d * d
    end
    @cost = total
    return @cost
  end

  def mate(gene)
    pivot = @code.length / 2 - 1
    child1 = @code[0...pivot] + gene.code[pivot..-1]
    child2 = gene.code[0...pivot] + @code[pivot..-1]
    return Gene.new(child1), Gene.new(child2)
  end

  def mutate(chance)
    return if rand > chance

    index = rand(@code.length)
    up_or_down = rand < 0.5 ? -1 : 1
    new_char = ((@code[index].ord + up_or_down) & 255).chr
    @code = @code[0...index] + new_char + @code[(index + 1) .. -1]
  end

  def to_s
    @code.inspect
  end
end

class Population
  def initialize(goal, size)
    @members = []
    @goal = goal
    @generation_number = 0
    size.times do
      gene = Gene.new
      gene.random(@goal.length)
      @members.push(gene)
    end
  end

  def sort
    @members.sort! {|a, b| a.cost <=> b.cost}
  end

  def generation
    @members.each do |member|
      member.calc_cost(@goal)
    end

    sort
    #display

    child1, child2 = @members[0].mate(@members[1])
    @members = @members[0...-2] + [child1, child2]

    @members.each do |member|
      member.mutate(0.5)
      member.calc_cost(@goal)
      if member.code == @goal
        sort
        #display
        return true
      end
    end
    @generation_number += 1
    return false
  end

  def to_s
    "Population: generation:#{@generation_number}, best:#{@members[0]}"
  end
end


population = Population.new('Hello, world!', 20)
until population.generation
  p population
end

p population
  • 実際の動作を見るには：http://codepad.org/A1imEb3P 運がよいと成功する。
  • 20個体で走らせて、だいたい1000世代くらいで答えにたどり着く。
  • 「これは遅い、しかしどこが非効率かを見つけ、直するのは簡単だろう」というんだけど、どこが問題なのかわからない…
  • 個体数を100とかに増やすと、世代数は減る。が、増やしすぎると負荷がかかる。
  • 交配させるときに常に真ん中でつなぎ変えてるのは、2回繰り返すと元に戻ってしまうけどいいのか？試しにつなぎ替えるピボットの位置を乱数で選んでも、世代数はあまり変わらないようだ。
  • 突然変異の割合が50%って相当高いように思うけど、割合を下げると世代がかかるようになる。
  • 突然変異で変化するのが、+1または-1だと正解にたどり着くまでに時間がかかるんじゃないか、とも思って完全にランダムにすると、より時間がかかるようになる。これは+1または-1の場合、50%の確率で正解に近づくのに対し、ランダムにしてしまうと最終的に1/256になってしまうからかもしれない。

関連記事

新着記事