第６回進化計算フロンティア研究会(2011/03/14‑15・名古屋)

トーナメント選択におけるトーナメント選出個体数に関する考察
Number of Participants in Tournament Selection
中田 和樹 1
Kazuki NAKATA1

片田 喜章 1∗
Yoshiaki KATADA1

11

摂南大学
Setsunan University

Abstract: Tournament selection has been employed in various evolutionary algorithms due toits own advantages. Such a characteristic as to choose some individuals randomly in a current
population for tournaments would make it possible to evaluate the only individuals chosen for
those tournaments. This would be a new advantage of tournament selection in shortening theevaluation time. This study investigated this possibility analytically and experimentally. The
results show that it is possible to shorten the computational time by evaluating only individuals
chosen for tournaments if the tournament size is less than ten.

1

はじめに

トーナメント選択は個体の適応度の上下関係だけを用いるため，スケーリングの必要がなく，また，トーナメントサイズを変えることで選択圧を調整することができるという特徴をもつ [1][2]．トーナメント選択の実行には，トーナメントに選出される親個体候補だけの適応度の情報が必要であり，必ずしもすべての個体の適応度の情報を必要としない．これは，トーナメン
ト選出個体のみ適応度の計算を行うことで，個体群の評価にかかる計算コストを削減することができる可能性を示している．しかもこれに，パフォーマンスとのトレードオフは存在しない．このことは，個体の評価に非常に時間がかかる類いの実問題では，実際的な評価回数が減ることにつながり，実用面において非常に望ましいことである．トーナメント選出個体のみ適応度の計算を行えば，計算コストを削減することができるということは直感的にはわかるが，どれくらい削減できるかという定量的な解析は行われていないように思われる．そこで本研究では，トーナメント選出個体数の期待値を，個体群の個体数およびトーナメントサイズをそれぞれ変更した場合の理論値と実験値を計算し，その比較を行う．また，トーナメント選択を用いた進化計算の実行過程における選出個体数の変動をテスト問題において調べる．

∗ 連絡先： 摂南大学理工学部電気電子工学科〒 572-8508 大阪府寝屋川市池田中町 17-8
E-mail: katada @ ele.setsunan.ac.jp

2

トーナメント選出個体数

2.1

トーナメント選択

本研究で取り扱う個体評価と選択に関して議論を始める前に，まず，GA を例として進化計算の基本的な手順を示す．
ステップ 1 初期個体群の生成ステップ 2 個体群に含まれる個体の評価
ステップ 3 親個体の選択
ステップ 4 交叉・突然変異の適用
ステップ 5 終了条件が満たされていなければ，ステップ 2 へ戻る．
トーナメント選択では，事前に設定されたトーナメ
ントサイズ (t ≥ 2) の個体が個体群からランダムにトーナメントに選出される．トーナメントに選出された個体のうち最良の適応度をもつ個体のみが次世代の親として選択される．個体数を一定に保つために，個体群の個体数 (N ) が満たされるまでトーナメントを実施する．したがって，N 回のトーナメントが実施され，1 世代で合計 (N t) 個の個体が親個体候補としてトーナメントに選出される．トーナメントへの個体の選出には復元抽出と非復元抽出を行う場合とがあるが，いずれにしても，いくつかの個体は複数回選出される可能性がある．よって，上述のステップ 2 とステップ 3 を入れ替えることで選出された個体のみ評価すれば良く，すべての個体を評価する必要がなくなり，計算コストが削減できるというのが本研究の基本的なアイデアである．

‑ 116 ‑

2.2

選出個体数の導出

以下では，トーナメントへの個体の選出は復元抽出を行い，個体群に含まれる個体はすべて異なるものと仮定する．この場合，各個体は等しく 1/N の確率でトーナメントに選出される．よって，1 世代で実行される全トーナメントには，確率 1/N で独立に (N t) 個の個体が親個体候補として選出されることになる．これは，確率論でいう独立試行である．以上より，トーナメン
トへの選出個体が X 種類 (ただし，X ∈ {1, 2, · · · , N })である確率 (P (X)) は以下のように P (X = 1) より順次計算できる1 ．
( )( )( )1
1
1
P (X = 1) = N···
N N
N|{z}

(Nt)N t1(1)N( )( )N tN
1Nt(2 − 2)2N( )( )N tN
1W2(2)
2N( )( )( )N tN
31Nt{3 −W2 − 3}32N( )( )N t
N
1W3(3)
3N( )[( )N
44N t −
W343( )] ( )N t
4
1−
W2 − 42N( )( )N t
N
1W4(4)4N..
.

= N
P (X = 2)=≡

P (X = 3)=≡P (X = 4)

=

≡..
.

( )[()
Nj
jN t −
Wj−1
j
j−1()
( )
j
j−
Wj−2 − · · · −W3j−23( )] ( )N tj
1−
W2 − jN2( )( )N tN1≡Wj(5)jN..
.

P (X = j) =..
.

` ´

1 だだし， nkは組合わせの個数 n Ck を表す．

( )[()NNNt
P (X = N ) =N −WN −1
NN −1()( )N
N−
WN −2 − · · · −W3
N −23( )] ( )N t
N
1−W2 − N(6)2N∑N式 (1)-(6) より j=1 P (X = j) = 1 である．以上より，
1 世代で全トーナメントに選出される個体数 (個体の種類) の期待値は以下で求められる．
X theo = E(X) =N∑

jP (X = j)

(7)

j=1

つまり，式 (7) の期待値が個体群の個体数 (N ) よりも小さいとき，上述の手順の入れ替えに効果があり，計算コストの削減が期待できる．

3数値実験

本節では，第 2 節で導出したトーナメント選出個体数の確率分布から期待値を計算し，シミュレーションによって得られる期待値と比較する．
まず，シミュレーションの設定について述べる．2.2
節で述べた仮定に基づき異なる個体を N 個作成し，ランダムに N t 個選出する．このとき，選出された個体の種類を Xi とする．これを n 回独立に試行して得られ∑nる結果 {X1 , X2 , · · · , Xn } の平均 X sim =i=1 Xi /nを計算する．
N ∈ {5, 10, 25, 50, 100, 200, 500, 1000}, t ∈ {2, 3, · · · ,N }，n = 1000 として計算を行った．ただし，式 (7) の計算では，大きい値をとる (N, t) の各組合わせに対し式 (1)-(6) 中の値が非常に大きくなることから数値計算を実行することが難しい．本稿では Excel で計算できる範囲の結果を示す．
図 1，表 1 に N を変化させたときの t に対する選出個体数（X theo : 理論期待値，X sim : シミュレーション期待値）を示す．得られた範囲の理論値とシミュレーションの値は非常によく一致していることがわかる．第2 節で述べたように，選出個体数の期待値 (以下，X と示す) が個体群の個体数 (N ) よりも小さいとき，計算コストの削減が期待できる．t が最小値 2 から増加していくと X も増加し，t が 10 以上で X は N に収束している．N = 5, 10 では N の値が 10 以下であるため，t が N の値に近づくまで X は増加する (図 1(a)-1(b))．
X が N に収束する厳密な t の値は定かではないが，おおむね t = 8 付近で収束している．つまり，第 2 節で述べた手順の入れ替えに効果があるのはトーナメント
サイズが 1 桁の場合であり，現実的には t ≤ 4 の場合であろう．

‑ 117 ‑

5.010.0

Expected value

Expected value

9.5

4.5

9.0

8.5
theorysimulation

4.0
23
Tournament size

theorysimulation

8.0

45234(a) N = 5567
Tournament size

8910182018201820(b) N = 102550492448
Expected value

Expected value4723224645
4443214241

theorysimulation

2024681012
Tournament size

1416

theorysimulation

40
1820

246(c) N = 25

81012
Tournament size1416(d) N = 50

1002009896190
Expected valueExpected value

94929088180861708482
simulation

80
246810121416simulation

160
1820246Tournament size

810121416Tournament size(e) N = 100(f) N = 200

500

1000

490
480
950
Expected value

Expected value

470
460
450
440

900

430
850
420
410
simulation

400
24681012
Tournament size

1416simulation

800
1820(g) N = 500

24681012Tournament size1416(h) N = 1000

図 1: トーナメントサイズに対する選出個体数の期待値 (theory: 理論期待値，simulation: シミュレーション期待値)‑ 118 ‑

表 1: (N, t) の各組合わせにおける選出個体数の期待値(上段: X sim ，下段: X theo )t2345678N =54.4490
4.46314.81204.8241
4.94204.94244.98204.9811−−−−−−

N = 108.79208.78429.58309.57619.85509.85229.95809.94859.98209.98209.99409.99379.99809.9978N = 2521.7440
21.752923.821023.829724.5360
24.5782
24.8400
24.8480
24.941024.9452
24.9780
24.980324.9850
24.9929

N = 5043.2340
43.3690
47.5600
47.5852
49.1260−
49.7130−
49.8890−
49.9550−
49.9840−

N の値を変えて実験を行っているため，X は様々な値をとるが，N からの削減率は t に対して同じような値をとる．これを示すために以下の削減率 RED[%] を定義する．
X
RED = (1 − ) × 100(8)N
理論値 X theo は (N, t) のすべての組合わせに対しては値を計算できていないため，RED の計算にはシミュレーションで得られた値 X sim を用いる．図 2，表 2 に
t = 1, 2, · · · , 10 の範囲の RED を示す．N = 5, 10 で少しバラつきがあるものの，RED は N の値に依らずt に対して近い値をとる．

15N=5N=10N=25
N=50
N=100
N=200
N=500
N=1000RED [%]

104

進化計算実験

本節では，トーナメント選択を用いた進化計算実行
時の選出個体数を調べ，第 2 節および第 3 節の結果と比較する．進化計算にトーナメント選択を用いた簡単 GA(以下，GA とよぶ) を採用し，テスト関数にはONEMAX 関数と (k, l)-DECEPTION 関数 [3] を用いる．ONEMAX 関数はバイナリーコーディングを用いた GA のテスト関数として最も簡単で単峰性を示し，(k, l)-DECEPTION 関数は局所解をもつため，これらが個体群の構成，つまり，選出個体数に影響を与えるかを調べるために採用した．ONEMAX 関数はストリング長を L = 100，DECEPTION 関数は文献 [4] に従い，k = 3, l = 20 の L = 60 とする．また，(k, l)DECEPTION 関数の設定を表 3 に示す．GA の各パラメータを表 4 のように設定し，個体数・トーナメントサイズを変更して，世代数に対するトーナメント選出個体数を調べた．これは，第 2.2 節で設定した，個体群に含まれる個体はすべて異なるという仮定が 1 世代目では成り立つが，それ以降の世代では GA のダイナミクスに依存して必ずしも成り立たず，その挙動を調べるためである．
GA を 100 試行行ったときの各世代に対する選出個体数の平均・最小値・最大値を図 3，4 に示す．(N, t) の各組合わせに対し，平均値は第 2 節および第 3 節で求めた値に世代を通してほぼ等しいことがわかる．選出個体数のゆらぎがどの程度か調べるために最小値・最大値を示したが，そのゆらぎの幅はトーナメントサイズ・個体数に依存していることがわかる．ただし，(N, t) の各組合わせに対し 2 つの問題間ではそれほどの差は見られない．(k, l)-DECEPTION 関数の局所解の存在が個体群の収束をもたらすことで異なる個体数が減少し，選出個体数が減少するのではないかと予想したが，結果はそれに反するものであった．これは設定したトーナメントサイズの範囲が小さいもので収束をもたらすほどの選択圧ではなかったか，用いた 1 点交叉によってある程度の異なる個体数が確保されたためではないかと推測する．以上の結果より，GA 実行時においても，第 2 節および第 3 節で得たトーナメント選択を用いた場合の評価回数の削減率は評価回数 (個体数 × 世代数)5

表 3: (3, l)-DECEPTION 関数

02

34567
Tournament size8910

図 2: (N, t) の各組合わせにおける削減率 [%]‑ 119 ‑

ストリング
111
101110011

適応度
30000

ストリング
100010001000

適応度
14222628

表 2: (N, t) の各組合わせにおける削減率 [%]t2345678

N =511.0200
3.76001.16000.3600——————N = 1012.0800
4.17001.45000.42000.18000.06000.0200N = 2513.02404.71601.85600.64000.23600.08800.0600N = 5013.5320
4.88001.74800.57400.22200.09000.0320

表 4: GA のパラメータ設定
世代数点突然変異確率
1 点交叉確率個体数 (N )トーナメントサイズ (t)

100
1/L
0.9
{100, 1000}{2, 4, 6}

に対して期待値として得られることが確認できた．

5

むすび

本稿では，トーナメント選出個体数の期待値を，個体群の個体数およびトーナメントサイズをそれぞれ変更した場合の理論値と実験値を求めた．以下に結果をまとめる．

• トーナメント選出個体数の確率分布を導出し，期待値を求めた．ただし，数値計算の過程で非常に大きな数値を扱うため，設定した個体群の個体数およびトーナメントサイズのすべての組合わせに対し理論式から値を計算できたわけではない．得
られた範囲の理論値とその検証用計算機実験で得られた値は非常によく一致する．
• トーナメント選出個体数はトーナメントサイズがt = 2 のときに最小値をとり，t が増加していくと増加していく．おおむね t = 8 付近で個体群の個体数の値に収束する．また，個体群の個体数によらず，選出個体の削減率はトーナメントサイズに対し近い値をとる．
• 進化計算実行時の世代数に対する選出個体数は，理論式から得た値およびその検証用計算機実験で得られた値とよく一致する．

N = 100
13.52104.87301.73800.60800.22700.08000.0300N = 200
13.4260
4.94501.82050.64550.24100.09600.0320N = 500
13.5036
4.94141.81540.65480.23440.08840.0342

N = 1000
13.51594.94801.82380.66680.24250.08680.0310以上より, トーナメント選択による評価回数 (より正確には評価個体数) の削減は，トーナメントサイズが小さいときに可能であることがわかった．したがって，選択圧が弱いときにパフォーマンスが良い進化計算には有効な方法であるが，選択圧が高い必要のある進化計算には向かない．
トーナメント選択を採用しない進化計算も多くある．
これらに対しても，トーナメント選択を採用して同等のパフォーマンスが得られるならば，付加価値として評価回数の削減が期待できる．
本研究ではトーナメントへの個体の選出は復元抽出を行いた．非復元抽出を行いた場合，選出個体数（の種類）は最低でもトーナメントサイズ以上になり，その期待値は復元抽出の場合よりも高くなると予想される．
また，進化計算実行時の実験に GA を用いた．一般的に多くの個体数を設定する進化計算（例えば GP）でも本稿で考察した内容は有効であると期待される．今後これらについて検証していく予定である．

参考文献[1] Goldberg, D.: Genetic Algorithms in Search,Optimization and Machine Learning, AddisonWesley (1989)[2] 電気学会 進化技術応用調査専門委員会 (編): 進化
技術ハンドブック 基礎編, 近代科学社, (2010)[3] Goldberg, D., Deb, K. and Korb, B.: Messy Genetic Algorithms Revisited: Studies in Mixed
Size and Scale, Complex Systems, 4:415-444(1990)[4] Mühlenbein,H.:
Evolutionary
Algorithms:
Theory and Applications, citeseer.nj.nec.com/110687.html, (1993)‑ 120 ‑

100

95

95

95

90

85

80

75

90

85

80

75

70
40
60
Generation

80

100

85

80

70
20(a) (N, t) = (100, 2)

90

75

70
2040
60
Generation

80

100

20(b) (N, t) = (100, 4)
1000

950

950

950

850

800

900

850

800

750

750

700

700
204060Generation

80

Number of evaluations

1000

900

100

80

100

80

100

80

100

80100900850

800

750

700
20(d) (N, t) = (1000, 2)

4060
Generation(c) (N, t) = (100, 6)

1000

Number of evaluations

Number of evaluations

Number of evaluations

100

Number of evaluations

Number of evaluations

1004060
Generation

80

10020(e) (N, t) = (1000, 4)

4060
Generation(f) (N, t) = (1000, 6)

10010095959590

85

80

75

9085

80

75

70
4060
Generation

80

10085807020(a) (N, t) = (100, 2)

9075

70
204060Generation

80

10020(b) (N, t) = (100, 4)
1000950

950

950

850

800

750

Number of evaluations

10009009008508007507004060
Generation(d) (N, t) = (1000, 2)80100900850800

750

700204060
Generation(c) (N, t) = (100, 6)

1000

Number of evaluations

Number of evaluations

Number of evaluations

100

Number of evaluations

Number of evaluations

図 3: ONEMAX 関数における世代数に対する選出個体数 (最大値・平均値・最小値)

700
204060Generation(e) (N, t) = (1000, 4)80100204060
Generation(f) (N, t) = (1000, 6)

図 4: (3-20)-DECEPT 関数における世代数に対する選出個体数 (最大値・平均値・最小値)‑ 121 ‑