競争型共進化における適応度景観の特徴量推定

Estimation of Fitness Landscapes of Competitive Co-Evolution
摂南大学○ 半田 佑太，片田 喜章

Y. Handa and Y. Katada
Setsunan UniversityAbstract
A number of researchers in the field of evolutionary computation have been trying
to improve the performance of artificial evolution on traditional problems by incorporating redundancy in genotype to phenotype mappings in recent years. However, it is still not clear what kindof redundant mapping is useful for what class of problems. In this work, we conducted a series ofcomputer simulations with GAs with redundant mappings from genotype to phenotype in order
to investigate what kind of redundant mapping is useful for rugged fitness landscapes.

はじめに

1

競争型共進化において，種が存続するためには進化し(Ėb ) で表される．ruggedness が最も小さいとき Ėb ' 1.0に，ruggedness が最も大きいとき Ėb ' 0.0 になる [5]．

neutrality の推定続ける必要があり進化をやめるとその種は絶滅する「赤2.2の女王仮説」が提唱されている [1]．ここでは，ある種の利益は対立する種の損失となり，その種が利益を得る

neutrality の推定 [4] に用いる，根井の標準遺伝距離[6] は以下のように定義される．集団 X における第 i 番

ため対抗戦略を講じることを互いに繰り返す軍拡競争と目の遺伝子座の対立遺伝子 k の頻度を xik = nik /Mして現れる．この軍拡競争により，競争型共進化では適(i = 1, ..., L，L : 遺伝子長，M : 個体数，nik : 集団内応度景観が絶え間なく変化し，永続的進化を導くと考えの対立遺伝子 k ∈ {0, 1} の数) とする．同様に集団 Yられる．Hillis は，競争型共進化が人工進化において有22における yik を考え，jxi = x2i0 + x2i1 ，jyi = yi0+ yi1，効に働くことを示した [2]．また，Floreano らは，競争jxyi = xi0 yi0 + xi1 yi1 とする．ここで，jxi は集団 X か型共進化によって得られる各世代での最良個体を互いにら任意に選んだ 2 個体における第 i 番目の遺伝子座の対比較し，その適応度から「赤の女王仮説」について検証

立遺伝子が等しい確率であり，jyi は集団 Y のそれであしている [3]．そこで本研究では，我々の研究グループる．jxyi は集団 X と Y のそれぞれから任意に１個体ずで提案している適応度景観の推定法 [4] を用いて，計算つ選んだ２個体における第 i 番目の遺伝子座の対立遺伝機実験において競争関係にある 2 つの個体集団における子が等しい確率である．これらは各遺伝子座に対し定義PLされるので，全遺伝子座の平均は，JX = i=1 jxi /L，PL
PL
JY =i=1 jxyi /L となる．こi=1 jyi /L，JXY =適応度景観の特徴量を推定しその変遷を調べ，「赤の女王仮説」を検証する．

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

適応度景観の特徴量には ruggedness と neutrality があることが知られている [5]．本稿では，エージェントのコントローラに次節で述べる進化型 ANN を用いるため，その適応度景観にこの 2 つの特徴量が含まれると考えられる．これらを推定する方法について次に述べる．

2.1

ruggedness の推定実問題における ruggedness は適応度景観の相関に基づいて推定される．そこで ruggedness の指標として，その傾きが適応度景観の相関を表す Smith の Eb [5] をのとき，根井の標準遺伝距離は次のように与えられる：p p
D = −loge {(JXY )/( JX JY )}．さらに，集団 X とY について，t 世代での個体集団と t + 1 世代での個体集団を用いる．そして，世代間の遺伝距離 Dt,t+1 を求め，T 世代までの総和を GA における遺伝距離としてPT −1
以下のように拡張する：D(T ) = t=1 Dt,t+1 ．この遺伝距離には neutrality が大きいほど増加し，ruggednessが大きいほど減少するという特性がある [4]．このことを利用し，各世代における遺伝距離の変化率 α を求め，Ėb とあわせて，neutrality の推定を行う．

3

計算機実験

適応度を表す Eb は次のように定義される：Eb (k) =Pg∈G(k) V (g)/|G(k)|．ここで，G(k) は適応度 K の親か

3.1

実験設定

ら生まれる子の遺伝子型集合，g は子の遺伝子型，V (g)捕食集団 (Pr) と披食集団 (Py) を仮定する．エージェン

は子の適応度である．ruggedness の大きさは Eb の傾き

トは壁用と他エージェント用の 2 種類の距離センサをも用いる．適応度 k の親個体から生まれる子個体の平均

図 1 に環境の概略を示す．競争関係にある集団として

1㪧㫉㪼㪻㪸㫋㫆㫉

0.8

㪪㪼㫅㫊㫆㫉Fitness㪧㫉㪼㫐

0.60.40.20010002000 3000
Generationpr

図 1: 実験環境

40005000py

図 2: 世代に対する最大適応度の推移
ち，それぞれ図 1 のように搭載する．エージェントの制

0.020

御器として，中間層・出力層が相互結合された ANN を0.015用いる．入力ノード数は Ns = 18(センサ数)，出力ノーα

ド数は No = 2(左右モータの周速度)，中間ノード数は

Nh = 3 とする．図 1 の初期位置から，エージェントの初期姿勢をそれぞれ 90◦ ずつ変えた試行を 16 回行い，0.010
0.005
0.000

次の適応度関数を用いてそれぞれの適応度を計算する：
PT rials(1 − Stepi /M axStep)/T rials，Fpy =Fpr =PT rials i=1(Stepi /M axStep)/T rials．ここで，T rials はi=1

pr-1k
py-1k

試行回数 (16) であり，M axStep は 400 とする．進化手法として SGA を用いる．ANN の結合荷重を変数とし，10 ビット・バイナリコーディングを行う．遺伝子長はL = 1150 となる．遺伝的操作として点突然変異を用い，突然変異率は q = 1/L とする．選択法としてトーナメ

0.00.20.40.6.
Eb

pr-3k
py-3k0.81.0
pr-5k
py-5k

図 3: 各世代に対する (Ėb ,α) の推移

4

おわりにント選択を用い，トーナメントサイズは 2 とする．競争

本稿では，競争関係にある 2 つの個体集団における適する相手個体の選択方法は，同世代の対立集団の中から応度景観の特徴量を推定しその変遷を調べ，「赤の女王仮ランダムに１個体選出する．両集団ともに個体数を 50，説」の検証を試みた．今後，対立するエージェント間の世代数を 5000 とし，独立に 10 試行行う．

形態に差を与え，その適応度景観を調べることにより，

3.2

実験結果と考察

図 2 に世代に対する最大適応度の推移 (10 試行中の典

本稿の結果と比較および検証する予定である．

参考文献型例) を示す．Py の適応度の振動が激しく，Pr が常に高[1] マッド・リドレー: 赤の女王; 翔泳社, (1995)

い適応度を示している．本実験設定では，エージェント[2] W.D. Hillis: Co-Evolving Parasites Improve Simulated
Evolution as an Optimization Procedure; Artificial
Life II, Addition Wesley, pp. 313–323 (1991)の形態に差がなく，適応度のみが異なるため，Pr が有利になると考えられる．図 3 に各世代における (Ėb , α) の推移 (10 試行中の典型例) を示す．軍拡競争により，適応度景観が推移し続けるという予想に反して，(Ėb ，α)の値の変化は両集団ともに約 1000 世代で収束している．
これは Pr が常に高い適応度を持つことが影響していると考えられる．次に 1000 世代を詳しく観察すると，Ėbの値が大きく変化している．また，両集団の (Ėb , α) が世代に対して同期した推移を示しており，これが競争型共進化の特徴である可能性が考えられる．

[3] D. Floreano and S. Nolfi: God Save the Red Queen!
Competition in Co-Evolutionary Robotics; In proceedings of the 2nd International Cnoference on GeneticProgramming, Stanford University, (1997)[4] 片田, 大倉: 根井の標準遺伝距離を用いた適応度景観に含まれる neutrality の推定– 進化ロボティクスへの適用; システム制御情報学会論文誌, Vol. 18, No. 8, pp. 284–291(2005)[5] T. Smith, P. Husbands, P. Layzell and M. O’Shea: Fitness landscape and evolvability; Evolutionary Computation, Vol. 11, No. 4, pp. 381–415 (200)[6] 根井正利: 分子進化遺伝学; 培風館，(1990)