4

私は、シミュレーテッド アニーリング アルゴリズムについて学んでいる途中で、サンプル アルゴリズムをどのように変更して 0-1 ナップザック問題を解決するかについていくつか質問があります。

CP でこの素晴らしいコードを見つけました。

http://www.codeproject.com/KB/recipes/simulatedAnnealingTSP.aspx

私はそれが今どのように機能するかを理解していると確信しています（私が懸念している限り、ボルツマン条件全体を除いて、私は黒魔術ですが、局所最適を回避することについて理解しており、明らかにこれはまさにそれを行います）。これを再設計して、0-1 ナップザックの「っぽい」問題を解決したいと思います。基本的に、私は 5,000 個のオブジェクトの 1 つを 10 個の袋に入れ、未使用のスペースが最小になるように最適化する必要があります。ソリューションに割り当てる実際の「スコア」はもう少し複雑ですが、アルゴリズムとは関係ありません。

これは簡単そうです。これは、Anneal() 関数が基本的に同じであることを意味します。ニーズに合わせて GetNextArrangement() 関数を実装する必要があります。TSM の問題では、パスに沿って 2 つのランダムなノードを交換するだけです (つまり、反復ごとに非常に小さな変更を加えます)。

私の問題では、最初の繰り返しで、10 個のランダムなオブジェクトを選び、残りのスペースを調べます。次の反復では、10 個の新しいランダム オブジェクトを選択しますか? それとも、オブジェクトの半分または 1 つだけなど、いくつかのオブジェクトのみを交換するのが最善でしょうか? それとも、スワップアウトするオブジェクトの数は、温度に比例する必要がありますか? これらのどれも私には実行可能に思えますが、誰かが最善のアプローチについてアドバイスを持っているかどうか疑問に思っています (ただし、コードが機能したら、改善をいじることができます)。

ありがとう！

マイク

4

2 に答える 2

3

ああ、私はウィキペディアで私の答えを見つけたと思います..「隣人」状態に移動することを示唆しています.

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

「州の近隣は、特定の方法で特定の状態を変更した後に生成される問題の新しい状態です。たとえば、巡回セールスマンの問題では、各州は通常、訪問する都市の特定の順列として定義されます。ある特定の順列の隣人は、例えば隣接する都市のペアを交換することによって生成される順列です. 隣り合った解を見つけるために解を変更するためにとられる行動は「移動」と呼ばれ、異なる「移動」は異なる隣人を与えます.これら移動は通常、ソリューションの変更を最小限に抑えます、前の例が示しているように、アルゴリズムがソリューションを最大限に最適化し、ソリューションのすでに最適な部分を保持し、次善の部分のみに影響を与えるのを助けるため. 前の例では、ソリューションの一部がツアーの一部です。」

したがって、私の GetNextArrangement 関数は、ランダムなアイテムをセットで使用されていないアイテムと交換したいと考えています..

于 2010-08-02T11:36:49.447 に答える
3

シミュレーテッド アニーリングでは、隣接する状態をできるだけエネルギー的に近づけたいと考えています。隣人が非常に大きなエネルギーを持っている場合、非常に高い温度がなければ決してそれらにジャンプすることはありません。一方、低エネルギー状態を利用するヒューリスティックを思いつくことができる場合は、それを利用してください。

TSP の場合、これは隣接する都市を交換することを意味します。あなたの問題については、次のような条件付き近隣選択アルゴリズムをお勧めします。

  1. 空きスペースに収まるオブジェクトがある場合は、常に最大のものを入れます。
  2. 空のスペースにオブジェクトが収まらない場合は、スワップ アウトするオブジェクトを選択しますが、同様のサイズのオブジェクトをスワップすることをお勧めします。

つまり、オブジェクトには、サイズの違いに反比例する確率があります。ここでは、スライス サイズが (1 / (サイズ 1 - サイズ 2)^2) のようなルーレット選択のようなものを使用することをお勧めします。

于 2010-08-19T16:07:38.193 に答える