5

遺伝的アルゴリズムを使用して解決しようとしている最適化の問題があります。基本的に、10 個のバインドされた実数値変数 (-1 <= x <= 1) のリストがあり、そのリストのいくつかの関数を最大化する必要があります。問題は、リスト内の最大 4 つの変数のみが != 0 (サブセット条件) になる可能性があることです。

数学的に言えば: ある関数 f の場合: [-1, 1]^10 -> R min f(X) st |{var in X with var != 0}| <= 4

f の背景: この関数は、Sum x*weight などのナップザック目的関数とは似ていません。

私がこれまでに試したこと：

ゲノム [-1, 1]^10 に対する基本的な遺伝的アルゴリズムであり、変数に 1 点交差といくつかのガウス変異があります。最初の 4 つの非ゼロ (0に十分近いゼロ) の値のみを使用して、フィットネス関数のサブセット条件をエンコードしようとしました。このアプローチはうまく機能せず、アルゴリズムは最初の 4 つの変数でスタックし、それを超える値を使用することはありません。このアプローチがうまく機能する 01-knapsack 問題のある種の GA を見ましたが、どうやらこれはバイナリ変数でのみ機能するようです。

次に何を試してみるのをお勧めしますか?

4

3 に答える 3

3

「ピボット」スタイルのステップを試すことができます。既存のゼロ以外の値の1つを選択してゼロにし、既存のゼロ値の1つをゼロ以外に設定して置き換えます。(私の「ピボット」という用語は、ピボットがシンプレックス法の基本ステップである線形計画法から来ています)。

最も単純なケースは、これらの値のそれぞれを選択する際に公平にランダムにすることです。新しいゼロ以外の変数には、ランダムな値または複数の値を選択できます。よりローカルな種類のステップは、既存の非ゼロ変数に対してのみガウス ステップを使用することですが、それらの変数の 1 つがゼロを超えると、ゼロ値の 1 つにピボットするバリエーションを生成します。(両方の種類のステップを簡単に追加できるため、これらは相互に排他的ではないことに注意してください)。

フィットネス スコアの局所的な挙動に関する情報がある場合は、それを使用して選択を導くことができます。実際の進化がフィットネス関数を見ていないからといって、できないわけではありません...

于 2011-11-08T23:44:36.133 に答える
0

あなたの GA は、サブセットの制約なしで問題を解決できますか? そうでない場合は、最初にそれに取り組むことをお勧めします。

第 2 に、制約をハードではなくソフトにすることができます。4 を超えて、ゼロ値の変数ごとにソリューションの適合性にペナルティを課すことができます。 .そして、問題をより困難にする前に、GAがそれらの問題のバリエーションを処理できることを確認してください.)

第三に、1 ポイントの代わりに 2 ポイントまたはマルチポイント クロスオーバーを試してみてください。

それが役立つことを願っています。

-テッド

于 2011-11-28T04:33:29.690 に答える