論文の概要: How Good Is Neural Combinatorial Optimization? A Systematic Evaluation
on the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2209.10913v2
- Date: Wed, 12 Apr 2023 09:12:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 18:56:50.295962
- Title: How Good Is Neural Combinatorial Optimization? A Systematic Evaluation
on the Traveling Salesman Problem
- Title(参考訳): ニューラルコンビネーション最適化はどの程度優れているか?
旅行セールスマン問題に関するシステム評価
- Authors: Shengcai Liu, Yu Zhang, Ke Tang, Xin Yao
- Abstract要約: この研究は、ニューラル最適化ソルバと代替ソルバの総合的な比較研究を示す。
以上の結果から, NCO アプローチで学習した解法は, 従来の解法には及ばないことが明らかとなった。
- 参考スコア(独自算出の注目度): 31.451338706630583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Traditional solvers for tackling combinatorial optimization (CO) problems are
usually designed by human experts. Recently, there has been a surge of interest
in utilizing deep learning, especially deep reinforcement learning, to
automatically learn effective solvers for CO. The resultant new paradigm is
termed neural combinatorial optimization (NCO). However, the advantages and
disadvantages of NCO relative to other approaches have not been empirically or
theoretically well studied. This work presents a comprehensive comparative
study of NCO solvers and alternative solvers. Specifically, taking the
traveling salesman problem as the testbed problem, the performance of the
solvers is assessed in five aspects, i.e., effectiveness, efficiency,
stability, scalability, and generalization ability. Our results show that the
solvers learned by NCO approaches, in general, still fall short of traditional
solvers in nearly all these aspects. A potential benefit of NCO solvers would
be their superior time and energy efficiency for small-size problem instances
when sufficient training instances are available. Hopefully, this work would
help with a better understanding of the strengths and weaknesses of NCO and
provide a comprehensive evaluation protocol for further benchmarking NCO
approaches in comparison to other approaches.
- Abstract(参考訳): 組合せ最適化(co)問題に取り組む従来の解法は通常、人間の専門家によって設計される。
近年, 深層学習, 特に深層強化学習の活用への関心が高まっており, COの効率的な解法を自動学習している。
結果として得られる新しいパラダイムはneural combinatorial optimization(nco)と呼ばれる。
しかしながら、他のアプローチと比較してNCOの利点と欠点は経験的あるいは理論的によく研究されていない。
この研究は、NCOソルバと代替ソルバの総合的な比較研究を示す。
具体的には, 走行セールスマン問題をテストベッド問題として, 有効性, 効率性, 安定性, スケーラビリティ, 一般化能力の5つの側面で評価する。
以上の結果から, NCO アプローチで学習した解法は, 従来の解法には及ばないことが明らかとなった。
NCOソルバの潜在的な利点は、十分なトレーニングインスタンスが利用可能であれば、小さな問題インスタンスの時間とエネルギー効率が優れていることである。
この研究は、NCOの強みと弱みをより深く理解し、NCOアプローチをさらにベンチマークするための包括的な評価プロトコルを提供するのに役立つことを期待している。
関連論文リスト
- An Efficient Learning-based Solver Comparable to Metaheuristics for the
Capacitated Arc Routing Problem [67.92544792239086]
我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。
まず,方向対応型注意モデル(DaAM)を提案する。
第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
論文 参考訳(メタデータ) (2024-03-11T02:17:42Z) - Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。
私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。
以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
論文 参考訳(メタデータ) (2023-05-18T13:59:02Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - On the Generalization of Neural Combinatorial Optimization Heuristics [0.7049738935364298]
提案手法は,2つの最先端モデルの一般化を著しく改善することを示す。
我々は、個別の学習課題として、与えられたインスタンス分布上でのCO問題の解法を定式化する。
新しいタスクに適応する能力の最適化を目的として,様々なタスクのモデル学習のためのメタラーニング手法について検討する。
論文 参考訳(メタデータ) (2022-06-01T22:39:35Z) - Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization [16.127824824652077]
深部強化学習(DRL)に基づく最適化(CO)法は,従来のCO解法に比べて有意な効果を示した。
本稿では,既存のDRL-NCO法の性能向上を実現する新しいトレーニング手法であるSym-NCOを提案する。
論文 参考訳(メタデータ) (2022-05-26T07:55:43Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳(メタデータ) (2022-05-03T07:54:56Z) - Adversarial Robustness with Semi-Infinite Constrained Learning [177.42714838799924]
入力に対する深い学習は、安全クリティカルなドメインでの使用に関して深刻な疑問を提起している。
本稿では,この問題を緩和するために,Langevin Monte Carlo のハイブリッドトレーニング手法を提案する。
当社のアプローチは、最先端のパフォーマンスと堅牢性の間のトレードオフを軽減することができることを示す。
論文 参考訳(メタデータ) (2021-10-29T13:30:42Z) - Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。
本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
論文 参考訳(メタデータ) (2020-12-31T12:40:52Z) - Evaluating Curriculum Learning Strategies in Neural Combinatorial
Optimization [15.398857578319435]
NCOは問題解決のために、問題に依存しない効率的なニューラルネットワークベースの戦略を設計することを目指している。
現在のアプローチの欠点の1つは、複数の問題サイズのトレーニングの非効率性である。
本研究では、既存のアーキテクチャが競争力のある性能を達成するのに役立つカリキュラムベースのトレーニング手順を設計することに焦点を当てる。
論文 参考訳(メタデータ) (2020-11-12T04:21:04Z) - POMO: Policy Optimization with Multiple Optima for Reinforcement
Learning [8.819672165548477]
本稿では,マルチプルオプティマス(POMO)を用いたポリシー最適化について紹介する。
POMOは、幅広いCO問題に適用可能であり、CO溶液の表現における対称性を利用するように設計されている。
我々は,旅行セールスマン(TSP),キャパシタンドカールーティング(CVRP),0-1knapsack(KP)の3つの一般的なNPハード問題を解くことで,POMOの有効性を実証した。
論文 参考訳(メタデータ) (2020-10-30T00:57:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。