はじめに
「遺伝的アルゴリズム（Genetic Algorithms：以下、本文中では"GA"と表記）」……分かるような、分からないような微妙な名前ですね、ほんとに。まったく聞いた事のない言葉だったら変な先入観も持てませんが、なまじ知られている言葉が合体しているだけに、初めて接する人なんかは想像心が掻き立てられるのではないでしょうか？
GAとは端的に表現すると、「ダーウィンの進化論の概念を用いて、そこそこ難しい問題の答えを自動的に見つけてくれるアルゴリズム」です。日本ではここ数年、応用や実装手法に関する研究が進み、書店の理工学書の棚でGAに関する書籍を目にする事も多くなってきました。露出度が高くなった分、名前だけは聞いた事があるという人も多いのではないでしょうか？
本稿ではこのGAについて、なるべく楽しげに解説したいと思います。よろしくお付き合い下さい。
遺伝的アルゴリズムとは何に使えるのか
現在では、さまざまな分野でコンピュータが使われる為、作成されるプログラムも多岐にわたっています。基幹業務用データベースシステムの構築、株価予測、エレベータ管理、建築設計、etc… それぞれの分野でのプログラム作成には、プログラミングの知識だけではなく、対象となる分野に関する理解が必要不可欠です。それを踏まえた上でプログラムとは何かを考えてみると、これらのプログラムに共通して要求されている要素として次のようなものを挙げる事ができます。
1：人間の作業を支援する事が求められている。
2：人間の作業の肩代わりを期待されている。
それぞれの要素には、それを支えている概念が存在します。例えば、ワープロや表計算といったソフトウェアの設計思想は、1に対する要求の答えとして存在しています。ワープロを使えば、手書きよりも効率良く文書を作成できますし、表計算ソフトを使えば、電卓を叩きながら帳簿を埋めていくよりも速く仕事を終わらせる事ができます。また、OCRや自動翻訳に関する技術は、2を支える技術と言えます。OCRソフトは紙資料のコンピュータへの打ち込みを肩代わりしてくれますし、自動翻訳ソフトは英語の苦手な人が英語の文献を読む事を可能にしてくれます。
こうした観点から見ると、GAは、2を支えるという意味合いの強い技術です。GAのような技術は、よく十把ひとからげに「人工知能」というキーワードで括られる事が多く、私個人はそうした風潮を快く思っていないのですが、こう言った方が直感的なイメージは湧き易いかも知れませんね。
それでは、実際にGAが適用できそうな問題について、もっと具体的に見ていく事にしましょう。恐らく本誌読者の方のほとんどは、何らかの形でプログラミングをされる方々だと思いますので、次のような体験がある方も多いと思います。
CASE1：大量のデータを扱うプログラムの作成
動的に変化しないデータを、繰り返し検索するようなプログラムを作成する事になりました。作成中はテスト用の小さいデータを使っていたので、問題は表面化しなかったのですが、実運用時の巨大なデータを扱うようになってから、データの並びが動作速度に影響する事が判明しました。データを最適な順列に並べ替えるアルゴリズムは、ソートみたいな感じで考案する事が出来たのですが、このアルゴリズムで実運用時のデータを処理しようとすると、利用できるコンピュータで最速のものを用いても、3日ぐらいかかってしまいます。せめて半日ぐらいでデータを並べ替える手法が欲しいのですが……
CASE2：データ列の数式化
あるシステムのさまざまな状態を記録した膨大なデータがあります。状態を表現する値の中の2つの要素、xとyの間にy=f(x)と表現できる因果関係がありそうです。システムに関する考察を進めた結果、f(x)は3次式らしいという事は分かったのですが、y=ax^3+bx^2+cx+dとした場合のa、b、c、d各係数を、実際どんな値にすれば良いのかが分かりません。
CASE3：シミュレーション
球や直方体のような、さまざまな単純形状の物体に対して風洞実験を行った膨大なデータがあります。このデータのおかげで、どのような条件下でどの程度乱流が発生するかを予測できるようになりました。そこで次は、複雑な物体のアウトラインだけを人間が決定すれば、どのような単純形状で各部を構成すれば乱流の発生が抑えられるかを、自動的に判断して最適な設計を出力するような事が出来ないかと考えているのですが……
（事例として挙げるには、CASE3以外は抽象的すぎたかも知れませんね。業界を問わずイメージを共有してもらえるようにと考えてみました。）
世の中には、「規模が小さければ人間にも解けるが、規模が大きくなると実質的に解けなくなる」タイプの問題がたくさんあります。CASE1はそうした問題の典型で、データが少なければ、データの順列を人間が並べる事も可能でしょうし、その時の評価方法をそのまま自動化したアルゴリズムで、ある程度の規模までは対応可能です。CASE2についても、f(x)が1次式なら、x-y平面にデータをプロットして直線を引き、直線の傾きとy軸との交点を求められるので、「規模≒問題の複雑度」と考えれば同じような問題といえます。CASE3では、ケースバイケースの対処方法を経験として持っている設計者のスキルを当てにする事は可能でしょうが、具体的にこうした手順で設計すれば良いというガイドラインを設定するのは難しいと考えられるので、規模が大きくなった時の人間の設計が、どの程度最適かは未知数でしょう。
どのケースも、プログラム上で表現できる程度は問題の定式化が行われていますので、答えの候補全てをしらみつぶしに評価するようなアルゴリズムによって解答を得る事ができそうです。実際CASE1ではそうした手法での処理を試みています。しかしこうした問題では、理論上はそのアルゴリズムで解答を得られる場合でも、実際には要求された時間内に解答が得られない為に、そのアルゴリズムでは問題解決が事実上不可能とみなされる事が多いのです。
こうした問題の解決に際しては、「本当の最適解でなくても良いので、一定以上の成績を出せる解が欲しい」場合がほとんどです。GAは、こうした種類の問題にたいして有効に適用できる手法の一つです。つまりGAは、真の最適解が得られるかは分からないが、比較的短時間で、望む成績を上げられる近似解を得る為の手法だといえます。
巡回セールスマン問題を解く
それでは実際にGAが活躍するところを見てみる事にしましょう。
ここでGAに解いてもらう問題は「巡回セールスマン問題（Traveling Salesman Problem：以下、本文中では"TSP"と表記）」です。
TSPとは「各都市間の移動コストが設定されたn個の都市全てを、各都市1回ずつ訪れるものとし、最小のコストで巡回する経路を探す」という問題です。現実問題に置き換えると、「都内各地を地下鉄のみで移動しなければならない」といった感じでしょうか。
Fig.1 都市間の移動コストを行列表現したもの
Fig.2 都市間の移動コストを視覚化したもの
「それぐらいだったらコンピュータに頼まなくても自分で解けるよ」とおっしゃる方もおられるかも知れません。が、Fig.1、Fig.2を見てもそう言える方はなかなかおられないでしょう。今回コンピュータに解いてもらう15都市について、各都市間の移動コストを行列表現したものがFig.1（但し、0は移動できない事を示す）、それを都市間を結ぶ線の太さ（太い方が移動コストが低い）で表現したものがFig.2になります。15都市でさえこれ程ですから、50都市、100都市といった問題を、人間が手で解く事など事実上不可能でしょう。つまりTSPは「規模が小さければ人間にも解けるが、規模が大きくなると実質的に解けなくなる」タイプの問題といえるのです。
Fig.3 sales.c（GA）の実行例
それでは、お手持ちのCコンパイラでsales.cをコンパイルし、実行してみて下さい。実行した結果は例えばFig.3のようなります。この結果によると、80というコストで[0->2->1->6->12->14->7->3->11->9->8->5->13->4->10->0]という順路で一周出来る事が分かります。
※この実行例はBCB/BCCでコンパイルした場合の例です。他のコンパイラを使用した場合には結果が異なる可能性があります。その場合、29行目のSTOP_COSTの定義が80のままだと、プログラムが終了しない可能性があります。STOP_COSTを80より大きくして試してみて下さい。
このサンプルプログラムは、TSPを解く為の調整が加えられていないので、あまり良い答えを出せないのですが、それでも80という成績を出す能力はあると納得頂けるでしょう。
Fig.4 sales.c（厳密解）の実行例
GAを利用したプログラムの動作を見てもらった上で、次は全移動経路を検索して厳密解を求めるプログラムを見て頂きます。この問題の厳密解を求めるプログラムをsales.c内に付けてありますので、13行目の"#define GA_PROGRAM"をコメントアウトしてコンパイル、実行してみて下さい。結果はFig.4となり、厳密解におけるコストは24となります。しかも、GAを利用したプログラムがコスト80の答えを見つけるのに17秒を要したのに比べ、1秒もかからず答えを出しています。これではGAを使う意味がありません。
Fig.5 sales.c（GA）の20都市での実行例
Fig.6 sales.c（厳密解）の20都市での実行例
ここで、問題の規模を少し大きくしてみます。今度は20都市の問題を設定して比較してみる事にします。再び13行目の"#define GA_PROGRAM"を有効にし、14行目の"#define RAND"を有効、17行目のTOWN_COUNTを20に設定、29行目のSTOP_COSTを170に設定してコンパイル、実行して下さい。結果はFig.5となり、コスト165の答えを18秒で得られたと分かります。 では先ほど優秀であった厳密解を求めるプログラムの結果はどうなるでしょう？先ほどと同様に、13行目の"#define GA_PROGRAM"をコメントアウトしてコンパイル、実行してみると、結果はFig.6のとおりです。コスト41というGAに比べてはるかに優秀な答えを得ていますが、実行時間を461秒も要しています。15都市では1秒もかからなかったのに、この実行時間の爆発的増加は一体何からくるのでしょうか？
Fig.7 15都市問題における全経路数
厳密解を求める為には全ての移動経路を評価する覚悟が必要です。つまり15都市の規模なら、14!通り存在する経路(Fig.7参照)全てを評価しなくてはならないわけです。同様に20都市の規模なら、経路は19!通りになります。ここで経路数が何倍になっているかを考えると、大変な事が判明します。19! = 19 * 18 * 17 * 16 * 15 * 14! なので、実に経路数は1395360倍(!)になっているのです。これでは、30都市の問題を解くのに何年もかかってしまいそうです。このようにTSPでは数十都市程度の規模でさえ厳密解を求める事が困難となり、何らかの近似解を得られる手法、例えばGAの利用が必要とされるのです。
実は、「規模が小さければ人間にも解けるが、規模が大きくなると実質的に解けなくなる」タイプの問題のほとんどは、TSPと同様の性質から、厳密解の取得に必要な計算量が指数対数的に増加する事が知られています。したがって、解の精度を幾分犠牲にしても、与えられた計算量の中で解を求められるGAのような手法が有効とされるのです。
問題解決とは何か
ここまでの話の中で、さかんに「問題」という言葉を使ってきましたが、そもそも「問題」とは何なのでしょう？一般的化された「問題」という概念と、それを「解決」する事について少し考えてみます。
まず、ここでいう「問題」というものには答えが存在すると考えられます。もしかしたら、人生という問題に答えは存在しないかも知れませんが、そうした問題はここでいう「問題」には含めないものとします。
Fig.8 「問題」の例
また逆に、答えが存在している事は分かっていても、答えそのものが分からない場合が「問題」なのだという事ができます。近所に何軒かあるスーパーの中で、今日現在、一番キャベツの安い店は確かに存在しますが、実際にどこの店がそうなのかは、調べてみないと分かりません。(Fig.8参照)
「問題」の答えそのものが分からないという事をもう少し具体的にすると、答えの候補の中のどれが答えなのかが分からないという事だといえます。近所のスーパーを具体的に想像する事は可能ですし、TSPにおける全経路も別に隠されているわけではありません。一般的な数学の問題についても、例えば答えがaという実数なのであれば、答えaの候補が全実数と考えられ、やはり答えの候補が存在しているといえます。
通常、全ての答え候補の中で唯一存在するのが「厳密解」という答えです。よく数学の問題は必ず唯一の答えが存在するという事が言われますが、その時の答えとは、この厳密解を指しているのです。つまり、1+1の厳密解は2となります。Fig.8ではＸＸストアが厳密解といえます。
一方、答え候補の中で設定された条件を満たしている複数の候補が「近似解」です。例えば、1+1の近似解として、条件を厳密解の±0.1の範囲内とした場合、2.05や1.99などが近似解となります。先ほども解説したように、問題によっては厳密解を求める事が大変困難となる為、近似解で我慢しなければならない場合があります。Fig.8においても、時間が無いので全ての店で価格を調べる事ができない場合、140円以下だったら買うという条件を設定すると、ＸＸストアかスーパー△△で買う事になります。
厳密解、近似解という考え方を踏まえた上で答えというものを考え、集合の概念を導入すると、以下のように整理できます。
・答えの候補の集合が存在する。
・各候補は、答えという観点から評価される値を持つ。
・集合内で、最も評価の高いものが、厳密解である。
・集合内で、一定以上評価の高いもので構成される部分集合が、近似解である。
こうしてみると、厳密解、近似解に関わらず答えを求めるという事、つまり「問題」を「解決」する事は、答えの候補の集合から部分集合を得る行為といえます。そう考えると、問題解決の手法、すなわち解法は、この部分集合を得る為の手順(アルゴリズム)だという事になります。
Fig.9 状態空間と評価値曲面
Fig.10 厳密解
Fig.11 近似解
Fig.12 「状態空間と評価値」の例
問題解決の手法
ここでもう少し幾何学的に具体的な見方をしていく事にします。まず、答えの候補の集合が構成する空間を「状態空間」とします。すると、それぞれの候補が持つ、解としてどれだけ適当かを表す「評価値」は、状態空間上に曲面(解曲面)を構成します。Fig.9は、状態空間が1次元の場合の例になっています。この場合は状態空間が1次元の為、その上での曲面は曲線で表現されます。この図の上での厳密解は、解曲面(曲線)上で最高の評価値を持つ答えの候補となり(Fig.10参照)、近似解は、評価値軸上に設定されたしきい値を超える答えの候補の集合(Fig.11参照)として表現されます。具体的な例として、Fig.12を挙げておきます。状態空間と評価値の関係を図示するこの概念は、「問題」という抽象的な概念を、具体的に数学的手法で扱える形式に変換した結果得られたものといえます。
ここで注意しなければならないのは、評価値による解曲面はあくまでイメージであって、本稿で対象とする、そこそこ難しい問題においては、簡単に図のようには見る事ができないという事です。個々の答えの候補の評価値を求める事は可能ですが、それらからなる解曲面の式は簡単には求める事ができません。逆に、解曲面の式が得られれば、厳密解も近似解も思いのままです。
解曲面の存在をイメージしながら、実際には個々の候補の評価値を求める事しかできない状態で、評価値の高い解を求める方法を考える事にします。また、具体的なイメージを持ってもらう為に、状態空間を地域、評価値を土地の高度と考え、問題解決を地域内で最も高い場所を探す行為に喩えながら話を進めていく事にします。
Fig.13 しらみつぶしに厳密解を求める
まず、厳密解を求める手法として、状態空間内の全ての場所で評価値を算出し、その結果から解曲面を得るという手法が考えられます。地域に測量隊を送り込んで、地域の詳細な地図を作るわけです。この手法は確かに手堅いのですが、地域が広くなると測量点が増加する為に莫大な時間を費やします。(Fig.13参照)
Fig.14 ランダムサーチで近似解を求める
次に「ランダムサーチ」という手法を考える事ができます。ランダムサーチとはその名のとおり、ランダムに候補を抽出、評価値計算し、求める評価値以上の解を得るまで続けるという手法です。地域の上空から高度計を持った人を1人ずつ順番にパラシュート降下させ、降りた場所の高度を連絡してもらい、その高度が設定高度以上になるまで続けるわけです。全ての解候補を網羅的に調べる厳密解方式に比べると、近似解を求めるのであれば上手く機能しそうです。これは、状態空間内全ての場所での評価が必要な厳密解方式に比べ、予め設定したしきい値を超える解が得られた時点で探索を打ち切れるランダムサーチの方が有利な為です。ただ、ランダムサーチでは、評価値に科すしきい値を高くすれば高くするほど、評価値算出の量が増加します。これは、しきい値を高くする事によって近似解の個数が減り、解の出現確率が低下する為です。(Fig.14参照)
厳密解を求める手法とランダムサーチは、言わば対極を成す考え方です。しかし、この2つの手法は、解曲面に関する条件や知識を全く必要としない点では共通しています。そこで、解曲面に関する条件や知識を利用したスマートなやり方を考える事にします。
Fig.15 山登り法で近似解を求める
例えば、一般的に解曲面は連続である(平面、もしくは滑らかな曲面で構成される。切り立った崖のような部分を含まない。)事がほとんどです。そこで「山登り法(Fig.15参照)」という手法が考案されました。これは、ランダムに選んだ場所を出発点として、現在自分のいる場所の傾きを調べ、上に向かって歩いていくという手法です。自分のいる場所の傾きを得る事が必要になりますが、これは、周囲の高さを調べる事で分かります。また、そうして辿り着いた場所の傾きが0になった場合、山の頂上に辿り着いた事が分かります。この方法であれば、ランダムサーチとは異なり、闇雲にではなく目的を持って状態空間内を移動し、評価値計算を行うので、計算量を抑えられる可能性があります。したがって、速く解を見つける事ができる可能性があるのです。しかし、この山登り法にも欠点があり、局所最適解に陥り易い事が知られています。局所最適解とは、地域内にいくつも山が含まれるような場合に、最も高い山でない山に登ってしまう事をそう呼びます。山登り法の探索を開始する初期位置はランダムに決めるので、最初の位置がどの山の麓かで、登る山が変わってしまうのです。また山登り法は、人間の問題解決手法のモデルとして論じられる事もあります。例えば、サッカーで上手くボールを蹴れるように試行錯誤する場合、蹴り方を少しずつ変えてみて、調子の良い蹴り方を選ぶという事を繰り返し行い、蹴り方を学習していきます。この過程は、まさに山登り法といえます。
ここまで見てきたように、問題解決は、解曲面上の探索問題に一般化でき、さまざまな探索手法が利用できます。本稿で解説しようとするGAも、こうした観点から見ると、解曲面上の探索手法の一種なのです。
遺伝的アルゴリズムの仕組み
それでは、実際にGAの仕組みについて解説する事にします。冒頭で、GAとは「ダーウィンの進化論の概念を用いて、そこそこ難しい問題の答えを自動的に見つけてくれるアルゴリズム」だと述べました。そこで、GAの「遺伝的」な部分を見ていく事にします。
Fig.16 遺伝子による進化のしくみ
まず、簡単に本物の遺伝子の話をする事にしましょう。地球上の生物の形状を決定している設計図にあたるものが、俗にいわれる遺伝子(gene)です。生物の体の中では、遺伝子に関するさまざまな機能が働いているのですが、GAでは特に染色体(chromosome)という遺伝子の集合体を参考にしています。染色体をC言語での配列に喩えると、
gene chromosome[LENGTH];
といった感じになります。また、遺伝子は4種類ある蛋白質の何れかなので、geneは列挙型だと喩えられるかも知れません。遺伝子の取り得るバリエーションの事を対立遺伝子(alles)、染色体上の遺伝子の位置を遺伝子座(locus)といいます。染色体上の遺伝子は、遺伝的形質の保存を役割としています。例えば、5番目と11番目の遺伝子がAであった場合、髪の毛の色が黒になるなどといった具合に、情報を保持しているわけです。この染色体は同一種でも個体(individuals)によって異なり、子供は両親の染色体を半々で受け継ぎます。また染色体上の遺伝子は極まれに突然変異(mutation)を起こす場合もあり、両親とは異なる遺伝子を持つ子供が生まれる事もあります。(Fig.16参照)
一方、ダーウィンは、同一種においても形質の差違が存在し、形質上、環境に適応している個体ほど生存率が高くなる事を論じました。更に、生存率が高ければ、子孫を残す確率も高くなるので、環境に変化が無ければ、世代を経る毎に、環境に適応した形質の個体の割合が、種の中で高まっていくと考えました。
この2つの考え方を組み合わせると、生物種において、特定の形質が生存に有利であった場合、その形質を発現させる遺伝子を持つ個体が増える事が考えられます。GAはこの考えに基づき、次のような操作を行います。
1：状態空間を表現するように染色体を設計する。
2：さまざまな染色体を持つ個体の集団(population)を生成する。
3：各個体は染色体の発現によって異なった形質を示すが、それを評価値に換算する。
4：評価値の低い個体は死滅する。
5：生き残った個体を交配し、新たな染色体を持つ個体を生成する。
6：低い確率で、ランダムに選んだ遺伝子座が突然変異を起こした個体を生成する。
7：3に戻る。
先ほどまでの喩でいうと、次のように表現できます。
A：地域内から100地点をランダムに選び、初期の観測点集団とする。
B：各地点の高度を求める。
C：下位50地点の観測点を撤収する。
D：残した観測点の任意の2点を選び、その中間辺りに新たな観測点を設置する。撤収した観測点と同じ数の新たな観測点を設置する。
E：約5地点をランダムに動かす。
F：Bに戻る。
Fig.17 GAで近似解を求める
ここでは、評価値の高い個体は、染色体に優秀な部位を持つと考えるので、評価値の高い2つの染色体を合成する事で、より優秀な染色体を得られる可能性があるわけです(Fig.17参照)。この考えに基づき、5(D)の操作を行っています。Dにおいては、同じ山の異なる斜面に設置された2つの観測点の中間点が、より頂上付近に近づく事がイメージしてもらえると思います。この2つの染色体を合成する操作の事を、交叉(crossover)と呼びます。最も基本的な交叉ルールとして、染色体上のランダムに決めた位置によって染色体を分割し、一方の前半部分ともう一方の後半部分を繋ぎあわせて、新しい染色体を生成する操作があります。この交叉ルールの事を1点交叉と呼びます。
また、3(B)-7(F)のループによって世代交代が進んでいった時、基本的に個体の分布状態は収束していくので、先に述べた局所最適解に陥る可能性が皆無ではありません。そこで、6(E)の突然変異によって、集団内の多様性を確保しようとしています。突然変異によって厳密解の近傍の個体が得られれば、その個体を足がかりにして、より良い解が得られると考えられます。
交叉は、山登り法のように、高そうだと思われる所を探す操作であり、突然変異は、ランダムサーチのように、範囲内の一様な探索を行う為の操作といえます。GAは、この2つの相反する戦略をバランス良く使う事で、効率的に探索を行おうとするものです。
このようにGAは、生物進化モデルの仕組みを、そのまま問題解決に流用したものといえます。