2目次

目次

第１章

はじめに...................................................................6

１

はじめに

２

本書の構成

611

第２章

遺伝的アルゴリズム概説......................................14１14遺伝的アルゴリズムとは第３章

山登りをさせてみよう..........................................26

１

探索の代表，山登り

26

２

Windows プログラミング要領

３プログラムの作成

49

32

3

目次

４結果

61

第４章

できるだけ近道をしてみよう..............................63

１

巡回セールスマン問題とは

63

２

TSP 問題の分析

３

プログラ外部仕様または操作マニュアル

４

プログラムの作成

５結果

第５章

66
72

76

83

最短手順を発見してみよう..................................84

１

積木問題とは２遺伝子上への問題表現

３

クロスオーバとミューテーション

４

遺伝子の長さが変化する？！

５

プログラム外部仕様または操作マニュアル

６プログラムの作成

７結果

110

8485

97889192

4

目次

第６章

迷路からの脱出.................................................... 112

１

迷路

112

２

分析

113

３

プログラム外部仕様または操作マニュアル

４

プログラムの作成

５

考察

第７章

129

140神になったつもり................................................ 141

１

人工生命

２

外部仕様または操作マニュアル

３

プログラムの作成

４

考察

第８章

123

141
145

151

160

最適スケジュールはたてられるかな................. 162

１

スケジューリング問題

162

２

プログラム外部仕様または操作マニュアル

３

プログラムの作成

175

169

5

目次

４

考察

おまけの章

186

進化をシミュレートしてみる..................... 188

１

バイオモルフと累積淘汰

２

遺伝子の役目３

人為選択の行い方

４ウインドウ構成

５

結果

197

６

考察

199

191
192
193

ダウンロードサービスのご案内
用語解説

205

参考文献

211

あとがき

218

索引

188

200

220

著者略歴／著作権表示／奥付223

6

第 1 章 はじめに

第１章

１

1. はじめにはじめにはじめに遺伝的アルゴリズム（GA）という言葉には，神秘的な響きと知的好奇心をくすぐる魅力があります。筆者がこの言葉を見たのは，1987 年の別冊サイエンス中の記事「flib がすむ原始のコンピュータの海で遺伝的アルゴリズムを探検する」でした［DEW87］。これは，flib（finite living blob: 有限生命体）と名付けられた仮想の生物の進化をシミュレートするものでした。その生物に課せられた進化の目的は，自然環境からある記号列を受け取り，その記号列に出現する記号を予測するような能力を獲得することです。いわゆる有限オートマトンの機能を獲得させようというわけです。したがって，記号の出現をうまく予測できた者ほど優秀な個体であり，また，優秀な個体ほど子孫を残しやすくする工夫を持ち込むことで，そのうち完全なる予言者が出現するようになるというわけです。
ただ，少々概念的な話が多くて，実際の具体的な仕事をしていた筆者には，なにやら悠長な話だなといった感覚しかなく，そのときは，それをどうこうしようなどとは考えませんでした。恐らく，この言葉を初めて聞きあるいは目にして，その簡単な説明を聞いただけでは，成り行き任せの考えから，

7

第 1 章 はじめに1. はじめに本当に有効な結果がもたらされるのか疑問に思う人が多いでしょう。残念ながら，筆者もその一人でした。でも，今にして思えば，なんて浅はかだったんだろうと後悔をしています。一度，この仕組みが理解できると，誰にでも簡単にプログラミングができて，最短経路や最適な計画が求められることがわかるようになります。そして遺伝的アルゴリズムは皆さんの問題解決能力に１つの武器を与えてくれるでしょう。
さて，遺伝的アルゴリズムとは何者なのでしょう？

平たく説明すれば，ダーウィンの進化論，正確にはネオダーウィニズムの考え方を，ほとんどそのままアルゴリズム化したものです。すなわち，与えられた自然環境の中で，個体集団の各個体同士が交配と突然変異を繰り返しながら，その自然環境によく適応する個体ほど生き残り，子孫を増やすことができるようにするアルゴリズムです。自然環境に適応するということは，そのときに与えられた環境での各種の条件下で，その個体がいかにうまくやっていけるのかということです。もちろん自然環境は，季節によりある範囲の変化が絶えず起こっていますし，時がたつにつれて徐々に変化していきますから，そこでの個体は，環境が一定の場合とは異なった戦略をとる必要があるでしょう。ただいずれにしても，自然環境とは個体に与えられている外部からの条件ということになります。ここで曖昧に個体という表現を使っていますが，より厳密にいえば，遺伝子とその表現型であるカラダとの総体のことです。動物のカラダは，御存知のように蛋白質で成り立っています。
その成り立ちを決めているのが遺伝子なわけですが，遺伝子だけでは環境に作用することができません。そこで，カラダという遺伝子の入れ物があるわけです。遺伝子は自分が生き残るために，この入れ物をデザインして環境をうまく利用できるように仕組んでいるともいえます。たとえば，海という環境で生きるためには，海水から酸素を得るデザインが必要だし，抵抗の大きい海水中で素早く動きまわれるデザインが必要です。これらのデザインは，同じ海の中でも少し戦略を変えると，大きく変化してしまいます。
海老などは，素早い動きの代わりに堅牢な鎧をデザインとして採用しています。このように，同じ環境でも，その環境を利用するためのデザインはかなり変化に富んだものとなります。つまり自然環境に適応するということは，遺伝子が生き残っていけるよう，環境を利用できるデザインに発展8

第 1 章 はじめに1. はじめにさせることであるともいえます。本書には，遺伝的アルゴリズムという人工的な仕組みを各種の応用に適用させようという目的があります。自然界での環境適応という意味は，ここでは，応用問題における各種の制約条件や評価基準となります。通常，応用問題の世界では，これらの条件は一定ということで解法を実現しています。その意味では自然界よりも単純な仕組みがあればいいわけです。ところが，最近では，金融や証券といった世界での金利や株価予測などのカオス的挙動を示す分野での応用に代表されるような，環境の変動をも考慮した方式が必要になってきています。これは，まさに，自然界での進化プロセスそのものです。遺伝的アルゴリズムの特色は，このような環境の変化も簡単にモデル化してしまえるところにもあります。本書では，環境の変化に対応するような応用は掲載していませんが，条件一定での応用の要領がつかめれば，拡張することは比較的容易だと思います。
それでは，条件一定という各種の制約条件の下で何らかの評価値を最適な値にするということを考えてみましょう。たとえば，東京から長崎へ何らかの交通機関を使用して行くとします。ここで３日以内に目的地に着くという制約条件をつけて，旅行費用最小のコースを選択する問題を考えてみます。明らかに，コースを表現するのが個体の遺伝子で，自然環境の制約条件，評価値はそれぞれ「３日以内」と「旅行費用最小」ということになります。実際に計画を立てている様子を想像してみましょう。このコースを表現する遺伝子は，たとえばいくつかの中間地点を持った路線図を書いたメモみたいなものです。このメモがいくつか用意されていて，それぞれに旅行費用が算出されています。ここで，そのメモのうち旅行費用が安いメモを２つ選択して，それらの親メモに記されている中間地点を境界にして親メモをハサミで切断します。この切断のとき注意しなければならな
いことは，切断される中間地点は，両親とも同じになるようにすることです。
そうすると，いくつかの部分的なコースが要素として出てきます。この要素を中間地点が一致するように交換すると新しいコースが生じますが，これを子メモとしてその旅行費用の算出をしておきます。かなり煩雑ですが，このような操作を繰り返しているうちに，考えもつかないような旅行費用最小のコースが産まれてくるかもしれません。当然ながら，このような操

9

第 1 章 はじめに

1. はじめに作を紙とハサミを使って行っていては，いくら時間があっても願い下げです。幸いにも，以上の手続きは単純ですので，プログラミング能力があれば，だれにでも容易に計算機上で実現しシミュレーションできます。
遺伝的アルゴリズムはこのように，ダーウィンの進化論を全面的に正しいと信じて構成されているわけですが，進化論の世界では，反ダーウィン主義の考え方もあって，多くの議論がなされています［DEN85］。ダーウィンの進化論のどのような点が主に問題となっているのかというと，進化は漸進的に変化し，枝わかれして今のような生物の種類が生まれてきたということに関してです。このダーウィンの主張に対する反証として引き合いに出されるのが，化石にその証拠が見いだされないということなのです。つまり，もし漸進的な進化が真実ならば，もっと短い首を持つキリンの化石が見つかってもいいはずなのに，化石を見るかぎりにおいては突然首が長くなっているとしか解釈できないということです。この議論は，ダーウィンが『種の起源』を発表して以来続いていることなのですが，最初の頃は，地球上の全化石が調べられたわけでもないので，そのうち漸進的進化を裏付ける証拠が出るだろうと期待されていました。しかし，今日に至るまで，その種の化石は発見されていないようなのです。バージェス頁岩の話はご存じの方も多いと思います［GOU89］。1909 年に約６億年前のカンブリア紀の動物化石が大量に発見され，その中に漸進的進化を説明する中間的な動物化石が含まれているだろうと期待されていました。でも，その後の研究によってもその兆候は発見されず，むしろ，カンブリア爆発として有名な生物種の大量発生の時期であったことを改めて示す結果となっています。つまり，バージェス頁岩中の動物達は皆，それまでには知られていなかった新たな種類の動物で，充分に分化した後の系統木の末端に位置するものであるとの見方がなされています。決して，ダーウィンが望んでいた中間型の動物とはならなかったわけです。その他，爬虫類から鳥が進化したと言われていますが，その形態上の中間的生物の化石が発見されていないこと
や，鳥の翼にはえている羽の緻密な構造が試行錯誤を前提とした漸進的進化では，どう説明してよいのか不明なのです。始祖鳥の化石は有名ですが，始祖鳥は鳥に極めて近い存在ですので，先の中間物とはいいがたいものがあります［DEN85］。

10

第 1 章 はじめに

1. はじめに生物の進化ともなると，その時間スケールは長すぎておいそれと実験室で実験するわけにもいきません。しかし化石が生物の進化を充分な精度で再現しているのかといえば，そうではなさそうです。特に進化の系統上，欠落していると思われる部分が，本当に存在していなかったのか，あるいは化石になる機会がなかったのかを決定することはできません。化石になれる条件は，かなり厳しいものがあるでしょうから，存在していなかったことを示すのは化石だけからでは無理なのではないでしょうか。とすれば，何か 別 の 理 論 的 な 考 察 を 持 ち 込 む 必 要 が あ る で し ょ う。 実 は，RichardDawkins がそのような考察を加えて，累積淘汰という考え方を提唱しています［DAW86］。これは，小さな突然変移が遺伝子の中に蓄えられていき，やがては，種をも越えるような変化がもたらされるというものです。彼はこの考え方を示すために，９つの遺伝子により形態を決めることができる架空の生物を考え，遺伝子の変化から得られた形態を人為的に選択して，ある意図で進化を繰り返していけるようなちょっとしたシミュレータを作りました。もともとは，再帰プログラムの例題によく使われる樹木の発生を利用したものですが，この発生アルゴリズムと９つの遺伝子をからませて発生の仕方を変化させるようになっています。第１から第３遺伝子までは，樹木の横方向の枝振りに変化を与え，第４から第８遺伝子までは，縦方向の枝振りに変化を与えるようになっています。最後の第９遺伝子は，枝の分枝数を示しています。人為淘汰のやりかたは，現在の遺伝子からその９つの遺伝子それぞれの値を１だけ増減させるとすべてで 18 個の違った遺伝子が得られますが，それらの形態を表示して人間が選択するようにします。
こうして選択した１つだけを次の世代としていくわけです。彼自身も彼の著書『ブラインド・ウオッチメーカー』で書いているように，単に樹木の形態的な変化が起こるだけで，樹木の域を越えることはないと予測していたようですが，人為淘汰を繰り返すことにより，カエルやコウモリやトビケラ，アゲハチョウなど樹木の世界を飛び越して多くの動物たちを生み出せるようになったということです。
最初は，ほとんど１点かあるいは１本の棒だったものが，人為選択を繰り返すことにより，大きく変化していく様子は確かに感動的です。結局，小さな突然変移とは，毎回の遺伝子の僅かな増減なのですが，それが積み重11

第 1 章 はじめに

2. 本書の構成なることで形態に大きな変化を与え得るということを示していることになるわけです。
生物学の世界では，ダーウィンの進化論だけでなくこれまでにいくつかの異なった立場での進化論が登場してきましたが，本書は，そのような進化論のどれが正しいのかについて議論するといっただいそれたことをするものではありません。むしろ，ダーウィンの進化論を正しいものとして，進化というプロセスが工学的な応用に使えそうだという，少々乱暴ではありますが実際的な興味を主体に記述することにします。

２

本書の構成

筆者の前著『C でつくるニューラルネットワーク』［平野 91］においてもそうでしたが，本書においても理論的な解説については，世の中に優れた成書がありますので，そちらを参考にしていただくという立場をとりたいと思います。本書では，遺伝的アルゴリズムの応用面に焦点をあて，どうしたら与えられた問題に遺伝的アルゴリズムを適用できるのかが習得できるような内容となっています。
構成は，第２章で遺伝的アルゴリズムの概説を行い，第３章以下で，個別の応用問題を取り上げます。また，プログラムは Windows 3.1 の SDK を用いて開発していますが，Windows プログラミングについての解説は本書の目的ではありませんので，極力記述を避けています。しかしながら，全体の動作とプログラム構造については，各応用問題に共通な構造をとっていますので，第３章で少し詳しく紹介します。したがって，第２章と第３章を先に読み，他の章は興味あるところから読んで頂いても結構です。
以下に２章以下の構成と内容の概略を記述します。

12

第 1 章 はじめに第２章

2. 本書の構成

遺伝的アルゴリズム概説

遺伝的アルゴリズムについての基礎的な内容を解説します。どのような仕組みで最適解あるいはそれに近い解に到達できるのかを，感覚としてとらえることが目的です。いわば，簡単な理論編となっています。

第３章

山登りをさせてみよう

３次元空間内での，曲面上の最も高い頂上を見つけます。遺伝的アルゴリズムのからくりを直感的に理解してもらうのをテーマとした簡単な例です。
なお，Windows プログラミングについては，ウインドウの構成や各イベントに対するコールバック関数の構成など，他の章とも共通部分が多いため，ここで少し詳しく解説します。

第４章

できるだけ近道をしてみよう

最適化問題における典型的な NP 完全のクラスに属する問題である巡回セールスマン問題を取り上げます。この問題自体は歴史が古く，他の最適化手法でも真っ先に取り上げられる問題です。遺伝的アルゴリズムにおいても，当初から研究され，遺伝子表現が最も工夫されてきた問題です。
また，なぜ巡回セールスマン問題が，応用として重要かも解説します。

第５章

最短手順を発見してみよう

積木を積み替える最短手順を発見する問題です。ここでは，手順の遺伝子上への表現方法とか，有効な染色体の長さが可変となりますので，その遺伝的操作をどう扱うかといったことがテーマです。もともとは，インターフェース誌 1992 年２月号［平野 92］に掲載した内容に加筆訂正を行い，Windows 上に移植したものです。

13

第 1 章 はじめに第６章

2. 本書の構成

迷路からの脱出迷路を設定し，そこから抜け出す方法を見つけだすものです。通常の深さ優先探索とか幅優先探索といった探索法とは全く異なった方法で迷路脱出を試みます。一見，手続き的な遺伝子表現となりそうですが，積木問題とは異なって冗長な遺伝子を含ませた方法をとります。

第７章神になったつもり

人工生命の例題として取り上げます。行動遺伝子を持った虫が，その指示するとおりに動き回り餌を食べるという状況で，行動遺伝子がどう進化したら生き延びることができるかをシミュレーションします。

第８章

最適スケジュールはたてられるかな

これまた，典型的な最適化問題であるジョブショップスケジューリング問題を取り上げます。
Muth & Thompson のベンチマーク用問題に対して適用してみます。こ
こでは，遺伝子表現に順序型を用いて，比較的よい結果が出たことを示します。

おまけの章

進化をシミュレートしてみる「はじめに」でも述べましたが，Richard Dawkins は，累積淘汰をシミュレートするバイオモルフというプログラムを作り，その効果をアピールしています。この章では同様のプログラムに挑戦してみます。

218 あとがき

あとがき

筆者が遺伝的アルゴリズムに本格的に係わりだしたのは，拙著『 C でつくるニューラルネットワーク』の執筆を終えた頃からでした。そのころ，従来の論理をベースとした手続指向やルール指向のプログラミングでは，実現不可能な領域があるのではないかと感じだしていました。少し高尚な表現をすれば，デカルト流の還元主義ではなく対象を全体として捉える方法が必要だということです。言葉にしてしまえば，簡単なのですが，具体的にどう展開できるのかはわかりません。
当時，ファジィー，ニューラルネットワーク，遺伝的アルゴリズムを並べて眺めていると，複雑さと集団とへ立ち向かう武器に見えていたものです。また，一方では，生物の情報処理の巧みさに感心もありましたから，少なくともニューラルネットワークと遺伝的アルゴリズムは理解しておく必要があるだろうと思い，ことあるごとに応用を企んでいたわけです。そのうち，人工生命という枠組みが提案されていることを米国出張の折に知り，「全体として捉える」ということに対するアプローチへのヒントがあるに違いないと確信するに至りました。
このあたりがベースになって，本書を書くことができました。ニューラ
ルネットワークと遺伝的アルゴリズムを組み合わせた例も多く報告されて

219 あとがき

いますが，本書では，そこまで立ち入ることができませんでした。この点が筆者の心残りとなってしまいました。
なお，本書を執筆するにあたり，応用に重点をおき，可能なかぎり具体化をこころがけたつもりです。前著同様，具体的なプログラミングを通して，多くの人に遺伝的アルゴリズムの利用技術を理解していただければ幸いです。
末筆になりましたが，本書の企画を取り上げて頂いたパーソナルメディ
ア株式会社出版部，特に本書をより親しみやすく読みやすくするような紙面作りやきめ細かな校正をしていただいた編集の皆さんに深く感謝いたします。

・・・ この続きは、製品版でお楽しみください。

購入ご案内
iPad 用 PDF リーダアプリ「Smooth Reader」をご利用の方は、以下のボタンをタップすると購入手続きに進みます。

その他の電子書籍や、全国書店でお買い求めになれる紙書籍に関する情報は、当社ウェブページをご覧ください。
→ http://www.personal-media.co.jp/book/223 著者略歴／著作権表示／奥付

著者略歴

平野廣美（ひらのひろみ）

昭和 51 年，京都大学航空工学科卒業後，( 株 ) 日本 CAD，( 株 ) 新日鉄ソリューションズ等を経て，現在，楽天株式会社 楽天技術研究所に在籍。
大学卒業後まもなくして人工知能に興味を持ち始め，Lisp や Prolog の処理系の開発に従事する。
また，日本語によるデータベースの検索システムの開発や工場等の生産計画の最適化，テキストマイニングなどの知識処理などを行ってきた。
著書に『C でつくるニューラルネットワーク』『遺伝的アルゴリズムと遺伝的プログラミング』『続・遺伝的アルゴリズムと遺伝的プログラミング』『C++ と Java でつくるニューラルネットワーク』（いずれも，パーソナルメディア刊）がある。
本書に関する情報を web サイトでご案内しております。

http://www.personal-media.co.jp/book/comp/136/

本書に記載されているハードウェア名，ソフトウェア名は一般に各メーカーの登録商標または商標です。

応用事例でわかる
遺伝的アルゴリズムプログラミング
1995 年 11 月 30 日 初版 1 刷発行（書籍版）
2011 年 1 月 7 日 iPad 版 発行
著
発者行所

平野廣美
パーソナルメディア株式会社						〒 141--0031 東京都品川区西五反田 1--29--1 コイズミビル
TEL（03）5759--8303 ／ FAX（03）5759--8306
E-mail pub@personal-- media.co.jp		

http://www.personal-- media.co.jp© 1995Hiromi Hirano

224 著者略歴／著作権表示／奥付