論文の概要: Equity-Transformer: Solving NP-hard Min-Max Routing Problems as
Sequential Generation with Equity Context
- arxiv url: http://arxiv.org/abs/2306.02689v3
- Date: Mon, 5 Feb 2024 02:36:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 06:17:00.463432
- Title: Equity-Transformer: Solving NP-hard Min-Max Routing Problems as
Sequential Generation with Equity Context
- Title（参考訳）: Equity-Transformer: NP-hard Min-Max Routing 問題を量子コンテキスト付き逐次生成として解く
- Authors: Jiwoo Son, Minsu Kim, Sanghyeok Choi, Hyeonah Kim, Jinkyoo Park
- Abstract要約: 最小限のルーティング問題は、エージェントが協調的にタスクを実行することで、複数のエージェント間の最大ツアー長を最小化することを目的としている。
既存の手法は、特に数千の都市をカバーするために多数のエージェントの調整を必要とする大規模な問題において、課題に直面している。
本稿では,大規模なmin-maxルーティング問題を解決するためにEquity-Transformerを提案する。
- 参考スコア（独自算出の注目度）: 33.270494123656746
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Min-max routing problems aim to minimize the maximum tour length among
multiple agents by having agents conduct tasks in a cooperative manner. These
problems include impactful real-world applications but are known as NP-hard.
Existing methods are facing challenges, particularly in large-scale problems
that require the coordination of numerous agents to cover thousands of cities.
This paper proposes Equity-Transformer to solve large-scale min-max routing
problems. First, we employ sequential planning approach to address min-max
routing problems, allowing us to harness the powerful sequence generators
(e.g., Transformer). Second, we propose key inductive biases that ensure
equitable workload distribution among agents. The effectiveness of
Equity-Transformer is demonstrated through its superior performance in two
representative min-max routing tasks: the min-max multi-agent traveling
salesman problem (min-max mTSP) and the min-max multi-agent pick-up and
delivery problem (min-max mPDP). Notably, our method achieves significant
reductions of runtime, approximately 335 times, and cost values of about 53\%
compared to a competitive heuristic (LKH3) in the case of 100 vehicles with
1,000 cities of mTSP. We provide reproducible source code:
\url{https://github.com/kaist-silab/equity-transformer}.
- Abstract（参考訳）: 最小限のルーティング問題は、エージェントが協調的にタスクを実行することで、複数のエージェント間の最大ツアー長を最小化することを目的としている。
これらの問題には影響のある実世界の応用が含まれるが、NPハードとして知られている。
既存の手法は、特に数千の都市をカバーするために多数のエージェントの調整を必要とする大規模な問題に直面している。
本稿では,大規模なmin-maxルーティング問題を解決するためにEquity-Transformerを提案する。
まず、min-maxルーティング問題に対処するためにシーケンシャルプランニングアプローチを採用し、強力なシーケンスジェネレータ(Transformerなど)を活用する。
第2に,エージェント間の均等なワークロード分布を確保するための重要な帰納バイアスを提案する。
Equity-Transformerの有効性は、min-maxマルチエージェント旅行セールスマン問題(min-max mTSP)とmin-maxマルチエージェントピックアップ・デリバリ問題(min-max mPDP)の2つの代表的なmin-maxルーティングタスクにおいて、優れた性能で実証されている。
特に,mTSP1000都市100台において,競争的ヒューリスティック(LKH3)と比較して,約335倍,コストが約53倍のランタイムの大幅な削減を実現している。
再現可能なソースコードは \url{https://github.com/kaist-silab/equity-transformer} です。
関連論文リスト
- MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
SoftMaxは現代の機械学習アルゴリズムのユビキタスな成分である。
分散性はSoftMaxの変種族によって達成できるが、それらはしばしば代替損失関数を必要とし、多重モダリティを保たない。
入力入力範囲に応じて出力分布を適応的に変調するMultiMaxを提案する。
論文 参考訳（メタデータ） (2024-06-03T10:51:43Z) - DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems [26.48767051423456]
本稿では、分割とナビゲーションのための異なる埋め込みを学習する、新しいアテンションベースのパーティション・アンド・ナビゲーション・エンコーダ(P&N)を提案する。
エージェント置換対称損失関数(APS)を開発した。
論文 参考訳（メタデータ） (2024-05-27T15:33:16Z) - 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) - Robust Multi-Task Learning with Excess Risks [24.695243608197835]
マルチタスク学習(MTL)は、全てのタスク損失の凸結合を最適化することにより、複数のタスクのジョイントモデルを学ぶことを検討する。
既存の方法は適応的な重み更新方式を用いており、各損失に基づいてタスク重みを動的に調整し、困難なタスクを優先順位付けする。
本稿では,過度リスクに基づくタスクバランス手法であるMulti-Task Learning with Excess Risks (ExcessMTL)を提案する。
論文 参考訳（メタデータ） (2024-02-03T03:46:14Z) - Parameter-efficient Tuning of Large-scale Multimodal Foundation Model [68.24510810095802]
我々はこれらの課題を克服するために、クロスモーダル転送(Aurora)のための優雅なプロンプトフレームワークを提案する。
既存のアーキテクチャの冗長性を考慮すると、まずモード近似を用いて0.1Mのトレーニング可能なパラメータを生成し、マルチモーダルプロンプトチューニングを実装する。
6つのクロスモーダルベンチマークの徹底的な評価は、最先端のベンチマークを上回るだけでなく、完全な微調整アプローチよりも優れていることを示している。
論文 参考訳（メタデータ） (2023-05-15T06:40:56Z) - M$^3$ViT: Mixture-of-Experts Vision Transformer for Efficient Multi-task
Learning with Model-Accelerator Co-design [95.41238363769892]
マルチタスク学習(MTL)は、複数の学習タスクを単一のモデルにカプセル化し、それらのタスクを共同でよりよく学習できるようにする。
現在のMTLレギュレータは、1つのタスクだけを実行するためにさえ、ほぼすべてのモデルを起動する必要がある。
効率的なオンデバイスMTLを実現するためのモデル-アクセラレータ共設計フレームワークを提案する。
論文 参考訳（メタデータ） (2022-10-26T15:40:24Z) - Pruning Self-attentions into Convolutional Layers in Single Path [89.55361659622305]
ビジョントランスフォーマー(ViT)は、様々なコンピュータビジョンタスクに対して印象的なパフォーマンスを実現している。
トレーニング済みのViTを効率よく自動圧縮するSPViT(Single-Path Vision Transformer pruning)を提案する。
われわれのSPViTはDeiT-Bで52.0%のFLOPをトリミングできる。
論文 参考訳（メタデータ） (2021-11-23T11:35:54Z) - 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) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。
都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
論文 参考訳（メタデータ） (2020-05-27T01:10:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。