論文の概要: A Parallel Ensemble of Metaheuristic Solvers for the Traveling Salesman
Problem
- arxiv url: http://arxiv.org/abs/2308.07347v2
- Date: Wed, 13 Sep 2023 15:29:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-14 17:21:29.355156
- Title: A Parallel Ensemble of Metaheuristic Solvers for the Traveling Salesman
Problem
- Title（参考訳）: 旅行セールスマン問題に対するメタヒューリスティックな解の並列アンサンブル
- Authors: Swetha Varadarajan and Darrell Whitley
- Abstract要約: トラベリングセールスマン問題(TSP)は、文献でよく研究されているNPハード問題の一つである。
最近の研究は、再起動機構を持つEAXが広範囲のTSPインスタンスで良好に動作することを示唆している。
2,000から85,900の問題について検討する。
ハイブリッド版のアンサンブルは、1万以上の都市で、最先端の問題解決者より優れています。
- 参考スコア（独自算出の注目度）: 2.44755919161855
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The travelling salesman problem (TSP) is one of the well-studied NP-hard
problems in the literature. The state-of-the art inexact TSP solvers are the
Lin-Kernighan-Helsgaun (LKH) heuristic and Edge Assembly crossover (EAX). A
recent study suggests that EAX with restart mechanisms perform well on a wide
range of TSP instances. However, this study is limited to 2,000 city problems.
We study for problems ranging from 2,000 to 85,900. We see that the performance
of the solver varies with the type of the problem. However, combining these
solvers in an ensemble setup, we are able to outperform the individual solver's
performance. We see the ensemble setup as an efficient way to make use of the
abundance of compute resources. In addition to EAX and LKH, we use several
versions of the hybrid of EAX and Mixing Genetic Algorithm (MGA). A hybrid of
MGA and EAX is known to solve some hard problems. We see that the ensemble of
the hybrid version outperforms the state-of-the-art solvers on problems larger
than 10,000 cities.
- Abstract（参考訳）: トラベリングセールスマン問題(TSP)は、文献でよく研究されているNPハード問題の一つである。
最先端のTSP解決者はLin-Kernighan-Helsgaun(LKH)ヒューリスティックとエッジアセンブリクロスオーバー(EAX)である。
最近の研究は、再起動機構を持つEAXが広範囲のTSPインスタンスでうまく機能することを示唆している。
しかし、この研究は都市問題2000に制限されている。
2,000から85,900の問題について検討する。
解法の性能は問題の種類によって異なることが分かる。
しかし,これらの解器をアンサンブル設定で組み合わせることで,個々の解器の性能より優れる。
計算資源の豊富さを活用する効率的な方法として,アンサンブルの設定が考えられる。
EAX と LKH に加えて、EAX と Mixing Genetic Algorithm (MGA) のハイブリッド版もいくつか使用しています。
MGAとEAXのハイブリッドは、いくつかの難しい問題を解くことが知られている。
ハイブリッド版のアンサンブルは1万都市以上の問題に対して最先端の解法よりも優れています。
関連論文リスト
- Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
グラフベースの拡散フレームワークであるDIFUSCOを導入する。
本フレームワークは, NPC問題を離散0, 1ベクトル最適化問題とみなす。
MIS問題に対して、DIFUSCOは、挑戦的なSATLIBベンチマークにおいて、以前の最先端のニューラルソルバよりも優れている。
論文 参考訳（メタデータ） (2023-02-16T11:13:36Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
ユークリッド凸化関数の違いは、統計学と機械学習の異なるタイプの問題の違いとして記述できることを示す。
最終的に、より広い範囲、より広い範囲の作業を支援するのです。
論文 参考訳（メタデータ） (2022-06-22T23:57:40Z) - 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) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。
近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。
本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
論文 参考訳（メタデータ） (2022-02-07T18:52:56Z) - A New Constructive Heuristic driven by Machine Learning for the
Traveling Salesman Problem [8.604882842499212]
近年,機械学習(ML)を用いてTSP(Traking Salesman Problem)を解くシステムでは,実ケースシナリオにスケールアップしようとすると問題が発生する。
問題に対処するため、候補リスト(CL)の使用が提起されている。
この作業では、高い確率のエッジに対してのみ、ソリューションの追加を確認するために、マシンラーニングモデルを使用します。
論文 参考訳（メタデータ） (2021-08-17T21:37:23Z) - Learning to Delegate for Large-scale Vehicle Routing [4.425982186154401]
車両ルーティング問題 (VRPs) は、幅広い実用化の課題である。
従来あるいは学習ベースの作業は、最大100人の顧客の小さな問題インスタンスに対して、適切なソリューションを実現します。
本稿では,大規模VRPを解くために,新たな局所探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-07-08T22:51:58Z) - Garden optimization problems for benchmarking quantum annealers [0.0]
本稿では,アドバンテージシステムとハイブリッド・ソルバが,前者よりも少ない時間で解けることを示す。
また,2000以上の量子ビット系DW2000Qに基づく解法により,解法が解ける場合には,より有利な結果が得られることも示している。
論文 参考訳（メタデータ） (2021-01-26T14:59:17Z) - A Hybrid Framework Using a QUBO Solver For Permutation-Based
Combinatorial Optimization [5.460573052311485]
本稿では,高性能な2次非制約バイナリ最適化器を用いて,大規模な置換に基づく問題を解くためのハイブリッドフレームワークを提案する。
通常はビット数に制限があるQUBOソルバを使用する際の課題を克服する手法を提案する。
論文 参考訳（メタデータ） (2020-09-27T07:15:25Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳（メタデータ） (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。