論文の概要: Hybrid Metaheuristic Combining the Dragonfly Algorithm and Tabu Search for the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2606.09529v1
- Date: Mon, 08 Jun 2026 14:14:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-09 14:42:07.181566
- Title: Hybrid Metaheuristic Combining the Dragonfly Algorithm and Tabu Search for the Traveling Salesman Problem
- Title（参考訳）: DragonflyアルゴリズムとTabu Searchを組み合わせたハイブリッドメタヒューリスティックによる旅行セールスマン問題の解法
- Authors: Ammar Bouketta,
- Abstract要約: 本稿では,Dragonfly Algorithm(DA)とTabu Search(TS)を組み合わせた旅行セールスマン問題(TSP)のハイブリッドメタヒューリスティックを提案する。
提案手法は高レベルリレーハイブリダイゼーション(HRH)方式に従っており、DAは最初に解空間を探索し、有望な初期ツアーを生成する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Traveling Salesman Problem (TSP) is a classical NP-hard combinatorial optimization problem that aims to find the shortest Hamiltonian cycle visiting each city exactly once and returning to the starting point. This paper proposes a hybrid metaheuristic for the TSP by combining the Dragonfly Algorithm (DA), a swarm-intelligence-based global search method, with Tabu Search (TS), a memory-based local search technique. The proposed method follows a High-Level Relay Hybridization (HRH) scheme, in which DA is first used to explore the solution space and generate a promising initial tour, while TS subsequently refines this solution through neighbourhood-based improvement and tabu memory. The hybrid approach is evaluated on standard TSPLIB benchmark instances, including burma14, att48, and ch150, and compared with standalone DA, standalone TS, and several classical metaheuristics such as Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization, and Random Search. A systematic grid-search procedure is also conducted to study the influence of the main hyperparameters on solution quality and execution time. The experimental results indicate that the proposed hybrid can improve tour quality compared with the standalone DA and TS on the tested instances, highlighting the benefit of combining global exploration with local exploitation. However, the results also suggest that performance remains sensitive to parameter settings and problem size, motivating further validation on larger benchmarks and stronger TSP-specific baselines.
- Abstract（参考訳）: トラベリングセールスマン問題 (TSP) は古典的なNPハード組合せ最適化問題であり、各都市を正確に1度訪れて出発点に戻る最短のハミルトンサイクルを見つけることを目的としている。
本稿では,Swarm-intelligence-based global search法であるDragonfly Algorithm(DA)と,メモリベースのローカル検索手法であるTabu Search(TS)を組み合わせたTSPのハイブリッドメタヒューリスティックを提案する。
提案手法は高レベルリレーハイブリダイゼーション(HRH)方式に従っており,DAはまず解空間を探索し,期待できる初期ツアーを生成する。
ハイブリッドアプローチは、burma14、att48、ch150などの標準TSPLIBベンチマークインスタンスで評価され、スタンドアロンのDA、スタンドアロンのTS、および遺伝的アルゴリズム、アントコロニー最適化、パーティクルスワーム最適化、ランダム検索などの古典的メタヒューリスティックと比較される。
また, 主パラメータが溶液品質および実行時間に与える影響を解析するために, 系統的グリッドサーチ手法も実施した。
実験結果から,本ハイブリッドは,テストインスタンス上でのスタンドアロンDAやTSと比較してツアー品質を向上し,グローバル探索とローカルエクスプロイトを併用するメリットを浮き彫りにした。
しかし、結果はパラメータ設定や問題サイズに敏感であり、より大きなベンチマークとより強力なTSP固有のベースラインに対するさらなる検証を動機付けていることも示唆している。
関連論文リスト
- STABLE: Efficient Hybrid Nearest Neighbor Search via Magnitude-Uniformity and Cardinality-Robustness [59.119196450578364]
Hybrid ANNS (Hybrid Approximate Nearest Neighbor Search) は、大規模な異種データに対する基礎的な検索技術である。
本稿では, 類似性マグニチュード不均一性に対する適合性バリアと, 属性心に対する耐性ボトルネックを克服するためのrobuSt heTerogeneity-Aware hyBrid retrievaL framEwork, STABLEを提案する。
論文 参考訳（メタデータ） (2026-04-02T04:52:35Z) - Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimization [58.54587318370824]
ツアーと最小スパンニングツリー(MST)のばらつきを分析してトラベルセールスマン問題(TSP)に対するトポロジカルフィードバック機構を導入する。
論文 参考訳（メタデータ） (2025-12-16T20:04:25Z) - A Gradient Meta-Learning Joint Optimization for Beamforming and Antenna Position in Pinching-Antenna Systems [63.213207442368294]
マルチ導波路ピンチアンテナシステムの新しい最適化設計について検討する。
提案したGML-JOアルゴリズムは,既存の最適化手法と比較して,様々な選択や性能に頑健である。
論文 参考訳（メタデータ） (2025-06-14T17:35:27Z) - Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。
大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。
統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
論文 参考訳（メタデータ） (2025-05-13T16:47:00Z) - PSO and the Traveling Salesman Problem: An Intelligent Optimization Approach [0.0]
トラベリングセールスマン問題(TSP)は、各都市を正確に1度訪れて出発点に戻る最短ルートを見つけることを目的とした最適化問題である。
本稿では,人口ベース最適化アルゴリズムであるParticle Swarm Optimization (PSO) のTSP解決への応用について検討する。
論文 参考訳（メタデータ） (2025-01-25T20:21:31Z) - LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。
このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
論文 参考訳（メタデータ） (2024-10-03T18:12:29Z) - Surpassing legacy approaches to PWR core reload optimization with single-objective Reinforcement learning [0.0]
単目的および多目的の最適化のための深層強化学習(DRL)に基づく手法を開発した。
本稿では、PPO(Proximal Policy Optimization)を用いて、RLに基づくアプローチの利点を実証する。
PPOは学習可能なウェイトを持つポリシーで検索機能を適応し、グローバル検索とローカル検索の両方として機能する。
論文 参考訳（メタデータ） (2024-02-16T19:35:58Z) - A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman
Problem [0.9790236766474201]
本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。
新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。
我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
論文 参考訳（メタデータ） (2023-07-14T01:57:10Z) - Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic
Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
本稿ではHenry Gas Solubility Optimization(HGSO)アルゴリズムの新しい変種であるHGSO(Hybrid HGSO)について述べる。
前者とは異なり、HHGSOは異なるメタヒューリスティックアルゴリズムを提供する複数のクラスタを同じ集団内で共存させることができる。
HHGSOは、適応的な切替係数を持つペナル化および報酬モデルによる動的クラスタ-アルゴリズムマッピングを発明し、メタヒューリスティックなハイブリダイゼーションのための新しいアプローチを提供する。
論文 参考訳（メタデータ） (2021-05-31T12:42:15Z) - A Population-based Hybrid Approach to Hyperparameter Optimization for
Neural Networks [0.0]
HBRKGAは、Biased Random Key Genetic AlgorithmとRandom Walk技術を組み合わせて、ハイパーパラメータ空間を効率的に探索するハイブリッドアプローチである。
その結果、HBRKGAは8つのデータセットのうち6つにおいて、ベースライン法よりも優れたハイパーパラメータ構成を見つけることができた。
論文 参考訳（メタデータ） (2020-11-22T17:12:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。