1

私は現在、いくつかのセットから置き換えることなくサンプリングする必要がある最適化アルゴリズムを実装しています。私はMATLABでコーディングしていますが、これは本質的にCSの質問です。

状況は次のとおりです。

有限数のセット（A、B、C）があり、それぞれに有限ですが、おそらく異なる数の要素（a1、a2 ... a8、b1、b2 ... b10、c1、c2 ... c25）があります。また、各セットの確率のベクトルがあり、そのセット内の各要素の確率がリストされています（つまり、セットAの場合、P_A = [p_a1 p_a2 ... p_a8]ここで、sum（P_A）= 1）。私は通常、これらを使用して各セットの確率母関数を作成します。これは、0から1までの均一な数が与えられると、そのセットから要素の1つを吐き出すことができます（つまり、u = 0.25が与えられる関数P_A（u）はa2を選択します）。

セットA、B、 Cから交換せずにサンプリングしたいと思っています。各「完全なサンプル」は、異なるセット（a1、b3、c2）のそれぞれからの要素のシーケンスです。完全なサンプルのスペースは、 A、B、およびCの要素のすべての順列のセットであることに注意してください。上記の例では、このスペースは（a1、a2 ... a8）x（b1、b2 ... b10）x（c1、c2 ... c25）であり、8 * 10 * 25=2000の一意の「フル」があります。私のスペースのサンプル」。

この設定で置き換えずにサンプリングすることの厄介な部分は、最初のサンプルが（a1、b3、c2）の場合、要素a1を再度サンプリングできないことを意味するのではなく、完全なシーケンス（a1、 b3、c2）再び。もう1つの厄介な部分は、私が使用しているアルゴリズムでは、サンプリングしていない要素のすべての順列に対して関数評価を行う必要があることです。

私が今自由に使える最善の方法は、サンプリングされたケースを追跡することです。私のサンプラーは以前にサンプリングされたすべてのケースを拒否することを余儀なくされているため、これは少し非効率的です（私は交換なしでサンプリングしているため）。次に、ネストされたforループを使用して各順列（ax、by、cz ）を調べ、（ ax、by、cz）の組み合わせがサンプリングに含まれていない場合にのみ関数評価を行うことにより、サンプリングされていないケースの関数評価を行います。ケース。繰り返しますが、各順列（ ax、by、cz）がすでにサンプリングされているかどうかを「チェック」する必要があるため、これは少し非効率的です。

この問題に関して何かアドバイスをいただければ幸いです。特に、置換せずにサンプリングし、完全なサンプル空間を明示的にリストしない非サンプリングのケースを追跡する方法を探しています（私は通常、それぞれ10個の要素を持つ10セットで作業するため、完全なサンプル空間をリストするには10が必要です^ 10 x 10マトリックス）。これは不可能かもしれませんが、効率的な方法を見つけることで、アルゴリズムの真の限界を示すことができます。

4

2 に答える 2

2

サンプリングされていないすべてのケースを本当に追跡する必要がありますか？順列がサンプリングされたかどうかを示す真または偽の論理値を格納する1行10列の10ベクトルがある場合でも、約10 GBのストレージが必要であり、MATLABは「そのサイズの変数を作成しようとすると、「メモリ不足」エラーが発生するか、マシン全体が急停止します。

考慮すべき代替案は、すでにサンプリングした順列のインジケーターのスパースベクトルを保存することです。あなたの小さな例を考えてみましょう：

A = 1:8;
B = 1:10;
C = 1:25;
nA = numel(A);
nB = numel(B);
nC = numel(C);
beenSampled = sparse(1,nA*nB*nC);

1 x 2000のスパース行列beenSampledは、開始時に空であり（つまり、すべてゼロが含まれています）、サンプリングされた順列ごとに、指定されたインデックスに1を追加します。関数RANDIAを使用して新しいサンプル順列を取得し、、、、BおよびC新しい値のセットのインデックスを取得できます。

indexA = randi(nA);
indexB = randi(nB);
indexC = randi(nC);

次に、これら3つのインデックスを単一の一意の線形インデックスに変換beenSampledして、関数SUB2INDを使用できます。

index = sub2ind([nA nB nC],indexA,indexB,indexC);

これで、インデックス付けされた要素をテストしbeenSampledて、値が1（つまり、すでにサンプリング済み）または0（つまり、新しいサンプル）であるかどうかを確認できます。すでにサンプリングされている場合は、上記の新しいインデックスのセットを見つけるプロセスを繰り返します。まだサンプリングしていない順列を取得したら、それを処理できます。

while beenSampled(index)
  indexA = randi(nA);
  indexB = randi(nB);
  indexC = randi(nC);
  index = sub2ind([nA nB nC],indexA,indexB,indexC);
end
beenSampled(index) = 1;
newSample = [A(indexA) B(indexB) C(indexC)];
%# ...do your subsequent processing...

スパース配列を使用すると、考えられるすべての順列のごく一部をサンプリングするだけの場合に、多くのスペースを節約できます。上記の例のように、順列の総数が少ない場合は、スパースベクトルの代わりに論理ベクトルを使用する可能性があります。

于 2011-03-16T20:40:31.357 に答える
0

関数については、MATLABのドキュメントを確認してくださいrandi。lengthこれを関数と組み合わせて使用​​して、各ベクトルからランダムなエントリを選択するだけです。サンプリングされた各ベクトルを追跡することは、それを行列に連結するのと同じくらい簡単である必要があります。

current_values = [5 89 45];  % lets say this is your current sample set
used_values = [used_values; current_values];
% wash, rinse, repeat
于 2011-03-16T18:50:16.893 に答える