[ruby-list:44164] Re: 2個づつの組を作る方法のすべて

畠山です。

ちょっと結果がおかしいなと思って見直したら、
前回のスクリプト間違っていました。ごめんなさい。

主な勘違い場所は、
(元の組み合わせ情報(Geneインスタンス)を元に複製するとき)
・クラス中で配列を保持していて、かつ
・cloneでインスタンスを複製して
・複製先で配列をいじってしまった
→複製元のインスタンスが保持している配列情報も書き換わってしまう

というのを忘れてやってしまっていました。
リファレンスにもちゃんと書いてあった；
「clone や dup は「浅い(shallow)」コピーであることに注意してください。
　オブジェクト自身を複製するだけで、オブジェクトの指している先
　(たとえば配列の要素など)までは複製しません。 」

ちょっと長くて関係ない人には申し訳ないですが、
修正版コードを最後に添付しておきます。
(冗長性が高く速度もそんなに速くもないですが)

> 解説、script どちらも私に取っては、少し敷居が高いのかなと思います。

スクリプトに関しては個人的に聞いていただいても全然
かまいませんので気軽にメールください。

畠山
[e-mail]


====

# PARAMETERS
NUM_AGENTS = 20
NUM_LEVEL  = 20
NUM_GENE_POOL = 100
MAX_GENERATION = 100
MUTATION_RATE = 0.1

# 20日分の対戦履歴(テスト用、ランダムに生成)
$match_history = []
20.times do 
	list = Array.new(NUM_AGENTS){|i| i}.sort_by{rand}
	pair = []
	pair << list.slice!(0,2) while list.length > 0
	$match_history << pair
end

# 表示
print "対戦履歴\n"
$match_history.each_with_index do |day,i|
	print "day ",i,": "
	day.each do |pair|
		print "[",pair[0],",",pair[1],"]"
	end
	print "\n"
end


# プレーヤー情報(レベルをランダムに設定)
class Agent
	def initialize
		@level = (rand * NUM_LEVEL).truncate
	end
	attr_reader:level
end

# 対戦組み合わせの情報
class Gene
	def initialize(agents, match_history)
		# 新規作成

		@match_history = match_history
		@agents = agents
		# 適当にランダムな2つずつの組をつくる
		list = Array.new(agents.length){|i| i}.sort_by{rand}
		@agent_pair = []
		@agent_pair << list.slice!(0,2) while list.length > 0

		# 評価値を計算しておく
		@fitness = 0
		calc_fitness
	end
	def copy(gene)
		# 既存のGeneを元に複製

		@agent_pair = []
		gene.agent_pair.each do |ap|
			@agent_pair << [ap[0],ap[1]]
		end
		
	end

	attr_reader:agent_pair
	attr_reader:match_history
	attr_reader:fitness

	# プレーヤーaとbの対戦がどのくらい前に行われたかを検索するメソッド
	def search_match(a,b)
		count = match_history.length
		@match_history.each_with_index do |daylist,i|
			daylist.each do |game|
				if (game[0] == a && game[1] == b) || (game[1] == a && game[0] == b	)
					count = i
					break
				end
			end
		end
		return count
	end

	def calc_fitness
		# 評価値の計算(どのくらいその組み合わせが「良い」のか)
		
		# 注意：対戦日数に関するコストとレベル差に関したコストにそれぞれ
		# 　　　どのくらい重みをつけるかは自由
		@fitness = 0
		@agent_pair.each do |ap|
			# 前回対戦した時からのゲーム数に応じてコストを加算
			period = search_match(ap[0], ap[1])
			@fitness += (@match_history.length - period)
			# レベル差に応じてコストを加算
			@fitness += 2**((@agents[ap[0]].level - @agents[ap[1]].level).abs)
			
		end


	end

	def mutation
		# 組み合わせを一箇所ランダムに入れ替える
		a = (rand * @agent_pair.length).truncate
		b = (rand * @agent_pair.length).truncate
		pos1 = (rand * 2).truncate
		pos2 = (rand * 2).truncate
		@agent_pair[a][pos1],@agent_pair[b][pos2] = @agent_pair[b][pos2],@agent_pair[a][pos1] 
		calc_fitness
	end

	def debug
		# デバッグ用

		@fitness = 0
		@agent_pair.each do |ap|
			# 前回対戦した時からのゲーム数に応じてコストを加算
			period = search_match(ap[0], ap[1])
			@fitness += (@match_history.length - period)
			print ap[0]," vs ",ap[1],": period:",period,"\n"
			# レベル差に応じてコストを加算
			@fitness += 10**((@agents[ap[0]].level - @agents[ap[1]].level).abs)
			print ap[0]," level:",@agents[ap[0]].level," ",ap[1]," level:",@agents[ap[1]].level," cost:",10**((@agents[ap[0]].level - @agents[ap[1]].level).abs),"\n"
			
		end
		print "fitness:",@fitness,"\n"
	end

end



# GA
class Genetic_Argorithm

	def initialize
		@agents = Array.new(NUM_AGENTS).map!{Agent.new}
		@gene_pool = Array.new(NUM_GENE_POOL).map!{Gene.new(@agents,$match_history)}

	end
	attr_reader:agents

	def selection
		# fitnessの低い上位2.5割を選抜

		new_gene_pool = []
		(NUM_GENE_POOL/4).times do 
			top_fitness = @gene_pool[0].fitness
			top_no = 0
			@gene_pool.each_with_index do |g,i|
				if top_fitness > g.fitness
					top_fitness = g.fitness
					top_no = i
				end
			end
			new_gene_pool << @gene_pool[top_no]
			@gene_pool.delete_at(top_no)
		end
		@gene_pool = new_gene_pool
		
	end

	def crossover
		# パッとアルゴリズムが思いつかないので簡単なアルゴリズムで。
		# 上位2.5割からランダムに突然変異させたものを5割
		# あと2.5割はランダムに追加
		# (crossover(交叉)というよりむしろ単為生殖に近いか?!)
		(NUM_GENE_POOL/2).times do
			pos = (rand * NUM_GENE_POOL/4).truncate
			new_gene = Gene.new(@agents, $match_history)
			new_gene.copy(@gene_pool[pos])
			new_gene.mutation
			@gene_pool << new_gene

		end
		(NUM_GENE_POOL/4).times do
			@gene_pool << Gene.new(@agents,$match_history)
		end
	end

	def mutationn
		# MUTATION_RATEでGeneの配列をランダムに入れ替える
		@gene_pool.each_with_index do |g,i|
			if rand < MUTATION_RATE
				g.mutation if i != 0	# 一応Bestのヤツは変異させない
			end
		end
	end

	def main
		# プレーヤー情報
		print "プレーヤー情報\n"
		@agents.each_with_index do |a,i|
			print "No.",i," level:",a.level,"\n"
		end
		print "\n"

		# GAのメイン処理
		MAX_GENERATION.times do |i|
			selection
			print "generation ",i,"\n"
			print "top fitness ",@gene_pool[0].fitness,"\n"
			crossover
			mutationn
		end
		selection


		# 結果表示
		print "上位3位表示\n"
		3.times do |i|
			print "\n"
			print i," fitness:",@gene_pool[i].fitness,"\n"
			print "No(level) vs. No(level)\t\tperiod\n"
			@gene_pool[0].agent_pair.each do |ap|
				print ap[0],"(",@agents[ap[0]].level,")\tvs.\t",ap[1],"(",@agents[ap[1]].level,")\t\t",@gene_pool[0].search_match(ap[0], ap[1]),"\n"
			end

		end
	end
end


# Main

Genetic_Argorithm.new.main

====
実行結果例

対戦履歴
day 0: [13,8][18,14][11,15][6,16][4,19][2,9][10,3][0,1][12,17][5,7]
day 1: [10,12][13,4][19,3][5,7][14,2][16,17][6,8][9,11][0,18][1,15]
day 2: [5,14][10,1][13,19][15,4][11,12][3,18][6,8][17,2][9,0][7,16]
day 3: [10,11][14,5][16,4][1,7][8,18][12,15][13,2][17,9][19,3][6,0]
day 4: [18,13][8,16][1,9][0,10][11,17][15,6][4,3][7,14][12,2][5,19]
day 5: [4,13][19,14][3,15][18,7][9,17][11,5][8,0][12,10][6,1][16,2]
day 6: [16,15][2,18][8,13][1,14][11,4][12,0][9,7][5,19][3,17][10,6]
day 7: [10,6][12,18][2,15][7,5][16,1][9,11][3,17][13,4][8,14][19,0]
day 8: [1,0][9,10][17,15][6,13][11,4][12,8][2,3][5,18][7,14][19,16]
day 9: [9,19][2,18][10,11][7,14][0,16][13,3][15,1][4,6][5,12][17,8]
day 10: [7,4][8,6][16,18][3,2][15,9][13,19][11,12][1,0][17,5][10,14]
day 11: [3,5][4,18][19,0][17,11][13,12][10,15][2,14][16,1][9,7][8,6]
day 12: [4,19][9,13][5,11][14,8][6,0][1,16][15,3][17,7][18,12][2,10]
day 13: [1,8][2,6][15,4][13,7][16,5][17,11][0,19][9,3][18,10][12,14]
day 14: [15,6][8,0][14,2][12,18][11,7][5,19][10,9][16,13][17,4][3,1]
day 15: [13,12][10,18][3,0][17,9][8,2][5,1][6,19][4,14][16,11][7,15]
day 16: [1,10][18,15][6,2][3,9][17,11][0,7][19,14][13,4][16,5][8,12]
day 17: [6,7][13,11][5,3][9,4][14,0][8,12][10,19][18,16][15,17][2,1]
day 18: [4,3][15,2][12,14][8,11][5,10][6,7][18,17][0,9][16,19][1,13]
day 19: [4,0][9,17][3,5][18,15][10,16][6,2][8,14][13,7][19,1][12,11]
プレーヤー情報
No.0 level:11
No.1 level:14
No.2 level:19
No.3 level:15
No.4 level:6
No.5 level:10
No.6 level:12
No.7 level:4
No.8 level:16
No.9 level:10
No.10 level:5
No.11 level:16
No.12 level:3
No.13 level:1
No.14 level:14
No.15 level:13
No.16 level:8
No.17 level:3
No.18 level:3
No.19 level:2

generation 0
top fitness 711
generation 1
top fitness 455
(中略) 
generation 98
top fitness 41
generation 99
top fitness 41

fitness:41
No(level) vs. No(level)		period
7(4)	vs.	12(3)		20
1(14)	vs.	11(16)		20
4(6)	vs.	10(5)		20
8(16)	vs.	2(19)		15
13(1)	vs.	17(3)		20
19(2)	vs.	18(3)		20
15(13)	vs.	0(11)		20
3(15)	vs.	14(14)		20
9(10)	vs.	16(8)		20
5(10)	vs.	6(12)		20



From: "[e-mail]" <[e-mail]>
Subject: [ruby-list:44163] Re: 2個づつの組を作る方法のすべて
Date: Wed, 31 Oct 2007 01:28:21 +0900

> 小原です。
> 
> 畠山様、丁寧な解説と、script ありがとうございます。
> 
> 解説、script どちらも私に取っては、少し敷居が高いのかなと思います。
> 
> 「組み合わせ最適化問題」 遺伝的アルゴリズム(GA) 等、
> まったく知りませんでした。Google で見て、結城浩さんのメールが
> 理解できなかったのも、尤もなことだと思いました。
> 
> script は私専用の教材として、じっくりと読ませていただこうと
> 思っているところです。
> 
>  以上 ありがとうございました。