論文の概要: Learning-guided iterated local search for the minmax multiple traveling salesman problem

• arxiv url: http://arxiv.org/abs/2403.12389v1
• Date: Tue, 19 Mar 2024 02:57:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-20 15:41:42.533140
• Title: Learning-guided iterated local search for the minmax multiple traveling salesman problem
• Title（参考訳）: 学習誘導型反復局所探索によるミンマックス多旅行セールスマン問題の解法
• Authors: Pengfei He, Jin-Kao Hao, Jinhui Xia,
• Abstract要約: 本稿では, ミンマックス多旅行セールスマン問題に対する, 傾き駆動型局所探索手法を提案する。 提案アルゴリズムは,ソリューションの品質と実行時間の観点から,優れた結果が得られることを示す。 特に、32の既知の結果が新たに達成され、35の他のインスタンスで最もよく知られた結果と一致している。
• 参考スコア（独自算出の注目度）: 13.924692115320553
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The minmax multiple traveling salesman problem involves minimizing the longest tour among a set of tours. The problem is of great practical interest because it can be used to formulate several real-life applications. To solve this computationally challenging problem, we propose a leaning-driven iterated local search approach that combines an aggressive local search procedure with a probabilistic acceptance criterion to find high-quality local optimal solutions and a multi-armed bandit algorithm to select various removal and insertion operators to escape local optimal traps. Extensive experiments on 77 commonly used benchmark instances show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances. Additional experiments shed light on the understanding of the composing elements of the algorithm.
• Abstract（参考訳）: ミンマックス・マルチトラベルセールスマンの問題は、一連のツアーの中で最長のツアーを最小化することである。 この問題は、いくつかの現実の応用を定式化するために使用できるため、非常に実践的な関心事である。 そこで本研究では,攻撃的局所探索手順と確率論的受容基準を組み合わせ,高品質な局所最適解を見つけるための傾き駆動型反復局所探索手法と,局所最適トラップを回避するための様々な除去・挿入演算子を選択するマルチアームバンディットアルゴリズムを提案する。 77のベンチマークインスタンスに対する大規模な実験により,我々のアルゴリズムは,ソリューションの品質と実行時間の観点から優れた結果が得られることが示された。 特に、32の既知の結果が新たに達成され、35の他のインスタンスで最もよく知られた結果と一致している。 さらなる実験は、アルゴリズムの構成要素の理解に光を当てた。

関連論文リスト

• 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)
• An Adaptive Repeated-Intersection-Reduction Local Search for the Maximum Independent Set Problem [5.459881847627117]
  独立集合問題(英: independent set (MIS) problem)は、様々な分野で応用される古典的なNPハード問題である。 我々は、ARIRと呼ばれるMISの効率的な局所探索アルゴリズムを提案する。 最先端の4つのアルゴリズムと比較して、ARIRは89のインスタンスで最高の精度を提供し、残りの3つのインスタンスで競合する結果を得る。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Learning to Control Local Search for Combinatorial Optimization [4.243592852049962]
  一般化の動物園と問題固有の局所探索の変種は、近似解を計算するのによく用いられる。 本稿では,そのような局所探索アルゴリズムの3つの独立したアルゴリズム的側面を同定し,最適化プロセス上でのシーケンシャルな選択を形式化する。 我々は、NeuroLSがオペレーティングリサーチの汎用ローカルサーチコントローラと最新の機械学習ベースのアプローチの両方より優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-27T10:48:56Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• An effective hybrid search algorithm for the multiple traveling repairman problem with profits [34.74325448504831]
  本稿では,メメティックアルゴリズムの枠組みに基づく効果的なハイブリッド検索アルゴリズムを提案する。 これは、高品質な子孫ソリューションを生成する専用のアークベースのクロスオーバーと、古典的な地区を探索する複雑さを減らすための高速な評価手法の2つの特徴を統合している。
  論文  参考訳（メタデータ） (2021-11-09T09:27:49Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。