コラム / 遺伝的アルゴリズム / 第3章

HOME 研究室概要 コラム 周辺探索 メンバー 掲示板 リンク

第3章 遺伝的アルゴリズムの特徴

 ここまで読んだ人なら、遺伝的アルゴリズムの考え方も、実際の動きも理解していただけたと思います。でも、他にもたくさんの探索法があるはずなのに、なぜ遺伝的アルゴリズムなのでしょうか? ここでは、そういう疑問にお答えするべく、遺伝的アルゴリズムの持っている特徴について説明していきます。

 このページの目次

3.1節 遺伝的アルゴリズムとその他の探索法との比較
3.2節 遺伝的アルゴリズムの特徴

 3.1節 遺伝的アルゴリズムとその他の探索法との比較

 遺伝的アルゴリズムが探索法であることは、ここまで読んだ方なら、たぶんわかっていると思いますが、遺伝的アルゴリズム以外にどんな探索法があると思いますか?

 世の中には、たくさんの探索法があるのですが、ここでは、代表的なランダムサーチ、最急勾配法(山登り法)と比較してみます。

『ランダムサーチ』

 ランダムサーチは、解の全ての可能性の空間を考え、その中から無作為に選び出した解が条件に適合するかを判定するという極めてシンプルな方法です。ただし、この方法では、ランダムに選ぶので、運が悪いと条件に適合する解がいつになっても見つからないという可能性もあります。

『最急勾配法(山登り法)』

 最急勾配法(山登り法)は、現在の状態からもっとも評価の良くなる方向へ変化させるというものです。どの方向でも評価が良くならなければ、その地点が答え(頂上)ということになります。もっとわかりやすく言いますと、自分の足下だけを見て、高い方高い方へと山を登っていく方法です。

 この方法は、初期地点によっては、評価の良い地点にたどり着いても、別の場所にもっと良い評価の地点がある場合があります。つまり、足下だけ見て山の頂上まで登ってみても、遠くを見るともっと高い山があったというようなことがあるのです。このような場合を局所安定とか局所最適などといいます。

最急勾配法(山登り法)

図.8: 最急勾配法(山登り法)

『遺伝的アルゴリズムによる探索』

 ランダムサーチ、最急勾配法(山登り法)ともに問題があるのですが、遺伝的アルゴリズムはどうなのでしょうか? 遺伝的アルゴリズムによる探索は、初期集団から選択と交叉の組み合わせにより並列的に山登り探索をし、なおかつ突然変異びよりときどきランダムな変化を起こしています。複数の解について並列的に調べていくため、最急勾配法のような局所安定には陥りにくく、それでも局所安定に近づいてしまっても、突然変異によってそこから抜け出すことができます。

 遺伝的アルゴリズムにももちろん問題があります。遺伝的アルゴリズムの問題は、個体数、交叉、突然変異の確率などのパラメータやコーディングの一般的手法が確立されていないことです。そして、必ず最適解を求めなくてはならないという場合には使えません。しかし、ある程度の基準以上の解をなるべく少ない計算量で求めたい場合には、良い手法だと云うことができます。

 3.2節 遺伝的アルゴリズムの特徴

 では、この章の最後に、遺伝的アルゴリズムの特徴について、まとめてみたいと思います。

○長所
 ・ 実用時間内に比較的優れた解を求めることができる。
 ・ 幅広い応用範囲を持っており、さまざまな問題に適応できる。
 ・ 多点探索アルゴリズムのため、関数の連続性の影響を受けにくい。

○短所
 ・ パラメータやコーディングに対する一般的な規範がない。
 ・ 問題に適用する一般的な方法が存在しない。

 今までは、遺伝的アルゴリズムの理論みたいなものについて、だらだらと説明してきましたが、次の最終章では、実際にナップサック問題と呼ばれる問題を遺伝的アルゴリズムを用いて解いてみようと思います。

ページの上へ 前の章へ 上のページへ 次の章へ


企画・製作 村上・泉田研究室 HP製作委員会(2001)
ご意見・お問い合わせは、こちら までどうぞ。