1

MarxanとConsNetという 2 つの保全地域設計ツールの比較を行っています。どちらもメタヒューリスティック アルゴリズムを使用して、最小集合被覆問題のバージョンを解決します。Marxan はシミュレーテッド アニーリングを使用し、ConsNet はタブー検索を使用します。私のバックグラウンドは生物学ですが、メタヒューリスティクスを通じて最適化の概念のいくつかを理解できたと思います。

しかし、タブー検索について、まだわかっていないことが 2 つあります。1 つ目は、ローカル オプティマを回避する方法です。私はそれがその動きを元に戻すことができないことを知っています、そしてそれはそれが循環するのを止めます、しかし私はそれがそれを見つけたらそれが局所最適を残す理由を知りません. シミュレーテッド アニーリングがどのようにそれを行うかは理解できます - より悪い解決策を受け入れなくなるまで時間の経過とともに減少するより悪い解決策を受け入れる可能性がありますが、TS がどのようにそれを行うかはわかりません。

2 番目の問題は、ConsNet のマニュアルに次の記述があることです。

検索は完全に決定論的ですが、ソリューション アーカイブの現在の状態または目標の現在の状態に基づいて、どのように進めるかを決定できます。

TS は常に決定論的ですか? いくつかの情報源を読んで、移動は SA のようにランダムである可能性があるという考えを得ました。しかし、「決定論的タブー検索」について話している論文がいくつかあります。決定論的タブー検索は、どの動きを取るべきかをどのように認識し、どのように局所最適を回避しますか? 時にはもっと悪い解決策を受け入れなければなりませんよね？

よろしくお願いします

4

1 に答える 1

2

複数の質問なので、複数の回答:)

  • タブー検索はローカル オプティマから抜け出します。これは、その方法を示す画像です。すべての改善ソリューションがタブーであり (そして熱望されていない)、すべての動きが評価されているか、selectionLimit または AcceptedLimit に達している場合、より悪いソリューションを受け入れます。

  • TS と SA はどちらも「再現可能」と書くことができます。つまり、2 回実行しても同じ結果が得られます。「完全に決定論的」（これは別のプロパティです）と言うことでそれを暗示したかったのだと思います。再現可能にするための秘訣は簡単です。どこでも同じ Random インスタンスを再利用し、固定の randomSeed で開始するだけです。

  • TS は、スケールアウトすると、妥当なサイズのデータ​​セットで、ステップごとに考えられるすべての移動を評価できなくなります。したがって、ランダム選択にも頼る必要があります。

  • TS、SA (およびその点については後期受理) は競争力があります。それは、最高のパフォーマンスを発揮するユースケースに依存します (事前に予測することはほとんど不可能です)。そのため、必要な制約はどれが最も効果的であるかに影響を与える可能性がありますが、実際のデータセットへの影響ははるかに小さくなります。

注: 私はOptaPlanner (Java、オープン ソース) と提携しています。

于 2013-11-13T07:22:04.653 に答える