1

シミュレートされたアニーリング プログラムを作成していますが、デバッグに問題があります。どんなアドバイスでも大歓迎です。

まず第一に、出力は決定論的ではないため、100 回実行して平均と標準偏差を調べました。

しかし、1 つのテスト ケースを完了するのに何年も (> 30 分) かかります。

通常、私は入力を削減しようとしますが、反復回数を減らすと、完全には予測できない方法で結果の精度が直接低下します。たとえば、冷却スケジュールは、反復回数にスケーリングされた指数関数的減衰です。個別の実行回数を減らすと、出力の信頼性が非常に低くなります (私が見つけようとしているバグの 1 つは、実行間の大きな差異です)。

時期尚早の最適化がすべての悪の根源であることは知っています。プログラムが正しくなる前に最適化するのは時期尚早であるに違いありませんが、これをより高速な言語 (Cython または C) に書き直すことを真剣に考えています。最終的に提出のためにPythonに移植します。

それで、私が今持っているものよりも優れたシミュレートされたアニーリングアルゴリズムをテストする方法はありますか? または、テストの合間に別の作業を行う必要がありますか?

開示：これはコースワークの課題ですが、実際のシミュレーションを手伝ってほしいと言っているわけではありません。

4

1 に答える 1

0

Drools Planner (Java、オープン ソース)でメタヒューリスティック (シミュレーテッド アニーリングやタブ検索など) を実装することから学んだ、デバッグのコツをいくつか紹介します。

  1. environmentModeさまざまなs ( DEBUG、REPRODUCIBLE(デフォルト) および)をサポートしていますPRODUCTION。モードDEBUGandREPRODUCIBLEでは、すべてのコードが同じ Random インスタンスを使用し、Randomインスタンスseedは固定されています。そのため、タブー検索の実装を 2 回実行すると、まったく同じ移動、ステップ、結果のスコアが得られます。シミュレートされたアニーリングの実装は時間勾配に依存しているため、その時点の CPU によっては、わずかな違いが生じる場合があります。注: これは統計的な実行を免除するものではありませんが、1 回の実行を再現可能にします。
  2. 良い、読みやすいログ。ログ レベルを使用します。詳細にログを記録しないでください。
  3. 当社のビルド サーバー (Hudson) は、パフォーマンス統計を保持しています。
  4. Benchmarkerアルゴリズムが何をしたかを簡単に確認できるように、図を出力するツールがあります。そのため、結果だけを見るのではなく、どのようにしてそこにたどり着いたかも見てください。最初はうまくいったかもしれませんが、後で局所的な最適化に行き詰まりました。

ベンチマークの概要

ベンチマークの詳細

アルゴリズムで実際に何が起こっているかについての洞察を与えるのは、好きなことです。

また、 Simulated Annealingに関する私のブログ記事も参照してください。

于 2011-03-08T11:26:20.840 に答える