進化型計算

トップページ研究分野と周辺

進化型計算(Evolutionary Computing)とは、変化と選択に基づく世代交代により解が進化していく計算の総称である。遺伝的アルゴリズム(GA)は生物界の進化の仕組みを模倣しているが、タブー探索法(TS)等は、必ずしも自然界に実在する方法ではない。進化型計算は、問題の正確な解法とは異なる簡単な方法(メタヒューリスティックな方法)で、問題の近似解が求められる場合が多い事に魅力があり、1990年代頃から盛んに研究されている。

遺伝的アルゴリズム

タブー探索法

進化型計算の重要な条件として、解の一部(部分解)の評価に意味がある事が挙げられるだろう。出来の悪い解を選択という進化オペレーションにより改良するには、部分解によりその時々の解に優劣を付けなければならない。GAでは交叉により劇的に進化速度は向上するが、これは優れた部分解同士の組合せにより起こる。

例えば、最短経路探索問題では、部分的な経路が非常に短いものであれば、全体の経路長も短くなるケースが多く、部分解に意味がある。しかし、ジグソーパズルのように最後の数片を入れてみるまで部分解の価値が決まらないような問題には、進化型計算は有効ではないだろう。

遺伝的アルゴリズムとタブー探索法では解の探索方法に違いがあるため、問題の種類に応じてどちらが有利かは異なる。突然変異を導入するGAでは、解の一箇所が変わっただけで評価値が大きく変わるような問題は苦手とする問題(GA-hard)となる。TSでは一箇所の変化に対する全ての可能性を検討したりする(近傍解探索)ため、このような問題にも強い場合があるが、逆にGAのようなダイナミックな探索は出来ないという欠点もある。

また、探索が容易な問題でも全ての解の数が膨大な問題(解空間の極端に大きい問題)は計算自体に時間が掛りすぎて、有効な解に到達出来ないことも起こり得る。

このような限界はあっても、原則「解の数字列表現」と「評価関数の設定」さえ出来れば、非常に幅広い様々な問題に適用出来るという点で、進化型計算は重要な意義を有していると言える。

図は遺伝的アルゴリズムとタブー探索法を比較したイメージで、横軸に全ての解を何らかの規則で並べ(近くが近傍解)、縦軸は各解の評価値(上ほど良い)を取ったもので、中央に最良解がある(解は通常、離散的なので厳密には折れ線グラフ)。大抵の場合、最良解ではないが山を成す局所解があり、ここを抜け出して最良解へ導く手段(局所解収束の脱出)が進化型計算では課題になる。

近傍解へ動くTSは地を這うように局所解を脱出するのに対し、GAは交叉・突然変異で大幅に解の形を変え、飛ぶように脱出するといった違いがあり、対照的な探索方法をとる。

GAとTSの比較のイメージ図

対話型進化計算

進化型計算は多数の解を繰返し評価して初めて進化するが、高速な評価を行なうために評価関数をプログラム化する必要があった。しかし、例えば文章の優劣の評価のように、評価をプログラム化出来ない場合も多く、その場合はシステムが解を画面等に提示し、人間が点数を入力してシステムに戻す対話型進化計算(Interactive Evolutionary Computing)の構成を取る。評価以外の部分は通常の進化型計算と同様となる。

対話型進化計算

アクセスカウンター