IIC–10–013

競争型共進化における世代間累積データを用いた適応度景観の特徴量推定半田佑太∗ ，片田喜章（摂南大学）
Estimation of Features of Competitive Co-Evolutionary Fitness Landscapes Based on Accumulated Data for
Certain Generations
Yuta Handa∗ , Yoshiaki Katada (Setsunan University)
Abstract
Open-ended evolution is considered to be caused by several factors, one of which would be co-evolution. Competitive co-evolution can give rise to the “Red Queen effect”, where the fitness landscape of each population might
be continuously changed by the competing population. Therefore, if such continuous changes could be captured,co-evolutionary progress would be measured. In this paper, we proposed a method to estimate features of competitive co-evolutionary fitness landscapes on a predator-prey problem and investigated the Red Queen effect on thefitness landscape in computer simulations. In the proposed method, features of fitness landscapes are calculated
based on accumulated data during a certain period of the evolution. The results suggest to us that our method cantrack the progress of fitness landscapes on competitive co-evolutionary robotics.
キーワード：進化ロボティクス，遺伝的アルゴリズム，ニューラルネットワーク，適応度景観(Evolutionary Robotics, Genetic Algorithm, Neural Networks, Fitness Landscape )1. はじめに競争型共進化において，種が存続するためには進化し続ける必要があり進化をやめるとその種は絶滅する「赤の女王仮説」が提唱されている (1)．ここでは，ある種の利益は競争関係にある種の損失となり，その種が利益を得るため対抗戦略を講じることを互いに繰り返す軍拡競争として現れる．
競争型共進化では軍拡競争により，適応度景観が絶え間なく変化し，永続的進化を導くと考えられる．したがって，適応度景観の変化を捉える，つまり，景観の特徴量が変化し続けることを観察できれば，人工進化における共進化の発生を確認できるのではないかと考えた．そこで，我々は捕食-被食関係にある 2 つの個体集団を設定し，各世代における適応度景観の特徴量 (3) を推定し，その変遷を調べることで，競争型共進化の発生について検証を行った (4) (5)．
しかしながら，その結果は上述の予想に反し，多くの場合，適応度景観の特徴量の変化が世代を経るにつれ次第に小さくなっていった．その原因としては採用した適応度景観の特徴量推定法の設定が各世代で変化するであろう特徴量を測定するのに適切ではないことが考えられる．そこで我々の研究グループでは，一定世代間に累積する遺伝子データを用いた競争型共進化における適応度景観の特徴量測定法を提案している (6)．この提案手法を用い，一定世代間は同一の対戦相手を選択する方法を採用した進化実験においては，適応度景観の特徴量の変化を捉えることが可能であることを確認している．
そこで本稿では，文献 (6) において提案した適応度景観の特徴量測定法を採用する．また，対戦相手の選択は，文献 (5) において用いた世代毎に変化する設定を採用する．これらを用い，計算機実験において捕食-被食関係にある 2 つの個体集団から適応度景観の特徴量を測定し，その変遷を調べることで提案手法の有効性を検証する．
2. 適応度景観の特徴量推定
適応度景観の特徴量には凸凹度 (ruggedness) と中立度(neutrality) があることが知られている (3) (7)．本稿では，エージェントのコントローラに次節で述べる進化型人工ニューラルネットワーク (Artifical Neural Networks: ANN)を用いるため，その適応度景観にはこの 2 つの特徴量が含まれると考えられる．これらを推定する指標について次に述べる．
2.1

凸凹度の指標実問題における凸凹度は適応度景観の相関に基づいて推定される．そこで凸凹度の指標として，その傾きが適応度景観の相関を求める Smith の測定法 (7) を用いる．
適応度 k の親個体から生まれる子個体の適応度における期待値として以下に定義される．
f¯k =

P

f (g)

g∈Gk|Gk |· · · · · · · · · · · · · · · · · · · · · · · · · · · (2.1)

ここで，Gk は適応度 k の親から生まれる子の遺伝子集合，g は子の遺伝子，f (g) は子の適応度である．この f¯ は凸凹度の影響のみを受け，凸凹度が増加すると k に対する f¯ の傾き γ は減少することが知られている (7)．この傾きは遺伝的操作として突然変異を用いた場合の自己相関関数に比例し，凸凹度が最も小さいとき γ ' 1.0 に，凸凹度が最も大きいとき γ ' 0.0 になる．
1/6

2.2
中立度の指標中立度の指標 (3) に用いる標準遺伝距離 (8) は以下のように定義される．集団 X における第 i 番目の遺伝子座の対立遺伝子 l の頻度を xil = nil /M (i = 1, ..., L，L : 遺伝子長，M : 個体数，nil : 集団内の対立遺伝子 l ∈ {0, 1} の数) とする．同様に集団 Y における yil を考え，jxi = x2i0 + x2i1 ，22
jyi = yi0+ yi1，jxyi = xi0 yi0 + xi1 yi1 とする．ここで，jxi
は集団 X から任意に選んだ 2 個体における第 i 番目の遺伝子座の対立遺伝子が等しい確率であり，jyi は集団 Y のそれである．jxyi は集団 X と Y のそれぞれから任意に 1個体ずつ選んだ 2 個体における第 i 番目の遺伝子座の対立遺伝子が等しい確率である．これらは各遺伝子座に対し定PL義されるので，全遺伝子座の平均は，JX =j /L，i=1 xi
PLPL
JY =j /L，JXY =j /L となる．このとi=1 yii=1 xyiき，根井の標準遺伝距離は次のように与えられる．

3. 計算機実験
3.1

実験設定

競争関係にある個体集団として捕食者集団 (Pr) と披食者集団 (Py) を仮定する．実験環境は図 1 のように設定し，周囲は壁に囲まれているものとする．エージェントは壁検出用と他エージェント検出用の 2 種類の距離センサをもち，その配置は図 2 のようになっている．移動機構として，左右二輪独立駆動型を用い，移動速度の最大値は，両エージェント共に等しい設定とする．エージェントの制御器として，中間層・出力層が完全相互結合された ANN を用いる．入力ノード数は Ns = 18(センサ数)，出力ノード数は No = 2(左右モータの周速度)，中間ノード数は Nh = 3 とする．図 1の初期位置から，それぞれのエージェントの初期姿勢を 90◦ずつ変えた試行を 16 回行う．Pr はより早く Py を捕えることを，Py はより長く Pr の追跡から逃れることを目的とJXY
D = −loge p p· · · · · · · · · · · · · · · · · · · · · · · (2.2)
JX JY

集団遺伝学では，遺伝距離の測定において突然変異率が十分に小さいことを仮定している．また，式 (2.2) を GA に適用するために，バイナリコーディングによって起こる “backmutation (9)” を考慮しなければならない．そこで，遺伝距離を計算する際に用いる 2 つの集団 X と Y について，t 世代での個体集団と t + 1 世代での個体集団を用い，世代間の遺伝距離 Dt,t+1 を求め，㪧㫉㪼㫐㪧㫉㪼㪻㪸㫋㫆㫉

tl −1D1,tl =X
t=1

Dt,t+1 · · · · · · · · · · · · · · · · · · · · · · · · · · · (2.3)のように拡張する (tl は最終世代数)．これは，中立度が大きいほど増加し，凸凹度が大きいほど減少するという特性をもつ．片田ら (3) は，適応度景観の変化しない単一種の進化に対しその特徴量が測定できることを確認している．
2.3
競争型共進化における適応度景観の特徴量測定法
文献 (6) において我々の研究グループが提案し，本稿でも採用する競争型共進化における適応度景観の特徴量測定法を以下に示す．一定の世代間累積データを用いて式 (2.1)
を基に f¯tks ,te として以下のように求める．
f¯tks ,te =Pg∈Gkt ,ts

te −1

Xt=ts

図 1 実験環境
Experimental set up for a pursuit-evasion contest．

f (g)e|Gkts ,te |· · · · · · · · · · · · · · · · · · · · · · (2.4)

ここで，Gkts ,te は，ts から te 世代における適応度 k の親から生まれる子の遺伝子集合，ts ，te はそれぞれ一定の世代間における最初の世代および最後の世代とする．同様に，遺伝距離を Dts ,te とし以下のように求める．
Dts ,te =Fig. 1㪪㪼㫅㫊㫆㫉㪧㫉㪼㫐㪧㫉㪼㪻㪼㫋㫆㫉Dt,t+1 · · · · · · · · · · · · · · · · · · · · · · · · · · (2.5)

式 (2.4) は k に対して，式 (2.5) は世代に対してそれぞれの傾きを最小二乗法で求め，γ，α とし，適応度景観の特徴量の指標とする．

図 2 センサ設定
Fig. 2 Simulated models of sensors for predator and preyrobots．
2/6

し，次の適応度関数を用いてそれぞれの適応度を計算する．

X 1 − Stepi /M axStep

T rials

Fpr =T rials

i=1

X Stepi /M axStep

1.0· · · · · · · · · · · · · (3.1)

0.8

i=1

T rials· · · · · · · · · · · · · · · · · (3.2)

ここで，T rials は試行回数 (16) であり，Stepi は試行 iにおけるエージェント同士が接触するまでのステップ数，
M axStep は最大のステップ数で 400 とする．進化手法として Simple GA を用いる．ANN の結合荷重を変数とし，10ビット・バイナリコーディングを行う．先に述べた ANN の構造から，遺伝子長は L = 1150 となる． 2 . 2 で述べた遺伝距離を求めるため，点突然変異のみを遺伝的操作として用い，突然変異率は十分に小さく設定する必要があることから 1/L とする (3)．選択法としてトーナメント選択を用い，トーナメントサイズは 2 とする．両集団ともに個体数を M ＝ 50，世代数を 5000 とし，独立に 10 試行行う．特徴量測定法に関する設定は，ts ∈ {1, 1001, 2001, 3001, 4001}，
te ＝ ts + 999 とする．また，競争する対戦相手の個体の選択方法として，次の 3 パターンの設定を用いる．
–SG評価を行う世代と同じ世代の対戦相手の個体集団からランダムに 1 個体を対戦相手として選択する方法である．これを SG と呼ぶ．
–BP1 評価を行う世代に対して 1 世代前の対戦相手における個体集団から最良個体の 1 個体を選択する方法である (10)．これを BP1 と呼ぶ．
–BP10
評価を行う世代に対して 10 世代前までの各世代の対戦相手における個体集団からそれぞれの世代における最良個体の 10 個体を選択する方法である (10)．これを BP10 と呼ぶ．
3.2.1

Pr
Py01000

2000 3000
Generation

4000

5000

4000

5000

4000

5000

(a) SG

1.0
0.8
0.60.40.20.0Pr
Py01000

2000 3000
Generation(b) BP1

実験結果と考察
最大適応度の推移

図 3 に，対戦相手の各選択方法における，世代に対する最大適応度の推移の 10 試行中の典型例を示す．SG において，ほぼすべての世代で Pr が高い適応度を示しており，Pyはほぼすべての世代で低い適応度を示している (図 3(a))．
これは，移動速度の最大値が両集団共に等しいことから，文献 (4) と同様に Pr が有利になったのだと考えられる．BP1，BP10 においても同様の傾向が見られる (図 3(b),3(c))．
3.2.2

0.40.0

適応度景観の特徴量

図 4 に図 3 で示した試行における世代間 (ts , te ) で求めた
相関 γ と遺伝距離の変化率 α の推移を示す．SG においては，Pr の γ が高い値を示し，α も変化が見られる (図 4(a))．
Py は初期 1000 世代における γ が高い値を示しているが，それ以降の γ は低い値を示している．α においても 4001 世代から 5000 世代にかけて高い値へ変化している (図 4(a))．
SG の適応度の推移においては，世代を通して Pr が高い値を示し，Py が低い値を示している．これは γ の値，つまり，相関が高い Pr の適応度が高くなり，相関の低い Py の1.00.8Fitness

3.20.60.2Fitness

Fpy =Fitness

T rials

0.6
0.4
0.2
0.0Pr
Py01000

2000 3000
Generation(c) BP10

図 3 世代に対する最大適応度の推移
Fig. 3 Maximum fitness at each generation．

3/6

Genetic Distance Rate α0.00080.00060.00040.0002

0.0

0.2

0.4

0.6

0.8

1.0

Correlation Coefficient γ
Pr1-1000
Py1-1000

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000(a) SG

Genetic Distance Rate α0.00080.00060.00040.00020.00.2

0.4

0.6

0.8

1.0

Correlation Coefficient γ
Pr1-1000Py1-1000

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000(b) BP1

Genetic Distance Rate α0.0008

0.00060.00040.0002

0.0

0.2

0.4

0.6

0.8

1.0

Correlation Coefficient γ
Pr1-1000
Py1-1000

Pr1001-2000
Py1001-2000

Pr2001-3000
Py2001-3000

Pr3001-4000
Py3001-4000

Pr4001-5000
Py4001-5000(c) BP10
図 4 各世代に対する (γ,α) の推移
Fig. 4 α as a function of the correlation γ for each generation．

適応度が低くなっており，適応度の推移に相関が影響していると考えられる．また，Py の初期 1000 世代が高い相関を示していることに関しては，進化初期の世代において生じる，あまり強くない対戦相手に対して評価される遺伝子データが影響していると考えられる．
BP1 における Pr の γ は，SG と同様に高い値を示す．αは SG における Pr ほどではないが，少しの変化が見られる(図 4(b))．Py では，初期世代から 1000 世代における γ が高い値を示しており，それ以降の世代は低い値に変化している．α は，初期世代から 1000 世代は高い値を示し，1001世代から 2000 世代，2001 世代から 3000 世代と順に低い値に変化し，3001 世代から 4000 世代，4001 世代から 5000世代と再び高い値へと変化する (図 4(b))．BP1 における適応度の推移と γ の値の関係は，SG と同様の傾向を示している．
BP10 の Pr は，SG，BP1 と同様に γ が高い値を示している．Py は初期から 3000 世代までにかけて γ が高い値に変化しており，3001 世代から 4000 世代で低い値に変化し，4001 世代から 5000 世代において再び高い値を示している．両集団の α においては，SG，BP1 ほど変化していない (図 4(c))．BP10 の適応度の推移においては，Pr の相関に関しては SG，BP1 と同様の傾向にある．しかし，Py
では初期 1000 世代の相関が他の世代間に対して高い値を示していない．さらに，SG，BP1 と比べ BP10 の α の値が小さくなっている．これらは，進化初期であっても複数の対戦相手に対して評価を行っていることから，選択圧が強くなるためだと考えられる．
3.2.3

過去の世代との比較

前節では，世代間累積データを用いた適応度景観の特徴量測定法により適応度景観の特徴量の変化を捉えることができることがわかった．しかし，進化時の適応度は Pr が一方的に高い値を示す傾向にあり，両集団で適応的な進化が行われているかを確認することは困難である．競争型共進化では，進化時の評価に用いられた対戦相手だけでなく，過去の世代に遡った対戦相手に対し適応度が改善されていることが望ましい．そこで本節では，Floreano ら (2) が行っている，各世代の最良個体を過去の世代の最良個体と対戦させる方法を用い，全世代における対戦成績からその検証を行う．
図 3 で示した試行における過去の世代との対戦成績を図 5に示す．ここでは，色の濃淡で成績を示しており，色が明るいほど成績が良く，濃い程成績が悪い設定となっている．
また，過去の世代との対戦であるため，ある世代 (例えば 10世代) の個体は，その世代以降の世代 (10 世代からその後)の相手とは対戦しないことから対角線の上側のみで成績は表される．さらに，計算時間の問題から本実験では，100 世代毎の最良個体を選択し対戦させる．SG における VP1 のPr は，ほぼすべての対戦において良い成績を示しており，Py はあまり良い成績を示していない (図 5(a)，5(b))．これ
は，最大適応度の推移において Pr が常に良い適応度を示
4/6

5000

5000
14000

140000.80.8

3000

0.40.2

2000

00.6
Generation-py

Generation-pr0.610003000

0.40.2

2000

01000

1111000

2000
3000
Generation-py

4000

5000

11000

(a) SG,Pr

2000
3000
Generation-pr4000

5000(b) SG,Py

5000

5000
14000

14000

0.80.83000

0.40.2

2000

00.6
Generation-py

Generation-pr

0.6

1000

3000

0.4
0.2

2000

01000

1111000

2000
3000
Generation-py

4000

5000

11000

(c) BP1,Pr

2000
3000
Generation-pr4000

5000(d) BP1,Py

5000

5000
14000

14000

0.80.83000

0.40.2

2000

01000

0.6
Generation-py

Generation-pr0.6
3000

0.40.2

2000

01000

1111000

2000
3000
Generation-py

4000

5000

11000

(e) BP10,Pr

2000
3000
Generation-pr40005000(f) BP10,PyFig. 5

図 5 過去の世代との比較
Current individual vs. ancestral opponents．

5/6

していたことが原因だと考えられる．これらの特徴は BP1，BP10 においても同様のものが見られる (図 5(c)–5(f))．本
実験では，各世代の最良個体が進化時に獲得した適応度にほぼ等しい対戦成績を示し，過去の対戦相手に対して，全ての世代で必ずしも良い成績を示していないことから，理想的な共進化が起こっているとはいえない．
4. おわりに
本稿では，一定の世代間に累積した遺伝子データを用いて競争型共進化における適応度景観の特徴量を測定する手法を用い，捕食-被食関係にある 2 つの個体集団において，毎世代変更される対戦相手に対する適応度景観の特徴量変化を調べ，提案手法の有効性を検証した．得られた結果について次にまとめる．
• 適応度景観の特徴量測定を世代間に累積した遺伝子データを用いることにより，特徴量の変化を確認することができた．SG，BP1 においては相関と遺伝距離が，BP10においては相関が特に変化していることがわかる．
• Pr，Py 共に，相関の値が大きくなると進化が容易になり，高い適応度を示す．
• SG，BP1 の適応度景観の特徴量では，初期世代において生じるあまり強くない対戦相手の影響から初期 1000世代の Py が高い相関を示す傾向にある．一方で，BP10
では，初期世代から複数の対戦相手に対する評価を行うことから SG，BP1 に比べ Pr の相関が高く，両集団の遺伝距離の変化率が低い値を示す傾向にある．
• 過去の世代との比較では，全世代に対して必ずしも良い対戦成績を示さない．両集団共に，進化時に獲得した適応度にほぼ等しい値を示しており，理想とする軍拡競争とは言い難い．
今後は，競争型共進化を適用する他の問題においても適応度景観の変化を捉えることが可能であるかを検証していきたい．また，測定した適応度景観の特徴量に基づき進化ダイナミクスの解析を行い，その問題に適した GA を適用することで理想的な競争型共進化が発生するのではないかと考えられる．そこで，SGA と比べ，より良い解空間を探索することができる Operon GA (11) を用いることにより，理想的な競争型共進化が起こるかを検証していく予定
である．

講演会論文集, pp. 249–250 (2008)（ 5 ） 半田佑太・片田喜章:「捕食-被食関係にある進化型ヱ-ジェンとにおける適応度景観の特徴量推定」, 第 18 回インテ
リジェント・システム・シンポジウム (FAN シンポジウム) 講演会論文集, pp. 251–256 (2008)（ 6 ） 半田佑太・片田喜章:「捕食-被食関係にある進化型エージェントにおける対戦相手の選択方法に関する一考察」, 計測
自動制御学会システム・情報部門学術講演会 2009 講演論文集, pp. 131–136 (2009)（ 7 ） T. Smith, P. Husbands, P. Layzell and M. O’Shea:“Fitness Landscape and Evolvability“, Evolutionary
Computation, Vol.11, No.4, pp. 381–415 (2002)（ 8 ） 根井正利:「分子進化遺伝学」, 培風館 (1990)（ 9 ） T. Ohta: “The Nearly Neutral Theory of MolecularEvolution“, Annual Reviews Ecology and Systematic
23, pp. 263–286 (1992)（10） D. Cliff, G. F. Miller: “Tracking the Red Queen: Measurements of Adaptive Progress in Co-Evolutionary
Simulations“, In Proceedings of the Third European
Conference on Artificial Life, pp. 200–218 (1995)（11） 大倉和博・上田完次:「非定常関数最適化問題のための遺伝的アルゴリズム」, システム制御情報学会論文誌, Vol.8,No.6, pp. 269–276 (1995)

参考文献（ 1 ） マッド・リドレー:「赤の女王」, 翔泳社 (1995)（ 2 ） D. Floreano and S. Nolfi: “God Save the Red Queen!
Competition in Co-Evolutionary Robotics“, In Proceedings of the 2nd Annual Conference on Genetic Programming, Stanford University, pp. 398–406 (1997)（ 3 ） 片田喜章・大倉和博:「根井の標準遺伝距離を用いた適応度景観に含まれる neutrality の推定– 進化ロボティクスへの適用」, システム制御情報学会論文誌, Vol.18, No.8,pp. 284–291 (2005)（ 4 ） 半田佑太・片田喜章:「競争型共進化における適応度景観の特徴量推定」, 第 52 回システム制御情報学会研究発表
6/6