Ｄ３‐１

捕食-被食関係にある進化型エージェントによる適応度景観の特徴量推定

Estimation of Fitness Landscapes by Evolutionary Predator andPrey Robots
摂南大学○ 半田 佑太，片田 喜章○ Y. Handa and Y. Katada, Setsunan UniversityAbstract

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”, wherethe fitness landscape of each population is continuously changed by the competing population.
Therefore, if such changes are captured, co-evolutionary progress can be measured. In this paper,
we estimate features of competitive co-evolutionary fitness landscapes on predator and prey robots
with different sensory and motor characteristics in computer simulations and investigate the RedQueen effect on the fitness landscape.

1

はじめにエージェントのコントローラに次節で述べる進化型人

競争型共進化において，種が存続するためには進化し工ニューラルネットワーク (Artifical Neural Networks:の女王仮説」が提唱されている [1]．ここでは，ある種徴量が含まれると考えられる．これらを推定する指標にを得るため対抗戦略を講じることを互いに繰り返す軍拡

2.1

続ける必要があり進化をやめるとその種は絶滅する「赤ANN) を用いるため，その適応度景観にはこの 2 つの特の利益は競争関係にある種の損失となり，その種が利益ついて次に述べる．

競争として現れる．

凸凹度の指標実問題における凸凹度は適応度景観の相関に基づいて

この軍拡競争により競争型共進化は，適応度景観が絶推定される．そこで凸凹度の指標として，その傾きが適がって，適応度景観の変化を捉える，つまり，景観の特適応度 k の親個体から生まれる子個体の平均適応度をえ間なく変化し，永続的進化を導くと考えられる．した

応度景観の相関を表す Smith の Eb [4] を用いる．

徴量が変化し続けることを観察できれば，人工進化にお表す Eb は次のように定義される．
Pg∈G(k) V (g)Eb =|G(k)|ける共進化の発生を確認できるのではないかと考えた．
文献 [2] において，我々は適応度景観の推定法 [3] を用い，形態の等しい捕食-被食関係にある 2 つの個体集団における適応度景観の特徴量を推定し，その変遷を調べることで，競争型共進化の発生について検証を行った．
しかしながら，その結果は上述の予想に反し，多くの場合，適応度景観の特徴量の変化が世代を経るにつれ次第に小さくなっていくというものであった．この原因は，捕食エージェントが被食エージェントに対し常に高い適応度を示し，形態を等しく設定することが捕食エージェントにとって有利となっていることにあると推測される．
そこで本研究では，計算機実験において形態の異なる捕食-被食関係にある 2 つの個体集団を用いて [2] と同様の実験を行い，景観の特徴量を推定し，競争型共進化の発生について検証する．

2

適応度景観の特徴量推定
適応度景観の特徴量には凸凹度 (ruggedness) と中立度(neutrality) があることが知られている [4]．本稿では，(1)

ここで，G(k) は適応度 k の親から生まれる子の遺伝子型集合，g は子の遺伝子型，V (g) は子の適応度である．
この Eb (k) は中立度の値の影響を受けず，凸凹度が増加
すると k に対する Eb の傾き (Ėb ) は減少することが知られている [4]．この傾きは遺伝的操作として突然変異を用いた場合の自己相関関数に比例し，凸凹度が最も小さ
いとき Ėb ' 1.0 に，凸凹度が最も大きいとき Ėb ' 0.0になる [4]．

2.2

中立度の指標中立度の指標 [3] に用いる根井の標準遺伝距離 [5] は以下のように定義される．集団 X における第 i 番目の遺伝子座の対立遺伝子 l の頻度を xil = nil /M (i = 1, ..., L，L : 遺伝子長，M : 個体数，nil : 集団内の対立遺伝子l ∈ {0, 1} の数) とする．同様に集団 Y における yil を考
22え，jxi = x2i0 +x2i1 ，jyi = yi0+yi1，jxyi = xi0 yi0 +xi1 yi1とする．ここで，jxi は集団 X から任意に選んだ 2 個体

第 18 回インテリジェント・システム・シンポジウム（2008 年 10 月 23 日～24 日・広島）－251－

SY0010/08/0000-0251 © 2008 SICE

における第 i 番目の遺伝子座の対立遺伝子が等しい確率であり，jyi は集団 Y のそれである．jxyi は集団 X とY のそれぞれから任意に１個体ずつ選んだ２個体にお㪪㪼㫅㫊㫆㫉ける第 i 番目の遺伝子座の対立遺伝子が等しい確率である．これらは各遺伝子座に対し定義されるので，全遺伝
PLPL
子座の平均は，JX = i=1 jxi /L，JY = i=1 jyi /L，
PL
JXY = i=1 jxyi /L となる．このとき，根井の標準遺伝距離は次のように与えられる．

JXY
D = −loge p p
JX JY(a) SP1(2)集団遺伝学では，突然変異率が十分に小さいことを仮㪪㪼㫅㫊㫆㫉

定している．また，集団 X と Y の選び方として，t 世代での個体集団と t + 1 世代での個体集団を用いる．そして，世代間の遺伝距離 Dt,t+1 を求め，T 世代までの総和を GA における遺伝距離として以下のように拡張する．

(b) SP2

D(T ) =T−1X

Dt,t+1(3)t=1㪪㪼㫅㫊㫆㫉

この遺伝距離は中立度が大きいほど増加し，凸凹度が大きいほど減少するという特性をもつ [3]．このことを利用し，世代数に対する遺伝距離の変化率 α を世代毎にそれまで獲得した遺伝距離のデータを基に最小二乗法を用いて求め，式 (1) の傾き Ėb と併せて，中立度の指標とする．

Fig. 2: Simulated models of sensors for predator andprey robots

計算機実験

3
3.1(c) SP3

実験設定

競争関係にある個体集団として捕食者集団 (Pr) と披種類の距離センサをもち，その配置を SP1(Fig. 2(a))，

設定し，周囲は壁に囲まれているものとする．1. でもSP2(Fig. 2(b))，SP3(Fig. 2(c)) とする．移動機構として，左右二輪独立駆動型を用い，移動速度の最大値は，Pr に設定する．エージェントは壁用と他エージェント用の 2ように設定する．エージェントの制御器として，中間層・食者集団 (Py) を仮定する．実験環境は Fig. 1 のように述べたように，両エージェントの形態は異なるように

対し Py が 2 倍の最大速度を持つ (Vmax,py = Vmax,pr ×2)

出力層が完全相互結合された ANN を用いる．入力ノー
ド数は Ns = 18(センサ数)，出力ノード数は No = 2(左右モータの周速度)，中間ノード数は Nh = 3 とする．

㪧㫉㪼㫐Fig. 1 の初期位置から，エージェントの初期姿勢をそれ㪧㫉㪼㪻㪸㫋㫆㫉ぞれ 90◦ ずつ変えた試行を 16 回行う．Pr はより早く Pyを捕えることを，Py はより長く Pr の追跡から逃れることを目的とし，次の適応度関数を用いてそれぞれの適応度を計算する．

Fpr =Fig. 1: Experimental setup for a pursuit-evasion contestTXrials
i=1

Fpy =TX
rials
i=1－252－

1 − Stepi /M axStep，T rials(4)

Stepi /M axStep
T rials(5)ここで，T rials は試行回数 (16) であり，Step はエー

1.0

は最大のステップ数で 400 とする．進化手法として Sim-0.8

ジェント同士が接触するまでのステップ数，M axStep

Fitnessple GA (SGA) を用いる．ANN の結合荷重を変数とし，10 ビット・バイナリコーディングを行う．遺伝子長はL = 1150 となる．遺伝的操作として点突然変異を用い，突然変異率は，2. で述べたように，十分に小さく設定する必要があることから，q = 1/L とする．選択法として

0.6
0.4
0.2

トーナメント選択を用い，トーナメントサイズは 2 とす0.0る．競争する対戦相手の個体の選択方法は，同世代の競Pr
Py01000

方法 (SG)，1 世代前の最良個体を選択する方法 (BP1)，

5000

4000

5000

4000

5000

1.0取る方法 (BP10) を用いる．すべての設定において，両集団ともに個体数を 50，世代数を 5000 とし，独立に 100.8Fitness試行行う．

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

0.60.4

Fig. 3–5 に，対戦相手の選択方法に対する各センサパ

0.2

試行中の典型例を示す．全ての設定において，世代を通0.0

ターンにおける，世代に対する最大適応度の推移の 10

して Pr の適応度が高くなる傾向にあるが，Py の適応度Pr
Py01000が高くなる世代も見られ，そのときは Pr の適応度が低くなっている．このときのエージェントの振舞いを観察

2000 3000
Generation(b) SP2

すると，最大速度の違いから，Py が Pr を周回し，Pr1.0に捕えられることなく逃げ切る行動がみられる．この結果から，エージェントの形態に差を与えることで，両集0.8団で交互に適応度が改善されることがわかった．
適応度景観の特徴量

Fitness

3.2.2

4000(a) SP1

10 世代前までの各世代の最良個体と対戦しその平均を3.2.1

3000

Generation

争関係にある集団の中からランダムに１個体を選択する

3.2

2000

Fig. 6–8 に，Fig. 3–5 で示した試行における各世代に対する (Ėb , α) を示す．形態に差を与えることによって，

0.6
0.40.2

両集団において最大適応度にも変化があったこと (前節参照) から，適応度景観の特徴量は変化し続けていると0.0いう予想をしていた．しかし，[2] と同様に，(Ėb , α) の値の変化は両集団ともに約 1000 世代以降でほとんど変化しなくなっている．初期 1000 世代の間では，Ėb , α とPr
Py
01000

2000 3000
Generation(c) SP3もに大きく変化しているが 1000 世代以降になると，世Fig. 3: Maximum fitness at each generation (SG)

代を経る毎に (Ėb , α) の値の変化が小さくなっており，過去の世代との比較

約 3000 世代以降では変化はほとんど見られない．本実

3.2.3

q = 1/L と非常に小さく設定している．このことから，世代以降でほぼ変化が見られなくなっており，この結果

験設定では，遺伝距離の特性のために，突然変異率を種間に競争関係を設定し両種を進化させた場合でも，突然変異率が非常に小さいときは，世代を経るにつれて集団がそれぞれの遺伝子型空間で収束していくのではないかと考えられる．

前節の実験結果では，適応度景観の特徴量は約 1000から適応度景観が常に変化しているとは言えず，共進化の発生を十分に確認できない．これを別の方法で確認するため，Floreano ら [6] が行っている，各世代の最良個体を過去の世代の最良個体と対戦させる方法を用いる．

－253－

1.00.8

0.8

0.6

0.6FitnessFitness

1.00.40.2
0.00.2Pr
Py01000

2000

3000

0.4

4000

0.05000

Pr
Py01000

Generation

0.80.80.60.6

Fitness

Fitness

1.00.41000

2000 3000
Generation

4000

0.05000

01000

0.80.80.60.6

Fitness

Fitness

1.00.41000

5000

2000 3000
Generation

4000

5000

0.40.2Pr
Py02000 3000
Generation(b) SP2

1.00.04000

PrPy(b) SP2

0.2

5000

0.40.2Pr
Py04000(a) SP1

1.00.03000

Generation(a) SP1

0.2

2000

4000

0.05000(c) SP3

Pr
Py01000

2000 3000
Generation(c) SP3

Fig. 4: Maximum fitness at each generation (BP1)

Fig. 5: Maximum fitness at each generation (BP10)

競争型共進化では，過去の対戦相手 (の最良個体) に対しの世代との対戦であるため，ある世代 (例えば 10 世代)わたり，適応度が順次改善されていることが望ましい．

相手とは対戦しないことから対角線の上側のみで表されて各世代の個体が良い適応度を示す，つまり，全世代にFig. 9 に，(BP10，SP3) における過去の世代との対戦成績 (適応度で評価) を示す (Fig. 5(c)，8(c) の試行に対応)．ここでは，色の濃淡で成績を示しており，色が明るいほど成績が良く，濃いほど成績が悪い．また，過去の個体は，その世代以降の世代 (10 世代からその後) のる．さらに，計算時間の問題から本実験では，100 世代おきに最良個体を選択し対戦している．Pr はほぼ全ての対戦において良い成績を示している (Fig. 9(a))．特に，2700 ∼ 3500 および 4900 世代の Pr は，ほとんどの過－254－

0.020

0.015

0.015
ǩ

ǩ

0.020

0.010
0.005
0.000
0.00.010
0.005

0.2

0.4

0.6

0.8

1.00.000
0.00.2Pr1-1000
Pr1-1000

Pr1001-3000
Pr1001-3000

0.4.
Eb
Pr1-1000
Pr1-1000

Pr1001-3000
Pr1001-3000

Pr3001-5000
Pr3001-5000

0.020

0.020

0.015

0.015

0.010
0.005
0.000
0.0

0.2

0.4

0.6

0.8

1.0

0.000
0.00.2

Pr1001-3000
Pr1001-3000

Pr3001-5000
Pr3001-5000

Pr1-1000
Pr1-1000

Pr1001-3000
Pr1001-3000

0.4

0.020

0.015

0.015
ǩ

ǩ

0.6.
Eb

0.8

1.0

Pr3001-5000
Pr3001-5000(b) SP2

0.020

0.010
0.005

0.010
0.005

0.2

0.4

0.6

0.8

0.000
0.0

1.00.20.4.
Eb
Pr1-1000
Pr1-1000

Pr3001-5000
Pr3001-5000

0.005(b) SP2

0.000
0.0

1.00.010.
Eb
Pr1-1000
Pr1-1000

0.8(a) SP1

ǩǩ(a) SP1

0.6.
Eb

Pr1001-3000
Pr1001-3000

Pr3001-5000
Pr3001-5000

Pr1-1000
Py1-1000(c) SP3

0.6.
Eb

Pr1001-3000
Py1001-3000

0.8

1.0Pr3001-5000
Py3001-5000(c) SP3

Fig. 6: α as a function of the correlation (Ėb ) for eachFig. 7: α as a function of the correlation (Ėb ) for eachgeneration (SG)generation (BP1)

去の対戦相手に対し，良い成績を示している．これは，(Fig. 5(c))．本実験では，各世代の最良個体が進化実験

Fig. 5(c) で Pr の適応度が高かった世代に対応する．一方，Py はほぼ全ての対戦においてあまり良い成績を示しておらず (Fig. 9(b))，特に，2000，3000 および 4900
世代では，過去の対戦相手に対し，良い成績を示していない．これは，Py の適応度が低かった世代に対応する

時に獲得した適応度にほぼ等しい対戦成績を示し，過去の対戦相手に対して，全ての世代で必ずしも良い成績を示していないことから，理想的な共進化が起こっているとはいえない．

－255－0.020

5000

0.015

4000

Generation-prǩ

10.010
0.005
0.000
0.0

Pr1-1000Pr1-1000

0.80.6

3000

0.4

2000

00.2

1000

0.20.40.6.
Eb

Pr1001-3000
Pr1001-3000

0.8

1.0

111000

2000

3000

4000

5000

Generation-py

Pr3001-5000
Pr3001-5000(a) Pr5000
1Generation-py(a) SP1

0.020

ǩ

0.015
0.010

4000

0.8
0.6

3000

0.4

2000

00.2

1000

0.005

111000

2000

3000

4000

5000

Generation-pr

0.000
0.0

Pr1-1000
Pr1-1000

0.2

0.4

0.6.
Eb

Pr1001-3000
Pr1001-3000

0.8

1.0(b) Py

Fig. 9:Current individual vs. ancestral opponents(BP10, SP3)

Pr3001-5000
Pr3001-5000

景観の特徴量は，形態が等しいときと同じく，世代を経るにつれほとんど変化しなくなった．これは種間に競争ǩ(b) SP20.020

関係を設定しても (適応度関数，エージェントの形態)，0.015によって集団が収束し得ることを示している．今後，形突然変異率 (より一般的には遺伝的オペレータ) の設定態に差を与えることに加えて，2. で述べた遺伝距離の0.010

特性が現れる範囲で突然変異率を上げ，適応度景観を観察するとともに，過去の世代の最良個体との比較と併せ0.005
0.000
0.0

Pr1-1000
Py1-1000て，競争型共進化の発生を検証していく予定である．

0.20.40.6.
Eb

Pr1001-3000
Py1001-3000

0.8

参考文献

1.0

[1] マッド・リドレー: 赤の女王, 翔泳社 (1995)[2] 半田佑太, 片田喜章: 競争型共進化における適応度景観の特徴量推定, 第 52 回システム制御情報学会研究発表講演
会論文集, pp. 249–250 (2008)

Pr3001-5000Py3001-5000(c) SP3

Fig. 8: α as a function of the correlation (Ėb ) for eachgeneration (BP10)

4

おわりに

本稿では，捕食-被食関係にあり形態の異なる 2 つの個体集団における，適応度景観の特徴量を推定しその変遷を調べ，競争型共進化の発生について検証を試みた．形態に差を与えることで，両集団の適応度が変化し，交互に適応度が改善されることを確認した．しかし，適応度[3] 片田喜章, 大倉和博: 根井の標準遺伝距離を用いた適応度景観に含まれる neutrality の推定– 進化ロボティクスへの適用, システム制御情報学会論文誌, Vol. 18, No. 8,
pp. 284–291 (2005)[4] T. Smith, P. Husbands, P. Layzell and M. O’Shea: Fitness Landscape and Evolvability, Evolutionary Computation, Vol. 11, No. 4, pp. 381–415 (2002)[5] 根井正利: 分子進化遺伝学, 培風館 (1990)[6] 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)－256－