1

コレクションからアイテムを選択するという問題に取り組むのに苦労しています。

私はアイテムのコレクションを持っています。各アイテムには、X、Y、Z の 3 つの機能があり、2 倍の値があります。

いくつかのターゲットがあります。

1) 選択した項目のすべての X 値の合計の特定の下限に到達する。

2) 選択した項目のすべての Y 値の合計の特定の下限に到達する。

3) 選択した項目のすべての Z 値の平均の特定の下限に到達する。

4) 上記の要件を満たす項目の数を最小限に抑えます。

どのタイプの最適化アルゴリズムを試せばよいかわかりません。正しい方向へのポインタをいただければ幸いです。可能であれば、何らかの形で目標に優先順位を付け、境界を「ソフト」にしたいと考えています。たとえそれらすべてを一斉に満たすことができなくても、「近い」選択を返します。

4

3 に答える 3

1

あなたが説明している問題は、ナップザックの問題に似ています。ナップザックの問題では、特定のサイズの特定のバッグと、特定のサイズで特定の値のアイテムがあります。次に、サイズを超えないように値を最大化します。

ただし、問題は少し異なります。X、Y、Z の値の合計を最小化し、アイテムの数を最小化し、下限を表す X、Y、Z に制約を課すように定式化します。この定義を使用すると、問題が実際には多目的であることがわかります (実行可能なスペースを持つアイテムの最小化など、この目的のいくつかは競合していると思います)。あなたが書かなければならない関数は、特定の選択の質を計算するフィットネス関数と呼ばれます。制約に対処するには、フィットネスとして返すペナルティを使用するか、アルゴリズムで制約を処理できる場合は、制約違反の程度を指定します。

この問題を解決するには、ヒューリスティックなアプローチを使用します。このためには、問題の解の表現 (データ構造) を選択する必要があります。

ナップザックと同様に、バイナリ表現を選択できます。これは、すべてのアイテムに対してバイナリ ベクトルに 1 つの次元があり、含まれている場合は 1、含まれていない場合は 0 であることを意味します。ベクトルの長さはアイテムの数と同じです。

ソルバーに関しては、そのような表現のための多くのメタヒューリスティックが存在します。しかし、最も近い選択肢はおそらく、バイナリ エンコーディングを念頭に置いて開発された遺伝的アルゴリズムでしょう。多目的な方法で問題を解決したい場合は、アルゴリズムとして NSGA-II または SPEA2 を選択します。目標を加重和アプローチまたは他の手段で 1 つの値に組み合わせる場合、John Holland によって定義された標準的な遺伝的アルゴリズムで十分です。多目的アルゴリズムには、すべての非優越解のパレート フロントを探索するという利点があり、たとえば、X が大きいが Y と Z は、X、Y、Z が最小である他の解と同じではない解が得られます。 、しかしアイテムの数はより多くなります。

前述のシミュレーテッド アニーリング アルゴリズムは、このような問題を解決するためのもう 1 つのメタヒューリスティックです。しかし、アプリオリに、どちらがよりうまく機能するかを現時点で判断することはできません。ただし、適合値の範囲が事前にわからない場合、シミュレーテッド アニーリングを構成するのは少し難しくなります。これは、この範囲に適合する初期温度と冷却スケジュールが必要になるためです。

また、たとえば貪欲な方法で機能する、より単純な構築ヒューリスティックを使用することもできます (たとえば、境界のすぐ下または境界に達する最大の X、Y、および Z を持つアイテムを常に取得します。しかし、メタヒューリスティックがより良い解決策を見つけると思います。

于 2012-12-08T08:44:25.683 に答える
1

問題は、混合整数問題でモデル化できます。コレクションが大きすぎない場合 (数百の値など)、ヒューリスティックをプログラムしてパラメーター化するよりも標準の lp ファイルに書き込む方がはるかに簡単なので、このモデルを使用します。

この問題を混合整数問題ソルバーに与えることができます。

  • COIN-OR（無料）、
  • Cplex (アカデミックでない限り、商業的で拡張的)、
  • ぐろび（CM）、
  • GLPK (無料だが遅い)...

以下の疑似数学言語で以下の 2 つのモデルを書きました (これは LP 形式ではないことに注意してください)。

ハードバウンド

N をオブジェクトのセット、X_min と Y_min を到達する必要がある下限、ZZ を Z 値の平均下限とします。オブジェクト i が選択されている場合は値が 1 で、選択されていない場合は 0 のバイナリ変数 s_i を使用します。正確な問題は次のように記述できます。

Minimize sum_{i in N} s_i
Subject to:
      sum_{i in N} X_i s_i >= X_min
      sum_{i in N} Y_i s_i >= Y_min
      sum_{i in N} (Z_i - ZZ) s_i >= 0
      foreach i in N, s_i in {0, 1}

多目的

アンドレアスの回答で述べられているように、これを行うには他の方法があることに注意してください。これは、（私の意見では）目標に優先順位を付けて問題を「緩和」するためのより簡単な方法であり、上記の線形ソルバーを使用できます。

3 つのスラック変数 dX、dY、dZ、および 3 つの (正の) 重み係数 wX、wY、wZ を追加します。変数 dX、dY、および dZ は制約違反を表し、「重み」は制約違反に与える重要度を表します。

次に、問題を次のように記述できます。

Minimize sum_{i in N} s_i + wX dX + wY dY + wZ dZ
Subject to:
      dX >= sum_{i in N} X_i s_i - X_min
      dY >= sum_{i in N} Y_i s_i - Y_min
      dZ >= sum_{i in N} (Z_i - ZZ) s_i
      foreach i in N, s_i in {0, 1}
      dX, dY, dZ >= 0

次に、目標に優先順位を付けるために wX、wY、および wZ をパラメータ化できます。たとえば、重みの値が大きい場合、モデルは「ハード バウンド」ソリューションが存在する場合はそれを返します。次に、より高い重みを持つ制約は、他の制約よりも違反される可能性が「低く」なります（もちろん、アイデアを提供するためだけに単純ではありません）。

于 2012-12-08T13:47:28.267 に答える
1

たとえば、シミュレートされたアニーリングのように聞こえます

http://en.wikipedia.org/wiki/Simulated_annealing

この問題では非常にうまく機能します。

適切なソフト化されたターゲット関数 (つまり、持っている 4 つのターゲットのそれぞれにペナルティを課す) を使用してから、アニーリングを開始します。

いくつかの用語: 変数は 2 進数であるため (つまり、この項目が含まれているか)、これは間違いなく線形計画法ではありません。

ターゲット関数が十分に優れている場合は、貪欲なアルゴリズムを使用して、妥当な結果を非常に高速に取得できます

于 2012-12-07T19:27:51.857 に答える