遺伝的アルゴリズム

トップページ研究分野と周辺進化型計算

遺伝的アルゴリズム(Genetic Algorithms:GA)は、生物界の進化の仕組みを模倣する解探索手法として、1975年にミシガン大学のJohn Hollandが提案した。解の探索を原則「偶然の変化」と「たまたま良く出来たものの採用」で行なうため、当初は「こんな偶然に頼る出鱈目な方法がアルゴリズム(計算手順)と言えるのか?」と厳しい批判にさらされたと言われる。

しかし、Holland一派の考えは間違っていなかった。1990年代に入るとGAは人工知能の主要分野に躍り出て、世界中で研究が行なわれるようになった。背景にはコンピュータの計算速度の飛躍的向上がある。生物の進化と同様、GAの進化には非常に多くの繰返しが必要な事を、批判していた人達は気付かなかったのである。

遺伝的アルゴリズムのソース・コード(プログラム)の一例

単純GAの処理の流れ

最も単純なGAは、出鱈目な初期解群生成→各解の評価(点数付け)→点数に基づく選択淘汰→進化オペレーションによる解の変化→各解の評価(点数付け)を図のように一定回数繰返し(世代交代)、最終世代の最良解が最終的な解答となる。

図は、一世代の個体数が6、選択淘汰の方法に「ルーレット選択」、進化オペレーションに「一点交叉」と「突然変異」と「エリート保存」を用いた例となる。

解の数字列表現

GAではまず、解を数字で表現する方法を考えなければならない。例えば「一定以下の重さ(或いは容量)で、どういう商品の組合せが最も価値が高いか?」(ナップザック問題)を解く場合、選択可能な商品に名前に代わる通し番号を付け、その数字の組合せ(例えば1番と3番と5番を選べば、1、3、5等)が解の数字列表現となる。

一回ずつ訪問する複数の場所に対してどのような順番が最短経路になるかという問題(巡回セールスマン問題:TSP)では訪問箇所に通し番号を付け、3→5→2→1→4等の数字列が一つの解になる。勤務表作成問題であれば、社員に通し番号を付け、社員番号+出勤時刻+退勤時刻を人数分並べたものになる。

数字列に実数を用いる場合を実数型GA、実数を二進数に変換した0と1の並びで表現する場合をバイナリ型GAと呼ぶこともある。また数字列の長さが一定のGAを固定長GA、解により長さが変わる場合を可変長GAと呼ぶ。

評価関数と致死遺伝子

一つの解を受け取り、それに点数を付ける関数をプログラム化する必要がある。ナップザック問題は、各商品の価値をデータとして用意しておいて、一つの解で選ばれている商品の価値の総和が点数となる。巡回セールスマン問題では、各訪問箇所の座標を用意して、或る解に於ける訪問順序に従って経路長を求める(ピタゴラスの定理等を使う)が、短いほど得点を高くするため経路長の逆数を評価点にしたりする。勤務表問題では評価関数は複雑になり、人件費を抑えたい場合は総勤務時間の短いものほど良くしたり、サービスレベル向上を重視する場合は逆に単位時間当たりの出勤人数等で評価したりする。

複数の観点から解を評価する必要がある複雑な問題である程、評価関数の設計もより難しくなる。点数は大小の比較出来る一つのスカラー値にする必要があるため、重み付け等で調整する。さらに、文章の優劣等、アルゴリズム化出来ない問題も多く、その場合は解の評価部分だけを人間が行なう対話型GAの適用となる。

最適化問題にGAを応用する場合、或る条件に合わない解は無条件に除外する場合があり、これを致死遺伝子という。例えばナップザック問題に於いて一定の重さや容量を越えてしまう解等が該当する。致死遺伝子は評価点に0点を付ける等、選択に掛らないようにしたり、初期解生成や進化オペレーション自体に工夫して最初から発生させない等の対応を取る。

初期解生成

まず一つの世代を構成する解の数(個体数)を決める。単純なGAでは個体数は世代交代を経ても一定だが、世代毎に個体数の異なるGAを構成する事も可能である。通常は数十~数百のレベルが多い。次に、決めた数だけ初期解を生成するが、概ね全く出鱈目に行なわれる場合が多い。

ルーレット選択

選択法にも何種類もあるが、代表的なのがルーレット選択で、解の評価値に比例して、次世代に残る確率が決まる。イメージとしては図のように、評価値に応じた長さを持つように解を並べ、ランダムな位置に矢印を当てる。個体数分の矢印を当て、次の世代を決める。少しは評価値の低い解も残すようにするのは、今のところ悪い解でも或る部分が変化する事によって突然優秀な解に化ける事があり、その可能性を残すためである。

ルーレット選択の図解

交叉と突然変異

交叉は左図の様に二つの遺伝子(解)の数字列の一部を交換し、新しい遺伝子を作る。生物界では雌雄による子の生成に相当する。例は切断箇所が一箇所なので一点交叉と呼ばれる。切断点の数により二点交叉、多点交叉等がある。

右図は順序交叉である。これは解の数字列に重複が許されない問題(順序を決める問題等)に用いる。上の遺伝子の赤線から右側が、7,6,0,4,5だとすると、この数字の組合せは変えず、下の遺伝子において、これらの数字がどんな順番になっているかを見る。他の数字を除外すれば、左から6,5,0,4,7なので、その順番に並び替える。下の遺伝子も同様に、赤線から右側の自分の数を上の遺伝子の並び順で入れ替える。

突然変異(真ん中の図)は、或る解の一部をランダム(出鱈目)に他の数字に変える。生物界では放射線や活性酸素等による遺伝子の切断等に相当する。

交叉の切断箇所、切断箇所の数、突然変異の箇所と箇所数、交叉するペアの組合せ、或る解に交叉、突然変異処理を加えるか否か(この確率が交叉率、突然変異率)等は、その都度ランダムに決める場合も多い。ここにはあまり規則性を導入しないほうがよい。突然変率は5%程度の比較的低い確率(あまり突然変異ばかりしていると進化しない)、交叉率は80%以上等の比較的高い確率を用いる場合が多い。

エリート保存

エリート保存は各世代の最良解は交叉にも突然変異にも掛けずに次世代に残す、という方法である。必須の進化オペレーションではないが、導入メリットとしてはどこで打ち切っても、それまでの最良解を出力出来る事にある(導入しない場合は、若干の上下をしながら全体としては右肩上がりの進化となる。プログラムは一定世代で打ち切るため、場合により少し前の最良解より悪い解を結果として出力する事になる)。

改良型遺伝的アルゴリズム

上記の方法は最も基本的な遺伝的アルゴリズムの仕組みで、シンプル(単純)GA(SGA)等と呼ばれる。
しかし、SGAは意外と局所解からの脱出が困難であったり、突然変異率等、様々なパラメータの選定が困難である等の課題も多かった。
或る最適化問題等に、単純にSGAを適用しただけでは、充分な効果が得られない場合も多い。
これらの課題を克服するため、様々な改良型遺伝的アルゴリズムが開発されている。

様々な選択・交叉・突然変異

実数型GAに於ける交叉法の改良

島モデル(並列分散GA)とMGGモデル

パラメータフリーGA(PfGA)

アクセスカウンター アクセスカウンター