タブーサーチ
アルゴリズムの流れを以下に示す。
初期状態 S0 を決定する(通常はランダム)。
最良状態 Sb と現在状態 S を作成し、とりあえず S0 を両方に記録しておく。
S の近傍を複数(M 個)選び、その中で最も成績の良い近傍を S' とおく(この比較にS は入らないことに注意)
状態遷移を判定(以下のどちらか) もしS' がSb より良い値ならSb =S =S' とする。このときタブーリストにS →S' になる操作が記載されている場合、その部分をタブーリストの一番新しい記載に移動する。 もしS' がSb より悪い値なら、S →S' になる操作がタブーリストに記載されているかどうかを確認する。記載されていないならタブーリストにS →S' となる操作を記載して S =S' とする。このときタブーリストのサイズが上限を越えているなら、一番古い記載を削除する。
終了条件が満たされるまで 3. 以下の操作を繰り返し、最終的にSb を解として出力する。
この方法は他のメタヒューリスティックと違い最良解は必ず保存することがアルゴリズム内に組み込まれている。この理由はタブーサーチにおける状態は常に遷移し続けている(タブーリストの記載方法しだいでは停滞することもあるが、それはやってはならない操作とされる)ため最終状態が最良状態である可能性が極めて低いからである。