可変突然変異率戦略を用いた GA による進化ロボティクスへのアプローチ–ハンターロボットの進化的行動獲得への適用–
神戸大 ○ 片田 喜章, 高崎 真也, 大倉 和博

An Approach to Evolutionary Robotics Using a Genetic Algorithmwith a Variable Mutation Rate Strategy– Application to Evolving Pursuit Strategies –Yoshiaki KATADA∗, Shinya TAKASAKI ∗ and Kazuhiro OHKURA∗*Faculty of Engineering, Kobe University
Abstract: Neutral networks, which occur in ﬁtness landscapes containing neighboring
points of equal ﬁtness, have attracted much research interest in recent years. In a recentpaper, we have shown that, in the case of the simple test functions, the mutation rate ofa genetic algorithm is an important factor for improving the speed at which a population moves along a neutral network. Our results also suggested that the beneﬁts of thevariable mutation rate strategy used by the operon-GA increase as the ruggedness of thelandscapes increases. In this paper, we conducted a series of computer simulations withan evolutionary robotics problem which is expected to have a rugged landscape in order
to investigate whether our previous results are applicable to this problem domain. The
evolutionary dynamics we observed were consistent with those observed in our previous
experiments, conﬁrming that the variable mutation rate strategy is also beneﬁcial withthis problem.
Key Words: Evolutionary Robotics, Genetic Algorithms, Fitness Landscape1.

はじめに人工進化を用いて自律ロボットの制御機構を設計する進化ロボティクスがある．その際，遺伝子型-表現型写像もしくは表現型-適応度写像には多くの冗長性が含まれる．しかしながら，これを排除することは実質不可能であり，その結果，その適応度景観には台地状の neutral networks が非常に多く含まれることになる[1, 2, 3] ．進化ロボティクスの研究者はこの問題を強く意識するには至っていないが，neutral networks は進化ロボティクスだけではなく evolvable hardware[4, 5]などの適応度景観でも確認されており，近年盛んに議論されるようになってきている [6, 7, 8] ．

neutral networks における進化ダイナミクスは，transition period と equilibrium period に分類することができる [9, 10] ．equilibrium period では，遺伝子型空間において個体集団は，“準種 [11]” とよばれるクラスタを形成し，適応度のより高い neutral networksへと導く portal を見つけるまで移動し続ける．その後，transition period が始まる．この transition period は
equilibrium period に比べてその長さが極端に短いものが典型である．
このように equilibrium period では適応度空間において個体集団が収束するため，スキーマ定理を基本とした従来理論に基づく GA では，主遺伝的操作として交叉がうまく働かず，むしろ，交叉によりスキーマを破壊してしまうことが予想される．Nimwegen ら
は，スキーマ定理を実証するために設計された RoyalRoad Functions の適応度景観に neutral networks が含まれ，equilibrium period で交叉は有効ではない [9]と報告している．このことから，適応度景観に neutralnetworks を含む問題では，突然変異を主遺伝的操作として捉える必要がある．
突然変異率に関連して，equilibrium period における個体集団の分布に明確な相転移が見られる．低い突然変異率では，個体集団はクラスタを形成し移動する．
しかし，突然変異率が高くなるにつれ，いくつかの個体は現在の neutral network から適応度の低いものへと落ち始める．そして突然変異率があるしきい値を越えると，個体集団は完全に落ちてしまい，ランダム探索を始める．このしきい値は error threshold:qerr と呼ばれ，neutral network 毎にその値が異なることが報告されている [9, 12, 13] ．
一般に，効率的な探索を行う上で qerr は突然変異率の上限を定めるものである．これが意味することは，一定突然変異率を採用する場合，すべての neutral

2.

計算機実験

2.1.

設定

図 1 にハンターロボットによる追跡問題の概略を示す．生物界における捕食・被食の関係に倣い，追跡問
題では捕食者と被食者に別種を仮定することが多い．
本稿でもこれに従い，異なるセンサを有する二種のロPrey

Hunter

Fig.1 Experimental setup for a simulated pursuit problem.
The initial starting positions for a hunter robot and a prey
robot are given in the arena. The initial orientation is set atrandom.

IR Sensor Range

IR Sensor(a) Omni-directional sensor for a hunter robot(b) IR sensors for a preyrobotyVLVR

2R

network に対し qerr を越えないように突然変異率を予めかなり低く設定する必要があるということである．
しかしながら，ruggedness をも同時に含む問題においては，低い一定突然変異率では個体集団は往々にして局所解に陥ってしまう．error threshold を考慮して低い突然変異率に設定すると ruggedness によって個体集団が局所解に収束しやすくなるというジレンマを打破する一つの方法として，可変突然変異率戦略を用いることが考えられる．
我々は neutral networks における個体集団の移動速度および ruggedness を同時に含むテスト関数におけるパフォーマンスに関して，可変突然変異率戦略を用いた operon GA (以下 OGA)[14] が一定の突然変異率を採用する simple GA (以下 SGA) に比べ明らかに優位にあることを示してきた [15] ．この知見を基に，SGAと OGA を進化ロボティクスの一問題である自律エージェントによる運動パターン識別問題に適用し，この問題の進化ダイナミクスに equilibrium period が認められること，及び，探索空間が大きくなる程，OGAは SGA に対し優位となることを確認した [16, 17] ．
運動パターン識別問題における適応度景観の ruggedness は比較的小さいものであることがわかっている[16] ．本稿では，運動パターン識別問題よりも ruggedness が大きいことが予想される進化ロボティクスの一問題である自律エージェントによる追跡問題に SGAと OGA を適用し，これまで得られた知見を検証することを目的とする．以下，2. ではシュミレーションに
おいて SGA と OGA の進化ダイナミクスを観察し，3.
では，本問題の適応度景観における neutral networksの存在を検証する．最後にまとめを示す．

P(x,y)

0x(c) Model of a mobilerobot
Fig.2 Simulated models for a hunter robot and a prey robot

ボットを仮定する．つまり，ハンターロボットは全方位カメラを搭載し，獲物ロボットは近接センサを搭載していると設定する．
図 2 に各ロボットのセンサ入力・モータ出力モデルを示す．全方位カメラのモデルは以下のように仮定する．まず，ハンターロボットに最も近い対象物の座標を計算する．次に，全方位画像 (ここで，全方位画像の中心はハンターロボットの中心に一致する) を図2(a) のように分割し [18] ，先に計算した対象物の座標を用いて，どのセルに物体が存在するかを判定する(qij = {0, 1}, i = 1, . . . , I;j = 1, . . ., J ．ここで qij は物体の存在の有無を表す)．全方位カメラの特徴より，カメラの高さとほぼ同じ高さの物体の対象物の最近点が第 j 番目のセルに存在する場合，第 j +1 番目のセルから第 J 番目のセルにおいても物体が検出されることから，これと同様に設定する (qij+1 = · · · = q iJ = 1,
if q ij = 1)．近接センサは図 2(b) に示す距離まで測定が可能であり，物体までの距離と反比例する値を出力するように設定する．
両ロボットの移動機構を左右二輪独立駆動型と仮定
し，式 (1) のようにモデル化する (図 2(c))．

xk+1=yk+1=

θk+1=

VR + VLcos θk + ωxk+12
VR + VLyk +sin θk + ωyk+12
VR − VLθk ++ ωθk+1 ,2R
xk +(1)

ここで，VR と VL は両車輪の周速度，2R は車輪間隔，
ω[·]k はシステム誤差のモデルとする．式 (1) 中のシス
テム誤差は平均 0・標準偏差 σ の正規分布 N (0, σ) で

2.2.

IR sensor
excitatory

Fig.3 Architecture of a Braintenberg vehicle

表されることが知られている [19] ．本実験では，σ は各ステップにおける移動量の 10%に設定する．
ハンターロボットのコントローラとして，中間層・出力層が完全相互結合された Pulsed Neural Networks(以下 PNN) を用いる．入力ノード数は 64(全方位画像の分割セル数)，出力ノード数は 2(左右モータ)，中間ノード数は 3 とする．PNN で用いられる他のパラメー
タは [20] の設定に従う．一方，獲物ロボットのコントローラとして，障害物回避行動を示す “Braitenbergvehicle” モデル [21] を用いる (図 3)．入力数は 8(近接センサ:前方 6 個，後方 2 個)，出力数は 2(左右モータ)とする．
ハンターロボットは，より早く獲物ロボットを捕獲することを目的とする．両ロボットの初期姿勢を変えた試行を 10 回行い，次の適応度関数を用いてハンターロボットの適応度を計算する:
N umT
rialsStep)
M axStepi=1(2)
こ こ で ，N umT rials は 試 行 回 数 (10) で あ り，
M axStep は 400 とする．
進化手法として SGA および OGA を用いる．PNNの結合荷重・しきい値を変数とし，10 bits バイナ
リコー ディン グを行 う．文献 [15] と同 様の理 由により，遺伝的操作は点突然変異のみを用い，交叉は両 GA ともに用いない．OGA で用いる他の遺伝的操作 (結合 gcon ，分割 gdiv ，重複 gdup ，欠失 gdel ，逆位 ginv : [14]) の各パラメータは文献 [15] における 推 奨 値 を 参 考 に ，(gcon , gdiv , gdup , gdel , ginv ) =(0.3, 0.3, 0.6, 0.3, 0.3)(s=6 の 場 合) 及 び(0.3, 0.3, 0.2, 0.05, 0.05)(s = 2 の場 合) を 使 用 する．各遺伝子座における値のリスト長は 6 とする．両GA ともに，選択法としてトーナメント選択を用い，エリート戦略1 を付加的に適用する．SGA では弱い選択圧が，OGA では強い選択圧が推奨されていることから，トーナメントサイズを s = {2, 6} に設定する．遺伝子長は L = 3500 となる． qerr を考慮して，点突然変異率は q = 1/L とする．個体数を 50，世代数を 6000 とし，各計算回数を 10 回とする．
F itness =1
N umT rials(1 −1 適応度が最も高い個体からランダムに 1 つの個体を次世代の親個体として引き継ぐ．

実験結果と考察

図 4 に SGA を用いた場合の適応度景観の相関係数を示す．1. で予想したように本問題の適応度景観はruggedness が比較的大きくなっている．
図 5 に世代数に対する各 GA の平均最大適応度を示す．このグラフからは equilibrium period を含んでいることは確認できないが，試行毎に調べると短いequilibrium period を含んでいることが確認できた．
これについては 3. で議論する．また，適応度の上昇が望まれないほどの大きな適応度の振動は起きていないことから，本実験における実効突然変異率2 は各 GA
において qerr 以下となっていると考えられる．
s = 2 の場合，初期世代においてエリート戦略を用いたものと用いないものを比較すると，OGA は SGAよりも良いパフォーマンスを示すが，最終世代においてエリート戦略を用いた SGA と OGA の間で大きな違いは見られない (図 5(a),5(b))．一方，s = 6 の場合，OGA は局所解に陥いることなく，より良い解空間を探索し続けているが，SGA は局所解に陥っている (図5(c),5(d))．両 GA で推奨されている選択圧で比較した場合 (SGA:s = 2, OGA:s = 6)，OGA は SGA よりも良いパフォーマンスを示していることがわかる．
図 6,7 に SGA と OGA を用いて得られた最終世代におけるハンターロボットの最良個体の振舞いを示す．SGA においては，おおむね (A) 積極的な振舞いと，(B) 消極的な振舞い，の二種類の振舞いが観察された: (A) 試行が始まると，すぐに獲物ロボットに近づき，追いかけ回し，遂には捕獲する (図 6(a))．(B)
試行が始まっても初期位置の周りに留まり，しばらく獲物ロボットが近づくのを待ち，現在の移動速度で捕獲できる範囲に獲物ロボットが入るとすぐに追いかけ捕獲する (図 6(b))．一方，OGA においては，(A) の積極的な振舞いのみが観察された (図 7)．このように獲得された振舞いに差が生じる理由は以下のように説明することができる．本実験で採用した適応度関数 (式(2)) は，ハンターロボットがより素早く獲物ロボットを捕獲するほど，その値は増加する．従って，時間を浪費する消極的な振舞いは，獲物ロボットを捕獲できたとしても高い適応度を獲得することはできない．こ1.0
0.8
Correlation

IR sensor
inhibitory

0.6
0.40.2sga
elitism-sga0.001234
Hamming distance

56Fig.4 The correlation coeﬃcient as a function of the Hamming
distance between parents and oﬀspring for the SGA
2 遺伝子型における遺伝的操作によって反転したビット数の割合

Fitness

0.80.70.6
sga
oga

0.501000 2000 3000 4000 5000 6000
Generation(a) s = 2 without elitism(a) Positive behavior

Fitness

0.80.70.6
elitism-sga
elitism-oga

0.501000 2000 3000 4000 5000 6000
Generation(b) s = 2 with elitism
0.8(b) Negative behavior

FitnessFig.6 Behaviors of the genetically determined controller bythe SGA with elitism for s = 2: a prey robot (left) and a

0.7

hunter robot (right)
0.6
sga
oga

0.501000 2000 3000 4000 5000 6000
Generation(c) s = 6 without elitism

Fitness

0.80.70.6(a) Positive behavior 1elitism-sga
elitism-oga

0.5
01000 2000 3000 4000 5000 6000
Generation(d) s = 6 with elitism
Fig.5 Maximum ﬁtness at each generation

れが本実験の進化過程で積極的な振舞いが支持される理由であると考えられる．実際，OGA は SGA よりも良いパフォーマンスを示し，高い適応度を得ることができており (図 5)，このことが SGA と OGA で獲得された振舞いの差になって現れたと考えられる．

(b) Positive behavior 2
Fig.7 Behaviors of the genetically determined controller by
the OGA with elitism for s = 6: a prey robot (left) and ahunter robot (right)

neutral networks の存在検証

1.4

2. で観察された進化ダイナミクスは，1. で述べた
neutral networks を含む適応度景観で典型的に見られる equilibrium period がその大部分を占めるものとは異なっており，各試行毎に調べても equilibrium periodが非常に短いものであった．従って，適応度の推移のみから，本稿で扱った追跡問題の適応度景観に neutralnetworks が含まれるかは判定できない．これまで得られた知見 [15] は適応度景観に neutral networks が含まれることを仮定しており，本追跡問題においてその有効性を示すには，適応度景観に neutral networksが含まれていることを示す必要がある．そこで，次に述べる “根井の標準遺伝距離 [22, 23]” を用いることにより [24] ，本追跡問題の適応度景観における neutralnetworks の存在を検証する．
根井の標準遺伝距離 [22, 23] は以下のように定義される．集団 X における第 i 番目の遺伝子座の対立遺伝子 k の頻度を xik = nik /M (i = 1, . . . , N , M : 個体数, nik :集団内の対立遺伝子 k ∈ {0, 1} 3の数) とする．
同様に集団 Y における yik を考え，jxi = x2i0 + x2i1 ,22jyi = yi0+ yi1, jxyi = xi0 yi0 + xi1 yi1 とする．ここで，jxi は集団 X から任意に選んだ二つの相同な遺伝子が均一である確率であり，jyi は集団 Y のそれである．jxyi は集団 X と Y のそれぞれから任意に一個ずつ選んだ二つの相同な遺伝子が均一となる確率である．
これらは各遺伝子座に対し定義されるので，全遺伝子N
N
座の平均は，JX =jxi /N , JY = i=1 jyi /N ,i=1
N
JXY = i=1 jxyi /N となる．このとき，根井の標準遺伝距離は，突然変異率が小さいことを仮定すると次のように与えられる．
JXY
D = − loge √ √JX JY(3)

式 (3) を GA に適用するためには，バイナリコーディングによって起こる “back mutations [25]” を考慮しなければならない．そこで，遺伝距離を計算する際に用いる二つの集団 X と Y について，t 世代での個体集団と t + 1 世代での個体集団を用いる．そして，世代間の遺伝距離 Dt,t+1 を式 (3) より求め，T 世代までの総和を GA における遺伝距離として以下のように拡張する．
T−1
D(T ) =Dt,t+1(4)t=1[24] において，我々は，適応度景観に neutral networks を含むテスト問題において SGA を用いた計算機実験を行い，得られた遺伝子型データから根井の標準遺伝距離を計測し，その特性を調べた．結果は次のようにまとめられる．
突然変異率が十分に小さいという条件の下で，3 k の要素数はバイナリコーディングを用いた GA の対立遺伝子数に対応している．

1.2
Genetic distance

3.

1.0
0.8
0.6
0.4
0.2
0.00

1000 2000 3000 4000 5000 6000
Generation

Fig.8 Genetic distance at each generation for the SGA at
q = 1/L in 10 runs

(1) neutrality を含む適応度景観において，根井の標準遺伝距離は世代数に対し，ほぼ線形的に増加し続ける．一方，neutrality を含まない適応度景観においては，遺伝距離は初期数世代の間に収束する．つまり，遺伝距離が増加し続けることは，適応度景観に neutrality が含まれることを表す．
(2) 遺伝距離は neutrality が大きいほど増加する．
(3) 遺伝距離は ruggedness が大きいほど減少する．
(4) 遺伝距離は集団の個体数が多いほど減少する．
本追跡問題における遺伝距離の推移を図 8 に示す．
全試行とも，世代数に対し遺伝距離がほぼ線形に増加していることから，上で述べた根井の標準遺伝距離の特性 (1) より，本問題の適応度景観は neutrality，つまり，neutral networks を含むことがわかる．この結果は，進化ダイナミクスにおいて equilibrium periodが認められない問題でも，その適応度景観に neutralnetworks を含む可能性があることを示唆している．

4.

おわりに

本稿では，一定の突然変異率を採用する SGA と可変突然変異率戦略を採用する OGA を進化ロボティクスの一問題である自律エージェントによる追跡問題に適用し，そのパフォーマンスを検証した．得られた結果について次にまとめる．
• 本問題で観察された進化ダイナミクスは，equilibrium period が非常に短いものであった．
• 根井の標準遺伝距離の増加を調べることにより，本問題の適応度景観には neutralil networks が含まれることを確認した．
• 適応度景観の相関係数を調べた結果，本問題の適応度景観の ruggedness は比較的大きいことがわかった．
• OGA は局所解に陥いることなく，より良い解空間を探索し続けることができているが，SGA は局所解に陥ってしまう．
以上より，ruggedness が比較的大きい実問題でも，OGA は SGA に対し優位となることを確認し，テスト関数で得られた知見 [15] が有効であることを示した．
今後，これまで得られた知見を基に，実環境における進化ロボティクスの問題に挑戦したい [26] ．

参考文献[1] I. Harvey and A. Thompson: Through theLabyrinth Evolution Finds a Way: A SiliconRidge, Proc. of the ﬁrst International Conference on Evolvable Systems: From Biology toHardware, pp.406-422, (1996)[2] I. Harvey: Artiﬁcial Evolution for Real Problems, Evolutionary Robotics: From Intelligent
Robots to Artiﬁcial Life (ER’97), AAI Books,(1997)[3] T. Smith, P. Husbands and M. O’Shea: Neutral
Networks in an Evolutionary Robotics Search
Space, Proc. of the 2001 IEEE Congress on Evolutionary Computation: CEC2001, pp. 136-145,
IEEE Press, (2001)[4] A. Thompson: An Evolved Circuit, Intrinsic
in Silicon, Entwined with Physics, Proc. ofthe First International Conference on Evolvable
Systems: From Biology to Hardware, pp. 390405, (1996)[5] V. K. Vassilev, T. C. Fogarty and J. F.
Miller: Information Characteristics and theStructure of Landscapes, Evolutionary Computation, 8(1), pp. 31-60, (2000)[6] M. Ebner, P. Langguth, J. Albert, M. Shackleton and R. Shipman: On Neutral Networks andEvolvability, Proc. of the 2001 IEEE Congress
on Evolutionary Computation: CEC2001, pp. 18, IEEE Press, (2001)[7] T. Smith, P. Husbands, P. Layzell and M.
O’Shea: Fitness Landscapes and Evolvability, Evolutionary Computation, Vol. 10, No. 1,pp. 1-34, (2002)[8] F. Rothlauf and D. Goldberg: Redundant Representations in Evolutionary Computation, Evolutionary Computation, Vol. 11, No. 4, pp. 381415, (2003)[9] E. Nimwegen, J. Crutchﬁeld and M. Mitchell:
Statistical Dynamics of the Royal Road Genetic Algorithm, Theoretical Computer Science,Vol. 229, No. 1, pp. 41-102, (1999)[10] L. Barnett: Netcrawling - Optimal Evolutionary
Search with Neutral Networks, Proc. of the 2001
IEEE Congress on Evolutionary Computation:
CEC2001, pp. 30-37, IEEE Press, (2001)[11] M. Eigen, J. McCaskill and P. Schuster: The
Molecular Quasi-species, Advances in Chemical
Physics, 75, pp. 149-263, (1989)[12] L. Barnett: Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality, MSc. Dissertation, School of Cognitive andComputing Sciences, Sussex University, (1997)[13] M. Newman and R. Engelhardt: Eﬀect of Neutral Selection on the Evolution of MolecularSpecies, Proc. of the Royal Society of London B,
256, pp. 1333-1338, Morgan Kaufmann, (1998)[14] 大倉，上田: 中立突然変異型 GA による騙し問
題の最適化, 計測自動制御学会論文集, Vol. 32,
No. 10, pp. 1461-1469, (1996)[15] 片田，大倉，上田: Neutral Networks を含む適応度景観における遺伝的アルゴリズムの進化ダイ
ナミクス, システム制御情報学会論文誌, Vol. 17,
No. 5, pp. 187-195, (2004)[16] Y. Katada, K. Ohkura and K. Ueda: An Approach to Evolutionary Robotics Using the Genetic Algorithm with Variable Mutation Rate
Strategy, Proc. of Parallel Problem Solving fromNature (PPSN VIII), pp. 952-961, (2004)[17] 片田，大倉，上田: 可変突然変異率戦略を用いた
GA による進化ロボティクスへのアプローチ, 第48 回システム制御情報学会研究発表講演会講演
論文集, pp.587-588, (2004)[18] D. Sekimori, T. Usui, Y. Masutani andF. Miyazaki: High-speed obstacle avoidanceand self-localization for mobile robots basedon omni-directional imaging of ﬂoor region,
RoboCup 2001: Robot Soccer World Cup V,
Lecture Note in Artiﬁcial Intelligence 2377,pp.204-213, Springer, (2002)[19] 小森谷, 大山, 谷: 移動ロボットのためのランドマーク観測計画, 日本ロボット学会誌, Vol.11,No.4, pp.533-540, (1993)[20] D. Floreano and C. Mattiussi: Evolution ofSpiking Neural Controllers, Proc. of Evolutinary
Robotics -From Intelligent Robots to Artiﬁcal
Life (ER’01), pp.38-61, Springer-Verlag, (2001)[21] V. Braitenberg: Vehicles: Experiments in Synthetic Psychology, MIT Press, (1996)[22] M. Nei: Genetic distance between populations,The American Naturalist, Vol. 106,pp. 283-292, (1972)[23] 根井正利: 分子進化遺伝学, 培風館, (1990)[24] Y. Katada, K. Ohkura and K. Ueda: The Nei’s
Standard Genetic Distance in Artiﬁcial Evolution, Proc. of the 2004 IEEE Congress on Evolutionary Computation (CEC2004), pp.12331239, (2004)[25] T. Ohta: The nearly neutral theory of molecularevolution, Annual Reviews Ecology & Systematic, 23, pp. 263–286 (1992)[26] 高崎, 片田, 大倉, 田浦: 進化型自律移動ロボットのオンラインモデル更新に関する一手法, 第 47
回自動制御連合講演会, CD-ROM 予稿集, 404,
(2004)