はじめに
本記事はある程度遺伝的アルゴリズム/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位ぐらいに入る出力もでました． ただ打ち込むのがだるいのであまりやっていないのが現状です．
楽に打ち込む方法とか，そもそもアルゴリズムがだめとか，指摘があればぜひコメントしていただきたいです．
ここまで読んでいただき，ありがとうございました．