遺伝的アルゴリズムに関する基礎知識を解説｜遺伝的アルゴリズムの欠点とは

遺伝的アルゴリズムとは

遺伝的アルゴリズムとは生物の進化を模倣したアルゴリズムです。遺伝的アルゴリズムは1975年にミシガン大学のホランド教授の著書において提唱されたものです.

その後、人工知能研究に影が薄くなっていましたが、ニューラルネットワークの流行で再び注目されています。具体的には自然界では生活環境に適応できない個体は死滅してしまいますが、環境に敵推した個体は生存し、子孫を増やします。

このメカニズムをモデル化し、問題に対し最もよく適応する個体、すなわち最適解をコンピュータ上で生成しようという考え方です。

遺伝的アルゴリズムの概要4つ

遺伝的アルゴリズムとは、遺伝子を模したデータ（個体）を、生物の進化のアルゴリズムを用いてより優位性の高い個体へと進化させることを言います。

様々な方式を使い、より優勢性の高い個体を交叉や突然変異などの遺伝子を操作し、世代交代を繰り返しながら近似解を探索します。

優位性は評価関数によって数値化されます。また、解の表現方法次第で、組合せ最適化問題やNP困難な問題などの解決に応用することが可能です。

1：単純GAの処理フロー

単純なGAは、デタラメに生成された初期個体群をもとに行われます。

デタラメな初期個体群の生成、各個体群の点数付け→点数に基づく次世代生成、交叉→変化した個体群の点数付け→ 点数に基づく次世代生成、交叉を一定回数繰り返し、最終世代の最も優秀な個体が最終的な解答となります。

2：解を数字で表現する方法

遺伝的アルゴリズムでは、解を数字で表現しなければなりません。

例えば、先程の単純GAの処理フローであれば、生成した各個体群に通し番号をつけ、解を数字で表現できます。（1の個体が最も優秀であった等）このように実数を用いて表現することを実数型GAと呼びます。

その他の方法として、実数を二進数に変換し表現する場合をバイナリ型GAと呼びます。数字列が一定の長さの遺伝的アルゴリズムを固定長GA、長さが変わる遺伝的アルゴリズムを可変長GAと呼びます。

3：致死遺伝子と評価関数とは

各個体に点数を付ける際に、評価基準が必要です。また、その評価基準を関数にしプログラム化します。

評価する観点が多く複雑な問題である程、評価基準を関数にしプログラム化することが難しくなります。また、文章の優劣などのプログラム化できない場合は、各個体の点数付けだけを人間が行なうことがあります。その評価方法を対話型GAと呼びます。

遺伝的アルゴリズムを応用する場合、条件に合わない個体を無条件に排除する場合があります。除外する個体を致死遺伝子と呼びます。

致死遺伝子は、初期個体群や次世代生成の際にできる限り生成されないようします。また、発生した場合は、0点を付ける、選択に掛らないようするなど対応します。

4：初期解生成とは

一つの世代を構成する個体群の個体数を決め、その個体数の初期解を生成します。

多くの場合は全くのデタラメに生成されます。また、通常は数十〜数百のレベルで生成されます。

遺伝的アルゴリズムに対する改良型遺伝的アルゴリズムとは

改良型遺伝的アルゴリズムとは、様々な課題を克服するために改良した遺伝的アルゴリズムのことです。

単純GAだけでは、局所的な解から脱出ができなかったり、突然変異率などの様々なパラメータの選定が困難です。

様々な課題を克服するために、改良型遺伝的アルゴリズムの開発が行われています。

遺伝的アルゴリズムの遺伝的操作3つ

遺伝的アルゴリズムによる解探索は、個体と呼ばれる解の集合である母集団に対して、選択・交叉・突然変異と呼ばれる遺伝的操作を繰り返し適用することによって行われ、次第により良い個体が生成され最適解に近づくというのが遺伝的アルゴリズムの考え方です。

この遺伝的アルゴリズムの遺伝子操作をおこなう方法として、選択・交叉・突然変異があります。いずれも生物の繁殖の上で重要な操作になります。

1：選択

遺伝的アルゴリズムの遺伝子操作の一つである選択は、新しい世代を生み出すため、個体の適合度によって次世代の母集団を作成する遺伝子操作です。

選択の方法としてランキング選択、トーナメント選択、ルーレット選択、エリート選択があります。どの方法でも最終的に生き残る個体を限定して母集団を最適解へ収束させる役割があります。

ランキング選択

遺伝的アルゴリズムの遺伝子操作選択の一つランキング選択とは、もともと個体の持つ優位性で判断をして、優位性の高い個体から順番に次世代に残す確率を決める方法です。

具体的には、各個体に一位なら確率50％、2位なら確率30％、3位なら確率15％とランクごとにあらかじめ確率を決めておく方式です。この方法の特徴は選択確率が適応度の格差に影響されないことです。

問題点としては、適応度にあまり差がない個体でも選択確率に大きな差が生じる可能性があります。また個体にランク付けするため次世代がそろうたびにソートを行う必要があります。

トーナメント選択

遺伝子アルゴリズムの遺伝的操作の一つトーナメント選択とは、個体同士のトーナメント方式によって優位性を判断し、より優位性を持つ個体を選択していく方法です。

具体的には、あらかじめ決めた数だけ、集団の中から無作為に個体を取り出し、その中で最も適応度の高い個体を選択するやり方です。問題点は、初期収束による局所最適解に陥る危険があります。

ルーレット選択

遺伝的アルゴリズムの遺伝子操作の一つルーレット選択とは、各個体につけられた点数に応じて枠を作り、ランダムなルーレット方式で残す次世代を決める方法です。

具体的には、各個体に100点なら5枠、80点なら4枠、60点なら3枠と点数ごとに枠の大きさを決め、その枠を使いランダムなルーレット方式で残す次世代を確率で決める方式です。

この方式の特徴は、点数が低い個体も残る事により、点数が低い個体が突然優秀な個体になる可能性を残すことです。

エリート選択

エリート選択とは、一つ世代の最も優位性の高い個体は、交叉や突然変異をせずにそのまま次世代に残す方法です。

この方式の特徴は、いつ遺伝子操作を辞めても、最も優位性の高い個体を決めることが出来ることです。

2：交叉

遺伝的アルゴリズムの遺伝的操作のうち交叉とは、生物が交配によって子孫を残すことをモデル化したものです。

基本的には選択によって選出された個体に対して、ある交叉位置において双方の染色体の一部ずつを採ってきて、子孫の染色体を作る操作です。

交叉は親同士の遺伝子を掛け合わせる操作であるため、ランダムに2つの個体を選んだ上で実行されます。交叉は遺伝的アルゴリズムの遺伝子的操作で影響が大きいと言われています。

一点交叉

遺伝的アルゴリズム遺伝的操作の交叉のうち一点交叉について説明します。例えば人は親の遺伝子を受け継いで子が生まれます。遺伝的アルゴリズムにおいてもこの遺伝的操作を基に最適解を求める方法です。

一点交叉とは、この遺伝子となる個体の染色体の一か所を選び、その箇所から後ろを入れ替える操作です。交叉の中では一番単純な方法です。現在では効率が悪い為あまり用いられていません。

二点交叉

遺伝的アルゴリズムの遺伝的操作のうち二点交叉について説明します。一口に言って一点交叉との違いは、選択する交叉点の数の違いです。二点交叉は二か所を選んで操作する方法になります。一点交叉よりも利用頻度が多い方法になります。

多点交叉

遺伝的アルゴリズムの遺伝的操作のうち多点交叉について説明します。基本的に一点交叉、二点交叉と同じです。交叉点が三点以上の場合に多点交叉と呼ぶ操作方法です。一点交叉、二点交叉より効率よく最適解が求められる方法です。

一様交叉

遺伝的アルゴリズムの遺伝的操作のうち一様交叉について説明します。今までは交差点の数でみてきました。しかし一様交叉は、1と0のビットが連続するビット列を用いて、ある個体に対応するビットをあらかじめ設定し、条件が変わるごとにビット選択していく操作方法です。

すなわち一様交叉とは、要素ごと独立に二分の一の確率で入れ替える交叉方法です。特徴は、後で問題点として記述があるヒッチハイク問題を抑えることができるとされています

3：突然変異

遺伝的アルゴリズムの遺伝的操作の最後は突然変異です。生物学的に突然変異と聞くと寿命が短かったりと、自然淘汰されてしまう場合がほとんどです。

しかし遺伝的アルゴリズムの遺伝子操作の場合は突然変異の操作をすることで最適解を導き出すとき、早期に収束させないように多様性を持たせるために行う操作です。

具体的には、ランダムに選んだ任意の個体に遺伝子の値を対立遺伝子に置き換えるというような操作を行います。

置換

遺伝的アルゴリズムの遺伝子操作のうち置換について説明します。ランダムに遺伝子を選び、全く別の値に入れ替える遺伝子操作方法です。

具体的には、ランダムに選ばれた遺伝子を0→10や100などと全く別の値に入れ替えます。遺伝子情報がバイナリ（0or1）で表される時に、その値を反転させる際に使用します。

摂動

遺伝的アルゴリズムの遺伝子操作のうち摂動について説明します。ランダムに遺伝子を選び、その値に数字を足したり引いたりする遺伝子操作方法です。

具体的には、ランダムに選ばれた遺伝子を10→プラスして11、12やマイナスして8、9などと足したり引いたりします。

ランダムに選ばれた遺伝子の近い情報を持っているため、調整するという特徴を持ちます。

遺伝的アルゴリズムが使われる場面

遺伝的アルゴリズムが使われる場面として、組み合わせ最適化の解が必要な場面で使われています。具体的にはつぎのとおりです。

ライン生産順位編成の最適化・機械における処理順位の割り振り最適化などの順序に関した問題、工場稼働計画・勤務計画などの組み合わせに関係した問題、トラックの配車計画の最適化・鉄道貨車輸送の最適化などの順序と組み合わせに関係した問題、図形の配置・画像復元などの図形に関係した問題に適したアルゴリズムです。

組合せ最適化問題

最適化には数理的最適化と組み合わせ最適化の2種類あります。数理的最適化は最適化問題のうち気が連続的なものです。それに対し組み合わせ最適化は最適化問題の解が離散的なものです。この問題の典型的な例として巡回セールスマン問題があります。

これは、多数の指定された位置をすべて通過し、一巡した時の最小移動距離を求めるというものです。この問題は単純そうに見えますが、指定された位置の数に対し厳密な最適解を求めようとすると相当な手間がかかる上に、最適解を得ることが通常の計算方法では困難になります。そこで生物学的な計算手法を用いる遺伝的アルゴリズムが利用されています。

遺伝的アルゴリズムの欠点2つ

遺伝的アルゴリズムは様々な問題に対し使用できる手法ですが、問題と使う方式によっては、最適な解が見つからない場合があります。

一般的によく起きるとされる遺伝的アルゴリズムの問題点は、過剰反応(初期収束ともいう)とヒッチハイク問題があります。それぞれについて説明をしていきます。

過剰適応

遺伝的アルゴリズムの欠点の一つである過剰反応について説明します。ある水準以上の解を求めようとしたとき、偶然その水準に近い解を得られた場合、その求めようとする水準以下で解が収束してしまうことです。

中途半端な段階で収束してしまうと、最適解を得ることが難しくなります。この場合は、突然変異の確率や、選択の確率を見直しが必要になります。

ヒッチハイク問題

遺伝的アルゴリズムの欠点の一つヒッチハイク問題について説明します。ヒッチハイク問題は交叉において、最適解の生成を妨げる遺伝をしてしまう現象です。

ある個体の両端の数値が正しく、間の数値が間違っていた場合、間違った数値が見逃されてしまう問題です。これは等確率な交叉を行う一様交叉を使用することで、防ぐことができます。

遺伝的アルゴリズムを応用しよう！

遺伝的アルゴリズムの応用は普遍的なアプローチでは容易に対処できない問題の解析ツールとして、集積回路や通信ネットワークの設計などの工業部門、経済及び政治に関する複雑問題解決など多岐にわたっています。特に最適化問題への応用が多くなっています。

そのほかに、複数の目的を同時に追求する多目的最適化、時系列予測、観測誤差やノイズを含む観測データからの最適値解析及び陰関数の解法など、課題要素を同時に含む問題解析への応用例が挙げられます。

いずれも最適化手法としての遺伝的アルゴリズムの特質を生かしての物であり、従来の手法では困難だった最適化対象に利用できる点で注目です。

このほか、計算の実装方法として、遺伝的アルゴリズムは並列計算と相性がよくPCクラスタやグリッドコンピュータの利用が容易になってきたことからさらに応用が期待できます。