genetic-algorithm - ニッチングスキームとは？

Question

現在、制約付き最適化問題での GA の使用に関する論文を読んでいます。ある部分では、個体 (または個体が作るパレート フロント) にニッチ スキームを適用することについて話しています。

典型的な選択スキームのように思えますが、検索したところ、適切な説明が見つかりませんでした。

ニッチングスキームとは何か、できるだけ簡単に説明してもらえますか?

Answer 1

簡単に言えば、ニッチングは、1回の実行中に複数のソリューションに収束しようとするメソッドのクラスです。

ニッチングとは、GAの母集団を互いに素なセットにセグメント化するという考え方であり、適応度関数の各領域に「興味深い」メンバーが少なくとも1人いるようにすることを目的としています。一般に、これは、複数の局所最適点をカバーすることを意味します。

のような関数を想像してみてくださいf(x) = sin(x^2)。

通常のGAは、最終的に2つのグローバル最小値のいずれかに収束します。どちらが最初の人口と実行中に発生するランダムな遺伝的浮動に依存しますが、最終的にはn、いずれかの谷で1人の個人のコピーを取得します。たとえば、ほぼ収束したときにそのようなGAを見ると、次のように表示される場合があります。

ニッチングは、人口の約半分が各最小値に収束することを目的とした一般的なクラスの手法です（または、最小値に適合しないメンバーを数人含めることもできますx=0）。

先ほど述べたように、ニッチングは実際にはアルゴリズムではなく、一般的なクラスのアルゴリズムです。そのような方法の1つは、ゴールドバーグのフィットネス共有です。この方法では、ニッチ半径を定義しますsigma。これよりも接近している2人の個人sigmaは同じニッチにいると見なされるため、フィットネス値を共有する必要があります（これは、ニッチの人口密度が高いほど、ニッチの各メンバーのフィットネスを低下させる関数であると考えてください）。次に、生の値ではなく、共有されたフィットネス値でGAを操作します。

ここでの考え方は、リソースが限られているふりをして、適応度関数の単一の領域への収束を阻止することです。より多くの個人が入居しようとすると、彼ら全員が悪化します。その結果、GAがどこかで単一の局所最適点に収束すると、ニッチ内での競争が激化するため、その最適点の適合度が低下します。最終的に、フィットネスランドスケープの別の領域がより魅力的になり、個人はそこに移動します。アイデアは、各ニッチの適切な表現が維持される定常状態（ダイナミクスの固定点）に到達することです。

ニッチ半径を手動で設定する必要があるため、共有は困難であり、アルゴリズムはこの選択に非常に敏感です。別の選択肢は混雑です。特に、昔から人気のあった「決定論的混雑」を調べるかもしれません。混雑ベースの方法では、明示的な半径を処理する代わりに、新しい子孫が置き換えることができる個体のセットを同様のソリューションのセットに制限することによって機能します。たとえば、子孫はその親の1つだけを置き換えることが許可される場合があります。その効果は、ユニークな個体を、集団内の他の12の個体と非常に類似している個体に置き換えないようにし、そのようにして多様性を維持しようとすることです。

Answer 2

はい、ニッチについてのdeongによる良い説明。これらの技術はすべて、個体群の多様性を維持するために作られています。

パレートフロントもそうです。パレート フロントを探している GA は、多目的進化アルゴリズムです。1 つの基準だけでなく、2 つ以上の基準を最適化しようとします。したがって、パレート フロントは、集団の個体によってパレート支配されていないすべての個体です。 http://en.wikipedia.org/wiki/Pareto_efficiency

つまり、個体 A は、すべての基準に関して少なくとも A と同程度であり、少なくとも 1 つの基準で A より優れている個体 B が母集団に存在しない場合、パレート フロントのメンバーです。