問題タブ [tabu-search]

このタブー検索ページ 7 の例を理解するのを手伝ってくれませんか:

TS は数学的最適化手法であり、軌跡ベースの手法のクラスに属します。タブー検索は、訪問したソリューションを記述するメモリ構造を使用することにより、ローカル検索メソッドのパフォーマンスを向上させます。潜在的なソリューションが決定されると、「タブー」(「タブー」は同じ単語の異なるスペル) としてマークされます。アルゴリズムはその可能性に繰り返しアクセスしません。タブー検索は Fred W. Glover によるものです

上三角形が使用される理由と、これがなぜなのかわかりません。

タブー構造は、モジュール 4 と 5 の位置の交換が 3 回の繰り返しで禁止されていることを示しています。このステップで最も改善する方法は、3 と 1 を入れ替えて 2 倍にすることです。

なぜ三角形なのか、なぜそれが上記のステートメントなのか説明していただけますか?

???

最も重要な詳細なタブー検索の例を知っていますか。

私はこのクールなアルゴリズムを理解するのを邪魔しているので、難しいことではありません。

私はこのチュートリアルとこれをSATの問題で見つけましたが、あまり詳細ではありません

「Drools Planner」パッケージを使用して、部分的に初期化された数独パズル (新聞に掲載されているようなもの) を解こうとしていました。3 秒でゼロから(ランダムな) パズルを生成できますが、部分的に初期化されたパズルを解くループに陥ります。

質問: タブー検索やシミュレートされたアニーリングなどのヒューリスティックは、数独にとって基本的に悪い選択ですか? 私が話しているのは、完全性 (解決策に到達するかどうか) と効率性 (やり過ぎかどうか) です。

私の疑問は、数独パズルには常に正確で単一の解決策があり、ヒューリスティックアルゴリズムは（AFAIK）「それらに到達する」ように設計されていないという事実から来ています。

それぞれ 10 ～ 50 のエッジを持つ何千もの頂点を含むグラフの色付けの問題があります。多くのグラフ カラーリング ヒューリスティック (GA、タブー検索など) を調査してきましたが、それらを比較して、どれが自分に最も適しているかを判断するのは難しいと感じています。技術を推奨するため、またはこのドメインの現在の最先端のアルゴリズムについて私に知らせるために、大規模なグラフの色付けの経験がある人はいますか?

ありがとう。

TSPTW問題にタブーサーチを適用したところ、交換ピボットルール（2都市間の交換）を使用して最良の改善を得るのと同様の結果が得られましたが、いくつかの論文では、タブーは最適なものに近い良い結果を与えると述べられています（私は持っています別のアルゴリズムを使用して、制約違反が 0 の同じ初期ソリューションの最適なソリューション)。だから私は確信したい、この結果は正常ですか?そして、ここにタブーを適用する私の擬似コードがあります:

}

テキスト ファイル内の項目を読み取るコードがあります。行ごとに読み取ります。アイテムが読み取られると、リストに追加され、再度アクセスできないようになります。リストがいっぱい (最大サイズ) になると、リストはクリアされます。ただし、リストがクリアされた場合でも、事前定義された値のためにこの特定のアイテムに再度アクセスするのを防ぐために、リストに追加されたアイテムを確認する必要があります。

C# 2012 で行う方法を理解するのを手伝ってください。

ありがとう

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

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

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

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

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

よろしくお願いします

巡回セールスマンの問題を解決するために、ヒル クライミング アルゴリズムを使用してタブー検索を理解しようとしています。

「純粋な」ヒル クライミング アルゴリズムは理解していますが、タブー検索がこのアルゴリズムをどのように変更するかはよくわかりません。

ヒルクライミングデモンストレーション：

たとえば、6 つの都市A、B、C、D、E、Fが与えられ、移動コストが 120の初期状態(A、B、C、D、E、F)をランダムに選択するとします。

次に、隣接する州のセットを選択し (1 番目の要素を 2 番目、3 番目、4 番目などと交換して)、それぞれの移動コストを計算します。

これで、局所最適値 (F,B,C,D,E,A) が見つかりました。

Tabu Search は上記のアルゴリズムをどのように変更しますか? 1 回か 2 回の反復を実演していただければ、非常にありがたいです。