Accumu Vol.6

遺伝アルゴリズムについて

植田 浩司

私たちが学校やオフィスで使うコンピュータは，あらかじめ，何をどうすればいいのか，というコンピュータの動作がプログラムという形で決めてあります。文字が入力されればそれはスクリーン上に表示され，マウスが移動すればカーソルも移動する。これらのことはプログラマが設計した通り，私たちの操作に対応して情報が処理されるもので，プログラムがなければコンピュータはなにもしません。

さらに，たとえば表計算ソフトなどでは，売上げ高を計算しようとすると，この列とこの列の数値を足して，この列に結果を入れる，と人間の方で指定してやらなければなりません。またワープロでは，頭の中で考えている文章をキーボードから入力して正しい漢字に変換してやらなければなりません。

しかしここで，もしも私たちがなにも指示しなくても，コンピュータが試行錯誤で，正しい計算方法を表計算ソフトに設定してくれたなら，また特に何も考えなくてもタイトルさえ入力したなら，コンピュータがどんどん文章を作っていってくれたなら。あるいは，たくさんある選択肢の中から一番早く，そして一番安く，世界一周旅行ができるプランを立ててくれたならどうでしょう。

遺伝アルゴリズム

遺伝アルゴリズムというのは，その名の通り，生物の遺伝のメカニズムをコンピュータのプログラムに取り入れたものです。それはあたかも生物が進化を遂げていくように，プログラムがある環境に適応していく（問題が解けるようになる）ようになるものです。私たちは最初に，どのような問題を解きたいのか，それをどのように表現すればこのアルゴリズムで使えるのか，どのような答えだと満足できるのか，どういう形式で遺伝情報を子孫に伝えるのか，という点に頭を悩ませるだけです。あとは黙ってコンピュータの前に座っていればいいのです。何分か，何十分か，あるいは何時間か後にはなんらかの答えが出てきます。このようなアルゴリズムは最近提唱され，多くの研究者によってその有効性が認められて，現在つぎつぎと新しい応用分野・方法の発見がなされています。いわば遺伝アルゴリズム自身が研究の進化の途上にあるといえ，これから人工知能の研究において，大いに期待されている分野です。

生物界での遺伝

生物の世界での遺伝とはいったいどういうものなのでしょうか。私たち人間を含め，現在の地球上の生き物は，最も原始的な生物から数十億年という時間をかけて進化してきました。海の中で生まれた原始生物がやがてひれを持って泳ぐようになり，後に陸に上がり，あるものは地上で生活し，あるものは空を飛ぶようになり，さらにあるものは二本足で歩くようになりました。またあるものは環境の変化に対応できず絶滅しました。

ところで，生物は染色体と呼ばれる遺伝子の集合体を持っており，生物が子孫を増やすとき，この遺伝子を後代に伝えます。子は雄，雌両方の親から遺伝情報を受け継ぎ，そのまた子供へと遺伝子を伝えます。生物はこれを気が遠くなる程繰り返し現在に至りました。親から子へと遺伝子が伝わる際，突然変異などにより，親の遺伝子とは少し違ったものを持つものもでてきます。この生物個体は，時にほかの個体より環境にうまく適応することができたり，ほかの個体とは異なる特徴を持つことがあります。あるひとつの形態から長い時間をかけて，自らがおかれている環境に適応できるように自分自身の形態を変化させていく，これが進化です。つまり世代から世代へと生物の情報を引き渡していくことが遺伝で，遺伝の結果，先代よりも良い方向で生物の特徴を変化させることが進化といえます。

コンピュータの世界での遺伝

それではコンピュータの世界での遺伝とはなんでしょう。その名が示すように，遺伝アルゴリズムにも遺伝子，染色体，その染色体をもつ生物個体（？）が登場します。コンピュータの世界でも，遺伝とはある情報を次の世代（プログラムの繰り返しループをひとつ増やすこと）に伝えていくことです。そして伝わった情報により，問題を解き，前の世代よりも良い結果がでれば進化したと言えます。では，プログラムにとって染色体や，遺伝子とは一体何なのでしょうか。このアルゴリズムでは，遺伝子はビット配列，あるいは自然数の配列として表現されます。最適解をもたらす染色体を探し出すのがこのアルゴリズムの目的であり，優れた遺伝子の組み合わせが最適な染色体です。

ここで生物の世界を例にとって説明しましょう。稲の品種改良を考えてみます。良い遺伝情報を持った稲を選び出して交配し，より良い品種に育てることが目的だとします。寒さに強い稲の遺伝子を探し，どの遺伝子がどのような特徴をもたらすのかを調べたとします。もしも人為的に寒さ暑さに強く，水質の変化に強く，繁殖力が強く，そして味がよくなる遺伝子ばかりを集めて一つの染色体にまとめることができれば，この染色体から作られる稲はとても良いお米になるでしょう。この時，遺伝子の一つ一つは暑さ寒さに強いとか，水質の変化に強い等の情報であり，それらは与えられた良いお米を作り出すという問題の答を構成するための構成要素です。

遺伝アルゴリズムはこれをプログラムでモデル化します。つまり，遺伝子とはこのアルゴリズムにとって，ある問題を解く構成要素なのです。問題を解くための正しい構成要素がすべて出揃ったとき，最適解が得られるのです。稲の場合，何世代にも渡り品種を改良して行き，最後には非常においしいお米を得るように，何世代にも渡り良い染色体どうしの交配を繰り返すことで，ある問題の最適解に近づいていくというのが遺伝アルゴリズムです。ただしそのような構成要素は，ビット配列や自然数の配列として（表現するため）コード化されるのが普通です。どのような因子を構成要素（遺伝子）として選ぶか，それをどのようにコード化するのかが遺伝アルゴリズム研究の最大の課題です。

遺伝アルゴリズムでは，プログラマが自分の解きたい問題を分析し，どのような因子がどんな条件になった時に問題が解決するのか調べます。そしてそのような因子を遺伝子という情報としてモデル化し，この遺伝子を持つ生物個体の集合の存続をコンピュータでシミュレートします。その結果，環境にうまく適応できる個体が生き残り，繁殖していきます。新しい個体が生まれる度にその遺伝子を解読し，ベストの遺伝情報を持つ個体が現われたらそこでシミュレーションは終了します。この時に得られた染色体が，最適解を構成する遺伝情報を持っているのです。シミュレーションの様子を詳しく見ていくと，最初は環境への適応力の小さい個体が多く存在しますが，時間とともに，環境にうまく適応できる個体の数が少しずつ増えていくのが分かります。良い遺伝子を持つ個体の子孫が生き残り，そうでないものは絶滅していきます。ここで環境に適応するというのは，個体の遺伝子が，与えられた問題の答（期待する答）に近い解答を作ることのできる条件を備えているということです。このように遺伝アルゴリズムは，ダーウィンの進化論のようなことをコンピュータープログラムで再現しています。その方法はいろいろありますが，そのうちの一つが，トーナメント法と言われるものです。

アルゴリズム

このトーナメント法を，例を用いて説明します。まず，ある小さな町を想像してください。人口は100人くらいです。この町をスポーツ万能の子供たちでいっぱいにしようとするのが目的です。町民の陸上，水泳，サッカー，テニスのスポーツの素質が上位からどれくらいであるかが，この町に住める条件だとします。ただしこの素質は遺伝によってのみ決まるもので，本人の努力は関係ないとします。そして毎年，素質が最低である町民2人は町から追放されます。

年に1回，ランダムに男性女性それぞれ3名ずつが選手に選ばれ，競技をします。競技の成績について，男女それぞれのトップを選出し，このカップルだけがその年に子供を作ることを許され，常に1組のカップルから2人の子供ができます。町の人口は100人に固定しなければ人が住むところがなくなるので，当の競技結果が最低であった2人は町から追い出され，代わりに新しい子供が町に住みます。ただし，新しい子供のスポーツの素質が，最低であった人より劣れば，その子供は町には住めません。それぞれの子供は両親からスポーツの素質を，父親から半分，母親から半分受け継ぎます。

たとえば父親は，陸上と水泳は不得意で，サッカーとテニスは普通ぐらいだとします。母親は，陸上は普通ぐらいで，水泳とサッカーは抜群に良くでき，テニスはまったく駄目だとします。この両親からできた2人の子供AとBは，Aは陸上は普通ぐらいで，水泳は抜群に良くでき，サッカーとテニスは普通ぐらいの子供になり，もう一方のBは，陸上と水泳は不得意で，サッカーは抜群に良くでき，テニスはまったく駄目になったとします。これは陸上と水泳は母親から，サッカーとテニスの素質を父親から受け継いだ子供と，その反対の組み合わせの素質を両親から受け継いだ子供ということになります。Aは全般的に普通以上によく，Bはサッカー以外はあまり良くないという結果になります。平均で考えるとAは両親より強くなり，進化したことになります。このようなルールで毎年競技会を開催し，その勝者のみが子供を作り，素質の無い者が町を去るようにすると，何十年か後には，この町はスポーツ万能の子供たちでいっぱいになるというのがこのアルゴリズムです。

遺伝子操作オペレーション

上の例で遺伝アルゴリズムの特徴的なオペレーションが出てきました。それはクロスオーバー(crossover)と言われるもので，2つの遺伝子の情報を半分ずつ入れ替えることです。プログラミングの点から言うと，ある2つの配列の中身を，あるインデックスのところからごっそりと入れ替えることです。インデックスの場所はランダムに決めます。この操作により，遺伝情報は元のものから当然変化するのですが，この変化が良い方へ働く場合もあれば悪い方へ働く場合もあります。良い方へ働けば，この遺伝子を持つ生物個体の環境への対応力は良くなったといえます。クロスオーバーはこのトーナメント法では2つの生物個体が選出され，子供を作るときに必ず適応されます。クロスオーバーにより二つの生物個体が生ずることを増殖（reproduction）と言います。遺伝アルゴリズムではそのほかに突然変異（mutation）というオペレーションがあります。これは配列の形でコード化されている遺伝子の各ビットを，ある確率で0と1を反転させるというものです。確率はユーザーが事前に設定します。（普通はかなり低くする）遺伝子が操作された後，遺伝情報を解読し，それをもとに与えられた問題を解き，どの程度最適解に近づいたか，どの程度以前より向上したかを評価する必要があります。このように評価方法をプログラムしたものを評価関数（evaluation function）と言います。

遺伝アルゴリズムには染色体と遺伝子，前記のクロスオーバー，突然変異，増殖という遺伝子操作オペレーション，生物個体の人口（集合・population），そして遺伝情報を評価する評価関数が，プログラムを作る上での基本的な構成要素です。初期化の段階で遺伝子の遺伝情報をランダムに生成し，ユーザーが指定した人口の数だけ生物個体を作ります。これはプログラムに解法のさまざまなバリエーションを与えます。人口の中から良くない情報を取り除いて行き，またクロスオーバーや突然変異でさらにバリエーションを増やしていきます。その過程で良い遺伝情報を見い出し，その良い遺伝情報の変種を作っていくことで遺伝アルゴリズムは最適解を見つけ出していきます。人口が多いこと，つまり遺伝情報のバリエーションを広く持ちながら最適解を探すということは，局所的な解に陥らない良い方法です。このことを，冒頭に書いた世界一周のプランを立てるという例を用いて説明します。

遺伝アルゴリズムの強み

費用が一番安くて済むように，飛行機で，すべての国を訪問するためのプランを立てることが目的だとします。遺伝アルゴリズムはまず，100通りのプランを立てます。各ルートはランダムに選ばれたので最初は費用も高く，同じところを2度3度訪問するプランがあるかもしれません。ここで遺伝子とは国と国，都市と都市を結ぶルートと，それに係る費用だとします。生物個体はこの遺伝子，つまりルートと費用の情報の集合体である染色体を持ちます。100通りのプランとは100個の生物個体を用意するということです。様々なバリエーションの中から費用の安いプラン一つを選び，このプランの一部を他のプランの一部と交換していくことで，一番安いルートを見つけてゆきます。多くのプランを用意するということは，最適解を探す際にルートの見落としを防ぐことができ，比較的安いプランを立てることはできたが，一番安いプランは見つけられなかったという状況を防ぎます。このことが局所的な解に陥らないということです。広範囲に選択肢を設定し，その中から問題を解く鍵を絞り込んでいくことと，評価関数での評価が劣るものは，違う選択肢と入れ替えるということで，広い範囲を効率よく調査します。このことが遺伝アルゴリズムの強みです。

まとめ

以上述べてきたように，遺伝アルゴリズムは無限に近い組み合わせの中から，ユーザーが望む最適の組み合わせを見つけ出すことに威力を発揮します。その方法は，最初はあまり良い組み合わせでないものから，徐々にユーザーが望むような最適値に近づけようとします。それはまるで生物が自然淘汰されるように，徐々に，ある環境に最適な形態に向かって進化していくものです。このようなしくみをうまく利用して「遺伝プログラミング」や「人工生命」と呼ばれる研究も行われるようになってきました。遺伝アルゴリズムは，これからますます色々な発見や発明がなされ，エキサイティングな分野になっていくと思われます。もしかするとSF小説やアニメに出てくるようなロボットは，将来この分野の研究から生まれるかもしれません。

■参考文献

Goldberg, D.E., "GENETIC ALGORITHMS in Search, Optimization & Machine Learning", Addison Wesley, 1989

Ueda, K., Anderson, P.G., Biles, J.A., "Training Neural Networks Using a Genetic Algorithm and an Iterated Pseudo-Inverse", ASME Proceedings of the Artificial Neural Networks in Engineering (ANNIE '93), vol. 3, 1993, page 187-192,