4

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

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

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

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

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

(B,A,C,D,E,F) = 110   /* <120; mark as optimal */
(C,B,A,D,E,F) = 127
(D,B,C,A,E,F) = 145
(E,B,C,D,A,F) = 102   /* <110; mark as optimal */
(F,B,C,D,E,A) = 80    /* <102; mark as optimal */

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

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

4

2 に答える 2

5

タブー検索 ( TS ) との違いは、保持しているタブー リストです。そして、それが検索にどのように影響するか。このようなタブーリストを生成する最も簡単な方法は、最近の検索を追跡し、それらをタブーリストに含めて、アルゴリズムがさまざまな可能性を「探索」できるようにすることです。タブー リスト ヒューリスティックの例: 都市 D から都市 E に行ったのが 'n' 回未満の反復の場合、'n' は格納される以前のソリューションの数であり、タブー リストに追加されます (タブー内の要素リストには有効期限があります）。

それが実行するステップは、山登りとほとんど同じです。

  1. 初期状態 (ランダムな場合もあります) を選択し、それを最適なオプションとして設定します。

  2. ユーザーによって指定されたブレーク条件 (この例ではしきい値または移動コスト) が満たされているかどうかをチェックするループに入ります。

  3. 空の候補リストを作成します。タブー要素を含まない特定の近隣の各候補は、この空の候補リストに追加されます。

  4. このリストで最適な候補を見つけ、そのコストが現在の最適な候補よりも優れている場合は、ソリューションとしてマークされます。

  5. タブー リストのタブーの数がタブーの最大数 (ユーザーが定義している数) に達した場合、タブーは期限切れになります。リストのタブスは、入力された順序で期限切れになります.. 先入れ先出し。

このプロセスは、ユーザーが定義したしきい値に達するまで繰り返されます。これがどのように機能するかを理解するのに役立つことを願っています:)）

于 2013-12-04T15:02:03.547 に答える
4

免責事項：この回答はリンクに基づいています 【参考-1】Geoffrey De Smetが共有し、彼のコメントでここを指しています。クレジットは彼に行くべきです。

以下に示す 2 つの画像は、タブー検索がヒル クライミング アルゴリズムをどのように変更するかを理解するのに役立ちました。

山登り

山登り (出典: OptaPlanner ユーザーガイド)

タブーサーチ

タブーサーチ (出典: OptaPlanner ユーザーガイド)

参照：

[参考-1] JBoss.orgコミュニティのドキュメント。OptaPlanner ユーザー ガイド。[オンライン] http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/index.htmlで入手できます。[2013 年 12 月 7 日にアクセス]。

于 2013-12-07T09:58:54.283 に答える