0

私は、フィットネス (バッグ内のアイテムの値) を最大化する必要があるナップザックの問題を解決しようとして、シミュレートされたアニーリングに取り組んでいます。

float weight[5]={2, 3, 5, 4, 3}; // weight
float value[5]={10, 20, 15, 25, 5}; // value of corresponding item
float bagSize = 11.0;

厳密な計算により、最適解は {1,1,0.4,1,0} であることがわかっています。しかし、私はこの解決策を得ません。

ここでは、すべての長いコードを避けるために、疑似コードで私の C++ コードを説明します。

While (temperate > 1){
  1) Generate random values between (0,1) to fill the 5 sized array for each item
  2) Perform random swapping of values in the 5D array above.
  3) Calculate the fitness and new weight
  4) Save the best solution. 
}

基本的に、これは私のコードです。私の質問

  1. スワップを実行するときのステップ 2 では、現在、配列の要素をスワップしています。それが正しいか？または、以前のソリューションを追跡し、現在の要素 (i) を以前のソリューション要素と交換する必要がありますか? （これは単なるアイデアです）。
  2. 配列で実際の値を使用する場合、実行中に以前のソリューションが最大境界に近づいたことをシステムに伝えるにはどうすればよいですか。これは、現在の実装では、システムが冷えるまで繰り返されるステップ 1 でランダム値を継続的に生成するためです。

最後に、私の実装に大きな間違いがあるかもしれません。この問題で助けてもらえれば本当に感謝しています

4

1 に答える 1

2

あなたの疑似コードはシミュレートされたアニーリングではありません。あなたは無作為に探索空間を飛び回っています。

最初の質問:

スワップを実行するときのステップ 2 では、現在、配列の要素をスワップしています。それが正しいか？または、以前のソリューションを追跡し、現在の要素 (i) を以前のソリューション要素と交換する必要がありますか? （これは単なるアイデアです）。

perturb という関数を実装する必要があります。この摂動は、配列の値を交換する必要があります。その名前がアニーリングの概念を使用していることを意味するように、シミュレートされたアニーリング。それはあなたが熱く始めることを意味します。摂動関数は値を大幅に変更します。次に、ソリューションが冷却を開始します。これは、摂動関数が値を少しだけ変更することを意味します。

次のプレゼンテーションを参照してください

液体の徐冷…

  • 高温では、分子は自由に動きます
  • 低温では、分子は「くっつく」

あなたのソリューションによれば、次の行でランダム性を取得します。

2) 上記の 5D 配列の値をランダムに交換します。

段階的な冷却を実装する方法は次のとおりです。

  • 2a) int MaxRandomValueToAddToArrayValues = 20;
  • 2b) どうやって 20 を見つけたのですか、それはドメイン知識です。あなたの価値観と最良の解決策によると、20 は適切な値のようです。
  • 2c) この境界を使用して、上記の 5D 配列の値のランダムなスワップを実行します
  • 2d) MaxRandomValueToAddToArrayValues を徐々に減らします。たとえば、10 回の反復ごとに 0.1 ずつ減らすことができます。

2 番目の質問:

配列で実際の値を使用する場合、実行中に前の解が最大境界に近づいたことをシステムに伝えるにはどうすればよいですか?

解が最大境界に近いかどうかはわかりません。自分のソリューションが以前のソリューションよりも優れていることだけを知ることができます。最大境界を知ることができる場合、SA やその他のヒューリスティックな方法を実装する理由は何ですか。最善の解決策 (つまり、最大境界) を知ることは不可能であるか、非常に費用がかかるため、ヒューリスティックな解決策を使用します。

于 2013-11-05T08:37:59.537 に答える