論文の概要: iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning
- arxiv url: http://arxiv.org/abs/2405.00285v1
- Date: Wed, 1 May 2024 02:26:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-02 16:37:17.263613
- Title: iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning
- Title（参考訳）: iMTSP: インペラティブ学習による最小限のマルチトラベリングセールスマン問題の解決
- Authors: Yifan Guo, Zhongqiang Ren, Chen Wang,
- Abstract要約: MTSP(Min-Max Multiple Traveling Salesman)問題の検討
目標は、最長ツアーの長さを最小化しながら、各エージェントが一括してすべての都市を訪れるツアーを見つけることである。
我々は、命令型MTSP(iMTSP)と呼ばれる、新しい自己教師型双方向エンドツーエンド学習フレームワークを導入する。
- 参考スコア（独自算出の注目度）: 8.747306544853961
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP), where the goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tour. Though MTSP has been widely studied, obtaining near-optimal solutions for large-scale problems is still challenging due to its NP-hardness. Recent efforts in data-driven methods face challenges of the need for hard-to-obtain supervision and issues with high variance in gradient estimations, leading to slow convergence and highly suboptimal solutions. We address these issues by reformulating MTSP as a bilevel optimization problem, using the concept of imperative learning (IL). This involves introducing an allocation network that decomposes the MTSP into multiple single-agent traveling salesman problems (TSPs). The longest tour from these TSP solutions is then used to self-supervise the allocation network, resulting in a new self-supervised, bilevel, end-to-end learning framework, which we refer to as imperative MTSP (iMTSP). Additionally, to tackle the high-variance gradient issues during the optimization, we introduce a control variate-based gradient estimation algorithm. Our experiments showed that these innovative designs enable our gradient estimator to converge 20% faster than the advanced reinforcement learning baseline and find up to 80% shorter tour length compared with Google OR-Tools MTSP solver, especially in large-scale problems (e.g. 1000 cities and 15 agents).
- Abstract（参考訳）: 本稿では,各エージェントが各都市を総括して訪問し,最長ツアーの長さを最小化することを目的とした,MTSP(Min-Max Multiple Traveling Salesman Problem)について考察する。
MTSPは広く研究されているが、NP硬度のため、大規模問題に対する準最適解を得ることは依然として困難である。
データ駆動手法の最近の取り組みは、厳密な監督の必要性と勾配推定のばらつきに直面する問題に直面する。
本稿では,インペラティブラーニング(IL)の概念を用いて,MTSPを二段階最適化問題として再定義することでこの問題に対処する。
これには、MTSPを複数の単一エージェントの旅行セールスマン問題(TSP)に分解するアロケーションネットワークの導入が含まれる。
これらのTSPソリューションからの最長のツアーは、アロケーションネットワークを自己監督するために使用され、その結果、新しい自己監督型、双方向のエンドツーエンド学習フレームワークが生まれ、これは命令型MTSP(iMTSP)と呼ばれる。
また、最適化中の高分散勾配問題に対処するために、制御変数に基づく勾配推定アルゴリズムを導入する。
以上の結果から,Google OR-Tools MTSPソルバと比較して,勾配推定器が高度強化学習ベースラインよりも20%高速に収束し,ツアー長が最大80%短いことが示唆された。
関連論文リスト
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Faster Stochastic Variance Reduction Methods for Compositional MiniMax
Optimization [50.10952609321302]
合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。
構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
論文 参考訳（メタデータ） (2023-08-18T14:57:21Z) - Online Multi-Task Learning with Recursive Least Squares and Recursive Kernel Methods [50.67996219968513]
本稿では,オンラインマルチタスク学習(MTL)回帰問題に対する2つの新しいアプローチを紹介する。
入力空間の次元の2次パースタンスコストで精度よく近似的な再帰を実現する。
我々は,実世界の風速予測ケーススタディにおいて,オンラインMTL法と他の競技者との比較を行った。
論文 参考訳（メタデータ） (2023-08-03T01:41:34Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
トラベリングセールスマン問題(TSP)は、もともと輸送と物流の領域で発生した古典的な経路最適化問題である。
近年, 深層強化学習は高い推論効率のため, TSP の解法として採用されている。
本稿では,多点変換器をベースとした新しいエンドツーエンドDRL手法であるPointerformerを提案する。
論文 参考訳（メタデータ） (2023-04-19T03:48:32Z) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
我々は、必要に応じて適切な選択を行う決定論的アルゴリズムを支援する模倣学習フレームワークについて検討する。
我々は、模倣学習フレームワークの下で訓練されたグラフニューラルネットワークの強力な一般化能力を示す。
論文 参考訳（メタデータ） (2022-10-12T03:56:37Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳（メタデータ） (2022-05-28T06:08:07Z) - An Effective Iterated Two-stage Heuristic Algorithm for the Multiple
Traveling Salesmen Problem [2.5374893654938324]
マルチトラベリングセールスマン問題mTSPは、有名なNPハードトラベルセールスマン問題(TSP)の一般的な拡張である
本稿では,mTSPを最小目標と最小目標の両方で扱い,mツアーの総長を最小化することを目的とした。
本論文では,ITHAと呼ばれる2段階の反復アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-01-24T02:43:08Z) - Off-Policy Correction For Multi-Agent Reinforcement Learning [9.599347559588216]
マルチエージェント強化学習(MARL)は、複数の対話エージェントに関わる問題のためのフレームワークを提供する。
単エージェントの場合と明らかに類似しているにもかかわらず、マルチエージェント問題はしばしば、理論的な訓練と解析が困難である。
我々は、V-TraceをMARL設定まで拡張する、新しいオンラインアクター批判アルゴリズムMA-Traceを提案する。
論文 参考訳（メタデータ） (2021-11-22T14:23:13Z) - DAN: Decentralized Attention-based Neural Network to Solve the MinMax
Multiple Traveling Salesman Problem [5.137147284997655]
我々は、DANと呼ばれるMinMax mTSPを解くために、分散注意に基づくニューラルネットワーク手法を導入する。
DANでは、エージェントは、他のエージェントの将来の決定を予測することによって、ツアーを共同で構築するための完全に分散されたポリシーを学ぶ。
我々は50から1000の都市、5から20のエージェントを含む小規模から大規模mTSPインスタンスで実験を行い、最先端のベースラインと比較した。
論文 参考訳（メタデータ） (2021-09-09T12:26:04Z) - Low-Latency Federated Learning over Wireless Channels with Differential
Privacy [142.5983499872664]
フェデレートラーニング(FL)では、モデルトレーニングはクライアントに分散し、ローカルモデルは中央サーバによって集約される。
本稿では,各クライアントの差分プライバシ(DP)要件だけでなく,全体としてのトレーニング性能に制約された無線チャネル上でのFLトレーニング遅延を最小限に抑えることを目的とする。
論文 参考訳（メタデータ） (2021-06-20T13:51:18Z) - Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated
Algorithm Selection [0.0]
トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。
我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。
その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
論文 参考訳（メタデータ） (2020-05-27T11:36:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。