問題タブ [simulated-annealing]

Visual Basicでシミュレーテッドアニーリングのかなりよく文書化された例を知っている人はいますか？

配置とルーティング（c ++またはjava）用のシミュレーテッドアニーリングの十分に文書化されたソースコードが必要です。誰かが私を助けることができますか？

シミュレーテッドアニーリングを使用して、NP完全リソーススケジューリング問題を解決しています。タスクの候補の順序ごとに、いくつかの異なるコスト（またはエネルギー値）を計算します。いくつかの例は次のとおりです（詳細はおそらく質問とは無関係ですが）：

• global_finish_time：スケジュールがまたがる合計日数。
• split_cost：他のタスクによる中断のために各タスクが遅延する日数（これは、タスクが開始された後の中断を阻止するためのものです）。
• deadline_cost：各期限を過ぎた日数の2乗の合計。

従来の受け入れ確率関数は次のようになります（Pythonの場合）。

これまでのところ、最初の2つのコストを1つにまとめて、結果をにフィードできるようにしていacceptance_probabilityます。しかし、私が本当に望んでいるのはdeadline_cost、常にを優先しglobal_finish_time、global_finish_timeを優先することsplit_costです。

したがって、Stack Overflowに対する私の質問は、複数のエネルギーを考慮に入れながら、常に最初のエネルギーが2番目のエネルギーよりも重要であると見なす受け入れ確率関数を設計するにはどうすればよいかということです。言い換えれば、私はいくつかのコストのタプルとして渡して、賢明な値を返しold_costたいと思います。new_cost

編集：提案されたソリューションを数日間実験した後、私にとって十分に機能する唯一の方法は、異なる単位を持つコストコンポーネントで他の多くの問題を引き起こすにもかかわらず、MikeDunlaveyの提案であると結論付けました。私は実際にリンゴとオレンジを比較することを余儀なくされています。

そこで、値を「正規化」することに少し力を入れました。まず、deadline_costは平方和であるため、指数関数的に増加し、他のコンポーネントは線形に増加します。これに対処するために、平方根を使用して同様の成長率を取得します。次に、コストの線形結合を計算する関数を開発しましたが、これまでに見られた最も高いコスト要素に従って係数を自動調整します。

たとえば、最も高いコストのタプルが（A、B、C）であり、入力コストベクトルが（x、y、z）である場合、線形結合はBCx + Cy+zです。そうすれば、zがいくら高くなっても、xの値が1よりも重要になることはありません。

これにより、新しい最大コストが検出されるため、コスト関数に「ジャギー」が作成されます。たとえば、Cが上がると、BCxとCyは両方とも、特定の（x、y、z）入力に対して高くなり、コスト間の差も大きくなります。コスト差が大きいということは、温度が突然1ステップ下がったかのように、受け入れ確率が低下することを意味します。実際には、これは問題ではありません。最大コストは最初は数回しか更新されず、後で変更されないためです。コストがより低い値に向かって収束することがわかっているので、これは理論的に正しい結果に収束することさえ証明できると思います。

まだ少し混乱しているのは、最大コストが1.0以下、たとえば0.5の場合にどうなるかということです。最大ベクトルが（0.5、0.5、0.5）の場合、これにより線形結合0.5 * 0.5 * x + 0.5 * y + zが得られます。つまり、優先順位が突然逆になります。これに対処する最善の方法は、最大ベクトルを使用してすべての値を指定された範囲にスケーリングすることです。これにより、係数は常に同じになります（たとえば、100x + 10y + z）。しかし、私はまだそれを試していません。

Beowulf クラスターで MPI を使って並列プログラミングを行っています。シミュレーテッド・アニーリングのための並列アルゴリズムを書きました。それは正常に動作します。シリアル コードよりも 15 倍速い実行が期待されます。ただし、パフォーマンス測定用に異なるデータ セットを使用できるように、さまざまなアーキテクチャとオペレーティング システムでシリアル C コードを実行しました。この Random 関数をコードで使用しました。Windows と ubuntu Linux の両方で GCC を使用しています。Linux では実行に時間がかかることがわかりましたが、その理由はわかりません。誰かが Linux と Windows で gcc を使ってこのコードをコンパイルし、説明してくれませんか。

NUM_ITERATIONS の引数として 100 000 000 を指定して実行すると、Linux では Windows よりも 20 倍遅くなります。デュアル ブート win + ubuntu linux を備えた同じアーキテクチャのマシンでテスト済み。このランダム関数は、データで表示したいもののボトルネックであるため、助けが必要です。

進化的アルゴリズムの理解に問題があります。私はこの手法を数回使用しようとしましたが、常に同じ問題に遭遇しました。それは、シミュレーテッドアニーリングへの縮退です。

かっこで囲まれたフィットネスを使用した最初の人口は次のとおりです。

A（7）、B（9）、C（14）、D（19）

交配と突然変異の後、私には次の子供がいます：

AB（8.3）、AC（12.2）、AD（14.1）、BC（11）、BD（14.7）、CD（17）

最も弱いものを排除した後、私たちは

A、AB、B、AC

次のターン、ABは再び交尾し、結果は約8になり、ACを押し出します。次のターン、ABは再び、Bを押し出します（突然変異が主に> 1の範囲で適応度を変えると仮定します）。

現在、わずか数ターン後に、プールには元々最も適切な候補（A、B）とそれら2つの突然変異（AB）が入力されます。これは、初期プールのサイズに関係なく発生しますが、少し時間がかかります。たとえば、初期人口が50の場合、50ターンかかり、その後、他のすべてが排除され、より複雑なシミュレーテッドアニーリングでセットアップ全体が回転します。初めに、私も候補者を自分たちと交配させ、問題を悪化させました。

だから、私は何が恋しいですか？私の突然変異率は単純に小さすぎますか？それを増やすと消えますか？

これが私がそれを使用しているプロジェクトです： http ：//stefan.schallerl.com/simuan-grid-grad/ ええ、コードはバグがあり、インターフェースはひどいです、しかし私は今それを修正するのが面倒です-そして注意してください、それはあなたのブラウザをロックするかもしれません。Firefoxは一度はクロームより遅くないと思っていても、クロームを使用する方が良いでしょう（おそらく、画像比較のトレースは効果があります、イェーイ！）。興味のある方は、ここでコードを見つけることができます。

ここで私はev-algのアイデアを捨てて、シミュレーテッドアニーリングに行きました。

ps：シミュレーテッドアニーリングについてさえよくわかりません-それは進化的アルゴリズムのようなもので、人口サイズが1だけですよね？

基本的に、多次元ナップザック問題のシミュレーテッド アニーリングの実装を作成しようとしています。より低い値の状態を受け入れるかどうかをシステムに決定させるのに問題があります。アニーリングは次の関数で制御されます。

acceptNext() 関数は、次の状態を受け入れるかどうかを決定し、次のように定義されます。

いくつかのテストを行った後、acceptNext() 関数が呼び出される前に currentBag フィールドが次の値に割り当てられていることがわかりました。どのコードにも別の「this.currentBag = next」が見つかりません。完全を期すために、ここに getNext() 関数を示します。

何がこの値を更新しているのかわかりません。誰かがコードに何かを見ていますか?

ありがとう

ベン

決定論的アニーリングのコードのオープン ソースの例を見つけたいと思います。C、C++、MatLab/Octave、Fortran など、ほぼすべての言語で使用できます。シミュレートされたアニーリング用の MatLab コードを既に見つけたので、MatLab が最適です。このアルゴリズムを説明する論文は次のとおりです。

決定論的アニーリングは、コスト関数のグローバルな最小値を見つけようとする最適化手法です。この手法は、ローカル情報を使用して最適化を実行しながら、ランダム性を使用してコスト面の大部分を調査できるように設計されています。この手順は、コスト関数を変更してランダム性の概念を導入することから始まり、広い領域を探索できるようにします。各反復でランダム性の量 (Shannon Entropy [2] で測定) が制限され、局所的な最適化が実行されます。課される乱数の量が徐々に減少し、終了時にアルゴリズムが元のコスト関数を最適化し、元の問題に対する解が得られます。

学生とプロジェクトの特定の割り当てを最適化するために、シミュレーテッド アニーリング アルゴリズムを実行しています。

これは、Wikipedia の言語に依存しない疑似コードです。

以下は、テクニックの適応です。私の上司は、そのアイデアは理論的には問題ないと言いました。

最初に、ランダム化された割り当てのセット全体からいくつかの割り当て (つまり、プロジェクトのランクを含む、学生と割り当てられたプロジェクトの辞書全体) を取得し、それをコピーして関数に渡します。この割り当てを呼び出しましょうaOld(辞書です)。aOldと呼ばれるそれに関連する重みがありwOldます。重み付けについては後述します。

この関数は次のことを行います。

• この割り当てaOldをbest_node
• すべての生徒からランダムな数の生徒を選び、リストに貼り付けます
• それらのプロジェクトを削除 (DEALLOCATE) ++ プロジェクト (allocatedパラメーターは now False) と講師の変更を反映 (1 つ以上のプロジェクトが割り当てられなくなった場合はスロットを解放)
• そのリストをランダム化する
• そのリスト プロジェクトの全員を再度割り当て (REALLOCATE) してください。
• 重みを計算します (ランクを合計します。ランク 1 = 1、ランク 2 = 2... およびプロジェクトなしのランク = 101)。
• この新しい割り当てaNewでは、重みが最初に選択しwNewた割り当ての重みよりも小さい場合、これは (上記のアルゴリズムで定義された) です。アルゴリズムを適用して続行します。wOldbest_nodeSimulated AnnealingaNew
• の場合wOld < wNew、アルゴリズムをaOld再度適用して続行します。

割り当て/データポイントは、「ノード」として表現されます。node = (weight, allocation_dict, projects_dict, lecturers_dict)

現時点では、このアルゴリズムは 1 回しか実行できませんが、数値 N (kmaxウィキペディアのスニペットでは で示されています) を試して、以前nodeの とbest_node.

元の辞書 (リセットしたいかもしれません) を変更しないように、辞書の浅いコピーを作成しました。ドキュメントで読んだことから、参照をコピーするだけのようで、辞書にはオブジェクトが含まれているため、コピーされた辞書を変更するとオブジェクトが変更されます。copy.deepcopy()これらの辞書は、SQLA でマップされたオブジェクトを参照します。

Questions:

私は直面している問題に対していくつかの解決策を与えられてきましたが、Python を使用することに対する私の環境への配慮のせいで、それらはすべて私にはやや不可解に聞こえます。

1. Deepcopy は SQLA とうまく連携していません。ORM オブジェクトのディープコピーにはおそらく問題があり、期待どおりに動作しないと言われています。どうやら、「コピー コンストラクター、つまり def copy(self): return FooBar(....) を作成する」ほうがよいようです。誰かがそれが何を意味するのか説明してもらえますか?

2. deepcopySQLAlchemy がオブジェクトに余分な情報を配置するため、問題があることがわかりました。つまり_sa_instance_state、コピーには入れたくないが、オブジェクトに必要な属性です。「古いものを手動で吹き飛ばして_sa_instance_state新しいものをオブジェクトに付ける方法はありますが、最も簡単なのは、新しいオブジェクトを作成して、__init__()重要な属性を設定することです。ディープコピー。」それは正確にはどういう意味ですか？古いマップされたクラスに似た、マップされていない新しいクラスを作成する必要がありますか?

3. 別の解決策は、「オブジェクトに実装__deepcopy__()し、新しい _sa_instance_state が設定されていることを確認する必要があります。それを支援できる関数が sqlalchemy.orm.attributes にあります。」繰り返しますが、これは私を超えているので、誰かが親切にそれが何を意味するのか説明できますか?

4. より一般的な質問：上記の情報が与えられた場合、best_node（whileループを通じて常に持続する必要がある）およびprevious_node実際のオブジェクト（辞書によって参照されるため、ノードの場合）の情報/状態を維持する方法に関する提案はありますか) が行われているため、割り当て解除/再割り当てが変更されていますか? つまり、コピーを使用せずに？

ウィキペディアとこのサイトの両方で、シミュレーテッド アニーリング アルゴリズムの同様のステップについて説明しています。

ウィキペディア:

Yuval Baror は、8 人の女王のパズルについて次のように述べています。

私の質問は次のとおりです。このランダムな動きは何を達成しますか?

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

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

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

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

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

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

ありがとう！

マイク