遺伝的アルゴリズムの遺伝的操作3つ|遺伝的アルゴリズムの流れと欠点

遺伝的アルゴリズムの遺伝的操作3つ|遺伝的アルゴリズムの流れと欠点のアイキャッチイメージ

遺伝的アルゴリズムとは

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

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

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

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

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

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

遺伝的アルゴリズムの遺伝的操作1:選択

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

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

ランキング選択

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

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

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

トーナメント選択

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

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

その他

遺伝的アルゴリズムの遺伝的操作のうちトーナメント選択、ランキング選択以外の選択方法として、ルーレット選択とエリート選択があります。まずルーレット選択とは個体全体から適応度の高い個体から順番に選んでいくことです。

この選択方法は最も有名な選択方法ですが、各個体の適応度の差が著しい場合は最適解が求められない場合があります。エリート選択とははじめから適応度が高いい個体を選ぶ方法です。

エリートを選択することにより、解が悪い方向に向かわないことが保証されます。ただしエリートの集団が集まりすぎて解の多様性が失われるという問題があります。

遺伝的アルゴリズムの遺伝的操作2:交叉

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

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

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

一点交叉

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

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

二点交叉

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

多点交叉

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

一様交叉

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

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

遺伝的アルゴリズムの遺伝的操作3:突然変異

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

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

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

遺伝的アルゴリズムの流れ2つ

遺伝的アルゴリズムの流れとしては、初期配列を決定することです。この初期配列は解く問題により変わります。

次に遺伝的操作の交叉を行います。次にある与えられた確率で突然変異を起こさせ、適応度を評価し、最初の個体数と同じ数まで環境に適応しない個体を淘汰します。

最終的に交叉~淘汰を繰り返し終了判定を行います。条件を満たした段階でループ終了という流れになります。

遺伝的アルゴリズムの流れ1:遺伝子のピックアップ

遺伝的アルゴリズムの流れとして、遺伝子のピックアップについて説明していきます。遺伝子のピックアップとは数百問題の回答結果で、成績の良い遺伝子のみを次世代に残すことです。

具体的には回答の正解上位10%だけ残す方法や、正解回答率が高いものを残すなど、選択の方法がいろいろあります。

遺伝的アルゴリズムの流れ2:遺伝子乗り換え

遺伝的アルゴリズムの流れとして、遺伝子の乗り換えについて説明していきます。優位性の高い個体は淘汰されず生き残っていきますが、その生き残った個体同士で繰り返し計算をしていくとそれ以上の成績が残せなくなります。

そこで遺伝子をシャッフルすることにより多様性が生まれより良い結果が得られるということです。これを繰り返し行うことにより、解が求められるようになります。

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

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

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

組合せ最適化問題

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

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

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

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

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

遺伝的アルゴリズムの欠点1:過剰適応

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

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

遺伝的アルゴリズムの欠点2:ヒッチハイク問題

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

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

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

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

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

いずれも最適化手法としての遺伝的アルゴリズムの特質を生かしての物であり、従来の手法では困難だった最適化対象に利用できる点で注目です。このほか、計算の実装方法として、遺伝的アルゴリズムは並列計算と相性がよくPCクラスタやグリッドコンピュータの利用が容易になってきたことからさらに応用が期待できます。

インフラエンジニア専門の転職サイト「FEnetインフラ」

FEnetインフラはサービス開始から10年以上『エンジニアの生涯価値の向上』をミッションに掲げ、多くのエンジニアの就業を支援してきました。

転職をお考えの方は気軽にご登録・ご相談ください。