Proceedings of the 53rd Annual Conference of the Institute of Systems, Control and Information Engineers (ISCIE), Kobe, May 20-22, 2009

W17-2
中立ネットワークに基づく進化ロボティクス適応度景観の構造解析

Analysis on Topologies of Evolutionary Robotics Fitness Landscapes
Based on Neutral Networks
摂南大学○ 片田 喜章

Y. Katada
Setsunan University
Abstract
The effects of neutrality and ruggedness on topologies of fitness landscapes have notbeen investigated enough since the introduction of the concept of neutrality into the EC community.
In a recent paper, we have shown that, in the test problems, landscapes with a higher degree ofneutrality have the larger sizes of neutral networks. Our results also suggested that for landscapeswith the smallest degree of ruggedness, all networks lead to the networks of the highest fitness, andfor landscapes with a higher degree of ruggedness, there are few contact points between the networkof higher fitness and other networks. In this work, we conduct a series of computer simulations
with an evolutionary robotics problem in order to investigate topologies of its fitness landscapes.

1

はじめにが多い．

中立性 (neutrality) は遺伝子型-表現型写像もしくは表現型-適応度写像に多くの冗長性を含むことで現れる．
実問題においても，進化ロボティクスにおけるニューラルコントローラや進化型ハードウェアなどで中立性が確認されている．中立性を含む適応度景観の概念は，Harvey[1] によって中立ネットワーク (neutral networks)

本稿では，進化ロボティクスの 1 問題である倒立振子制御問題において，先のテスト問題で得られた知見を検証することを目的とする．以下，第 2 節では，中立ネッ
トワークを定式化する．第 3 節では，中立ネットワークに基づいて，倒立振子制御問題の構造の解析を行う．

2

中立ネットワークとして EC 研究分野に初めて導入された．中立ネット
集団はクラスタを形成しネットワークに沿って移動する

Harvey が定義した中立ネットワークは一意に定まらないあいまいさを含んでいた．そこで，我々はネットワーこと，このしきい値以上ではランダム探索と同等になるクを集合として一意に定まるように定式化する．以下にこと，などが報告されている．しかしながら，適応度景それを示す．

ワークでは，あるしきい値以下の低い突然変異率で個体観に凸凹 (ruggedness) を同時に含む問題においては，従本稿で扱う遺伝子型は，固定長でバイナリコーディン

来議論されてきたように低い突然変異率では個体集団はグされていると仮定する．したがって，2 つの異なる遺局所解に陥ってしまうと予想される．このような中立性

伝子型 (xg , y g ∈ Φg ，Φg は遺伝子型集合) の遺伝距離はと凸凹を含む適応度景観の形状および問題の構造についハミング距離を用いて H(xg , y g ) と表される．ここで，て明らかにされてこなかった．

一般的に取り得る遺伝距離の最小値は 1 であることか

文献 [2] において我々は，Harvey が定義した中立ネッら，本研究では H(xg , y g ) = 1 を最小の変異とする．

トワークの概念を集合として定式化し，これに基づき本稿では，表現型-適応度写像が冗長である，つまり，中立性と凸凹を同時に含むテスト問題の解空間をクラ表現型-適応度写像 fp が全射であり単射でない場合にスタリングし，その問題の適応度景観の形状，つまり，ついて説明する．まず，つぎのような条件を満たす集中立ネットワークの構造および中立ネットワーク間の構造 (つながり) を調べた．ここでは次のことを確認している．(1) 中立性が大きくなると，ネットワークのサイズが大きくなる．(2) 凸凹が最も小さい問題では，どのネットワークを通っても最大適応度を示すネットワークに到達できる構造になっている．(3) 凸凹が最も大きい

gggg
合 {xgi }ni=0 ⊂ Φg を考える: (i) x = x0 , z = xn ,(ii) (fp ◦ fg )(xgi ) = (fp ◦ fg )(xg ), (iii) H(xgi , xgi+1 ) = 1.

ここで，fg は遺伝子型-表現型写像を表す．このような{xgi }ni=0 が存在するとき，xg と z g は連結されているといい，xg ∼ z g と表す．したがって，任意の遺伝子型 z gを含む中立ネットワークは Φ∗g (z g ) = {xg ∈ Φg |xg ∼ z g }問題では，高い適応度を示すネットワークは，より高いのように表される．以降，記法の簡素化のため，１つの適応度を示すネットワークへ移る接触点を持たないもの

中立ネットワークを Φi と表す．

第 53 回システム制御情報学会研究発表講演会－ 59 －

3

倒立振子制御問題の構造解析

3.1

実験設定

表 1: 中立ネットワークのサイズとその数

size

numbersize

number

倒立振子は水平方向に動く台車とその中央に回転自由1809

11で接続される一本の棒で構成される．台車は環境両端の22812

壁に接触することなく左右に移動することで振子の倒立313状態を維持しなければならない． 本研究では，台車が中4心より ±2.4[m] 以内に留まり，かつ，振子が垂直状態から ±36[◦ ] 以内に維持された状態を倒立状態とする．台size

number259111231132144141441481561541521401168162車は力 P を水平方向に加えて動かすものとする．台車

751726311の質量を 1.0[kg]，振子の質量を 0.1[kg]，長さ 1.0[m] と8218110361設定する．単位時間ステップを 0.01[s] とし，1 ステップ9325

1--毎に台車に作用させる力 P を決定する．本システムの10131

1--状態は，台車の位置 x，速度 ẋ，振子の垂直状態からの角度 θ および角速度 θ̇ で決定される．振子の初期角度を1[◦ ]，その他の初期値は 0 とする．1 個体の評価は倒立状態を維持したステップ数で与え，倒立状態を維持でき

表 2: 中立ネットワーク間の最小ハミング距離なくなるか，最大 3000 ステップに達したときに試行は終了とする．
倒立振子の制御器として，中間層・出力層が完全相互結合された ANN を用いる．結合荷重の符号 {+, −} のみを変数とし，その大きさは 1 とする．状態変数 x, ẋ, θ, θ̇

は [0.0, 1.0] の範囲に正規化され，ANN に入力される．

Φ902

Φ903

Φ904

Φ905

Φ906

Φ90164646Φ90206464Φ903-

0646Φ904--064Φ905---06

中間ニューロン数は 1，出力ニューロン数は 1 とする．
単位ステップ毎に台車に作用させる力 P を出力ニューロンの出力値より [−10.0, 10.0] [N] の範囲の実数として決定する．変数の数は L = 12 ビットとなる．遺伝子型空間の全探索を行い，2 節で述べた中立ネットワークに基づきクラスタリングを行う．

3.2

考えられるが，得られた結果は 4 もしくは 6 となっており，最大適応度を示す遺伝子型に到達することは難しいと考えらる．これらのことから，本問題の適応度上位の遺伝子型はネットワークを構成せず，また，他のネットワークからも孤立した状態であることがわかる．これはテスト問題で確認された中立性を含み凸凹が大きい場合実験結果と考察

表 1 に中立ネットワークのサイズとその数を示す．サイズが 1 のときは 2 節の定義よりネットワークではないが便宜上掲載している．|Φg | = 2L = 4096 であることの構造 [2] に類似している．

4

おわりにから，約 20%の遺伝子型がネットワークを構成せず孤立

本稿では，倒立振子制御問題において，その適応度景していることがわかる．サイズが 2 以上のネットワーク

観に中立ネットワークを含むことを確認した．また適応は数が少ないものの，大きいサイズも存在している．

度上位の遺伝子型はネットワークを構成せず，他のネッサイズが 1 のネットワークを含めるとその総数は 907となった．したがって，全てのネットワークに関する解析は紙面の制約上不可能であることから，適応度が上位6 位以内のネットワーク (Φi , i = 901, · · · , 906. 添字はネットワークの通し番号．ただし，|Φi | = 1 となり正確にはネットワークを構成していない) が構成する構造に注目する．表 2 にネットワーク間の最小ハミング距離を示す．ハミング距離が 1 の場合はネットワーク同士が「接触」しておりネットワーク間の移動が容易であるとトワークからも孤立していることがわかった．

参考文献[1] I. Harvey and A. Thompson: Through the labyrinth
evolution finds a way: A silicon ridge; Proceedings of theFirst International Conference on Evolvable Systems:
From Biology to Hardware, pp. 406–422 (1996)[2] 片田: 凸凹と中立性を含む適応度景観の中立ネットワークに基づく構造解析; 進化計算研究会 –進化計算シンポジウ
ム 2008–講演論文集, pp. 35–40 (2008)－ 60 －