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

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

制約付き最適化問題

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

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

最も一般的な方法のいくつかは-

*ペナルティ関数*を使用すると、実行不可能なソリューションの適合性が低下し、できれば、違反した制約の数または実行可能領域からの距離に比例して適合性が低下します。
実行不可能な解決策を取り、違反した制約が満たされるように修正する*修復関数*を使用します。
*実行不可能な解決策*を母集団に入力することを許可しません。
ソリューションの実行可能性を保証する*特殊な表現またはデコーダー関数*を使用します。

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

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

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

スキーマ*は「テンプレート」です。正式には、アルファベット= \ {0,1、}上の文字列です。 +ここで、は重要ではなく、任意の値を取ることができます。 +したがって、 *10 1は01001、01011、11001、または11011を意味する可能性があります。+幾何学的に、スキーマはソリューション検索スペースの超平面です。
スキーマの Order は、遺伝子内の指定された固定位置の数です。

スキーマ定理は、平均以上の適合度、短い定義長、低次のこのスキーマは、クロスオーバーと突然変異を乗り切る可能性が高いと述べています。

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

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

つまり、問題を理解すればするほど、GAの問題固有性が高まり、パフォーマンスが向上しますが、他の問題ではパフォーマンスが低下することで埋め合わせられます。

遺伝的アルゴリズムは機械学習にも応用できます。 分類システム*は、機械学習の分野で頻繁に使用される*遺伝学ベースの機械学習（GBML）システムの一種です。 GBMLメソッドは、機械学習に対するニッチなアプローチです。

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

クロスオーバー、突然変異、ラマルクまたはダーウィニアンなどの標準的な問題に留意してください。 GBMLシステムにも存在します。