第2章 遺伝的アルゴリズムの実装

遺伝的アルゴリズムのキモ

　本章では、GAのC言語による実際のコーディングを考えていく事にします。
　GAが問題解決に有用とされる重要な理由に、他の問題解決の概念に比べて動作が分かり易く、実装が容易な点が挙げられます。例えば、ニューラルネットワークとGAは両者ともほぼ同様の問題に対して適用が可能ですが、簡単に実装できる(利用できる)という観点から見た場合、GAに軍配を上げる事に多くの識者の同意を得られると思います。
　GAの実装において考えなければならない点は、主に次の4点です。

  1. 染色体の設計(評価値の算出方法も含む)

  2. 具体的な交叉の方法

  3. 具体的な突然変異の方法

  4. 集団の規模、生き残らせる個体の数、突然変異の確率など、システムのパラメータ

実際には1がほぼ全ての鍵を握っていると考えて頂いて結構です。1が決まれば、それに付随して2と3が決まるからです。また4は、得られる近似解の優劣や速度に関連するもので、あまり本質的な問題ではないといえるかも知れません。
　これらの点に注意しながらGAの実装を見てみる事にしましょう。

巡回セールスマン問題を解く

　まずは、1章で見て頂いたTSPを解くプログラムについて、実際に中身を見ていく事にしましょう。(sales.c参照)
　まず、セールスマンを個体と考える事にします。51行目以降に記述のある構造体individualは、個体を表現する為の構造体ですが、2つのメンバーを持たせています。1つは、この個体がどういった経路を移動するかについて、int型の配列で表現しようとするpathwayで、もう1つは、pathwayにしたがって移動を行った場合の移動コストの総計を格納するcostです。個体を規定している情報はpathwayですので、ここではpathwayを染色体としているわけです。


Fig.18 pathwayの表現例

　このプログラムでは、染色体pathwayは都市数分の配列になっていますが、これがどのように意味付けされているか(発現するか)を説明していきます。まず、対立遺伝子(遺伝子のバリエーション)として、都市の番号を持つものとします。15都市の場合、0から14までの15パターンです。次に、各遺伝子座の持つ意味として、遺伝子座の番号の都市にいる場合、次に訪れる都市を遺伝子として持つとしています。例えばpathway[3]=5を持つ個体の場合、3の都市に辿り着くと、次に5の都市を訪れるわけです。このように染色体を設計してあるので、例えば初期集団の生成は149行目以降のように行えます。(Fig.18参照)


Fig.19 巡回経路に現われない都市が存在する例


Fig.20 巡回経路が分断されている例

　次に、染色体pathwayから評価値costを算出する方法を規定する事にします。pathwayの設計上の問題として、個体の能力として必ずしも全ての都市を巡回できると保証されていない事が挙げられます。例えば、全ての遺伝子座が0の染色体を持つ個体の存在が可能ですが、この個体はどの都市を出発点にしたとしても、0の都市にやって来て、そこから動こうとはしません。したがって、移動した都市間のコストを加算するだけでなく、全都市巡回を行わなかった場合にペナルティとして大きなコストを加算する仕組みを導入します。こうして作成されたcost算出関数が70行目以降のcalculate_cost()です。最初に各遺伝子座に記された移動情報に基づいてmapから移動コストを拾い、加算していきます。それから染色体上に出現しない都市番号があった場合、ペナルティを加算し(Fig.19参照)、実際に都市0を起点に巡回を行って、全ての都市を通過したか検証し、非通過都市があった場合はまたペナルティを科す(Fig.20参照)としています。(実際には、2つのペナルティのうち、後ろの方だけで良いのですが、何かの参考になればと思い、残しています。) 因みにここでの評価値costは、値が小さいほど評価が高くなります。
　次いで交叉について考えます。染色体pathwayは1次元配列ですので、1点交叉がそのまま適用できます。GAの実装を簡単にしている大きな理由は、1点交叉という単純な実装でも、かなり使えるシステムが構築できる点に負うところが大きいと考えられます。通常の山登り法的な手法では、かなりの数学的素養を必要とするのに対し、1点交叉では119行目以降のcrossover()のような簡単なコーディングで良いのです。交叉により生成される染色体の両親を選び出す作業が、ga_next_genelation()の183行目以降で行われていますが、この作業は、優秀な両親を選び出す事が重要ですので、list.2のようなコードなどは、交叉をより有効に進めるのではないかと考えられます。
　突然変異についても、遺伝子座をランダムに選択し、ランダムに値を設定するという単純な実装を行っています。111行目以降のmutation()がそうなのですが、わずか1行のコードです。
　染色体、評価方法、交叉、突然変異が決まれば、あとは処理をループさせるだけです。このループがmain()の214行目以降のforループです。ga_ranking()により、集団内の全個体の評価を行い、順位付けをし、ga_next_genelation()で、交叉と突然変異を用いて次世代集団を生成します。こうして世代交代を繰り返す事で、より能力の高い個体の出現を待てばよいわけです。このプログラムでは、必要な能力を示す個体が出現した時点で終了するようになっていますが、例えば、214行目以降のforループをlist.3のようにすれば、設計したGAの枠組みの中で最も高い能力値の個体が出現するのを待つ事が出来ます。
　今回設計した染色体pathwayでは、先ほど述べた通り、全都市巡回できない染色体が存在してしまいます。15都市でのpathwayの全パターンが15^15であるのに比べ、実際の経路の全パターンは14!ですので、ほとんどのpathwayは全都市巡回すらできない事になります。このpathwayのように、染色体の表現が冗長過ぎる事は、GAの持つランダムサーチ的な側面を考慮すると、探索空間が広くなってしまう事から、明らかに良くありません。染色体設計時の注意点として覚えておいて頂くと良いでしょう。ただ、だからといって染色体の設計をむやみに難しくすると、コスト算出、交叉、突然変異のアルゴリズムが影響を受けますので、結局はバランス論といえるかも知れません。今回の染色体は1次元配列ですが、多次元配列やtree構造の染色体を利用する事も良く行われています。そうした場合は、当然、交叉や突然変異のアルゴリズムに工夫が必要になってきます。

倒立振子を制御する

　GAを実際に適用できる問題として良く知られているのが、制御問題です。ここでは代表的な制御問題として知られている倒立振子を例に、GAによって制御アルゴリズムが獲得される事を見る事にします。


Fig.21 倒立振子

　小中学生の頃の掃除の時に、箒を手の上に立て、バランスをとりながら何秒間耐えられるか競った経験が、皆さんにもあると思います。倒立振子とは、この遊びにそれらしい名前を与えたものと考えて下さい。(Fig.21参照)
　倒立振子の挙動を運動方程式で表現すると、

となります。この式は

x'' = f(F, θ, θ', θ'')
θ'' = g(F, θ, θ')

と表現できます。ある時点での倒立振子の状態は、x''とθ''からx'、x、θ'、θが決まるので、ここで問題なのはFをどのように与えるかという事になります。つまり、手を使って、棒にどのような力を加えれば良いかという問題なのです。Fを与えるにあたって参考となるのは、その時点での倒立振子の状態ですから、今回はその状態を表す情報のうち、x'、θ'、θを見てFを制御する事にします。そう考えると、この問題は

F = h(x', θ', θ)

として妥当である、関数hを求める問題であるともいえます。更に問題を単純化する為に、Fの大きさをある値に固定し、Fを加える方向のみの制御で目的を達成する事を考えます。


Fig.22 GAで倒立振子の制御則を得るサンプルプログラムの実行例

　それでは、サンプルプログラム(pendulum.c参照)について解説していきたいと思います。尚、サンプルプログラムの実行例はFig.22のようになります。プログラムの基本的な骨組みはsales.cと同じになっています。


Fig.23 状態空間分割の考え方

　まず、染色体の設計ですが、43行目以降に記述された構造体individualのメンバーの3次元配列controlが今回の染色体になります。関数hを表現する為に、x'、θ'、θによって構成される3次元空間を適当な大きさのマス目に区切り、そのマス目毎に出力Fの値をマッピング(Fig.23参照)する事にします。x'、θ'、θに基づいてcontrol内を検索すれば、Fの値が取り出せるわけです。このサンプルプログラムでは3次元空間を、x'、θ'、θ各成分方向に6区間となるように分割を行っています。この時、各成分上での分割が、正の領域と負の領域で対称であれば、特定のマス目の倒立振子の状態と、そのマス目を表すx'、θ'、θ各成分を符号反転したマス目の倒立振子の状態は、符号がすべて反転しているだけで、実際にはまったく同じ状態を表します。この性質を利用して、実装上のマス目の数を半減させる事にします。具体的には、θに関して負の領域のマス目を持たないとします。Fの大きさは固定するので、大きさは別途定めるものとし、control内の全ての要素は1もしくは-1とします。
　次に個体の評価方法ですが、これは今回の場合、倒立振子のシミュレーションを行って、実際にどれだけの時間耐えられるかを評価する事にします。83行目以降のcalculate_cost()では、5パターンの初期状態に対してシミュレーションを行い、結果の平均値を評価値に採用しています。各時点において加える力Fを、x'、θ'、θに基づいて、controlから値を取り出して求めています。シミュレーションの終了条件としては、

・手の位置が初期位置より±3m以上動いた。
・傾きが±π/6(30°)を超えた。
・設定時間の間、耐え凌いだ。

といったものを設定しています。長時間耐えれば耐えるほど良いのですが、適当な時間で終了させないと、calculate_cost()の実行時間が長くなり過ぎて、GA全体の動作速度が低下してしまうので、設定時間耐えたら終了にしています。シミュレーションにはオイラー法を用いています。
　交叉(165行目以降参照)には1点交叉を用いています。controlは3次元配列ですが、それを1次元配列に見立てて1点交叉を適用できるようにしてあります。また突然変異(157行目以降参照)では、controlの要素が全て1もしくは-1なので、符号反転を行うようになっています。今回は最優秀個体の染色体が突然変異によって破壊されないようになっています。
　このサンプルプログラムでは、次世代の集団を生成する225行目以降のga_next_genelation()にいくつかの工夫が加えられています。まず、生き残る個体の選別を、評価値の平均より成績が良かったかどうかで行うようにしています。この手法を導入する事によって、次世代の集団の評価値の平均を高める事をねらっています。例えば、一握りの個体が飛び抜けて高い評価値を持つような、エリート集団が存在する場合、生き残る個体の数が減り、結果的にエリート集団の子孫が増え、エリート同士の交叉による効果が高まる事が期待できます。しかし、エリート集団が小さすぎると、次世代の個体の染色体が似かより過ぎて、集団内の多様性が失われてしまう危険があるので、最低、集団の10%の個体を残すようにしてあります。また、新しく生成される個体の数が減ると、同様に集団内の多様性が失われてしまう可能性があるので、集団の60%以上の個体は残さないようにしています。更に、集団の60%以上の個体が平均値以上の評価値を持つような状態が何世代も続いた場合、集団内の多様性がすでに失われたものと判断し、集団の上位25%のみを残し、集団の25%に相当する数の個体を新たにランダムに生成し、残りをそれらの交叉で生成し、優秀な個体を残したまま集団の多様性を再確保する操作を行います。GA上では、集団の多様性を確保する為に突然変異があるのですが、突然変異は常に一様に働く為、集団内の多様性が危機的に失われた場合には役不足の感を否めません。したがって、場合によっては集団の一部をランダムに生成する操作が有効と考えられる事があります。
　ここでは制御問題へのGAの適用例をみてきましたが、GAを利用したプログラムで最も計算時間のかかる処理が評価値計算であることを理解してもらえたと思います。もし、シミュレーションを行うのに十分な情報がない場合などは、評価値算出に実際の制御対象(実機)を用いざるを得ず、評価値算出はますます困難になってしまいます。ただ、評価値算出では、全ての個体の評価値を求める必要がありますが、求める順序は関係ありません。したがって、並列処理が可能な環境下では、評価値算出部分を並列処理する事で高速化が可能であり、GAを高速化する場合の代表的な手法として利用されています。

モデリング時の諸問題

　GAの実装について、具体的に2つのケースをみていただきました。問題をGAの適用可能なモデルに変換する事ができれば、GA自体の実装は難しくない事が分かって頂けたでしょう。GAの利用において問題なのは、GAそのものではなく、如何に問題をモデル化するかなのです。ただ、GAに関しては、この部分の問題が染色体の設計に集約されているので、染色体の設計さえしっかりできれば良いことになります。そこで染色体の設計に関して、考え方をまとめておくことにします。

冗長性

　GAは、染色体の表現する空間内での探索問題を解くのが本質です。探索空間は狭い方が、より速く解を見つけられる可能性があります。したがって、染色体で表現される空間の広さ、つまり、染色体の全バリエーションを、なるべくなら小さくしたいわけです。TSPのサンプルプログラムの染色体設計では、ちゃんと巡回できないような染色体の存在が可能ですから、不必要に空間が広いといえます。逆に倒立振子のサンプルプログラムの染色体設計では、倒立振子の物理的な性質を考慮して、空間の圧縮をおこなっています。染色体を必要以上に短くすると、解の表現に必要な表現力が得られませんが、長すぎると解の探索が困難になります。対象となる問題の構造を理解しているほど、適切な染色体設計が可能になります。

染色体と交叉

　今回は1点交叉しか取り上げませんでしたが、そもそも交叉とは、2つの染色体から良いところを切り出して合成し、新しい染色体を作る操作ですから、いくらでもバリエーションが考えられます。例えば、染色体Aから奇数の遺伝子座を、染色体Bから偶数の遺伝子座を、それぞれ取り出して合成するといった操作も、交叉だといえるのです。無数にバリエーションを考えることのできる交叉ですが、どのような交叉を使うか考える時の基準は、適用対象となる染色体の構造に合っているのかどうかを判断材料にすることになります。


Fig.24 積み木理論

　GAがどのように最適な染色体を獲得していくのかを説明する「積み木理論」という考え方があります。例えば4つの遺伝子を持つ染色体があるとしましょう。ここで、最適な染色体が[ABCD]だとします。例えば、1番目がAの染色体は、そうでないものより少し評価が高くなるとすると、集団内の優秀な染色体をもつ個体に、1番目がAの染色体を持つものが増えていくと考えられます。同様の現象が、2番目がBという状況に対しても起こるとすると、はじめのうちは、それぞれの状態を持った染色体がバラバラに発生するのですが、交叉によって次第に2つの特徴を兼ね備えた個体が増えていくことが観察できるのです。つまり、最適な染色体の一部を持つ個体間の交叉によって、小さなブロックが集まって少し大きな塊になり、最終的に1つになるようなイメージで、集団内で染色体が組み上げられていく事で解が得られていると考えるわけです。(Fig.24参照)
　積み木理論を踏まえた上で交叉を考えると、一度構築されたブロックを壊してしまう可能性の高い交叉には問題があるといえます。例えば、隣り合った遺伝子が発現時に協調して働くような染色体の場合、先ほどの奇数/偶数で合成する交叉は、優秀なブロックを壊してしまう可能性が高いと考えられるので、利用に適さないと判断できます。この点、1点交叉は平均点以上の働きを期待できます。ブロックが連続した領域にあろうと、離れた2つの遺伝子だろうと、あらゆるブロックに対して壊す確率が一様だからです。特定の構造の染色体で有効に適用できる交叉を考えた場合は、それ利用するとして、そうじゃない場合は、1点交叉を利用しておけば、まず間違いないと思います。

表現力

　染色体の表現力は、得られる解に直結するので、重要な要素です。得たいと考えている評価値を持つような解を構造上表現できなければ、当然ながら何世代経っても解は得られません。表現力が足りないと考えられる場合というのも、実際には2つのケースに分けられます。
　まず1つめのケースは、単純に規模の問題から表現できない場合です。倒立振子のサンプルプログラムでは、本来連続な値である、x'、θ'、θといった量を扱う為に、区間分割による離散化を行いました。ここでは各成分に対して6区間での分割を行っています。もしこの分割が大雑把過ぎて、きめ細かな制御ができない為に、十分な評価値を持つ染色体が得られないと考えられる場合は、12区間分割などとする事で解決できます。
　もう1つのケースとして考えられるのは、そもそも染色体の設計に問題があり、本質的に表現できていない場合です。例えば倒立振子で、θを考慮しない染色体を設計した場合、いくらx'、θ'の区間分割を細かくしても、十分な解は得られないでしょう。こうした場合は、対象となる問題の捉え方を間違えているという事になりますから、もう少し注意深く問題について考える事が必要です。