冗長な遺伝子型-表現型写像を用いた GA の進化挙動

Evolutionary Dynamics of GAs with Redundant
Genotype-Phenotype Mappings
摂南大学○ 片田 喜章，星尾 隆行

Y. Katada and T. Hoshio
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

これまで人工進化の研究分野においては，スキーマ定伝子長は Lg = 96 となる．

2.3

Standard Voting Mapping: SVM

理・積木仮説に基づき，問題ごとに探索空間を狭めるた表現型 1 ビットの値は関連する複数の遺伝子座の値かめに冗長性を排除したコンパクトな遺伝子型–表現型写ら TVM と同様に決定される．文献 [2] を参考に Lg = 64，像の設計に着目されてきた．一方，自然進化は今日採用

表現型 1 ビットに関連する遺伝子座数は 49 とする．

されている人工進化アルゴリズムとは多くの点で異なっ

2.4

Cellular Automaton Mapping: CAており，その 1 つに遺伝子型–表現型写像における冗長セルは現在の自身の状態と両隣のセルの状態によって性がある [1]．近年，人工進化分野でも自然進化に動機付

セルオートマトンのルールに従い変化を繰り返し (20けられ，遺伝子型–表現型写像に冗長性を意図的に導入回)，表現型となる．CA ではこのルールを遺伝子型に含することの有効性が盛んに議論されている [2][3][4]．こめる．セルの初期状態に対し文献 [2] を参考に次の方法

こでは，冗長性により適応度景観に生成されるニュート
ラルパス [5] に沿って集団が移動することにより，局所を用いる．i) 初期世代で任意に生成し，それ以降は固定(CA1)．ii) セルの初期状態も遺伝子型に含める (CA2)．

解に固着することなく探索を続けることが可能になると

Lg = 256(CA1)，Lg = 288(CA2) となる．

期待されている．しかしながら，いまだにどのクラスの2.5問題においてどのような種類の冗長性が有効であるかについて十分に議論されていない．そこで本稿では，適応RBN は CA と同様のルールを遺伝子型に含む．これに加えて，CA では固定であったセルの関連を遺伝

度景観の ruggedness を調節できるテスト問題において，子型に含む．セルの初期状態を，i) 初期世代で任意にこれまで人工進化分野で提案されている代表的な冗長遺生成 (RBN1)，ii) セルの初期状態も遺伝子型に含める

伝子型–表現型写像 [2] および我々の研究グループで提案してきた冗長な遺伝子型–表現型写像 [6] を採用した GA(RBN2)，とする．Lg = 736(RBN1)，Lg = 768(RBN2)となる．のパフォーマンスについて検証する．

2.62

遺伝子型–表現型写像

2.1

一対一写像

Random Boolean Network Mapping: RBN

Operon GA: OGA

OGA の遺伝子型は次のように定義される [6]．string =Simple GA(以下 SGA) で採用されている写像であり，{operoni | i = 1, . . . , m}, operoni = {genej | j ∈ Oi },genej = {x1 , x2 , . . . , x6 }. ここで，Oi は operoni が含遺伝子型と表現型は一対一に写像され冗長性を含まなむ遺伝子集合である．各遺伝子は長さ 6 のリストをもい．冗長な遺伝子型–表現型写像との比較として用いる．

つ．operon に対して結合・分割，gene に対して重複・遺伝子長は Lg = 32 とする．

欠失・逆位と呼ばれる遺伝的操作を用いる [6]．この遺2.2

伝子型に対する表現型は，すべての遺伝子の x1 からな

Trivial Voting Mapping: TVM

表現型 1 ビットの値は関連する遺伝子座 3 ビットの値で決定され，0 が多ければ 0，1 が多ければ 1 になる．遺る．Lg = 192 となる．

3計算機実験第 2 節で示した冗長な遺伝子型–表現型写像を用いる

0.70

GA のパフォーマンスを，適応度景観に ruggedenss を含むテスト問題において検証する．ruggedness を調節で0.65きるテスト関数として提案されている NK ランドスケー
プ [7] を用いる．ruggedness を調節するエピスタシス数

0.600を K = {0, 4, 16} と変化させる [4]．すべての GA において個体数を 50，表現型のストリング長を Lp = 32 と

sga-2
oga-6
tvm-6

し，遺伝的操作として点突然変異を用いる．点突然変異率を q = 1/Lg とする (ただし，OGA はその構造により0.80ントサイズを s = 2, 6 と変化させる．各試行の最終世代0.75

れぞれの結果の平均値を示す．
図 1 に各 GA において最終世代数で適応度が高かっ

svm-2
ca1-2
ca2-6

rbn1-2rbn2-2

0.70
0.65
0

た方の s の結果を示す (図の凡例中，-2,6 が s を表す)．

5001000 1500 2000 2500 3000
Generation

K = 0 の場合，TVM,OGA,SGA が良いパフォーマンス

sga-2
oga-6
tvm-2を示している (図 1(a))．この TVM の結果は One-Max問題で得られている結果 [3] と一致する．K = 4 の場合，

OGA,SGA が良いパフォーマンスを示し，次に TVM，1000 1500 2000 2500 3000
Generation(a) K = 0q = 1/Lp とする)．各 GA ともに，選択法としてトーナ
メント選択を用い，エリート戦略を適用する．トーナメ数を 3,000 とする. 各 K に関し独立に 50 試行行い，そ500

svm-2
ca1-2
ca2-2

rbn1-6rbn2-2(b) K = 40.75

CA1,2, SVM という順で良いパフォーマンスを示す (図1(b))．K = 16 の場合，OGA,SGA が良いパフォーマンスを示し，次に他の K でパフォーマンスが悪かった0.70

RBN が良いパフォーマンスを示すようになる (図 1(c))．
以上より，ruggedness が大きくなるほど OGA は有効であることを確認した．また，SGA は s = 2 のときに良いパフォーマンスを示した．そして，SGA，OGA，CA1
ではつねに同一の s の値が良いパフォーマンスを示したが，それ以外の GA では s による傾向は見られなかった．

4

おわりに

0.65
0500

sga-2
oga-6
tvm-2

1000 1500 2000 2500 3000
Generation
svm-2
ca1-2
ca2-6

rbn1-2rbn2-6(c) K = 16

図 1: 各 GA の世代数に対する最大適応度の推移

本稿では，NK ランドスケープにおいて，これまで提案されている冗長な遺伝子型– 表現型写像を用いた GAのパフォーマンスを検証した．今後，各 GA の挙動を実効突然変異率をもとに解析し，得られたパフォーマンスとの相関を調べる予定である．

参考文献[1] M. Kimura: The Neutral Theory of Molecular Evolution; Cambridge University Press (1983)[2] M. Shackleton, R. Shipman and M. Ebner: An Investigation of Redundant Genotype-Phenotype Mappings
and Their Role in Evolutionary Search; Proc. of the2000 IEEE Congress on Evolutionary Computation:
CEC2000, pp. 493–500, IEEE Press, (2000)[3] F. Rothlauf and D. Goldberg: Redundant Representations in Evolutionary Computation, EvolutionaryComputation, Vol. 11, No. 4, pp. 381–415, (2003)[4] J. D. Knowles and R. A. Watson: On the Utility ofRedundant Encodings in Mutation-based Evolutionary Search; Proc. of Parallel Problem Solving fromNature - PPSN VII, LNCS 2439, pp. 88–98, (2002)[5] I. Harvey and A. Thompson: Through the Labyrinth
Evolution Finds a Way: A Silicon Ridge, Proc. of theﬁrst International Conference on Evolvable Systems:
From Biology to Hardware, pp. 406–422, (1996)[6] 大倉，上田: 中立突然変異型 GA による騙し問題の最適化; 計測自動制御学会論文集, Vol. 32, No. 10, pp. 1461–1469, (1996)[7] S. Kauﬀman: The origins of order; Oxford University
Press, (1993)