中立性と凸凹を含む適応度景観の構造解析と進化ダイナミクス
Topology Analysis and Evolutionary Dynamics on Fitness
Landscapes with Neutrality and Ruggedness
摂南大学
Setsunan University

片田 喜章∗
Yoshiaki Katada

Abstract: The effects of neutrality and ruggedness on topologies of fitness landscapes have notbeen investigated enough in the EC community. In a recent paper, we investigated them in test
problems based on neutral networks. This work summarizes the obtained results in the above
paper and discusses the relationship between topologies of the fitness landscapes and evolutionarydynamics of GAs.

1

はじめに

中立性 (neutrality) は遺伝子型-表現型写像もしくは表現型-適応度写像に多くの冗長性を含むことで現れる．
実問題においては，進化ロボティクスにおけるニューラルコントローラ [1] や進化型ハードウェア [2] などで中立性が確認されている．これらの問題では一般に，上述の写像を一対一に設計することが困難で，冗長になるという共通の特徴がある．また，冗長性を排することが良いとされてきた遺伝子コーディングに意図的に冗長性を導入し，GA の解探索能力を高めようという研究も多くなされている [3]．
中立性を含む適応度景観の概念は，Harvey[4] によって中立ネットワーク (neutral networks) として進化論的計算分野に初めて導入された．その定義を以下に引用する．“A neutral network of a fitness landscapeis defined as a set of connected points of equivalent
fitness, each representing a separate genotype: hereconnected means that there exists a path of single(neutral) mutations which can traverse the network
between any two points on it without affecting fitness.”
中立ネットワークを含む問題で典型的に見られる進化ダイナミクスは平衡期と過渡期で構成される [5]．平衡期では，遺伝子型空間において個体集団は，“準種”とよばれるクラスタを形成し，中立ネットワークに沿って，より高い適応度を示す中立ネットワークへと導く
ポータルと呼ばれる地点 (遺伝子型) を見つけるまで移動し続ける．その後，個体集団はポータルから適応度の高い中立ネットワークへ移るべく，過渡期が始まる．
∗ 連絡先： 摂南大学工学部電気電子工学科〒 572-8508 大阪府寝屋川市池田中町 17-8
E-mail: katada@ele.setsunan.ac.jp

この過渡期は平衡期に比べてその長さが極端に短いものが典型である．
適応度景観には一般に中立性だけではなく凸凹 (ruggedness) も同時に含まれることが知られている．凸凹を含めば，従来議論されてきたように低い突然変異率では個体集団は局所解に陥ってしまうと予想される．中立性と凸凹の度合いを調節可能なテスト問題である Terraced
NK ランドスケープ (以下 TNK) に関する研究 [6] において，中立性を増加させると局所解の数は減少するものの，凸凹の度合いは変化しないということが報告されている．これらが示すことは，中立性を含む適応度景観であっても，凸凹を同時に考慮したアルゴリズムが必要があり，また，中立性と凸凹が作り出す景観の構造は未だ十分に議論されていないということである．
我々の研究グループでは，中立ネットワークの概念を集合として定式化し，これに基づき中立性と凸凹を同時に含む問題の解空間をクラスタリングし，その問題の適応度景観の形状，つまり，中立ネットワークの構造および中立ネットワーク間の構造 (つながり) を調べてきた [7, 8]．本稿では，それらをまとめ，別途研究を行っているこれらの問題における GA の進化ダイナ
ミクス [9, 10] の観点から考察する．

2中立性と凸凹を同時に含む適応度景観の構造解析

文献 [7, 8] で定義した中立ネットワークに基づき，TNK の解空間をクラスタリングし，その適応度景観の形状を調べる．ここで，遺伝子長 10，遺伝子間のエピスタシス数 K = {0, 9} とし，TNK で最大の中立性の度合いとなるように設定する．

表 1: ネットワークサイズとその個数 (K = 9)size number size number size number
1210711612398222131091721411111212
156141226
162151-

変突然変異率戦略を採用する GA が有効であることを確認している [9, 10]．これを上述の適応度景観の構造から考えると，凸凹が小さい場合にはネットワークのサイズは大きくなることから，可変突然変異率によりネットワーク上の集団の移動速度が増加すると考えられる．また，凸凹が大きい場合にはネットワークは孤立する傾向にあることから，可変突然変異率により，孤立したネットワーク間を大きく飛び越えるような突然変異が起こっていると考えられる．

3
表 2: 適応度上位 7 以内のネットワーク間の最小ハミング距離 (K = 9)Φ284 Φ285 Φ286 Φ287 Φ288 Φ289
Φ283
544564Φ28457693Φ2856564
Φ286
544Φ28733Φ2886

凸凹が最小となる K = 0 では，すべての遺伝子型はいずれかの中立ネットワークに属し，サイズが 16 のネットワークが 64 ある．凸凹が最大となる K = 9 では (表 1)，多くの遺伝子型が中立ネットワークを形成せず (サイズが 1 のもの)，全遺伝子型の 20%になる．またネットワークのサイズは不均一で，サイズの大きいものも含まれる．また，中立性の度合いが大きくなるとネットワークのサイズは大きくなることがわかっている [7]．
つぎに中立ネットワーク間の構造について述べる．ここで，ネットワーク間の最小ハミング距離が 1 の場合はネットワーク同士が「接触」しておりポータルをもつことから，ネットワーク間の集団の移動は容易であると考えられる．K = 0 では，適応度上位のネットワークと最大適応度を示すネットワークの間のハミング距離は 1 となり，上位同士のハミング距離も 2 となった．他のネットワーク間を調べると，全てのネットワークがより高い適応度を示すネットワークに対して必ずポータルをもつことがわかっている (詳細は [7] 参照)．
K = 9 では (表 2，添字はネットワークの通し番号でf (Φi ) ≤ f (Φi+1 ))，最小ハミング距離は 3 から 6 となっており，最大適応度を示すネットワークと他は接触していない．つまり，最大適応度を示すネットワークは他に対し孤立，もしくは，“だまし” のような状況になっている [7]．この状況では個体集団が最大適応度を示すネットワークに到達することは難しいと考えられる．
我々は，中立性と凸凹を同時に含む問題において，可おわりに

本稿では，中立性と凸凹を同時に含むテスト問題の適応度景観の構造を調べた．また，それに基づき，このような景観で有効性が確認されている可変突然変異率戦略を採用する GA の進化ダイナミクスに関して考察を行った．今後，進化過程で集団がどのネットワークに沿って移動しているかをモニタリングする方法を考えたい．

参考文献[1] T. Smith, P. Husbands and M. O’Shea: Neutral networks in an evolutionary robotics search space; Proceedings of the 2001 IEEE Congress on Evolutionary
Computation: CEC2001, pp. 136–145, IEEE Press(2001)[2] A. Thompson: An evolved circuit, intrinsic in silicon,
entwined with physics; Proceedings of the First International Conference on Evolvable Systems: FromBiology to Hardware, pp. 390–405 (1996)[3] F. Rothlauf and D. Goldberg: Redundant representations in evolutionary computation; EvolutionaryComputation, Vol. 11, No. 4, pp. 381–415 (2003)[4] I. Harvey and A. Thompson: Through the labyrinth
evolution finds a way: A silicon ridge; Proceedings ofthe First International Conference on Evolvable Systems: From Biology to Hardware, pp. 406–422 (1996)[5] E. Nimwegen, J. Crutchfield and M. Mitchell: Statistical dynamics of the royal road genetic algorithm; Theoretical Computer Science, Vol. 229, No. 1,pp. 41–102 (1999)[6] M. Newman and R. Engelhardt: Effect of neutral selection on the evolution of molecular species; Proceedings of the Royal Society of London B, 256, pp. 1333–1338, Morgan Kaufmann (1998)[7] 片田: 凸凹と中立性を含む適応度景観の中立ネットワー
クに基づく構造解析, 進化計算研究会 –進化計算シンポ
ジウム 2008–講演論文集, pp. 35–40 (2008)[8] 片田: 中立ネットワークに基づく進化ロボティクス適応度景観の構造解析, 第 53 回システム制御情報学会研究
発表講演会論文集, (2009), (掲載予定)[9] 片田，大倉，上田: Neutral Networks を含む適応度景観における遺伝的アルゴリズムの進化ダイナミクス, シス
テム制御情報学会論文誌, Vol. 17, No. 5, pp. 187–195(2004)[10] 片田，大倉: ニュートラルネットワークを含む適応度景観における遺伝的アルゴリズムの進化ダイナミクス –進化ロボティクスでの検証, システム制御情報学会論文誌,

Vol. 21，No. 2，pp. 31–39 (2008)