Loading article…
タブーサーチ（TS）は、数学的最適化に使用される局所探索法を採用したメタヒューリスティック探索法です。これは、1986年にフレッド・W・グローバーによって考案され[ 1 ]、1989年に形式化されました[ 2 ] [ 3 ]。
局所探索（近傍探索）は、問題の潜在的な解を取り上げ、そのすぐ近くにある解（つまり、ごくわずかな細部を除いて類似している解）を調べて、より良い解を見つけようとする手法です。局所探索法は、最適解ではない領域や、多くの解が同程度に適合するプラトーに陥りやすい傾向があります。
タブーサーチは、局所探索の基本ルールを緩和することで、その性能を向上させます。まず、各ステップにおいて、 改善する手がない場合（例えば、探索が厳密な局所最小値で行き詰まっている場合など）、悪化する手も許容されます。さらに、以前に訪れた解に戻ることを防ぐために、禁止事項（タブーという用語の由来）が導入されています。
タブーサーチの実装では、訪問したソリューションやユーザーが指定したルールセットを記述するメモリ構造を使用します。[ 2 ]潜在的なソリューションが特定の短期間内に以前に訪問されたことがある場合、またはルールに違反している場合は、「タブー」（禁止）としてマークされ、アルゴリズムがその可能性を繰り返し考慮しないようにします。
タブーという言葉は、神聖なものであるため触れてはならないものを指すトンガ語に由来する。 [ 4 ]
タブーサーチは、組み合わせ最適化問題（選択肢の最適な順序付けと選択が求められる問題）を解決するために使用できるメタヒューリスティックアルゴリズムです。
タブーサーチの現在の応用分野は、資源計画、電気通信、VLSI設計、財務分析、スケジューリング、空間計画、エネルギー配分、分子工学、ロジスティクス、パターン分類、フレキシブル製造、廃棄物管理、鉱物探査、生物医学分析、環境保全など、多数の分野に及んでいます。近年、さまざまな分野の学術誌に、タブーサーチによって効果的に処理できる問題の範囲を拡大することに成功したチュートリアル記事や計算研究が掲載されており、その結果得られるソリューションの質は、従来適用されていた方法で得られたものを大幅に上回ることがよくあります。実用的な実装から得られた成果の概要を含む、応用例の包括的なリストは[ 5 ]に記載されています。
タブーサーチは、局所的または近傍的な探索手順を使用して、1 つの潜在的な解から反復的に移動します。より良い解決策へ近隣では何らかの停止条件 (一般的には試行回数の制限またはスコアの閾値) が満たされるまで、探索を続けます。局所探索手順は、スコアが低い領域やスコアが横ばいになる領域で行き詰まることがよくあります。このような落とし穴を回避し、他の局所探索手順では探索されない探索空間の領域を探索するために、タブー探索では、探索の進行に伴って各解の近傍を慎重に探索します。新しい近傍に受け入れられた解は、はメモリ構造を用いて決定されます。これらのメモリ構造を用いて、探索は現在の解から反復的に移動することで進行します。より良い解決策へで。
タブーサーチは、シミュレーテッドアニーリングといくつかの類似点があり、どちらも下り坂の移動の可能性を伴います。実際、シミュレーテッドアニーリングはタブーサーチの特殊な形式と見なすことができ、そこでは「段階的テニュア」、つまり、特定の確率で移動がタブーになるという仕組みを採用しています。
これらのメモリ構造はタブーリストと呼ばれるものを形成し、近隣に受け入れられるソリューションをフィルタリングするために使用される一連のルールと禁止ソリューションです。検索によって探索される。最も単純な形式では、タブーリストは、最近（1週間未満）訪問されたソリューションの短期的なセットである。反復前、 は保存される以前の解の数です（タブー期間とも呼ばれます）。より一般的には、タブーリストは、ある解から別の解へ移行する過程で変化した属性で構成されます。説明を容易にするために、「解」はこのような属性によってコード化され、表現されると理解するのが便利です。
タブーサーチで使用されるメモリ構造は、大まかに3つのカテゴリに分類できます。[ 6 ]
短期記憶、中期記憶、長期記憶は実際には重複することがあります。これらのカテゴリ内では、記憶は変更の頻度や影響などの尺度によってさらに区別できます。中期記憶構造の一例として、特定の属性を含むソリューション（例えば、特定の変数に望ましくない値または望ましい値を含むソリューション）を禁止または推奨する構造、あるいは特定の動きを防止または誘発する記憶構造（例えば、過去に見つかった魅力的でないソリューションまたは魅力的なソリューションと共通の特徴を共有するソリューションに適用される頻度記憶に基づく）が挙げられます。短期記憶では、最近訪れたソリューションの選択された属性は「タブーアクティブ」とラベル付けされます。タブーアクティブ要素を含むソリューションは禁止されます。ソリューションのタブー状態を上書きするために、アスピレーション基準が使用され、それによって、そうでなければ除外されるソリューションが許可されたセットに含まれます（ソリューションが品質または多様性の尺度に従って「十分良い」場合）。単純でよく使用されるアスピレーション基準は、現在知られている最良のソリューションよりも優れたソリューションを許可することです。
短期記憶だけでも従来の局所探索法で見つかる解よりも優れた解を得るのに十分かもしれないが、より難しい問題を解決するには中間および長期の構造が必要になることが多い。[ 7 ]タブー探索は、シミュレーテッドアニーリング、遺伝的アルゴリズム、アリコロニー最適化アルゴリズム、リアクティブ探索最適化、ガイド付き局所探索、または貪欲ランダム化適応探索などの 他のメタヒューリスティック法と比較されることが多い。さらに、タブー探索は、ハイブリッド法を作成するために他のメタヒューリスティックと組み合わされることもある。最も一般的なタブー探索ハイブリッドは、TS とスキャッター探索[ 8 ] [ 9 ]を組み合わせることによって生じる。スキャッター探索は、タブー探索と共通のルーツを持つ集団ベースの手順のクラスであり、大規模な非線形最適化問題を解決するためによく使用される。
以下の擬似コードは、上述のタブー探索アルゴリズムの簡略版を示しています。この実装は基本的な短期記憶を備えていますが、中間記憶や長期記憶構造は含まれていません。「適合度」とは、数学的最適化のための目的関数で表される、候補解の評価を指します。
sBest ← s0sCurr ← s0ベスト候補← s0タブリスト← []tabuList.push ( s0 )while (停止条件()でない場合)sNeighborhood ← getNeighbors ( sCurr )ベスト候補者の適性← - ∞( sCandidate in sNeighborhood )if ( ( not tabuList . contains ( sCandidate ))かつ( fitness ( sCandidate ) > bestCandidateFitness ) )ベスト候補者← s候補者ベスト候補者の適性←適性(ベスト候補者)終わり終わりif ( bestCandidateFitness is -∞ )壊す;終わりsCurr ←ベスト候補者if ( bestCandidateFitness > fitness ( sBest ))ベスト←ベスト候補者終わりtabuList.push ( bestCandidate )if ( tabuList . size > maxTabuSize )tabuList.removeFirst ( )終わり終わりsBestを返す1～5行目は、それぞれ初期設定を表しており、初期解（ランダムに選択される場合もある）の作成、その初期解を現時点で最良の解として設定すること、そしてこの初期解を用いてタブーリストを初期化することを行っています。この例では、タブーリストは、訪問した状態の要素を記録する短期記憶構造です。
コアとなるアルゴリズムループは6行目から始まります。このループは、ユーザーが指定した停止条件が満たされるまで最適な解の探索を続けます（停止条件の例としては、単純な時間制限や適合度スコアの閾値などがあります）。10行目では、近傍の解にタブー要素が含まれていないかを確認します。さらに、アルゴリズムは近傍でタブーではない最良の解を追跡します。
適合度関数は一般的に数学関数であり、スコアを返すか、または目標基準が満たされます。たとえば、目標基準は新しい探索空間が見つかったとみなすことができます。[ 4 ]最良の局所候補の適合度が現在の最良の候補よりも高い場合（20 行目）、それが新しい最良の候補として設定されます（21 行目）。局所最良の候補は常にタブー リストに追加され（23 行目）、タブー リストがいっぱいの場合（24 行目）、一部の要素が期限切れになります（25 行目）。一般的に、要素は追加された順序と同じ順序でリストから期限切れになります。この手順では、局所最適解から逃れるために、最良の局所候補（現在の最良の候補よりも適合度が低い場合でも）を選択します。
このプロセスは、ユーザーが指定した停止条件が満たされるまで継続され、その時点で検索プロセス中に見つかった最良の解が返されます（28行目）。
巡回セールスマン問題(TSP) は、タブーサーチの機能を示すためによく使用されます。[ 7 ]この問題は、都市のリストが与えられたとき、すべての都市を訪れる最短ルートは何かという単純な質問です。たとえば、都市 A と都市 B が隣接していて、都市 C が遠くにある場合、都市 C を訪れる前に都市 A と B を順番に訪問すると、移動の総距離が短くなります。 最適な解を見つけることはNP 困難であるため、ヒューリスティックに基づく近似法 (局所探索など) は、最適に近い解を考案するのに役立ちます。優れた TSP 解を得るには、グラフ構造を活用することが不可欠です。問題構造を活用する価値はメタヒューリスティック法で繰り返し取り上げられるテーマであり、タブーサーチはこれに適しています。タブーサーチに関連するエジェクションチェーン法と呼ばれる戦略クラスにより、高品質の TSP 解を効率的に得ることが可能になりました。[ 10 ]
一方、単純なタブーサーチは、巡回セールスマン問題の満足解（つまり、グラフ構造を利用して得られるような高品質ではないものの、妥当性基準を満たす解）を見つけるために使用できます。探索は初期解から始まります。初期解は、ランダムに生成することも、何らかの最近傍アルゴリズムに従って生成することもできます。新しい解を作成するには、潜在的な解で訪問する 2 つの都市の順序を交換します。すべての都市間の総移動距離を使用して、ある解が別の解と比較してどれだけ理想的かを判断します。サイクル（つまり、特定の解のセットを繰り返し訪問すること）を防ぎ、局所最適解に陥ることを避けるために、解が解の近傍に受け入れられた場合、その解はタブーリストに追加されます。。
反復回数などの停止条件が満たされるまで、新しい解が生成されます。単純なタブー探索が停止すると、実行中に見つかった最良の解が返されます。