3

ルールに従ってリソースを割り当てることができるアプリケーションを設計したいと思います。シミュレーテッドアニーリングは機能すると思いますが、あまり詳しくないので、適切な代替アルゴリズムがあるかどうか疑問に思いました。

たとえば、グリッドがあり、グリッド内の各セルに色を付けることができる場合、次のようなルールセットの最適または最適に近いソリューションを見つけるアルゴリズムを設計したいと思います。

  • 1000x1000グリッド
  • 500個の赤血球、500個の青色のセル、および1000個の緑色のセルを配置する必要があります
  • 赤血球が別の赤血球に接触している必要があります
  • 青いセルが別の青いセルに触れてはいけません
  • 緑色のセルは、端に沿ってのみ配置できます
  • 配置は、左上隅からの色付きのセルの平均距離に基づいてスコアリングできます

シミュレーテッドアニーリングはこの問題に適していますか？解を確実にすばやく（数秒から数分）計算できるアルゴリズムが必要です。

4

2 に答える 2

3

これは基本的に制約充足問題であり、シミュレーテッドアニーリングが妥当な時間内に最適に近づくとは思われません。ただし、最適ではないソリューションにすぐに到達する可能性があるため、時間切れになると終了する可能性があります。

とはいえ、これを最適に解決したい場合は、ある種のCSPソルバーを使用するのが最善の方法です。これをIBMCPLEXOPLでコーディングしました。これは、整数線形計画（ILP）にコンパイルされ、CPLEXソルバーによって解決されます。アカデミアにいる場合はCPLEXの無料コピーを入手でき、そうでない場合はGLPKで非常によく似たことができます。また、一定の時間が経過した後に多くのILPソルバーを終了して、これまでのところ最良のソリューションを取得することもできます。

また、この特定のセットアップで実行できるスピードアップがいくつかあります。まず第一に、緑のノードは問題から取り除くことができます。それらは常に上端と左端に沿って並んでいます。赤/青と比較して緑の数が常に多い場合は、それらの端に青または赤。これらの変更により、1000x1000グリッドのソルバーは、10秒以内に最適値の7％以内に収まるようになりましたが、15分後も実際の最適な割り当ては見つかりませんでした。

興味がある場合は、100 x 100グリッドのOPLコードを、100緑、50赤、50青で示します。

using CPLEX;
dvar int grid[0..102][0..102][0..2] in 0..1;
minimize (sum(i in 1..101, j in 1..101, k in 0..2) grid[i][j][k]*(i*i + j*j));

subject to {

// edge conditions so I can always index i-1 and i+1 in all cases
forall(i in 0..102) (sum(j in 0..2) (grid[i][0][j] + grid[i][102][j])) == 0;
forall(i in 0..102) (sum(j in 0..2) (grid[0][i][j] + grid[102][i][j])) == 0;

// only one color per cell
forall(i in 1..101, j in 1..101)
    (sum(k in 0..2) grid[i][j][k]) <= 1;

// 50 red
sum(i in 1..101, j in 1..101) grid[i][j][0] == 50;

// 100 green
sum(i in 1..101, j in 1..101) grid[i][j][1] == 100;

// 50 blue
sum(i in 1..101, j in 1..101) grid[i][j][2] == 50;

// green must be on the edge (not on not-edge)
forall(i in 2..100, j in 2..100)
    grid[i][j][1] == 0;

// red must be next to another red
forall(i in 1..101, j in 1..101)
    (1 - grid[i][j][0]) + grid[i+1][j][0] + grid[i-1][j][0] + grid[i][j+1][0] + grid[i][j-1][0] >= 1;

// blue cannot be next to another blue
forall(i in 1..101, j in 1..101)
    (1-grid[i][j][2]) + (1-grid[i+1][j][2]) >= 1;
forall(i in 1..101, j in 1..101)
    (1-grid[i][j][2]) + (1-grid[i-1][j][2]) >= 1;
forall(i in 1..101, j in 1..101)
    (1-grid[i][j][2]) + (1-grid[i][j+1][2]) >= 1;
forall(i in 1..101, j in 1..101)
    (1-grid[i][j][2]) + (1-grid[i][j-1][2]) >= 1;
}

これが3.05Ghzマシンで約10秒で解決した最適な配置です

G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G G 
G B R R R B R R R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R B R B R R _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R B R R R B R B R B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R B R R R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R R R B R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R B R R R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R B R B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R B R R R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R B R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G R R R B _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B R B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ B _ B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G B _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
G _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
于 2011-02-24T07:04:44.040 に答える
3

シミュレーテッドアニーリングは、最適なソリューションに非常に速く近づきます。ただし、シミュレーテッドアニーリングを正しく実装すること（コードはそれほど多くありません）は非常に難しい場合があります。多くの人（過去の私を含む）はそれを間違って実装し、彼らはそれを正しく行ったと思い、アルゴリズムはそれほど良くないと思います。

代替アルゴリズムは、タブーサーチ、遺伝的アルゴリズム、シンプレックス、...

Drools Planner（Java、オープンソース、ASL）での制約は次のとおりです。

rule "A red cell must be touching another red cell"
when
   // There is a cell assignment of color red
   $a1: CellAssignment(color = RED, $x1 : x, $y1 : y)
   // There is no other red cell a neighbor of it
   not CellAssignment(color = RED, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1))
then
   insertLogical(new IntConstraintOccurrence(
            "A red cell must be touching another red cell", 
            ConstraintType.NEGATIVE_HARD, 1, // weight 1
            $a1));
end

rule "A blue cell must not be touching another blue cell"
when
   // There is a cell assignment of color blue
   $a1: CellAssignment(color = BLUE, $x1 : x, $y1 : y)
   // There is another blue cell a neighbor of it
   $a2: CellAssignment(color = BLUE, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1))
then
   insertLogical(new IntConstraintOccurrence(
            "A blue cell must not be touching another blue cell", 
            ConstraintType.NEGATIVE_HARD, 1, // weight 1
            $a1, $a2));
end

...

ここで楽しい部分は次のとおりです。ルールをスコアリングしたら、いくつかのアルゴリズム（タブーサーチ、シミュレーテッドアニーリングなど）をその上にスローして（Benchmarkerサポートを参照）、本番環境で最高のアルゴリズムを使用できます。詳細については、リファレンスマニュアルを参照してください。

于 2011-02-24T09:02:42.840 に答える