円周率チャレンジを遺伝的アルゴリズムで解く

はじめに

本記事はある程度遺伝的アルゴリズム/Rubyの知識がある人向けの雑な記事になってます．
遺伝的アルゴリズムに関しては【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】が非常に参考になります．（ここのコードをほぼコピペしています）

円周率チャレンジとは

円周率チャレンジというゲームで， ＋２をする操作とsqrtを取る操作を繰り返して，円周率に近づけようというものです．
これを見たときに，遺伝的アルゴリズムが使えそうだと思い付き挑戦してみました．
今回は，最適解ではないにしろ良い値を作ろうという企画になってます．（これがある今必要なのかという疑問はおいておきます）

やったこと

sqrt,+2,何もしないという３つの操作を0,1,2の値に対応させ，これを遺伝子一個の値としました．
また記事に習って．成績の良いものから選択し，それらを二点交差させた後に，ランダムに遺伝子の値を変異させています．

コード

汚く雑なものですが，以下コードになります．

main.rb

require_relative './genom'
# 遺伝子情報の長さ
GENOM_LENGTH = 70
# 遺伝子集団の大きさ
MAX_GENOM_LIST = 100
# エリート遺伝子選択数
SELECT_GENOM = 20
# 個体突然変異確率
INDIVIDUAL_MUTATION = 0.15
# 遺伝子突然変異確率
GENOM_MUTATION = 0.10
# 繰り返す世代数
MAX_GENERATION = 4000

# GENOM_LENGT分のランダムな遺伝子を持つGenomを生成する
def create_genom()
  random = Random.new
  return Genom.new((1..GENOM_LENGTH).to_a.map{random.rand(0..2)})
end

# SELECT_GENOMだけ成績上位のGenom達を取り出す
def select(gas)
  gas.sort_by {|ga| -ga.evaluation }[0..SELECT_GENOM-1]
end

# エリートとその子孫の数だけ成績下位のGenomを削除し，エリート及びその子孫のリストと結合する
def next_generation_gene_create(gas, ga_elite, ga_progeny)
  next_generation_geno = gas.sort_by {|ga| -ga.evaluation }[ga_elite.size+ga_progeny.size..-1]
  next_generation_geno += ga_elite
  next_generation_geno += ga_progeny
  next_generation_geno
end

# 設定した確率に従い，genom_listの一部を変異させる
def mutation(gas)
  random = Random.new
  ga_list = []
  gas.each {|ga|
    if INDIVIDUAL_MUTATION > random.rand(0..99)/100.0
      genom_list = ga.genom_list.map { |g|
        if GENOM_MUTATION > random.rand(0..99)/100.0
          random.rand(0..2)
        else
          g
        end
      }
      ga_list.push(Genom.new(genom_list))
    else
      ga_list.push(ga)
    end
  }
  ga_list
end

# 世代ごとに結果を表示する
def print_result(gas, i)
  fits = gas.map{|ga| ga.evaluation} 
  min_ = fits.min
  max_ = fits.max
  avg_ = fits.sum / fits.size
  puts "-----第#{i}世代の結果-----"
  puts "  Min:#{min_}"
  puts "  Max:#{'%e' % max_}"
  puts "  Avg:#{'%e' % avg_}"
end

# mainの始まり
gas = (1..MAX_GENOM_LIST).to_a.map{create_genom()}
MAX_GENERATION.times {|i|
  elite_genes = select(gas)
  progeny_gene = []
  (elite_genes.size-1).times{|i|
    progeny_gene += elite_genes[i+1].crossover(elite_genes[i])
  }
  next_generation_group = next_generation_gene_create(gas, elite_genes, progeny_gene)
  next_generation_group = mutation(next_generation_group)

  print_result(gas, i)
  gas = next_generation_group
}
# 最後に結果を表示
elite = select(gas)[0]
puts "最も優れた個体は"
puts "評価: #{'%e' % elite.evaluation}"
puts "pi: #{elite.pi}"
puts "個体: #{elite.genom_list.select{|g| g != 2}}"
puts 
elite.print_operation

genom.rb

class Genom 
  attr_accessor :genom_list, :evaluation, :pi
  def initialize(genom_list)   
    @genom_list = genom_list
    @evaluation, @pi = evaluate()
    @len = @genom_list.size
  end

  # 手順を見やすく表示する
  def print_operation()
    operation_list = @genom_list.select{|g| g != 2}
    puts "計#{operation_list.size}回"
    before = operation_list[0]
    count = 1
    operation_list[1..-1].each { |g|
      if before == g 
        count +=1    
      else
        if before == 1
          puts "+2を#{count}回"
        else
          puts "sqrtを#{count}回"
        end
        count = 1
        before = g
      end
    }
    if before == 1
      puts "+2を#{count}回"
    else
      puts "sqrtを#{count}回"
    end
  end

  # 交配させる
  def crossover(ga) 
    random = Random.new
    cross_one = random.rand(0..@len-1)
    cross_second = random.rand(cross_one..@len-1)
    if cross_second == @len-1
      progeny_one = @genom_list[0..cross_one]+ga.genom_list[cross_one+1..cross_second] 
      progeny_sec = ga.genom_list[0..cross_one]+@genom_list[cross_one+1..cross_second] 
    else
      progeny_one = @genom_list[0..cross_one]+ga.genom_list[cross_one+1..cross_second] + @genom_list[cross_second+1..-1]
      progeny_sec = ga.genom_list[0..cross_one]+@genom_list[cross_one+1..cross_second] + ga.genom_list[cross_second+1..-1]
    end
    return [Genom.new(progeny_one), Genom.new(progeny_sec)]
  end

  private
  def evaluate()
    res = 0
    @genom_list.each { |g|
      if g==1 
        res += 2
      elsif g==0
        res = Math.sqrt(res)
      end
    }
    return 1/(res-Math::PI).abs, res
  end
end

Genomが主に遺伝子情報や評価値などを格納するクラスになっています．
流れとしては

1. ランダムに初期遺伝子群を決める
2. 遺伝子群からエリートを選択
3. 選択したもの同士で二点交差
4. エリート＋子孫＋あまりを前世代遺伝子群から選び，次世代とする
5. 結果を表示し，世代を入れ替えて2に戻る

ハイパーパラメータはいい感じに変えてください

結果

何度も実行するといい結果が出たり出なかったります．完全にガチャ
一例としては

-----第3999世代の結果-----
  Min:0.23832580163584324
  Max:1.593089e+10
  Avg:7.487520e+09
最も優れた個体は
評価: 1.593089e+10
pi: 3.1415926536525642
個体: [1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1]

計48回
+2を4回
sqrtを1回
+2を8回
sqrtを1回
+2を1回
sqrtを1回
+2を4回
sqrtを2回
+2を1回
sqrtを2回
+2を3回
sqrtを1回
+2を1回
sqrtを2回
+2を5回
sqrtを1回
+2を1回
sqrtを1回
+2を3回
sqrtを4回
+2を1回

な感じです．
ハイパーパラメータを変えたりすれば良い結果出るのでしょうか．誰か教えてください．．．

まとめ

遺伝的アルゴリズムを用いて，円周率チャレンジに挑戦しました．
結果としてはInfinityを除いて，30位ぐらいに入る出力もでました． ただ打ち込むのがだるいのであまりやっていないのが現状です．
楽に打ち込む方法とか，そもそもアルゴリズムがだめとか，指摘があればぜひコメントしていただきたいです．
ここまで読んでいただき，ありがとうございました．