遺伝的アルゴリズム-高度なトピック

このセクションでは、遺伝的アルゴリズムのいくつかの高度なトピックを紹介します。GAの紹介だけを探している読者は、このセクションをスキップすることを選択できます。

制約付き最適化問題

制約付き最適化問題は、特定の制約の対象となる特定の目的関数値を最大化または最小化する必要がある最適化問題です。したがって、次の図に示すように、解空間のすべての結果が実行可能であるとは限りません。解空間には実行可能領域が含まれています。

このようなシナリオでは、クロスオーバー演算子とミューテーション演算子によって、実行不可能なソリューションが得られる可能性があります。したがって、制約付き最適化問題を処理する場合は、GAで追加のメカニズムを使用する必要があります。

最も一般的な方法のいくつかは次のとおりです。

  • 使用する penalty functions これにより、実行不可能なソリューションの適合度が低下します。これにより、違反した制約の数または実行可能領域からの距離に比例して適合度が低下します。

  • 使用する repair functions 実行不可能な解決策を取り、違反した制約が満たされるように修正します。

  • Not allowing infeasible solutions 人口に入るのです。

  • 使う special representation or decoder functions これにより、ソリューションの実現可能性が保証されます。

基本的な理論的背景

このセクションでは、スキーマとNFLの定理について、ビルディングブロックの仮説とともに説明します。

スキーマ定理

研究者たちは遺伝的アルゴリズムの働きの背後にある数学を解明しようとしてきました、そしてオランダのスキーマ定理はその方向への一歩です。スキーマ定理をより一般的にするために、1年にわたってさまざまな改善と提案が行われてきました。

このセクションでは、スキーマ定理の数学については詳しく説明しませんが、スキーマ定理とは何かについての基本的な理解を深めようとします。知っておくべき基本的な用語は次のとおりです。

  • A Schemaは「テンプレート」です。正式には、アルファベット上の文字列= {0,1、*}、

    ここで、*は気にせず、任意の値を取ることができます。

    したがって、* 10 * 1は、01001、01011、11001、または11011を意味する可能性があります。

    幾何学的には、スキーマはソリューション検索空間の超平面です。

  • Order スキーマのは、遺伝子内の指定された固定位置の数です。

  • Defining length は、遺伝子内の最も遠い2つの固定記号間の距離です。

スキーマの定理は、平均以上の適合性、短い定義長、および低次のこのスキーマは、クロスオーバーと突然変異に耐える可能性が高いと述べています。

ビルディングブロック仮説

ビルディングブロックは、上記の平均適合度を備えた低次の低定義長スキーマです。ビルディングブロック仮説は、そのようなビルディングブロックは、そのような「ビルディングブロック」を連続的に識別して再結合することにより、GAの成功とGAでの適応の基盤として機能すると述べています。

ノーフリーランチ(NFL)の定理

WolpertとMacreadyは、1997年に、「最適化のための無料ランチ定理なし」というタイトルの論文を発表しました。基本的に、考えられるすべての問題の空間を平均すると、再訪しないすべてのブラックボックスアルゴリズムが同じパフォーマンスを示すと述べています。

これは、問題を理解すればするほど、GAは問題固有になり、パフォーマンスが向上することを意味しますが、他の問題のパフォーマンスが低下することでそれを補います。

GAベースの機械学習

遺伝的アルゴリズムは、機械学習にも応用できます。 Classifier systems の形式です genetics-based machine learning(GBML)機械学習の分野で頻繁に使用されるシステム。GBMLメソッドは、機械学習へのニッチなアプローチです。

GBMLシステムには2つのカテゴリがあります-

  • The Pittsburg Approach −このアプローチでは、1つの染色体が1つの解をエンコードしたため、適合度が解に割り当てられます。

  • The Michigan Approach − 1つの解は通常、多くの染色体で表されるため、適合度は部分解に割り当てられます。

クロスオーバー、突然変異、ラマルキアンまたはダーウィンなどの標準的な問題もGBMLシステムに存在することに留意する必要があります。