遺伝的アルゴリズム-はじめに

遺伝的アルゴリズム（GA）は、 Genetics and Natural Selection の原則に基づいた検索ベースの最適化手法です。これは、解決するのに一生かかるかもしれない困難な問題に対する最適または最適に近いソリューションを見つけるために頻繁に使用されます。最適化問題の解決、研究、機械学習で頻繁に使用されます。

最適化の概要

最適化とは、*何かをより良くする*プロセスです。どのプロセスでも、次の図に示すように、入力のセットと出力のセットがあります。

最適化

最適化とは、「最適な」出力値が得られるような方法で入力値を見つけることです。「最良」の定義は問題ごとに異なりますが、数学的には、入力パラメーターを変えることで1つ以上の目的関数を最大化または最小化することを意味します。

入力が取り得るすべての可能なソリューションまたは値のセットが、検索スペースを構成します。この探索空間には、最適な解を与える点または点の集合があります。最適化の目的は、検索スペースでそのポイントまたはポイントのセットを見つけることです。

遺伝的アルゴリズムとは何ですか？

自然は常にすべての人類にとって素晴らしいインスピレーションの源となっています。遺伝的アルゴリズム（GA）は、自然selectionと遺伝学の概念に基づいた検索ベースのアルゴリズムです。 GAは、 Evolutionary Computation として知られるはるかに大きな計算のブランチのサブセットです。

GAはジョン・ホランドと彼の学生およびミシガン大学の同僚、特にDavid Eによって開発されました。ゴールドバーグは、その後、さまざまな最適化問題で試行され、高い成功を収めています。

GAでは、特定の問題に対する*プールまたは可能な解決策の集団*があります。その後、これらのソリューションは組換えや突然変異（自然遺伝学のように）を受け、新しい子供を生み出し、このプロセスはさまざまな世代にわたって繰り返されます。各個人（または候補解）には（目的関数値に基づいて）適合値が割り当てられ、適合者には、より多くの「適合」個体を交配して生み出す可能性が高くなります。これは、ダーウィンの「適者生存」の理論と一致しています。

このようにして、停止基準に達するまで、世代を超えてより良い個人またはソリューションを「進化」させ続けます。

遺伝的アルゴリズムは本質的に十分にランダム化されていますが、履歴情報も活用するため、ランダムローカル検索（さまざまなランダムソリューションを試行し、これまでのベストを追跡する）よりもはるかに優れたパフォーマンスを発揮します。

GAの利点

GAにはさまざまな利点があり、GAは非常に人気があります。これらには-

派生情報は必要ありません（多くの実際の問題では利用できない場合があります）。
従来の方法と比較して、より高速で効率的です。
非常に優れた並列機能を備えています。
連続関数と離散関数の両方、および多目的問題を最適化します。
単一のソリューションではなく、「良い」ソリューションのリストを提供します。
問題に対する答えは常に得られ、時間の経過とともに改善されます。
サーチスペースが非常に大きく、多数のパラメータが関係する場合に役立ちます。

GAの制限

他の手法と同様に、GAにもいくつかの制限があります。これらには-

GAはすべての問題、特に単純で派生情報が利用可能な問題に適しているわけではありません。
フィットネス値は繰り返し計算されるため、問題によっては計算コストが高くなる場合があります。
確率的であるため、ソリューションの最適性または品質に関する保証はありません。
適切に実装されていない場合、GAは最適なソリューションに収束しない可能性があります。

GA –モチベーション

遺伝的アルゴリズムには、「十分に」ソリューションを「十分に」提供する機能があります。これにより、遺伝的アルゴリズムは最適化問題の解決に使用するのに魅力的です。 GAが必要な理由は次のとおりです-

難しい問題を解決する

コンピュータサイエンスには、 NP-Hard である大きな問題があります。これが本質的に意味することは、最も強力なコンピューティングシステムでさえ、その問題を解決するのに非常に長い時間（偶数年！）を要するということです。このようなシナリオでは、GAは短時間で*使用可能な最適に近いソリューション*を提供する効率的なツールであることが証明されています。

勾配ベースの方法の失敗

従来の計算ベースの方法は、ランダムなポイントから開始し、丘の頂上に到達するまで勾配の方向に移動することにより機能します。この手法は効率的であり、線形回帰のコスト関数のような単一ピークの目的関数に対して非常にうまく機能します。しかし、ほとんどの実際の状況では、風景と呼ばれる非常に複雑な問題があります。これは多くの山と谷で構成されており、そのような方法は失敗します。次の図に示すように。

GA動機

優れたソリューションを迅速に取得する

巡回セールスマン問題（TSP）のようないくつかの困難な問題には、経路探索やVLSI設計などの実際のアプリケーションがあります。 GPSナビゲーションシステムを使用していて、ソースから目的地までの「最適な」パスを計算するのに数分（または数時間）かかっていることを想像してください。このような実世界のアプリケーションの遅延は許容できないため、「高速」に配信される「十分な」ソリューションが必要です。

Genetic-algorithms-introduction

目次