論文の概要: An Effective Iterated Two-stage Heuristic Algorithm for the Multiple
Traveling Salesmen Problem
- arxiv url: http://arxiv.org/abs/2201.09424v1
- Date: Mon, 24 Jan 2022 02:43:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-26 05:15:36.869265
- Title: An Effective Iterated Two-stage Heuristic Algorithm for the Multiple
Traveling Salesmen Problem
- Title（参考訳）: マルチトラベリングセールスマン問題に対する効果的な2段階ヒューリスティックアルゴリズム
- Authors: Jiongzhi Zheng and Yawei Hong and Wenchang Xu and Wentao Li and Yongfu
Chen
- Abstract要約: マルチトラベリングセールスマン問題mTSPは、有名なNPハードトラベルセールスマン問題(TSP)の一般的な拡張である
本稿では,mTSPを最小目標と最小目標の両方で扱い,mツアーの総長を最小化することを目的とした。
本論文では,ITHAと呼ばれる2段階の反復アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 2.5374893654938324
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The multiple Traveling Salesmen Problem mTSP is a general extension of the
famous NP-hard Traveling Salesmen Problem (TSP), that there are m (m>1)
salesmen to visit the cities. In this paper, we address the mTSP with both of
the minsum objective and the minmax objective, which aims at minimizing the
total length of the m tours and the length of the longest tour among all the m
tours, respectively. We propose an iterated two-stage heuristic algorithm,
denoted as ITSHA. Each iteration of ITSHA consists of an initialization stage
and an improvement stage. The purpose of the initialization stage is to
generate high-quality and diverse initial solutions. The improvement stage
mainly applies the variable neighborhood search (VNS) approach based on our
proposed local search neighborhoods to optimize the initial solution generated
by the initialization stage. Moreover, some local optima escaping approaches
are employed to enhance the search ability of the algorithm. Extensive
experimental results on a wide range of public benchmark instances show that
ITSHA significantly outperforms state-of-the-art heuristic algorithms in
solving the mTSP on both the objectives.
- Abstract（参考訳）: 複数のトラベリングセールスマン問題mTSPは、有名なNPハードトラベリングセールスマン問題(TSP)の一般的な拡張であり、m(m>1)のセールスマンが市内を訪れている。
本稿では、mtspをminsumの目的とminmaxの目的の両方で扱う。mtspはmツアーの全長とmツアーの最長ツアーの長さをそれぞれ最小化することを目的としている。
本論文では,ITHAと呼ばれる2段階ヒューリスティックアルゴリズムを提案する。
ITSHAの各イテレーションは、初期化段階と改善段階で構成される。
初期化段階の目的は、高品質で多様な初期解を生成することである。
改良段階は主に,提案した局所探索地区に基づく可変近傍探索(VNS)アプローチを適用し,初期化段階から生成される初期解を最適化する。
また,アルゴリズムの探索能力を高めるために,局所的オプティマエスケープ手法が採用されている。
広範囲の公開ベンチマークインスタンスに対する大規模な実験結果から、TrusHAは両方の目的においてmTSPを解く際に、最先端のヒューリスティックアルゴリズムを著しく上回ります。
関連論文リスト
- Are Large-Language Models Graph Algorithmic Reasoners? [45.592341677933646]
明示グラフ上の古典的アルゴリズム推論タスクにおいて,LLM(Large Language Models)の性能を評価するために設計されたベンチマークを導入する。
我々のベンチマークは、接続のためのBFS(Breadth-First Search)とDFS(Depth-First Search)、すべてのノードの最短経路に対するDijkstraのアルゴリズムとFloyd-Warshallアルゴリズム、プリムの最小スパンニングツリー(MST-Prim's)アルゴリズムの5つの基本アルゴリズムを含む。
論文 参考訳（メタデータ） (2024-10-29T23:28:37Z) - iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning [8.747306544853961]
MTSP(Min-Max Multiple Traveling Salesman)問題の検討
目標は、最長ツアーの長さを最小化しながら、各エージェントが一括してすべての都市を訪れるツアーを見つけることである。
我々は、命令型MTSP(iMTSP)と呼ばれる、新しい自己教師型双方向エンドツーエンド学習フレームワークを導入する。
論文 参考訳（メタデータ） (2024-05-01T02:26:13Z) - 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) - New Characterizations and Efficient Local Search for General Integer
Linear Programming [17.80124240223163]
本研究では境界解の概念を用いた線形プログラミング(ILP)の新たな特徴付けを提案する。
そこで我々は,局所探索アルゴリズムのLocal-ILPを開発した。
MIPLIBデータセットで行った実験は、大規模ハードILP問題の解法におけるアルゴリズムの有効性を示した。
論文 参考訳（メタデータ） (2023-04-29T07:22:07Z) - Unsupervised Learning of Initialization in Deep Neural Networks via
Maximum Mean Discrepancy [74.34895342081407]
本稿では,入力データに対する優れた初期化を求めるための教師なしアルゴリズムを提案する。
まず、パラメータ空間における各パラメータ構成が、d-way分類の特定の下流タスクに対応することに気付く。
次に、学習の成功は、初期パラメータの近傍で下流タスクがいかに多様であるかに直接関連していると推測する。
論文 参考訳（メタデータ） (2023-02-08T23:23:28Z) - Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path
Finding [25.11387753357413]
本稿では,多目的タスク割り当てと経路探索(MG-TAPF)問題を理論的およびアルゴリズム的観点から検討する。
理論的には、MG-TAPF問題は最適解法としてNPハードであることが証明される。
本稿では,多エージェントパス探索問題に対するアルゴリズムに基づくアルゴリズムを提案し,MG-TAPF問題を最適・準最適に解く。
論文 参考訳（メタデータ） (2022-08-02T03:17:29Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
本稿では,高速CM-SPAMアルゴリズムに基づく汎用フレームワークTaSPMを提案する。
また,マイニングプロセスにおける無意味な操作を減らすために,いくつかのプルーニング戦略を提案する。
実験の結果,新たなターゲットマイニングアルゴリズムであるTaSPMは実行時間を短縮し,メモリ消費を低減できることがわかった。
論文 参考訳（メタデータ） (2022-02-26T17:49:47Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z) - Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
ガウス級報酬を用いたマルチアームバンディット問題について検討する。
本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
論文 参考訳（メタデータ） (2020-02-21T08:07:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。