人工生命による生態進化モデルとその応用に関する研究

(1)

人工生命による生態進化モデルとその応用に関する研究

著者武藤敦子

学位名博士(工学)

学位授与番号 13903乙第265号学位授与年月日 2010‑03‑16

URL http://id.nii.ac.jp/1476/00002916/

(2)

人工生命による生態進化モデルとその応用に関する研究

2 0 1 0

年

武藤敦子

(3)

(4)

i

図目次

1.1

人工生命研究．

. . . . 2

1.2

自然科学と人工生命の研究アプローチ．

. . . . 2

1.3

群れ行動シミュレーションの様子（赤：捕食者，黒：被捕食者）．

. . . 3

1.4 n-BDD(n=4)

の例．

. . . . 4

1.5

文化伝播シミュレーションの様子．

. . . . 5

1.6

獲得した歌オートマトンの例．

. . . . 5

1.7

種分化．

. . . . 7

1.8

世代交代モデルの概念図．

. . . . 9

2.1 BDD

のグラフ表現

(a)

とデータ構造

(b)． . . . . 17

2.2 h(= f ◦ g)

のアルゴリズム．

. . . . 18

2.3 n-BDD

の例（n

= 4）． . . . . 19

2.4 n-BDD

の遺伝的操作．

. . . . 20

2.5 APPLY

交叉の例．

. . . . 21

2.6

肉食エージェントの固定された戦略．

. . . . 22

2.7

適応度平均の推移．

. . . . 23

2.8

平均節点数の推移．

. . . . 23

2.9

草食エージェントの

BDD

の推移

(例)． . . . . 25

2.10

エージェントを扱う

1

ステップの流れ．

. . . . 27

2.11

シミュレーションの様子

(59

×

59)． . . . . 28

2.12

エージェント別個体数推移．

. . . . 29

2.13

エージェント別個体数推移（安定期間）．

. . . . 30

2.14 100

回のシミュレーション中の最長安定期間のステップ数分布．

. . . . 31

2.15

絶滅までのステップ数の分布．

. . . . 31

(9)

3.1

環境順応値と行動戦略によるエネルギー蓄積量の概念図．

. . . . 38

3.2 Flexible APPLY

交叉の例．

. . . . 40

3.3

目標とする

n-BDD (n=22)． . . . . 41

3.4

世代毎の平均適応度の推移．

. . . . 42

3.5

時間毎の平均適応度の推移．

. . . . 43

3.6

気温の知覚．

. . . . 44

3.7

実験のスナップショット

(左)

と発現した行動パターン

(右)． . . . . 46

3.8

安定期におけるエリア毎の個体数推移および気温変化．

. . . . 47

3.9

行動戦略

st

_stayを採るエージェントの

n-BDD

の一例．

. . . . 48

3.10

行動戦略

st

_migrateを採るエージェントの

n-BDD

の一例．

. . . . 49

3.11

安定期における行動戦略

st

_stay，stmigrateを採るエージェントの環境順応値

b

iの分布．

. . . . 49

3.12

安定期における行動戦略

st

stay，stmigrateを採るエージェントの環境順応値

b

_iの分布

(生殖隔離なし)． . . . . 50

4.1

提案エージェントモデル．

. . . . 56

4.2

エージェントの行動モデル．

. . . . 58

4.3

模倣対象となるオス

a

_kの選定

(a)

とオス

a

_jおよびメス

a

_iの模倣行動

(b)． 60 4.4

実験

(1)

における嗜好別メスエージェント平均生存割合．

. . . . 62

4.5

実験

(3)

. . . . 63

4.6

実験

(4)

. . . . 63

4.7

実験

(1)

における嗜好別メスエージェント生存割合*．

. . . . 64

4.8

実験

(1)

におけるメスエージェント嗜好遺伝子生存割合*．

. . . . 65

4.9

実験

(1)

におけるメスエージェント嗜好ミーム生存割合*．

. . . . 65

4.10

実験

(1)

における非同調エージェント生存割合*．

. . . . 66

4.11

実験

(1)

におけるメスの嗜好およびオスの形質の平均値．

. . . . 67

4.12

実験

(2)

におけるメスの嗜好およびオスの形質の平均値．

. . . . 67

5.1

エージェントの

1

ステップの行動モデル．

. . . . 73

5.2

嗜好別メスエージェント生存割合．

. . . . 77

5.3

同調化欲求遺伝子の平均値．

. . . . 78

5.4

「クレイズ」および「ブーム」発生回数の平均値．

. . . . 81

(10)

vii

6.1 SPX

を用いた多段交叉の例．

. . . . 88

6.2

世代交代の流れ．

. . . . 89

6.3 100

世代毎の平均成功回数および平均失敗回数（Schwefel 1.2 関数）．

. 90 6.4 100

世代毎の平均成功回数および平均失敗回数（Rastrigin関数）．

. . . 91

6.5

平均適応度の推移（Schwefel 1.2関数）．

. . . . 95

6.6 100

世代毎の段数選択回数の推移（Schwefel 1.2関数）．

. . . . 95

6.7

平均適応度の推移（Rosenbrock関数）．

. . . . 96

6.8 100

世代毎の段数選択回数の推移（Rosenbrock関数）．

. . . . 96

6.9

平均適応度の推移（Griewank関数）．

. . . . 97

6.10 100

世代毎の段数選択回数の推移（Griewank関数）．

. . . . 97

6.11

平均適応度の推移（Rastrigin関数）．

. . . . 98

6.12 100

世代毎の段数選択回数の推移（Rastrigin関数）．

. . . . 98

6.13

平均適応度の推移．

. . . . 100

6.14 10

世代毎の段数選択回数の推移．

. . . . 100

C.1

ロトカボルテラ系の個体数変動の例．

. . . . 110

D.1 Schwefel 1.2

関数．

. . . . 112

D.2 Rosenbrock

関数．

. . . . 113

D.3 Griewank

関数．

. . . . 114

D.4 Schwefel

関数．

. . . . 114

D.5 Rastrigin

関数．

. . . . 115

(11)

(12)

ix

表目次

1.1

代表的な世代交代モデルの構成．

. . . . 10

1.2

代表的な世代交代モデルの特徴．

. . . . 10

1.3

交叉オペレータの比較．

. . . . 11

2.1

入力ビット列の割り当てと意味．

. . . . 26

2.2

エージェントが選択できる行動．

. . . . 28

2.3

肉食動物又は草食動物絶滅までの平均ステップ数．

. . . . 29

3.1

エージェントaiの知覚情報．

. . . . 45

3.2

エージェントaiの行動．

. . . . 45

4.1

実験の組合せと結果．

. . . . 61

4.2

多数派に安定した嗜好の内訳．

. . . . 68

5.1

「クレイズ」および「ブーム」回数の

20

試行の平均値と標準偏差．

. . 80

6.1

実験パラメータ．

. . . . 94

6.2

最適解獲得平均計算時間

(単位:sec)． . . . . 94

6.3

実験パラメータ．

. . . . 99

6.4

最適解獲得平均計算時間

(単位:sec)． . . . . 101

B.1

制御パラメータの探索範囲と間隔．

. . . . 108

D.1

テスト関数の特徴．

. . . . 115

(13)

(14)

1

第 1 _章序論

1.1

研究の背景

生命に関わる諸現象を工学的手法で再現し解明しようとする生物学的研究，あるいは生命的な振る舞いにヒントを得た工学的研究が様々な分野で展開されている．このような研究アプローチは人工生命を用いて行なわれる．

人工生命研究は，一見して生命のように見えるものを工学的手法を用いて創造する試みであり，1987 年に第

1

回人工生命国際会議において

Christopher Langton

が提唱した概念である

[1][2][3][4]．人工生命は，もともと生物の進化のメカニズムのモデルと

して，集団遺伝学や進化生物学など，生物・進化に関連する学問分野

(これらを総称し

て，以下，生物学分野) での利用を目的としていた．一方で，Holland[5]によって遺伝的アルゴリズムの手法が定式化されてからは，工学的応用を目的とした組合せ最適化問題や各種の最大値探索問題などへの人工生命手法の適用が盛んになっている．それらの手法は総称して進化的計算と呼ばれ，代表的な手法として，遺伝的アルゴリズム

[5]，進化戦略 [6]，進化的プログラミング [7]，遺伝的プログラミング [8]

があり，最適

化，学習，解析などの応用をされている．

以上をまとめると，人工生命研究は，図

1.1

に示すように生物システムを模倣する進化シミュレータとしての生物学的応用と，進化的計算を用いた最大値探索問題に代表される生物モデルの工学的応用に大別することができる

[9]．

人工生命の生物学的応用研究の位置付けは難しく，確立された研究方法というものが存在しない．従来の典型的な自然科学では，具体的な現象やデータを観察し，そこから一般性を持つ仮説，法則，理論を推論する方法や，反対に，仮説，法則，理論を立て，

実験や観察を行なうことにより妥当性を裏付けていく方法が用いられる（図

1.2(a)）．

(15)

↢‛ቇ

↢‛ࡕ࠺࡞ߩᎿቇ⊛

ታࠪࠬ࠹ࡓ߳ߩᔕ↪

↢‛ࠪࠬ࠹ࡓߩᮨ୮ߣ ߘߩࡔࠞ࠾࠭ࡓߩ⸃᣿

↢‛␠ળ

ੱᎿ↢๮

Ꮏቇ

図

1.1:

人工生命研究．

一方で，典型的な人工生命モデルは，具体的な現象やデータとのつながりは必ずしも強く維持せずに，何らかの仮説や法則を制約として概念レベルにおいて人工生命モデルを構成する

[10]．そして，計算機の中で時間発展させ，興味深い創発現象を起こし

得た時に，その挙動を従来の仮説や法則の中に位置付けながら解釈する．その解釈の中で，あるいは元の人工生命モデルのレベルで，実際の現象やデータとの比較が可能な場合もある．

本研究では，人工生命の生物学的応用を図

1.2(b)

に示すような研究アプローチで行う．特に本論文で行う部分は，人工生命モデルを計算機上で構成するための人工生命手法の提案と，実際にそれらの手法を用いた人工生命モデルの構成である．人工生命モデルは仮説・法則や具体的な現象・データ等を参照して作成し，計算機上での進化

C⥄ὼ⑼ቇ

઒⺑ᴺೣ

⃻⽎

࠺࡯࠲

ᬌ⸽ ផ⺰

઒⺑ᴺೣ ⃻⽎

࠺࡯࠲

ޓޓޓ᭴ᚑ 㧔ੱᎿ↢๮ᚻᴺ㧕

ੱᎿ↢๮ࡕ࠺࡞

⸃㉼

ᬌ⸽

DੱᎿ↢๮

図

1.2:

自然科学と人工生命の研究アプローチ．

(16)

1.1.

研究の背景

3

により創発した人工生命体の挙動を元の仮説・法則や現象・データと比較しながら解釈または検証する．

1.1.1

人工生命の先天的情報

地球上に存在する生命体が先天的に保持する情報として遺伝情報がある．人工生命体の遺伝子表現としては，ビット列によるもの

[11][12][13][14][15]，オートマトンを用

いたもの

[16][17]，木構造で表現するもの [18][19][20][21][22][23]

など様々な表現方法が存在する．

例えば，人工生命体の遺伝子を群れ行動決定のためのパラメータとしてビット列で表現した研究がある

[24][25][26][27][28]．これは，ある限られた範囲のフィールド上に

おいて群れ行動をするエージェント集団を存在させたシミュレーションモデルである

（図

1.3）．群れエージェント集団は遺伝子として群れ行動決定のためのパラメータを持

ち，適応度評価値を群れエージェントが全滅するまでの期間とすることで，群れエージェント集団が捕食エージェントから逃れて長く生存し続けるためのパラメータを自然淘汰により獲得する．

図

1.3:

群れ行動シミュレーションの様子（赤：捕食者，黒：被捕食者）．

また，人工生命体が先天的に持つ行動戦略を遺伝的プログラミングを応用した多出力二分決定グラフ

(n-output Binary Decision Diagram ;n-BDD)

で遺伝子表現した研

(17)

究がある

[18][19][20][21][22][23]．1978

年に

Akers[29]

によって考案された

BDD

は論理関数の表現方法の一つであり，その記憶効率や処理速度に優れることから

LSI

や

CAD

の分野を中心に，様々な分野に応用されている．BDDの出力値を

0

か

1

の

2

通りから

n

通りに拡張したものが

n-BDD

（図

1.4）である [20]．n-BDD

の変数を用いてエージェントの知覚情報を表現し，n-BDDの出力，即ち定数節点をエージェントの

n

種類の行動に対応させることで，自律エージェントの行動戦略を表現できる．これを遺伝的プログラミング技法によって進化させることでエージェントの行動戦略の最適化を行うことができる．詳細については本研究の第

2

章において述べる．

X3

0 X11

X2

A B C D

0

1

terminal node decision node

図

1.4: n-BDD(n=4)

の例．

1.1.2

人工生命の後天的情報

地球上には，先天的情報である遺伝子に加え生まれた後に学習や模倣により獲得する後天的情報を持つ生命体が存在する

[30]．近年，後天的に獲得した情報を文化

伝達子（ミーム）として表現する研究が盛んに行なわれている

[31][32]．ミームとは，

R.Dawkins[33]

により提唱された，模倣・教示・学習等によって後天的に獲得する文化

伝達子の概念である．人工生命体のミーム表現としては，1.1.1節において述べた遺伝子表現と同じように様々な表現方法が考えられる．

例えば，文化嗜好を経験によって後天的に獲得するミームとして定義することで，文化嗜好を人工生命体に蓄積し伝播させるモデルがある

[34][35][36]．図 1.5

は，文化伝播シミュレーションのスナップショットであり，赤で示す

A

というオブジェクトを嗜

(18)

1.1.

研究の背景

5

好するエージェントと青で示す

B

というオブジェクトを嗜好するエージェントが地域毎に密集して存在し文化を伝播している様子が分かる．

objectA objectB

agent(preferA) agent(preferB)

図

1.5:

文化伝播シミュレーションの様子．

また，性淘汰の環境下における鳥の求愛の歌表現を後天的情報としてオートマトンを用いて表現した研究がある

[30]．図 1.6

は，後天的に獲得した歌オートマトンの一例であり，後天的情報である歌表現が学習により複雑に変化していることが分かる．

0

c b e d

1

a e

d a

2

b

3

c

c b a e

4

d c a d e

b b

e a c

d

5

a d e

図

1.6:

獲得した歌オートマトンの例．

(19)

1.1.3

人工生命の生物学的応用

人工生命の生物学的応用として，本研究では未だ明らかとなっていない生命体の諸現象について新たな進化モデルを提案し，実際に計算機上で構成した人工生命体の挙動を確認することでそのメカニズムを探る．人工生命の構成には，先に述べた先天的情報である遺伝子および後天的情報であるミーム等の人工生命表現を，構成するモデルによって組み合わせて用い，さらに必要に応じて人工生命手法（進化演算子）を定義する．

本研究では，生命体の生態進化に関わる現象として主に二つを取り上げる．一つは生物多様性を引き起こす要因となっている「種分化」，一つは異性をめぐる競争を通じて起きる進化である「性選択（性淘汰）」である．どちらも，進化生物学における重要な理論であり多くの生物学者が興味を抱いている研究分野である．

種分化

自然界に存在する生命体は進化の過程で様々な生態を発現し，その種類も多様化している．種の多様性を引き起こす生態の分化がどのようなメカニズムで生じるのかを解明することは重要である

[37]．種分化とは新しい生物学的種が誕生する進化プロセ

スの一つであり，種分化しつつある集団がどの程度母集団から地理的に隔離されているかで，以下のように

3

分類できる．図

1.7

にそれぞれの特徴を示す．

( 1 )

異所的種分化

( 2 )

側所的種分化

( 3 )

同所的種分化

一般的に種分化の多くが地理的隔離のある「異所的種分化」であると考えられている

が

[38]，部分的に地理的隔離のない「側所的種分化」の確認例もいくつか存在する．近

年では地理的隔離の全くない「同所的種分化」を示す事例研究が報告され注目を集め

ている

[39][40]．人工生命分野において同所的種分化を扱ったものには，性淘汰のみで

起こりうることを示したもの

[41][42]

や，相互作用による表現型の分化が遺伝型の進化を促す様子を表現した研究

[43]

などが報告されているがその数は事例研究と同様に少ないため，さらなる研究報告が求められている．

(20)

1.1.

研究の背景

7

図

1.7:

種分化．

性選択（性淘汰）

生態には，クジャクのオスの羽のように生物が生存する上で過度に派手で不利であると考えられる現象が見られる．

Darwin

はこのような現象を性選択（性淘汰）と定義することで説明した

[44][45]．性選択には，異性による選り好み（配偶者選択）が存在

する．配偶者選択にどのようなメカニズムが働いているかを示す理論モデルは大きく二種類に分けられる．一つはランナウェイ説のように，メスの選好の基準が生存上の有利さとは無関係な場合，もう一つはハンディキャップ説のように生存上の有利さに繋がる形質を選好の基準にしている場合である．ある形質や信号がランナウェイによって発達したのか，ハンディキャップによるものなのかは判断が難しい場合が多く，個々の事例に関してさらなる研究報告が求められている

[46]．

人工生命分野において性選択を扱ったものには，オスを形質遺伝子，メスを嗜好遺伝子で構成し計算機上で進化実験を行った研究

[47]

がある．また，性選択の過程にはアズマヤドリのアズマヤのようにオスがメスを引きつけるために後天的に装飾するという現象がみられる

[48]．このような生物は，配偶者選択において先天的な身体的特

徴に加え後天的な嗜好対象オブジェクト（ミーム）

[49][50][51][52]

を参照していると考えられる．

(21)

1.1.4

人工生命の工学的応用

人工生命の工学的応用として進化的計算の中で最も代表的な手法に遺伝的アルゴリズムがある．遺伝的アルゴリズムの工学的応用としては，超

LSI

のパターン配置，スケジューリング，ニューラルネットワークの構成，広域ネットワークのルーティング，

画像やデザインなど広範な問題がある．必ずしも常に最良の解が得られるとは限らないが，コンピュータのパワーがあれば，他の方法より効率良くかなり良好な解を得ることができる

[3]．遺伝的アルゴリズムを適用するとよいと考えられる代表的な工学的

問題として，巡回セールスマン問題やナップザック問題などに代表される組合せ最適化問題がある．巡回セールスマン問題とは，与えられた複数の都市の全てを，各都市をそれぞれ

1

回だけ訪問するという条件のもとで巡回する際の経路長を最小にする問題であり，ナップザック問題とは，大きさが異なる複数の荷物を容量の決まった袋にちょうどよく詰め込む問題である

[53]．

しかし，これらの問題は計算理論の検証のための問題という意味合いが濃く，実際の工学的問題を考えた時，実問題の多くはシミュレータを用いた評価を伴うため計算負荷が高く，試行錯誤的な探索手法である遺伝的アルゴリズムを用いることでさらに計算時間がかかるという問題点がある．

遺伝的アルゴリズムの計算負荷を解消することを目的とし，探索履歴を用いた交叉を分散遺伝的アルゴリズムに適用する研究がある

[54][55][56]．ここでは，生成された

個体のシミュレーションを伴う評価に探索履歴との類似度を用いた適応度予測を用いることで評価計算コストを削減し，対象問題による交叉回数の制限のない複数回交叉手法を実現した．しかしながら，実問題を遺伝的アルゴリズムに適用する際には遺伝子表現に実数値を用いる方が効率的であり，実数値遺伝的アルゴリズムが近年では主流となっている．よって，本研究では，実数値遺伝的アルゴリズムにおける探索の効率化を目的とした新たな探索手法を考える

[57]．

世代交代モデルの設計

進化的計算において，よりよい個体を次世代に生み出すための多くの拡張手法が提案されている

[58][59][60][61][62][63][64][65]．よりよい個体を次世代に生み出すために

は，適切な世代交代モデルおよび交叉の設計が不可欠である．

遺伝的アルゴリズムにおける世代交代モデルの代表例として，Simple Genetic Al-

(22)

1.1.

研究の背景

9 gorithm(SGA)

がある．今までに，多様性の観点から

SGA

に対して改善を行った

Iter-

ated Genetic Search(IGS), Steady State(SS), CHC, Elite Recombination(ER), Minimal Generation Gap(MGG)

などが提案されている

[66]．これらのモデルには，

「世代交代の連続化」を目的として子を生成した親個体にも生存の機会を与える戦略が採用され

ている．

IGS，SS

では親は無条件で残るのに対し，CHC，ER，MGGでは，子との競

争に勝った親のみが生存を許される戦略である．世代交代の一般的な枠組みとして，

図

1.8

に示すような

2

種類の選択，すなわち複製選択（Reproduction selection）と生存選択（Survival selection）があり，CHC，ER，MGGのいずれも複製選択はランダムに非復元抽出であるが，生存選択がそれぞれ異なる．CHCの生存選択は，親子

2

世代の中から適応度（ﬁtness）の高い順に集団サイズ分の個体を次世代に残すという方法，ERは各家族（親

2

個体，子

2

個体）の中から最良

2

個体を次世代に残すという方法，MGGは

ER

を発展させたもので，各家族の中から最良

1

個体とルーレット選択により選ばれた

1

個体を次世代に残すという方法である．それぞれの方法は問題により向き不向きがあるとされている．それぞれの世代交代モデルの構成を表

1.1

に，特徴を表

1.2

に示す．

Childbirth Present

generation

Reproduction selection

Next generation Survival

selection Fitness

evaluation

Alternation-generation model

図

1.8:

世代交代モデルの概念図．

これらの世代交代モデルでは，SGAがその構造がシンプルであることを理由に多用されていたが，近年では多峰性の形状を持つ問題に対して性能の良い

MGG

が一般的に多く用いられている．本研究では，第

6

章において以下に示す

MGG

を多親用に拡張したモデル

[67]

を用いることとした．

「MGGを多親用に拡張したモデル」

( 1 )

個体集団から一定数の親個体をランダムに選ぶ．

( 2 )

交叉によって一定数の子個体を生成する．

(23)

表

1.1:

代表的な世代交代モデルの構成．

モデル複製時の選択生存時の選択

SGA

ルーレットにより復元抽出無条件で親集団と子集団を入れ換え

SS

ランキングにより復元抽出親集団の最悪個体と子個体を入れ換え

CHC

ランダムに非復元抽出

2

世代より最良個体から順に集団サイズ

分を残す

IGS

ランダムに非復元抽出親集団の適応度の低い個体と子個体を入れ換え

ER

ランダムに非復元抽出各家族から最良

2

個体ずつを残す

MGG

ランダムに非復元抽出家族から最良

1

個体とルーレットによ

り

1

個体を残す

表

1.2:

代表的な世代交代モデルの特徴．

モデル適応度の使い方世代交代の連続化

世代交代の限定化

生存選択の局所化

SGA

基数的離散的全体的なし

SS

序数的連続的部分的なし

CHC

序数的連続的全体的なし

IGS

序数的連続的部分的なし

ER

序数的連続的全体的あり

MGG

主に序数的連続的部分的あり

( 3 ) (1)

の親個体からランダムに

2

個体を非復元抽出する．

( 4 ) (3)

の

2

個体と

(2)

の子個体の中から最良個体および適応度のランキングによる

ルーレット選択で選んだ

1

個体を選び，個体集団に戻す．

交叉オペレータの設計

喜多らは遺伝的アルゴリズムを構成する選択・世代交代モデル，交叉などの遺伝演算子の設計に関して，「機能分担仮説」[68]「統計量の遺伝」[69]と呼ばれる考え方を提案している．これは，遺伝演算子それぞれの担うべき機能を明確にし，その機能を考慮した設計指針に基づいて遺伝演算子を設計するべきであるという考え方である．喜多らが提案する設計指針をよく満たしている実数値遺伝的アルゴリズムの交叉手法の代表

(24)

1.1.

研究の背景

11

的なものに，Unimodal Normal Distribution Crossover(UNDX)[70][71], UNDX-m[68],

Simplex Crossover(SPX)[72]

がある．

表

1.3:

交叉オペレータの比較．

形質遺伝変数間依存

座標軸方向へ依存

スケールへの依存

統計量遺伝

子個体分布

バイナリ × × ？？ × ？

UNDX

○ ○ ○ × ○ 正規分布

UNDX-m

○ ○ ○ △ ○ 正規分布

SPX

○ ○ ○ ○ ○ 一様

これらの実数値遺伝的アルゴリズムにおける代表的な

3

種類の交叉演算子およびバイナリー遺伝的アルゴリズムの交叉演算子を比較をしたものが表

1.3

である

[72]．機能

分担仮説および統計量の遺伝は，遺伝的アルゴリズムの設計の自由度をコントロールするための一つの仮説に過ぎないが，本研究ではこれらを有効な設計指針であると考え，ここで述べた必要条件を全て満たす

SPX

を第

6

章での実数値遺伝的アルゴリズムにおいて用いることとした．なお，SPXの詳細は付録

A

に示す．

また，本研究ではいくつか存在する遺伝的アルゴリズムの工学的応用例

[68][73]

の中でも特に，シミュレーションを伴うために評価値計算に時間のかかる実問題に焦点を当てる．具体的には，次に示すメカトロニクスおよびパワーエレクトロニクスの分野における実問題を取り上げる．

工学的応用問題

メカトロニクスやパワーエレクトロニクスの分野では，各種設計パラメータの試行錯誤的で煩雑な決定作業を軽減するために，遺伝的アルゴリズムの最適化能力に着目した自律パラメータ設計に関する研究が報告されている

[74][75][76]．その中で，構造

設計段階で形状寸法が定められた

Switched Reluctance Motor（SRM）に対し，その

最大出力性能と対応する最適制御パラメータを遺伝的アルゴリズムを用いて探索する研究が行なわれている

[77][78]．探索に遺伝的アルゴリズムを適用することで他手法と

比較して大幅な計算時間削減を実現しているが，出力性能評価のための反復計算を伴う特性計算によって

1

回の適応度計算に時間がかかるため，依然として計算時間削減の余地が残っている．遺伝子表現，適応度関数等，詳細については付録

B

にて述べる．

(25)

以上に述べた世代交代モデルおよび交叉オペレータの設計指針に基づき，本研究では，実数値遺伝的アルゴリズムの効率化のための新たな進化オペレータを提案し，

SRM

制御パラメータ最適化問題に適用し評価する．

1.2

研究の目的

今日，人工生命研究の目的は二つに大別することができる

[9][79]．一つは，生物を

分析，模倣することによって，生命の本質を理解する，あるいは生物システムの挙動や進化のメカニズムを解明することである．もう一つは，生物システムをモデル化し，

そのモデルに基づいた工学的な実際のシステムを構築することである

[9][80]．本論文

の第

2

章から第

5

章までの人工生命は前者を目的とし，本論文の第

6

章は後者を目的としている．

人工生命の生物学的応用として，本研究では実在する各種生命体の生態現象，具体的には，食物連鎖，種分化，性選択についてモデル化を行い，計算機上で人工生命体が実在する生命体の諸現象を進化により創発する様子を確認する．そうすることで，生命の誕生，生態分化，生態進化システムなどのメカニズムを明らかにすることが最大の目的である．ここで，1.1節において述べたように実在する生命体の挙動を正確に再現することが人工生命の目的ではないことに注意したい．さらに，各種人工生命体の構成のための計算手法を提案することで人工生命研究・生物学研究への工学的一助となることを目指す．

人工生命の工学的応用として代表的なものが進化的計算である．進化的計算は，その膨大な計算負荷などの問題のために実用化は難しいとされていた．しかし，近年の計算機の処理能力の向上やコストの軽減などの理由で計算量の問題は解消されつつあるため，アルゴリズム上の探索効率を上げることで工学的応用に耐えうる進化的計算手法の提案を目指す．

第

2

章では，より現実に近い安定した人工生命モデルの生成が目的である．不安定な環境の中で自己適応していくシステムの研究として，微妙なバランスの上に成り立っている生態系の計算機シミュレーションがある．生態系のシミュレーションではより現実に近くかつ単純でシミュレートが容易なモデルを構築し，生物の諸現象を計算機上で調べることが課題となる．ここでは，生命体が世代交代をしていく上で欠かすことの出来ない生殖活動に着目し，交配を導入することでより現実に近いモデルを生成

(26)

1.3.

研究の内容

13

する．これにより長く安定したシミュレーションを確保することが目的である．

第

3

章では，種の多様性を引き起こす生態の分化がどのようなメカニズムで生じるのかを解明することが目的である．自然界に存在する生命体は進化の過程で様々な生態を発現し，その種類も多様化している．ここでは，同所的種分化がどのようなプロセスで発生したかを明らかにする．

第

4

章，第

5

章では，性選択が存在する環境下での遺伝子とミームが及ぼす相互作用について解明することが目的である．それぞれの章において，人工生命体に同調性・

非同調性の特徴を付け，その特徴によって異なる行動を行なうことで，配偶者選択における嗜好の遷移に与える影響を明らかにする．

第

6

章では，進化的計算手法の工学的応用，特に計算負荷の高いシミュレーションを伴う実問題への適用が目的である．遺伝的アルゴリズムを用いた探索において，探索局面は常に動的に変化をする．よって，探索過程を常に評価してそれにあった戦略を用いて探索をすすめることは重要だと考える．ここでは，探索過程を考慮に入れた実数値遺伝的アルゴリズムを提案しアルゴリズム上の探索効率を上げることで工学的応用に耐えうる計算手法の実現を目指す．

1.3

研究の内容

本研究は，全体の構成として大きく

2

つに分けられる．第

2

章から第

5

章は，人工生命の生物学的応用についての研究である．特に，第

2

章および第

3

章の前半では，人工生命を計算機上に実装するために必要となる計算手法を提案し，それらの章の後半および第

4

章，第

5

章において，人工生命を用いた各種生態進化モデルを計算機上で構成した結果について考察を行う．第

6

章は，人工生命の工学的応用についての研究である．ここでは，実数値遺伝的アルゴリズムの効率化を行う交叉手法を提案し，計算機上に実装した結果について述べる．

始めに，第

2

章では，人工生命を表現するための手段として多出力二分決定グラフ

(n-output Binary Decision Diagram;n-BDD)

の交叉手法を提案する．被食，捕食関係のある多種類の人工生命体を

n-BDD

を用いて計算機上に存在させ，不安定な環境の中で自然淘汰による進化を繰り返し自己適応させる人工生命モデルを提案する．ここでは，エージェントが環境の中で他のエージェントと相互に干渉しながら生態系全体で安定した食物連鎖関係を創発することを示す．

(27)

第

3

章では，変数順序の違う

n-BDD

同士の交叉を可能とした交叉手法を提案する．

この交叉手法を用いて，身体的特徴差を持つ各々の人工生命体が，環境変化に順応して異なる生命体に分化していく様子を計算機上で表現する．本システムにより，似た遺伝子を持った人工生命体がわずかな身体的特徴差（環境順応値）により，異なった方向へ互いに進化（分化）していくことを明らかにする．

第

4

章では，実在する一部の動物に見られる配偶者選択におけるメスの嗜好の流行現象がメスの嗜好ミームおよび同調性・非同調性に関与していると考え，遺伝子とミームをあわせもつ人工生命体の進化モデルに同調遺伝子を加えたモデルを提案する．同調遺伝子により模倣行動または独創行動を行い，世代交代により進化することで，配偶者選択における嗜好の循環型流行の発現を確認する．

第

5

章では，第

4

章の同調遺伝子に代わり同調・差別化欲求の強さを表す遺伝子を新たに定義し，さらに同調化行動および差別化行動を行うエージェントモデルを提案し，計算機シミュレーションを行う．実験において，オスを好むメスの嗜好に

2

種類の循環型流行の発現を確認する．また，同調・差別化欲求の存在がこれらの流行現象に与える影響について考察する．

第

6

章では，実数値遺伝的アルゴリズムにおいて，限られた生成子個体数での効率的な探索を行うモデルを目指し動的多段交叉を提案する．動的多段交叉は，評価値の良い個体を用いて交叉を段階的に行うことで進化を促し，その段数を探索過程に応じて動的に変化させる交叉法である．動的多段交叉を代表的な世代交代モデルに適用することで，最良個体の進化を促しつつ集団の多様性を維持できるモデルを実現したことを示す．

最後に，第

7

章において，本論文を総括し，今後の研究の展望について述べる．

(28)

15

第 2 _章

多出力二分決定グラフの APPLY _交叉を用いた食物連鎖モデル

本章では，多出力二分決定グラフ

(n-output Binary Decision Diagram ;n-BDD)

を用いた生態系モデルにおいて利用可能な交配方法を提案する．

n-BDD

は，人工生命の行動戦略の表現に適しているが，遺伝子操作に交叉の機能が存在しない．そこで，

n-BDD

の交叉方法として

BDD

の二項論理演算を拡張した

APPLY

交叉を定義し用いる．

APPLY

交叉は両親の行動戦略を確率的に均等に継承できることに特徴があり，エージェントの交配に用いることに適していると考えられる．簡単な競合問題を用いて

APPLY

交叉の有効性を確認し，さらに，被食，捕食関係のある多種類の人工生命体を存在させ交配による世代交代を繰り返すことで，他の個体と相互に干渉しながら生態系全体で安定した食物連鎖関係が創発した．

2.1

はじめに

生命的な振る舞いにヒントを得た手法の研究あるいは生命に関わる諸現象を工学的手法で再現し解明しようとする研究が様々な分野で展開されている．不安定な環境の中で自己適応していくシステムの研究として，微妙なバランスの上に成り立っている生態系のシミュレーションはその中の一つである．

Holland

によって最初に考案された生態系モデル

Echo

は，全ての生態系に共通の一

般的な性質の獲得のために，生態系を可能な限り単純化している

[5][81][82]．高階ら

は，個々の生命体を独立のプログラムで記述した生態系のシミュレーションを行った

[83][84]．我々は，自然界に存在する生命体を 3

種類に単純化した生態系において，被

食者，捕食者の行動戦略を

n-BDD

を用いて表現し，シミュレートする研究を行ってき

(29)

た

[19][20]．n-BDD

は文献

[19][20]

が示すように入力情報に対して行動を一つに決定する問題に適しており，生態系シミュレーションの実現のために有用である．

生態系の計算機シミュレーションではより現実に近くかつ単純でシミュレートが容易なモデルを構築し，生物の諸現象を計算機上で調べることが課題となる．本章は，

生命体が世代交代をしていく上で欠かすことの出来ない生殖活動に着目し，交配を導入することでより現実に近いモデルを生成する．これにより長く安定したシミュレーションを確保することが目的である．

有性生殖における交配には，交配相手の選択とその交配方法の

2

点が重要となり，これらに関しては今までに以下に示すような様々なモデルが提案されている．交配相手の選択に関しては，よく似た個体のみを交配相手とするモデル

[85]

や，逆に似た個体同士の交配

(近親婚)

を禁じたモデル

[86]

や，交配タグの一致した個体だけが相手となるモデル

[5]

などがある．また，Hillisは初期集団を

2

次元格子状に配置させ，空間において近傍の個体同士だけが交配を行うモデルを発案した

[87]．生態系モデル Echo

における交配は，各エージェントが持っている染色体を

2

点交叉で組み合わせて

2

匹の子を形成しており，Hillisは二倍体染色体を用いたより実世界に近い交配方法を提案している．

本研究では，この中から

n-BDD

を用いた生態系モデル

[19]

において利用可能な交配方法を利用し拡張する．交配相手の選択には，[5][85]のモデルで提案された異種間の交配を禁止する手法を採用し，また

[87]

において提案された空間的に制限された相手との交配をさらに拡張し，その中から評価値の高いエージェントと交配することとした．交配方法は

BDD

の二項論理演算

[88]

を拡張した

APPLY

交叉を定義し用いる．

APPLY

交叉は

n-BDD

のグラフ構造を利用しながら両親の行動戦略を確率的に均等に

継承できることに特徴があり，n-BDDを用いた本モデルにおけるエージェントの交配に用いることに適していると考えられる．

2.2 BDD

と

APPLY

演算

2.2.1 BDD

1978

年に

Akers[29]

によって考案された

BDD

は論理関数の表現方法の一つであり，

その記憶効率や処理速度の面での優秀さから

LSI

や

CAD

の分野を中心に，様々な分野に応用されている．

(30)

2.2. BDD

と

APPLY

演算

17 false or true

1 0

x1

x2 x3

(a)

0 0 - -

1 1 - -

(a) x1 c b (b) x2 1 0 (c) x3 0 1

(b)

図

2.1: BDD

のグラフ表現

(a)

とデータ構造

(b)．

図

2.1(a)

に

BDD

の一例を示す．図

2.1(a)

の丸で表される節点は変数節点である．変

数節点は

0

枝と

1

枝の

2

種類の枝を持つ．BDDの変数節点が持つ変数の値を

1

つに定めることで，1つの定数節点を対応させることができる．すなわち，根の節点から始めて変数節点に書かれた変数の値が

0

の時は

0

枝をたどり，1のときは

1

枝をたどる．

こうして最終的にたどり着く四角で表される節点に書かれた値が出力値である．四角で表される定数節点は

0

か

1

の

2

通りの値を持ち，これによって

BDD

は論理関数を表現する．

BDD

の節点は変数記号（または定数値），0枝につながる節点ラベル，1枝につながる節点ラベルの

3

つの属性を組にして持ち，この組の集合を保持し，その内

1

つを根節点（BDD

f

に対し，f.topと表記）として指定することで

1

つの

BDD

を表すことができる．本論文では，BDD

f

に対し，f.topの節点の

0

枝，1枝に続くグラフを

f

₀，

f

₁と書くことにする．つまり，

f.top = (x

_i

, f

₀

, f

₁

) (2.1)

と定義される．f0，f1は

0

枝，1枝につづくサブグラフだが，そのサブグラフが表現する論理式と同一視する．図

2.1(b)

に

BDD

をこの表現で表した例を示す．

根節点から葉への順に現われる変数の順序（変数順位）を一定にすることで，

BDD

に関する計算効率が良くなる．本研究においても与えられた変数順位に従うこととする．

2.2.2 APPLY

演算

APPLY

演算は

Bryant[88]

が考案した

BDD

のための二項論理演算の計算手続きであ

り，二つの論理関数

f

，gの

BDD

に対し二項論理演算（AND,ORなど）の結果を表す

(31)

BDD

を生成する．二項論理演算（◦）は次のように定義される．

f ◦ g(x

₁

, x

₂

, . . . , x

_k

) = f (x

₁

, x

₂

, . . . , x

_k

) ◦ g(x

₁

, x

₂

, . . . , x

_k

) (2.2)

この二項論理演算は

Shannon

の展開式により次のように表される．

f ◦ g(x

1

, . . . , x

i

, . . . , x

k

) =











f (x

1

, . . . , x

i−1

, 0, x

i+1

, . . . , x

_k

)

◦ g(x

₁

, . . . , x

_i₋₁

, 0, x

_i+1

, . . . , x

_k

); if x

_i

= 0 f (x

1

, . . . , x

i−1

, 1, x

i+1

, . . . , x

k

)

◦ g(x

1

, . . . , x

i−1

, 1, x

i+1

, . . . , x

_k

); if x

i

= 1

(2.3)

ここで図

2.1

で与えたデータ構造によって

BDD

が表現されるとする．式

(2.3)

において，f.top

= (x

_i

, f

₀

, f

₁

)

ならば

f (x

₀

, . . . , x

_i₋₁

, 0, x

_i+1

, . . . , x

_k

) = f

₀，

f (x

₀

, . . . , x

_i₋₁

, 1, x

_i+1

, . . . , x

_k

) = f

₁である．

したがって，BDDの上位の変数から順に展開して，それぞれの部分グラフ同士の演算を再帰的に実行し，定数値に関する自明な演算になったところで，再帰を打ち切ることで結果を得ることができる．この方法で

h(= f ◦ g)

を求めるアルゴリズムを図

2.2

に示す．

( 1 ) f, g

のいずれかが定数のとき，演算子

◦

に応じ，f

◦ g

を求める．

( 2 ) f.top

と

g.top

の順位が同じとき，

h

₀

← f

₀

◦ g

₀

, h

₁

← f

₁

◦ g

₁

if h

₀

= h

₁

then h ← h

₀

else h ← (f.top, h

₀

, h

₁

) ( 3 ) f.top

が

g.top

より上位のとき，

h

₀

← f

₀

◦ g, h

₁

← f

₁

◦ g

( 4 ) f.top

が

g.top

より下位のとき，

h

₀

← f ◦ g

₀

, h

₁

← f ◦ g

₀

図

2.2: h(= f ◦ g)

のアルゴリズム．

このアルゴリズムでは，生成される各

BDD

の変数順位が保存されることに注意する．

人工生命による生態進化モデルとその応用に関する 研究

人工生命による生態進化モデルとその応用に関する 研究

人工生命による生態進化モデルと その応用に関する研究

2 0 1 0

武 藤 敦 子

i

目 次

1

1

1.1

. . . . 1

1.1.1

. . . . 3

1.1.2

. . . . 4

1.1.3

. . . . 6

1.1.4

. . . . 8

1.2

. . . . 12

1.3

. . . . 13

2

APPLY

15 2.1

. . . . 15

2.2 BDD

APPLY

. . . . 16

2.2.1 BDD . . . . 16

2.2.2 APPLY

. . . . 17

2.3 n-BDD

. . . . 19

2.3.1

(n-BDD) . . . . 19

2.3.2 n-BDD

. . . . 19

2.4 APPLY

. . . . 20

2.4.1 APPLY

. . . . 21

2.5

. . . . 24

2.5.1

. . . . 24

2.5.2 APPLY

. . . . 25

2.6

. . . . 26

2.6.1

. . . . 26

2.6.2

. . . . 27

2.7

. . . . 30

3

Flexible APPLY

33 3.1

. . . . 34

3.2

. . . . 35

3.2.1

. . . . 35

3.2.2

. . . . 35

3.2.3

. . . . 36

3.2.4

. . . . 36

3.2.5

. . . . 36

3.2.6

. . . . 37

3.2.7

. . . . 37

3.2.8

. . . . 37

3.3 Flexible APPLY

人工生命による生態進化モデルとその応用に関する研究

人工生命による生態進化モデルとその応用に関する研究

人工生命による生態進化モデルとその応用に関する研究

武藤敦子

目次