Skip to content
検索結果に戻る

Agent-Based Tabu Search — 分散型マルチエージェントメタヒューリスティック最適化

提唱者
Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
年
1989–1995
種類
Hybrid metaheuristic — agent-based distributed tabu search
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

Agent-Based Tabu Search (ABTS) は、タブーサーチメタヒューリスティックをマルチエージェントフレームワーク内に埋め込んだもので、各自律エージェントが独立または協調的なタブーサーチスレッドを実行し、有望な解を共有することで局所最適解からの脱出を図り、単一スレッド実装よりも効果的に大規模な組み合わせ探索空間または連続探索空間を集合的に探索します。

手法の背後にある直感

古典的なタブーサーチは、短期記憶メカニズムを備えていても、狭い領域の探索に陥ることがあります。複数の自律エージェントを展開することで、それぞれが独自のタブーリストと近傍構造を維持し、探索は多様な開始点に広がります。エージェントは定期的にエリート解(強化学習)を共有し、意図的に未踏領域(多様化)に散らばります。この協調的かつ独立した構造は、生物の群れの行動を模倣しています。単一のエージェントが全体像を把握しているわけではありませんが、集合体は個々の探索者よりもはるかに速く高品質な解を見つけます。

歴史学

タブーサーチは、1986年から1989年にかけてFred Gloverによって形式化されました。分散型および並列型のバリアントは、マルチプロセッサアーキテクチャの活用を求める研究者によって1990年代初頭に登場しました。VerhoevenとAarts(1995)は、協調的なタブー戦略を含む並列局所探索の体系的な研究を提供しました。エージェントベースのフレームワークは、エージェントベースモデリングの語彙がオペレーションズリサーチに参入した2000年代に顕著になりました。

使うべき場面

Agent-Based Tabu Search は、単一スレッドのタブーサーチが停滞し、並列計算リソースが利用可能な場合に、スケジューリング、ルーティング、ネットワーク設計、リソース割り当てなどの困難な組み合わせまたは混合整数最適化問題を解決するために使用します。特に、探索ランドスケープに同程度の品質の局所最適解が多数存在する場合に効果的です。問題が正確解法(MILP、分枝限定法)で解けるほど小さい場合、単一の評価が計算上実行不可能である場合(多数の並列評価が不可能になる)、または再現性要件が非決定論的でエージェント間相互作用のダイナミクスと競合する場合を除いてください。

限界と注意点

  • エージェント間の同期オーバーヘッドと通信コストは、タイトに結合されたシステムまたは低速ネットワークでの並列化の利点を相殺する可能性があります。
  • 単一スレッドのタブーサーチよりも多くのハイパーパラメータが必要です。エージェント数、通信トポロジー、同期頻度、多様化トリガーはすべて調整が必要です。
  • 理論的な収束保証は正確な手法よりも弱いです。解の品質は、チューニングと問題構造に大きく依存します。
  • エージェント間の相互作用により、初期化のランダム性以外に追加の確率性が導入されるため、再現性の確保が困難です。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 並列探索は、単一スレッドのタブーサーチと比較して、大規模な組み合わせ問題における解発見時間を大幅に短縮します。
  • マルチエージェントフレームワークは、多様化を自然にサポートし、貧弱な局所最適解への早期収束のリスクを低減します。
  • 柔軟なアーキテクチャにより、異なる近傍構造、タブーテンチャー戦略、または混合メタヒューリスティックを持つ異種エージェントをサポートできます。
  • 協調的な解共有は、エージェント間で発見を転送し、高品質領域周辺の強化学習を加速します。
  • 利用可能な計算コアに合わせてうまくスケーリングするため、最新のマルチコアおよび分散コンピューティング環境に適しています。

応用

  • 車両ルーティングとロジスティクス:各エージェントがルートのサブ問題を最適化するのを調整します。
  • ジョブショップおよびフレキシブル製造スケジューリング:エージェントが機械サブセットを協調的に処理します。
  • 通信ネットワーク設計:分散チャネル割り当てとトポロジー最適化。
  • サプライチェーン計画:マルチエシュロン在庫および流通最適化。
  • タンパク質構造予測:コンフォメーション空間全体での並列近傍探索。
  • 学術タイムテーブルおよびコーススケジューリング(分散型学部レベルのエージェントを使用)。

使い方

使い方

1

自律エージェントの集団を定義します。各エージェントには役割が割り当てられます。一部は強化学習(有望な領域周辺の深い局所探索)に焦点を当て、他は多様化(未踏領域からの脱出)に焦点を当てます。各エージェントは、禁止された移動の独自のタブーリスト、現在の解、および問題タイプ(組み合わせ問題の場合はスワップ、挿入、または2-opt移動など)に合わせて調整された近傍構造を維持します。

2

エージェントを異なる開始解で初期化します。これらはランダムに生成されるか、構成ヒューリスティック(ルーティングの場合は最近傍法など)によってシードされます。開始解の多様性が重要です。同一の開始解は冗長な並列探索につながります。各初期解の目的関数を評価し、すべてのエージェントにわたるグローバルベスト解を記録します。

3

各エージェントは独自のタブーサーチループを実行します。現在の解の近傍を生成し、すべての(または一部の)近傍解を評価し、タブーではない最良の近傍を次の移動として選択します(願望基準により、候補がグローバルベストを上回る場合はタブーリストを上書きできます)。そして、固定または適応範囲から描画されたテンチャーを持つ逆移動を追加してタブーリストを更新します。

4

エージェントは、定義された同期間隔またはイベントトリガーで通信します。一般的な戦略には、現在のグローバルベストをすべてのエージェントにブロードキャストすること(エージェントはそこから再開する場合があります)、エージェントが定期的に参照する共有プールにエリート解を挿入すること、またはトポロジー(リング、完全接続、またはランダム)内の隣接エージェント間でソリューションをピアツーピアで交換することなどが含まれます。多様性制御は、同一の解を持つエージェントにペナルティを課すことで、早期収束を防ぎます。

5

最大反復回数、壁時計時間制限、または停滞基準(例:指定された反復回数でグローバルベストの改善がない)が満たされた場合に終了します。最終出力として、すべての反復を通じてすべてのエージェントで見つかったグローバルベスト解を選択します。複数の目的が追跡されている場合は、オプションでパレートフロントを報告します。

よくある落とし穴

  • すべて のエージェントに同一の開始解を設定すると、並列容量が無駄になります。多様な初期化を確保してください。
  • 過度に頻繁な通信は、エージェントを同じ解の盆地に押し込み、多様化の利点をなくし、実質的に探索を1つのスレッドに縮小させます。
  • タブーリスト設計で願望基準を無視すると、特に探索初期段階で、エージェントが明らかに優れた解を見逃す可能性があります。
  • 近傍評価がサロゲートモデルなしでは非常にコストのかかる問題にABTSを適用すると、実行時間が許容できなくなります。

よくある質問

Agent-Based Tabu Search は、単純に複数のタブーサーチスレッドを実行するのとどう違うのですか?

主な違いは協調性です。独立した並列実行では、スレッドは情報を共有しません。ABTSでは、エージェントは積極的に解を交換したり、共有エリートプールを更新したり、集合的な状態に基づいて多様化トリガーを採用したりして、独立した実行にはない創発的な探索動作を生み出します。

いくつのエージェントを使用すべきですか?

一般的な開始点は、利用可能なCPUコアごとに1つのエージェントです。研究によると、通信オーバーヘッドが増加するため、ほとんどの組み合わせ問題では8〜16エージェントを超えるとリターンの減少が見られます。4、8、16エージェントでのパイロット実験は、特定の問題のスイートスポットを特定するのに役立ちます。

ABTSは多目的問題を扱えますか?

はい。エージェントはパレートフロントのローカル近似を維持し、共有アーカイブを介して非支配解を共有できます。これは、Multi-Objective Agent-Based Tabu Search と呼ばれることもあり、標準的な単一目的ABTSとは異なります。

どの通信トポロジーが最適ですか?

完全接続トポロジーは良好な解を最も速く広げますが、高い通信コストが発生します。リングまたはスモールワールドトポロジーは、情報拡散と自律性のバランスを取ります。ほとんどの実用的な問題では、リングまたはランダムなスパーストポロジーがデフォルトとしてうまく機能します。

遺伝的アルゴリズムや粒子群最適化よりもABTSを好むのはどのような場合ですか?

問題が連続的で滑らかなランドスケープを持つ場合、またはクロスオーバー/組み換え演算子が明確に定義されている場合は、集団ベースの手法(GA、PSO)を好みます。ABTSは、タブーメモリが強力な探索利点を提供する離散的な組み合わせ問題で、明確に定義された近傍演算子を持つ場合に優れています。

関連する手法

参考文献

  1. Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    DOI 文献を開く
    コピーしました。
  2. Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.

    DOI 文献を開く
    コピーしました。