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

畠山と申します。

いわゆる「組み合わせ最適化問題」だと思います。
たくさんある組み合わせの中から最適なものを選ぶ、と。

遺伝的アルゴリズム(GA)やヒューリスティック探索など、まあ有名な
アルゴリズムが多々あると思います。

そんなに厳密に最適でなくとも近似的な解でよければ、
結城浩さんが言われたような
1.とりえあず、ランダムに対戦の組み合わせをつくって
2.評価関数を使って良い対戦の組を選択する、
という手法が手っ取りばやく比較的楽にコーディングできる手法だと
思います。

そのランダムな組の中から比較的良いものを選んで、それらの
少し組み合わせを変えてまた良いものを選んで・・・と
繰り返すと、遺伝的アルゴリズムの出来上がりだと(大雑把ですが)
思います。(専門家の人からしたら怒られるような説明かもしれませんが・・・)

ちょうど似たような問題に取り組んでいて、枠組みだけもっていたので、
即席でつくってみました。専門の人から見たら改良の余地は多々あるで
しょうがまぁ参考までにどうぞ。

> ・好きな個数だけ対戦表を作り、評価関数がもっともよいものを選ぶ。

以下のコードで
Geneというクラスが一つの対戦組の情報をもっています。
全部で100個Geneインスタンスを作ってその中から「良い」組み合わせ
を選んでいます。
Geneクラスの中のcalc_fitnessメソッドの部分が評価関数の部分です。
その組み合わせが「良い」か「悪い」かを計算する部分です。
ここでは、
・対戦する人との間隔が短いほどマイナス評価
・対戦する人とのレベルが違うとその差にしたがってマイナス評価
してfitnessという変数に値を入れています。
fitnessの値が低いほど、良い組み合わせと考えて選択しています。

ただ、下の評価関数ですと「平均的に良い」組み合わせが
良いと評価されるので、だいたいの人は満足するのだけど、
一人だけめっちゃレベルの違う人と当たってしまう、といった
組み合わせも「良い」と評価されてしまう場合があります。
分散などのばらつき具合なども評価できるともっと良い
評価関数になると思います。


以下の例では、
・一日に一回だけ誰かと対戦
・10日分の対戦履歴
・20人の強さ情報
を仮定してやっています。

問題設定を間違って解釈していたらごめんなさい。

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

# 10日分の対戦履歴(テスト用、ランダムに生成)
$match_history = []
10.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

# プレーヤーaとbの対戦がどのくらい前に行われたかを検索するメソッド
def search_match(match_history, 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

# プレーヤー情報(レベルをランダムに設定)
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
	attr_reader:agent_pair
	attr_reader:fitness

	def calc_fitness
		# 注意：対戦日数に関するコストとレベル差に関したコストにそれぞれ
		# 　　　どのくらい重みをつけるかは自由

		@agent_pair.each do |ap|
			# 前回対戦した時からのゲーム数に応じてコストを加算
			period = search_match(@match_history, ap[0], ap[1])
			if period != nil
				@fitness += 1.1 ** (@match_history.length - period)
			end

			# レベル差に応じてコストを加算
			@fitness += 1.1**(@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
		pos = (rand * 2).truncate
		@agent_pair[a][pos],@agent_pair[b][pos] = @agent_pair[b][pos],@agent_pair[a][pos] 
	end

	def debug
		calc_fitness
		p @agent_pair
		p @fitness
		mutation
		p @agent_pair
	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の高い上位半分を選抜

		temp_gene_pool = @gene_pool.clone
		new_gene_pool = []
		(NUM_GENE_POOL/2).times do 
			top_fitness = temp_gene_pool[0].fitness
			top_no = 0
			temp_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 << temp_gene_pool[top_no]
			temp_gene_pool.delete_at(top_no)
		end
		@gene_pool = new_gene_pool
	end

	def crossover
		# パッとアルゴリズムが思いつかないので簡単なアルゴリズムで。
		# 上位10位からランダムに突然変異させたものを2.5割
		# あと2.5割はランダムに追加
		(NUM_GENE_POOL/4).times do
			pos = (rand * 10).truncate
			new_gene = @gene_pool[pos].clone
			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 do |g|
			if rand < MUTATION_RATE
				g.mutation
			end
		end
	end

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

		MAX_GENERATION.times do |i|
			print "generation ",i,"\n"
			print "top fitness ",@gene_pool[0].fitness,"\n"
			selection
			crossover
			mutationn
		end



		# 結果表示
		print "上位3位表示\n"
		3.times do |i|
			print "\n"
			print i," total 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",search_match($match_history, ap[0], ap[1]),"\n"
			end
		end

	end
end


# Main

Genetic_Argorithm.new.main

====

実行結果例

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

generation 0
top fitness 36.9894771014285
generation 1
top fitness 28.0065476443931
generation 2
top fitness 28.0065476443931
(中略)
generation 98
top fitness 23.39581
generation 99
top fitness 23.39581

上位3位の組み合わせを表示

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

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

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


From: "[e-mail]" <[e-mail]>
Subject: [ruby-list:44159] Re: 2個づつの組を作る方法のすべて
Date: Tue, 30 Oct 2007 12:48:02 +0900

> 小原です。返信ありがとうございます。
> 
> 申し訳ありません。具体的なイメージが浮かびません。
> 
> > ・この二つの要件を評価関数にする。
> >     ・この関数は会員同士の対戦履歴を持っていて
> >     　「日にちが開いている」ことを評価できる。
> >     　開いているほうがよい評価値を出す。
> >     ・この関数は会員の強さを持っていて、
> >     　「差がない」ほうがよい評価値を出す。
> 
> どんな関数になるのでしょうか？
> 
> > ・会員をランダムにカップリングして、対戦表を作る。
> > ・好きな個数だけ対戦表を作り、評価関数がもっともよいものを選ぶ。
> 
> 「会員をランダムにカップリングする」とは、どういうことなのでしょうか？
> 定例会に出席している会員同志の、対戦表が欲しいのですが、、、。
> 対戦相手が決まれば、早速囲碁を打って楽しみます。
> 私は、なにかとんでもない勘違いしているのでしょうか?
> 
> 
> [44157]の私の説明も具体的ではないので、もう一度トライします。
> 
> システムでは、以下の情報をfileに保存しています。
> 
>  *members ：会員情報file  
>    レコード形式 →  会員コード：氏名：段級位：rank-seq(+改行コード）
>            例         102:山川 草木          :1段:51
>  *taisen  ：対戦履歴file  
>    レコード形式 →  日付+ラウンド：会員コード+会員コード：0(+改行コード）
>            例       0708041:102123:0
>  *presents：出席者file (これは定例会当日に作る。＝ 出席をとる)
>    レコード形式 →  日付：会員コード：会員コード：.....：会員コード(+改行コード）
>            例       070915:102:103:105:107.....:123
> 
>   (members、taisen のレコードは固定長です。)
> 
> 上記の file の 例を使って作業を進めます。
> 
> 作業の目的は、対戦配列 match=[] を完成することです。
> 
>  1。presents を読み 070915 の出席者の配列を作る。
>     mem0=["012","103",105",....,"123"]
>  2。members の情報と会わせて、各要素の頭にrank-seqを付けた配列を作る。
>     更に、(降順に)ソートする
>     mem1=["54112","54115","52108".....,"47121"]
>  3。mem1 の各要素の頭２文字を取ったものを要素とする配列を作る
>     mem2=["112","115","108",....,"121"]
>  4。x=mem2[0];a=mem2[1,10] とし、対戦履歴ファイルを参照して
>     x+a[0] 、x+a[1]、、、、x+a[9]の対戦日を調べ(注)、最も対戦日の古い者 y 
>    を x の 対戦相手とする。該当者が複数人いたときは、最初の者を y とする。
>    つまり   macth.push(x+y)
>       （注）x+a[0]の対戦日は、a[0]+xとして記録されているかもしれない。
>       #一日一回の対戦をする場合は、配列 a のなかには少なくとも一人、
>       #九日以上前に対戦した人がいるはずです。
>       #一日二回の対戦をする場合は四日以上、、、、。
>       #ただし、棋力の差は、最大で 10 になりますが、仕方ないと思います。
>       #会員構成、出席者により、色々な結果になると思われますが、
>       #私達の場合、約1月の試行では、納得してもらえる範囲と考えています。
>       #棋力差を小さくするには、配列 a の size を小さくする。
>  5。men2 より x,y を削除して 4。の操作を mem2.size=10 
>     となるまで繰り返す。
>  6。１０人をカップリングする方法全てにわたり、最新の対戦日を調べ、
>     これが最も古いものを、best のカップリングとし、macth[]に加える。
> 
> 10人ではたいへんなので、4人でやります。
> 
>  6ー1。mem2=["116","117","118","119"] から
>        対戦の組を要素とする配列 mmmを作る。
>  6ー2。mmm=[["116117","118119"],
>             ["116118","117119"],
>             ["116119","117118"]]
>           =[ mm1,mm2,mm3] と略記します
> 
>  6ー3。mmm の各要素のペアの対戦日を対戦履歴fileで調べその
>        最新のものを、各要素の対戦日とし、それを各要素に push する
> 
>        117、116 の対戦日＝ 0705051、118、119 の対戦日＝ 0706051、なら
>        mm1.push(0706051) => mm1=["116117","118119","0706051"]    です。
> 
>        同様に mm2,mm3 に付いても調べて
> 
>       mmm=[["116117","118119","070651"],
>            ["116118","117119","0801232],
>            ["116119","117118","0707071]]
>  6ー4。mmm のうち、最も古い対戦日のくみを best として選ぶ。
>        best=["116117","118119","070651"]
>  6ー5。best の対戦日を削除したものを、match に加える。
>        macth=match+best
> 
> 
> 
>  以上 よろしく
> 
> 
>