捕食-被食関係にある進化型エージェントにおける対戦相手の選択方法に関する一考察○ 半田 佑太 片田 喜章(摂南大学)

Coevolving Predator and Prey Agents: Opponent Selection Methods* Y. Handa and Y. Katada (Setsunan University)
Abstract– Open-ended evolution is considered to be caused by several factors, one of which would

be co-evolution. However, in general, artiﬁcial co-evolutionary systems should not be expected toexhibit continuous progressive adaptation with each generation improving on previous generations.
In this paper, we proposed an opponent selection method where each individual’s ﬁtness is evaluatedagainst the best competitors of the preceding generations in order to measure the “Red Queen eﬀect”
of ﬁtness landscapes on predator and prey agents and to investigate co-evolutionary progress.
Key Words: Evolutionary Robotics, Genetic Algorithm, Neural Networks, Fitness Landscape1

証している 2) ．しかし，この方法では，世代数が多くはじめに競争型共進化において，種が存続するためには進化し続ける必要があり進化をやめるとその種は絶滅する「赤の女王仮説」が提唱されている 1) ．ここでは，ある種の利益は競争関係にある種の損失となり，その種が利益を得るため対抗戦略を講じることを互いに繰り返す軍拡競争として現れる．
競争型共進化では軍拡競争により，適応度景観が絶え間なく変化し，永続的進化を導くと考えられる．し
たがって，適応度景観の変化を捉える，つまり，景観の特徴量が変化し続けることを観察できれば，人工進化における共進化の発生を確認できるのではないかと考えた．そこで，我々は捕食-被食関係にある 2 つの個体集団を設定し，各世代における適応度景観の特徴量を推定し 3) ，その変遷を調べることで，競争型共進化の発生について検証を行った 4)5) ．しかしながら，そなるほど計算時間が膨大になる．
以上を考慮して本研究では，適応度景観の特徴量を各世代で測定するのではなく，ある一定の世代間隔で測定する．また，自然進化において突然変異率は非常に小さく対戦相手の遺伝的性質は頻繁に変化しないと推測されることから，一定世代間は同一の対戦相手を選択する方法を採用する．これらを用い，計算機実験において捕食-被食関係にある 2 つの個体集団から適応度景観の特徴量を測定し，対戦相手の変更による適応度景観の変化を検証し，軍拡競争の発生について検証する．

適応度景観の特徴量推定2

適応度景観の特徴量には凸凹度 (ruggedness) と中立度 (neutrality) があることが知られている 3)6) ．本稿では，エージェントのコントローラに次節で述べる進化の結果は上述の予想に反し，多くの場合，適応度景観型人工ニューラルネットワーク (Artiﬁcal Neural Net-の特徴量の変化が世代を経るにつれ次第に小さくなっworks: ANN) を用いるため，その適応度景観にはこの2 つの特徴量が含まれると考えられる．これらを推定する指標について次に述べる．ていった．その原因としては採用した適応度景観の特徴量推定法の設定が各世代における特徴量の変化を測定するのに適切ではないことが考えられる．
また，競争型共進化における軍拡競争では，進化時に2.1

凸凹度の指標対戦相手に対して優位になるだけではなく，その時点実問題における凸凹度は適応度景観の相関に基づいより過去の世代における対戦相手に対しても優位になて推定される．そこで凸凹度の指標として，その傾きでは，世代が適応度景観の相関を表す Smith の Eb 6) を用いる．

毎に対戦相手が変化する設定としていたため，それぞ適応度 k の親個体から生まれる子個体の平均適応度ることが理想的と考えられる

2)．文献

4)5)

れの対戦相手に十分に適応することが難しくなり，過を表す Eb は次のように定義される．

去の世代に対して必ずしも優位にはならなかった．また，Floreano らは全ての最良個体を全世代の対戦相手の最良個体に対して評価を行い，軍拡競争について検∑Eb (k) =g∈G(k) V (g)|G(k)|．

(1)ここで，G(k) は適応度 k の親から生まれる子の遺伝子

ここで，Ts は一定世代間の初期世代である．式 (4) は，型集合，g は子の遺伝子型，V (g) は子の適応度である．

式 (3) と同様の特性をもつと考えられることから，世この Eb (k) は中立度の値の影響を受けず，凸凹度が増代数に対する遺伝距離の変化率 α を Tc 間に獲得した

加すると k に対する Eb の傾き (Ėb ) は減少することが遺伝距離のデータから最小二乗法を用いて求める．こ知られている 6) ．この傾きは遺伝的操作として突然変れを式 (1) の傾き Ėb と併せて，中立度の指標とする．

異を用いた場合の自己相関関数に比例し，凸凹度が最も小さいとき Ėb ' 1.0 に，凸凹度が最も大きいときĖb ' 0.0 になる．
2.23

計算機実験

3.1

実験設定

競争関係にある個体集団として捕食者集団 (Pr) と披

中立度の指標中立度の指標 3) に用いる標準遺伝距離 7) は以下のように定義される．集団 X における第 i 番目の遺伝子座の対立遺伝子 l の頻度を xil = nil /M (i = 1, ..., L，L :遺伝子長，M : 個体数，nil : 集団内の対立遺伝子 l ∈{0, 1} の数) とする．同様に集団 Y における yil を考え，
22jxi = x2i0 + x2i1 ，jyi = yi0+ yi1，jxyi = xi0 yi0 + xi1 yi1とする．ここで，jxi は集団 X から任意に選んだ 2 個体における第 i 番目の遺伝子座の対立遺伝子が等しい確率であり，jyi は集団 Y のそれである．jxyi は集団 X とY のそれぞれから任意に 1 個体ずつ選んだ 2 個体における第 i 番目の遺伝子座の対立遺伝子が等しい確率である．これらは各遺伝子座に対し定義されるので，全遺伝∑L∑L子座の平均は，JX = i=1 jxi /L，JY = i=1 jyi /L，∑L
JXY = i=1 jxyi /L となる．このとき，根井の標準遺食者集団 (Py) を仮定する．実験環境は Fig. 1 のように設定し，周囲は壁に囲まれているものとする．エージェ
ントは壁用と他エージェント用の 2 種類の距離センサをもち，その配置を Fig. 2 とする．移動機構として，左右二輪独立駆動型を用い，移動速度の最大値は，両エージェント共に等しい設定とする．エージェントの制御器として，中間層・出力層が完全相互結合された ANNを用いる．入力ノード数は Ns = 18(センサ数)，出力ノード数は No = 2(左右モータの周速度)，中間ノード数は Nh = 3 とする．Fig. 1 の初期位置から，それぞれのエージェントの初期姿勢を 90◦ ずつ変えた試行を16 回行う．Pr はより早く Py を捕えることを，Py はより長く Pr の追跡から逃れることを目的とし，次の適応度関数を用いてそれぞれの適応度を計算する，伝距離は次のように与えられる．

D=JXY−loge √ √ ．
JX JY

Fpr=T∑
rials(2)

集団遺伝学では，突然変異率が十分に小さいことを仮i=1

Fpy=T∑
rials
i=1

定している．集団 X と Y の選び方として，t 世代での個体集団と t + 1 世代での個体集団を用い，世代間の遺伝距離 Dt,t+1 を求める．文献3)

では，適応度景観が変(5)

Stepi /M axStep．
T rials(6)

ここで，T rials は試行回数 (16) であり，Stepi は試行i におけるエージェント同士が接触するまでのステップ数，M axStep は最大のステップ数で 400 とする．進化化しない問題に対し，D(T ) =

1 − Stepi /M axStep，T rials

T−1∑

Dt,t+1 ．

(3)

t=1とし (T は世代数)，各世代数に対する遺伝距離 D(T )の変化率 α を最小二乗法を用いて求めている．これは，中立度が大きいほど増加し，凸凹度が大きいほど減少㪧㫉㪼㫐㪧㫉㪼㪻㪸㫋㫆㫉するという特性をもつ．しかしながら，適応度景観が毎世代変化する競争型共進化問題 4)5) では α を毎世代求めると 1. で述べたように，世代を経るに従って各世代における遺伝距離の変化 Dt,t+1 が，式 (3) に与える影響が小さくなり，大きく反映しなくなる．したがって，特徴量の変化の検証が困難になっていた．そこで
本稿では，ある一定の世代間隔 (Tc ) に基いて遺伝距離を以下のように計算する．

D(Ts ) =Ts +T∑c −1
t=TsDt,t+1 ．

(4)

Fig. 1: Experimental setup for a pursuit-evasion contest．

㪫㫊䌾㩿㪫䌳䋫㪫㪺㪄㪈㪀㩷㪞㪼㫅㪼㫉㪸㫋㫀㫆㫅㪦㪫㫊㪪㪼㫅㫊㫆㫉

㪧㫉㪼㪻㪼㫋㫆㫉

䊶䊶䊶

㪧㫉㪼㫐

㪭㪪

(a) OP1Fig. 2: Simulated models of sensors for predator and㪈䌾㪈㪇㪇㪇㩷㪞㪼㫅㪼㫉㪸㫋㫀㫆㫅

prey robots．

䊶䊶䊶手法として Simple GA を用いる．ANN の結合荷重を㪦㪈㪭㪪

変数とし，10 ビット・バイナリコーディングを行う．先に述べた ANN の構造から，遺伝子長は L = 1150 となる．2.2. で述べた遺伝距離を求めるため，点突然変異のみを遺伝的操作として用いる 3) ．突然変異率は，2.2.

㪈㪇㪇㪈䌾㪉㪇㪇㪇㩷㪞㪼㫅㪼㫉㪸㫋㫀㫆㫅で述べたように十分に小さく設定する必要があること

㪦㪈用い，トーナメントサイズは 2 とする．両集団ともに個体数を M ＝ 50，世代数を 5000 とし，独立に 10 試

䊶䊶䊶から，1/L とする．選択法としてトーナメント選択を

㪦㪈㪇㪇㪈

㪭㪪

行行う．の 2 パターンの設定を用いる．

• Ts 世代から (Ts + Tc − 1) 世代における対戦相手として (Ts − 1) 世代での最良個体 (OTs ) を用い䊶䊶䊶

また，競争する対戦相手の個体の選択方法として，次㪫㫊䌾㩿㪫䌳䋫㪫㪺㪄㪈㪀㩷㪞㪼㫅㪼㫉㪸㫋㫀㫆㫅る．ここで Ts ∈ {1, 1001, 2001, 3001, 4001}，Tc

㪦㪈

㪦㪫㫊

㪦㪈㪇㪇㪈

相手は初期世代からランダムに選択した 1 個体と䊶䊶䊶＝ 1000 とし，初期世代から 1000 世代までの対戦

㪭㪪

㨯㨯㨯

する (Fig. 3(a))．この対戦相手の選択法を OP1 とする．

• Ts 世代から (Ts + Tc − 1) 世代における対戦相手として (Ts − 1) 世代での最良個体とそれまでの世代で対戦した最良個体の複数 ({O1 , O1001 , . . . , OTs })(b) OP2

Fig. 3: Method of selecting opponent．

を用いる．ここで Ts ，Tc は OP1 と同様とし，初期世代から 1000 世代までの対戦相手も OP1 と同その他においてはほぼ一定に保たれている (Fig. 4(a))．

様に設定する (Fig. 3(b))．この対戦相手の選択法

Py の適応度は，初期世代から 1000 世代まで非常に高いを OP2 とする．

値を示しており，1001 世代で適応度が一度低くなり世代を経るにつれ少しずつ適応度が高くなる．そして，次の 2001 世代目でまた適応度が低くなり，以降 1000 世代

3.2
3.2.1

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

毎にこれが繰り返される (Fig. 4(a))．OP2 における Prの適応度は，安定的に高い値を示している (Fig. 4(b))．

Fig. 4 に，対戦相手の各選択方法における，世代に対Py の適応度は，初期世代から 1000 世代まで非常に高する最大適応度の推移の 10 試行中の典型例を示す．OP1い値を示しており，1001 世代から 2000 世代，2001 世

における Pr の適応度は 2001 世代で少し下がるものの，代から 3000 世代と OP1 における Py の適応度の変化

0.0008

1.00.0006

0.6ǩ

Fitness

0.8

0.0004Pr1-1000
Pr1001-2000
Pr2001-3000
Pr3001-4000
Pr4001-5000
Py1-1000
Py1001-2000
Py2001-3000
Py3001-4000
Py4001-5000

0.4
0.00020.2Pr
Py

0.001000

2000 3000
Generation4000

0.00000.05000

0.20.4.
Eb

0.6

0.81.00.6

0.8

1.0(a) OP1(a) OP1
0.00081.00.0006

0.6ǩ

Fitness

0.8

0.0004Pr1-1000
Pr1001-2000
Pr2001-3000
Pr3001-4000
Pr4001-5000
Py1-1000
Py1001-2000
Py2001-3000
Py3001-4000
Py4001-5000

0.4
0.00020.2Pr
Py

0.001000

2000 3000
Generation4000

0.00000.05000

0.2

0.4

.
Eb(b) OP2(b) OP2Fig. 5: α as a function of the correlation (Ėb ) for eachFig. 4: Maximum fitness at each generation．

generation．と似た変化を示している．3001 世代以降は，対戦相手相手に対して適応できない，もしくは，十分に適応すが変更されても，適応度が下がることなく，より高い適る時間がなかったと考えられる．

応度を示している (Fig. 4(b))．Py に関して，初期 1000世代の適応度とそれ以降の適応度に大きな差が出る理由としては，初期 1000 世代の対戦相手は初期世代からランダムに選択した個体であることから，Py は Pr に追いかけられることがほとんどなく逃げることが容易であったためと考えられる．一方，Pr の適応度は，初期 1000 世代とそれ以降であまり変化しない．この理由としては，Pr と Py の初期位置 (Fig. 1) の関係から Prが獲得することのできる適応度に上限があり，1000 世代以降の対戦相手であっても，その上限に近い適応度を獲得できるほど十分に適応することが可能であった

3.2.2

適応度景観の特徴量

Fig. 4 で示した試行における各世代間 (Ts , Ts +Tc −1)で求めた (Ėb , α) を Fig. 5 に示す．Pr に関して Ėb は高い値を示し，α はほとんど変化していない．これは，対戦相手が変化すると，適応度景観の中立度は変化せず，相関のみが変化することを表している．2001 世代から3000 世代の Ėb は，他の世代の Ėb より低い値を示している (Fig. 5(a))．このことから，2001 世代から 3000世代における Pr の適応度は対戦相手の変更直後に低くなりその改善に時間がかかっていると考えられる．

からだと考えられる．また，OP1，OP2 ともにどの集

一方 Py における初期 1000 世代の特徴量は Ėb , α 共団においても，対戦相手が固定されている間は適応度に，最も高い値を示している．1001 世代以降では，Ėbの改善が見られる．しかし，Py の適応度は対戦相手を変更する前の適応度に達しておらず，変更された対戦の値は大きく変化しているが，α はほとんど変化していない．Py の初期 1000 世代の α が高い値を示している理由として，3.2.1. で述べた初期の対戦相手では

5000

5000
14000

14000

0.8

0.8

30000.40.2

2000

00.6
Generation-pr

Generation-pr0.6

1000

3000

0.40.2

2000

01000

1111000

2000
3000
Generation-py

4000

5000

11000

(a) Pr2000
3000
Generation-py

4000

5000

(a) Pr5000

5000
14000

14000

0.8

0.8

3000

0.40.2

2000

01000

0.6
Generation-py

Generation-py

0.6
3000

0.40.2

2000

01000

11
11000

2000
3000
Generation-pr4000

5000(b) Py

11000

2000
3000
Generation-pr4000

5000(b) PyFig. 6: Current individual vs. ancestral opponents (OP1)．

Fig. 7: Current individual vs. ancestral opponents (OP2)．

Py は追いかけられることがなく，高い適応度が得やすおける対戦成績からその検証を行う．

かったからだと考えられる．また，Fig. 4(a) におけるPy の適応度と比較すると，Py の Ėb が高い値を示している世代と，Py の適応度が高い値を示している世代が対応している．これは，Ėb の値が大きくなる，つまり，相関が大きくなっていることから進化が容易になり，適応度が高くなったと考えられる．さらに OP2 についても，Py，Pr 共に OP1 と同様の結果が確認できる (Fig. 5(b))．

Fig. 4(a) で示した試行における過去の世代との対戦成績を Fig. 6 に，Fig. 4(b) で示した試行における過去の世代との対戦成績を Fig. 7 にそれぞれ示す．ここでは，色の濃淡で成績を示しており，色が明るいほど成績が良く，濃い程成績が悪い設定となっている．また，過去の世代との対戦であるため，ある世代 (例えば 10世代) の個体は，その世代以降の世代 (10 世代からその後) の相手とは対戦しないことから対角線の上側の

3.2.3

過去の世代との比較みで成績は表される．さらに，計算時間の問題から本前節までに行われた結果によると，対戦相手を変更

実験では，100 世代毎の最良個体を選択し対戦させる．

することで，適応度景観の特徴量は変化し，その適応

Fig. 6(a)，Fig. 7(a) では，Pr がほぼ全ての対戦におい度景観に対応した適応度の改善も両集団に見られるこて良い成績を示している．Fig. 6(a) においては，2100，とから，進化実験の対戦相手に対し適応的に進化して2200 世代の Pr が全体と比較してあまり良い成績を示していない．これは，Fig. 4(a) において他の世代よりいると考えられる．しかし，競争型共進化においては，

1. で述べたように全世代にわたる対戦相手に対し適応度が改善されていることが望ましい．そこで本節では，
2)

Floreano ら が行っている，各世代の最良個体を過去の世代の最良個体と対戦させる方法を用い，全世代に低い適応度を示している世代の最良個体であるためと考えられる．一方，Fig. 6(b)，Fig. 7(b) の Py はほぼ全ての対戦においてあまり良い成績を示していない．特に，初期世代から 1000 世代では，全体と比較して良い対戦成績を示していない．これは，3.2.1. で述べたよ能性が考えられる．そこで，SGA と比べより良い解空うに対戦相手が初期世代からランダムに選択した個体間を探索することができる Operon GA8) を用い，さらであることが原因だと考えられる．また，Fig. 7(b) でなる適応度の改善が行われるのかを検証していく予定

は，2001 世代より後の Py の対戦成績がそれ以前の成である．

績と比較して良い成績を示している．この 2001 世代目
は，Fig. 4(b) において，進化実験時に複数の対戦相手が存在する設定 (OP2) に対して，うまく適応し最大適応度が下がること無く上がり始める世代である．本実験では，初期世代から 1000 世代の Py が進化時に獲得した適応度と比べて良い対戦成績を示さなかった．また，その他の世代に関しては，進化時に獲得した適応度にほぼ等しい成績を示した．このことから，過去の対戦相手に対して全ての世代で必ずしも良い成績を示していないことから理想的な軍拡競争が起こっているとは言い難い．

4

おわりに
本稿では，一定の世代間で適応度景観の特徴量を測定し，その間において同一の対戦相手を選択する方法を採用した．これを用い，捕食-被食関係にある 2 つの個体集団において，対戦相手を変更することによる適応度景観の変化を検証し，軍拡競争の発生について検証を試みた．得られた結果について次にまとめる．

• 適応度景観の特徴量の測定法を一定の世代間とすることで，特徴量の変化を確認できた．特に相関が変化していることがわかる．また，初期 1000 世代の対戦相手の設定から，Py におけるその世代間の中立度は他の世代と比べ大きくなっていた．

• Pr，Py 共に，相関の値が大きくなると進化が容易になり，高い適応度を示す．
• OP1 の最大適応度では，対戦相手の変更により最大適応度が下がり，世代を経るつれて適応度が改善される．OP2 では，世代を経るにつれ，対戦相手が変更されても適応度が下がることなく改善され続ける．

• 過去の世代との比較では，全世代に対して必ずしも良い対戦成績を示さない．Pr 及び 1000 世代以降の Py は，進化時に獲得した適応度にほぼ等しい値を示しており，理想とする軍拡競争とは言い難い．
今後は，初期世代から 1000 世代にかけての対戦相手の選択方法を，初期世代からランダムに選択するのではなく，評価を行った後の個体を用いることによる検証を行っていきたい．さらに，Py に関して最大適応度の改善の途中において対戦相手が変更により，変更前の対戦相手に対して十分に適応する時間がなかった可

参考文献
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, 398/406 (1997)3) 片田喜章, 大倉和博: 根井の標準遺伝距離を用いた適応度
景観に含まれる neutrality の推定– 進化ロボティクスへの適用, システム制御情報学会論文誌, 18-8, 284/291(2005)
4) 半田佑太, 片田喜章: 競争型共進化における適応度景観の特徴量推定, 第 52 回システム制御情報学会研究発表
講演会論文集, 249/250 (2008)5) 半田佑太, 片田喜章: 捕食-被食関係にある進化型ヱ-ジェンとにおける適応度景観の特徴量推定, 第 18 回インテ
リジェント・システム・シンポジウム (FAN シンポジウム) 講演会論文集, 251/256 (2008)
6) T. Smith, P. Husbands, P. Layzell and M. O’Shea:
Fitness Landscape and Evolvability, EvolutionaryComputation, 11-4, 381/415 (2002)
7) 根井正利: 分子進化遺伝学, 培風館 (1990)
8) 大倉和博, 上田完次: 非定常関数最適化問題のための遺伝的アルゴリズム, システム制御情報学会論文誌, 8-6,269/276 (1995)