この進化という言葉、「進」という字がはいっているせいか、目的をもって決まった方向に進むというニュアンスを感じてしまうこともあるけれど、それは誤解にすぎない。進化には別段特別の目的があるわけではなくて、ただその結果として、そのときどきの環境に適した機能や形態をもったものが生み出されるだけだ。その進化の原動力になっているのは、遺伝子に突然変異が起きることと、その遺伝子から作られる生物に自然淘汰が働くことのふたつである。突然変異によって環境に適応した機能をもつものが生まれるなら、その遺伝子は子孫に引き継がれて残っていく可能性が高いし、逆に環境に不適当なものになるならその遺伝子は淘汰されて消えてしまう。この 突然変異と自然淘汰を繰りかえしているうちに、環境に対して最適な形や機能が次第に作られていくことになる。
ところで、「最適」という言葉だけをとりだすなら、ことは生物だけに限らない。僕たちの身の回りにも、なにかの条件に対して最適にしたい問題が数限りなくある。例えば 部屋の中で家具をどう配置するかという問題はどうだろう。入り口の近くに大きな箪笥があったら邪魔でしょうがないし、窓をふさぐように棚をおくのは困る。テレビ画面には直射日光が当たらない方がいいけど、勉強机は明るいところのほうがいい。などなど、さまざまな条件に合うように配置を決めたいところだ。でも、おうおうにして全部の条件に合わせるのは無理だったりするので、なんとか妥協できる配置のしかたを探さなくちゃならない。
あるいは流通の分野なら、物資を配送するスケジュールからできるだけ無駄を省きたいだろうし、LSIの設計でも無駄のない配線ができるように素子の並べかたを決める必要があるだろう。この手の問題は一括して最適化問題と呼ばれている。「合理的に」とか「無駄のない」とかいうのは、まさに最適化問題を考えていることにほかならないわけだ。ボーナスの使いみちを考えることだって最適化問題ととらえることもできる。買いたいものはたくさんあるけど使える金額は限られているから、なんらかの方針にしたがってなるべく自分が満足できるように決めなくちゃならない。
ところが、この最適化問題というやつ、考えなきゃならない条件が少ないうちはともかくとして、ちょっと複雑になるとたちまちちょっとやそっとでは解けないものになってしまう。そこで、生物が進化の過程で「最適」なものを生み出してきたのを思い出して、進化の真似をすれば最適化問題が解けるんじゃないかというアイデアが生まれた。それが今回紹介する遺伝的アルゴリズムだ。下手にあれこれ考えるより、進化のしくみを取り入れて、勝手に問題の答にたどりつくのを待ってみようという、一見ずぼらな方法なのだけど、ある種の問題に対しては、これがなかなかうまくいくのである。
この手の組み合わせ最適化問題は本当に難しいのだろうか。行商人問題でもナップザック問題でも、要するに全部の組み合わせを試してみればいいだけなのに。ところが、これが実際に難しいのだ。行商人問題を考えてみよう。たとえば５都市をまわって最後に出発点に戻る問題なら、まわる順番は ２４通りしかないのだから、全部試してみてもたいしたことはない。ところが都市の数が増えると、まわりかたの数が急激に大きくなる。たかだか１００都市くらいでも、とても すべてのまわりかたを試すどころではない。組み合わせ最適化問題を難しくしているのは、このようにすべての組み合わせを試しているわけにはいかない、という点に尽きる。
これに習って、遺伝的アルゴリズムでは、組み合わせかたを「遺伝子」としてコード化する。たとえば行商人問題なら、 都市に番号をつけてそれを並べたものを遺伝子だと思えばいいだろう。設計図を書くための文字としてA,T,G,Cの代わりに都市の番号を使うわけだ。この番号の並ぶ順番がそのままセールスマンが都市をまわる順番を表すものとしよう。当然、都市の数が増えればそれに応じて遺伝子の長さも長くなる。
あるいはナップザック問題なら、品物の個数と同じ長さの遺伝子を用意すればいい。文字としては品物をナップザックに入れるか入れないかを表すふたつの記号を使う。１と０でもいいし、ＹとＮでもいい。たとえば１０個の品物があるときに、0100110001という遺伝子を考えると、これは２番、５番、６番、１０番の四つの品物をナップザックにいれるという意味を表している。
遺伝子のコード化が決まったら、次の手順は実際にこの遺伝子を進化させることだ。はじめにたくさんの遺伝子を用意しておく。これは記号をランダムに並べたものでかまわない。この遺伝子群に対して、進化を進めるためのメカニズムとしてと 突然変異、さらに 遺伝子同士の交配を取り入れる。手順としては、まず遺伝子の「よさ」に応じて淘汰をおこない、生き残ったものから一部を選んで交配や突然変異を行わせる。これで遺伝子の世代がひとつ進む。これを何世代も繰り返していけば、しだいによい遺伝子が進化してくると期待するのである。
2. 組み合わせ最適化
最適化問題だからといって、どんなものでも遺伝的アルゴリズムで扱えるというわけではない。遺伝的アルゴリズムが対象とするのは組み合わせ最適化と呼ばれるたぐいの問題だ。要するに、あらかじめ用意されたものの中から、条件にもっとも合う組み合わせかたを見つけなさいという問題がこれにあたる。代表的な組み合わせ最適化問題としては、たとえば、 行商人問題とか ナップザック問題などが知られている。
3. 遺伝的アルゴリズム
生物の遺伝情報はDNAに書かれている。といっても、もちろん鉛筆で書くわけにはいかないので、その代わりにA,T,G,Cの４種類の ヌクレオチドの並びかたで表現されている。いわば文字が４種類あって、DNAはその文字を並べて作られた文章のようなものだ。ヌクレオチドは三つがひと組になってひとつのアミノ酸を指定している。たとえばＧＣＣという順で並んでいたら、この部分アラニンはというアミノ酸を作れという指令を表す。アミノ酸は２０種類あって、これがたくさんつながってタンパク質が作られる。つまり、DNA上にはタンパク質を作るための設計図がヌクレオチドの配列として書かれているのである。
4. ボーナスの使い道を決める
例として３０個の品物がある場合のナップザック問題を解かせてみよう。品物の値段と重さは表のように決め、
| 品番 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 値段 | 77 | 19 | 96 | 95 | 97 | 83 | 40 | 72 | 15 | 34 | 66 | 51 | 66 | 14 | 76 | 27 | 38 | 33 | 75 | 95 | 79 | 89 | 12 | 31 | 10 | 18 | 29 | 45 | 44 | 33 |
| 重量 | 177 | 180 | 171 | 116 | 155 | 133 | 113 | 162 | 161 | 173 | 166 | 103 | 190 | 151 | 171 | 116 | 126 | 194 | 127 | 161 | 168 | 149 | 161 | 132 | 139 | 129 | 108 | 178 | 197 | 195 |
ナップザック問題を１２８個の遺伝子を使って計算した例。横軸は遺伝子の世代で、縦軸がその世代の中で合計価格が最も大きいものの値。最初の遺伝子群は０と１をランダムに並べて作ったもので、三通りの違った遺伝子群からはじめた結果を描いてある。
３０個の品物の組み合わせかたは約１０億通りもある。一方、今の計算では１２８個の遺伝子を２００世代調べただけなので、せいぜいで ２万通り程度以下の組み合わせしか調べていないはずだ。それにもかかわらず、ちゃんと値段が最大になる組み合わせが得られている。遺伝的アルゴリズムが単にランダムに組み合わせを作るよりはるかに効率よくナップザック問題を解いていることがわかるだろう。
ところで、ボーナスの使い途を決める問題も、考えようによってはこのナップザック問題と同じになる。ボーナスの場合は総重量ではなくて使える金額の上限が決まっている。問題はどういう基準で買うものを選ぶかだ。買いたい品物それぞれについてそれを手にいれたときの「満足度」のようなものを決めてやり、その 満足度の合計が最大になるような組み合わせを求めたいとするなら、これはまさにナップザック問題そのものだ。
さて、こういう「つきあいかた」の問題をひとつのゲームと捉えようという立場がある。相手に対する態度の決めかたを、いわばゲームの「手」だと思うのである。たとえば、「優しくする」と「つけこむ」の２通りの手が選択できるとしよう。ふたりが同時に自分の手を出し合う。自分が「優しくする」を選んだときに相手が「つけこむ」を選んでいれば相手の勝ちだ。ふたりとも「つけこむ」を選んでしまえば、どちらにもつけこむ隙がないのだから、この手は空振りに終わる。自分と相手がともに「優しくする」を選んだときは、ふたりともこのゲームにそこそこの勝ちを収められると思っていいだろう。この状況を点数で表すことにするなら、たとえば
5. 他人との関係の進化
ナップザック問題やボーナスの使い途は、決まった環境の中での進化を考えているようなものだ。ところが、世の中には、進化につれて環境自体も変化していくような問題がある。人間社会でいうなら、たとえば他人とのつきあいかたなどはどうだろう。他人に対する自分の態度が変わっていけば、自分に対するまわりの人間の態度も変わっていくはずだ。人に優しくすれば、まわりの人も優しくしてくれるかもしれない。でも、もしかしたら、こちらの優しさにつけこもうというずるい人間も現われるかもしれない。ずるい人間に出会ってしまったら、こちらも態度を変えることを学ぶことになるだろう。この「学ぶ」ことを進化だと思うなら、これはまさに自分の進化によってまわりの環境が変化し、さらにその環境に合わせて自分が進化するという現象ではないか。個人対個人の関係に限らず、会社と会社の関係や国と国の関係でも同じような「つきあいかたの進化」を考えることができる。
| 自分 | 相手 | 自分の点数 | 相手の点数 |
| 優しくする | 優しくする | ３ | ３ |
| 優しくする | つけこむ | ０ | ５ |
| つけこむ | 優しくする | ５ | ０ |
| つけこむ | つけこむ | ０ | ０ |
このゲームをふたりで一回だけ行うとすれば、自分が勝たないまでも少なくとも負けないためには、手として「つけこむ」を選ぶしかない。ところが、このゲームを何度も繰り返す場合は話が違ってくる。相手がどういう人間かを見極めて、それに合わせて手の出し方を変えることができるからだ。となれば、相手を見極める技術を磨くことが大切かもしれない。あるいはこれをゲームの戦略と呼んでもいいだろう。技術を磨くとは、最適の戦略を見つける、と言い換えてもよさそうだ。そこで、この最適戦略を遺伝的アルゴリズムで探すことを試みよう。
ゲームを何度も繰り返し行なうのなら、過去の相手と自分の手を参考にして次の手を決めることができる。ここでは話を簡単にするために、次の手を決めるための情報として、二回前までの自分と相手の手だけを考えることにする。この情報に対する戦略はナップザック問題と同じように 遺伝子としてコード化できる。
問題は遺伝子の「よさ」をどうやって評価するかだけど、なにしろゲームなので実際にその遺伝子にコードされた戦略で戦わせるしか評価のしようがない。そこで、たくさんの遺伝子を用意して、遺伝子同士を総当たりで戦わせてみることにする。得点の合計が高いほど「よい」戦略をもった遺伝子だと思うのである。
というわけで、試しに実際に遺伝子を進化させてみた結果をグラフで見てもらおう。
実は、今のように２回前の手までしか考えないという条件に限らず、もっと広い範囲での戦略を認めたとしても、この「しっぺ返し」戦略は大変に強いことがわかっている。はじめのうちはたしかに徹底的につけこむ戦略が強いのだけど、弱い戦略が淘汰されるうちにつけこめる相手がいなくなってしまい、「つけこむ」一辺倒では点数がかせげなくなるのである。一方、「しっぺ返し」は一対一では「つけこむ」より強いわけではないけれど、一旦仲間が増えると、仲間同士では優しくしあうので点数をかせぐことができる。つまり、集団になると強いのがこの「しっぺ返し」なのである。短期的には必ずしも強くなくても、このように飴と鞭を使い分ける戦略が長い目で見れば有利になるというのは、なかなか教訓的ではないだろうか。
いろいろな戦略を表す遺伝子数の変化。赤は「徹底的につけこむ」戦略とその仲間、青は「しっぺ返し」戦略とその仲間、緑がそれ以外を表す。 計算の詳細に興味のあるかたはこちらを
あまり細かいことを考えてもしょうがないので、似たような戦略はひとまとめにして表示した。これによると、１万世代のあたりまでは 「徹底的につけこむ」戦略の仲間が断然優勢なのだけど、その後、このタイプの戦略を持った遺伝子が急激に減って消滅してしまい、代わりに 「しっぺ返し」型の戦略が優勢になることがわかる。
6. おしまい
というわけで、進化のまねをする遺伝的アルゴリズムを紹介した。ちょっと聞いただけではどうにも胡散臭い方法のように思えるのだけど、実際に試してみると、たしかにある種の最適化問題ではうまくいくようだ。ナップザック問題などは見事に答にたどりついてくれる。もっとも、どうしてこのような方法がうまくいくのかはよくわからない。へたに人間が考えるよりも、自然にまかせてしまったほうがうまくできるというのだから、釈然としないかたも多いのではなかろうか。この方法を使うことによって進化のメカニズムが理解できるというよりは、むしろ進化というものの不思議さを再認識させられるという気がする。そう、進化はやっぱり不思議だ。
ここからは本文からリンクされたテキスト
以前とりあげたセル・オートマトンをおぼえておられるでしょうか。いろいろなルールのセル・オートマトンを自分で試せるシミュレータをJAVAで作ってみました。WWW上で公開しています。マックでもNetscape Navigatorの最近のバージョンなら動かせるはずなので、興味のあるかたはお試しください。まだ多少動作におかしな点が残っていますが、プログラム上の問題はおいおいなおします。URLは
http://glimmung.phys.sci.osaka-u.ac.jp/kikuchi/kougi/nonlinear/CA/
です。
戻る
進化ではなく神による創造説をとる人たちもいるのだけど、「創造」に比喩として以上の意味を持たせるのはやっぱり無理だと思う。
戻る
では、３０億個のヌクレオチドをでたらめに並べていって、人間のDNAを作ることができるだろうか。地球が生まれてから約５０億年もの時間があったんだから、それくらい長い時間をかければなんとかなるのだろうか。残念ながらそれではなんともならないことがすぐわかる。５０億年といえば一見すごく長い時間のようだけど、実は秒になおしてもせいぜい１０の１７乗秒くらいにしかならない。だから、でたらめに配列を作っていったのでは一秒間に何億通りの配列をためそうと１０の１８億乗という気の遠くなるような数にはぜんぜん追いつかない。
もちろん、でたらめにヌクレオチドを並べていったのでは、意味のある遺伝情報は作れないはずで、たぶんほとんどすべての組み合わせは無価値なものになってしまうだろう。でたらめにヌクレオチドを並べていってそれが人間の遺伝子に一致する可能性は、猿がでたらめにタイプライタをたたいて、それがたまたま シェイクスピアの小説と一致する可能性よりもはるかに低い。
にもかかわらず、これだけたくさんの可能性の中から実際に人間をかたち作る遺伝情報が生み出されたということは、進化のメカニズムが単にでたらめにヌクレオチドを並べていくよりもはるかに効率よく働いたことを意味している。
戻る
もっとも、実際に遺伝情報として使われているのは全体の一割程度らしい。残りの部分は、少なくとも遺伝情報としての役割はもっていないようだ。
戻る
４種類の記号（色）で書かれた長さ１２の遺伝子に対して突然変異を作用させた例。右から３番目の位置が変異によって黄色から赤に変わっている。
長さ１２の遺伝子２本がそれぞれ左から５番目と６番目の記号の間で切断されて、つなぎ変えられた例。