論文の概要: Few-shots Parallel Algorithm Portfolio Construction via Co-evolution
- arxiv url: http://arxiv.org/abs/2007.00501v2
- Date: Tue, 23 Feb 2021 07:12:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-14 22:25:38.578025
- Title: Few-shots Parallel Algorithm Portfolio Construction via Co-evolution
- Title(参考訳): 共進化による並列アルゴリズムポートフォリオ構築
- Authors: Ke Tang, Shengcai Liu, Peng Yang, Xin Yao
- Abstract要約: 一般化、すなわち、システム設計と開発フェーズで利用できない問題のインスタンスを解く能力は、インテリジェントシステムにとって重要な目標である。
本稿では,この課題に対する対策として,CEPSの共進化(Co-Evolution of CEPS)という新たな競争的共進化手法を提案する。
トラベルセールスマン問題(TSP)と同時ピックアップ・デリバリ・アンド・タイムウィンドウ(VRPSPDTW)の2つの具体的なアルゴリズムが提示される。
- 参考スコア(独自算出の注目度): 31.069132566211675
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generalization, i.e., the ability of solving problem instances that are not
available during the system design and development phase, is a critical goal
for intelligent systems. A typical way to achieve good generalization is to
learn a model from vast data. In the context of heuristic search, such a
paradigm could be implemented as configuring the parameters of a parallel
algorithm portfolio (PAP) based on a set of training problem instances, which
is often referred to as PAP construction. However, compared to traditional
machine learning, PAP construction often suffers from the lack of training
instances, and the obtained PAPs may fail to generalize well. This paper
proposes a novel competitive co-evolution scheme, named Co-Evolution of
Parameterized Search (CEPS), as a remedy to this challenge. By co-evolving a
configuration population and an instance population, CEPS is capable of
obtaining generalizable PAPs with few training instances. The advantage of CEPS
in improving generalization is analytically shown in this paper. Two concrete
algorithms, namely CEPS-TSP and CEPS-VRPSPDTW, are presented for the Traveling
Salesman Problem (TSP) and the Vehicle Routing Problem with Simultaneous
Pickup-Delivery and Time Windows (VRPSPDTW), respectively. Experimental results
show that CEPS has led to better generalization, and even managed to find new
best-known solutions for some instances.
- Abstract(参考訳): 一般化、すなわち、システム設計と開発フェーズで利用できない問題インスタンスを解決できる能力は、インテリジェントシステムにとって重要な目標である。
よい一般化を達成する典型的な方法は、巨大なデータからモデルを学ぶことである。
ヒューリスティック探索の文脈において、そのようなパラダイムは、pap構築と呼ばれる一連のトレーニング問題インスタンスに基づいて、並列アルゴリズムポートフォリオ(pap)のパラメータを設定するために実装することができる。
しかし、従来の機械学習と比較して、PAPの構築はトレーニングインスタンスの欠如に悩まされ、得られたPAPはうまく一般化できない。
本稿では,この課題に対する対策として,CEPS(Co-Evolution of Parameterized Search)という新たな競合的共進化手法を提案する。
構成人口とインスタンス人口の共進化により、CEPSは、少数のトレーニングインスタンスで一般化可能なPAPを得ることができる。
一般化におけるCEPSの利点を解析的に示す。
CEPS-TSP と CEPS-VRPSPDTW という2つの具体的なアルゴリズムが,TSP (Traveing Salesman Problem) とVRPSPDTW (Vine Routing Problem with Simultaneous Pickup-Delivery and Time Windows) に対してそれぞれ提示される。
実験の結果、CEPSはより一般化され、いくつかのインスタンスでよく知られた新しいソリューションを見つけることができた。
関連論文リスト
- Combinatorial Optimization with Policy Adaptation using Latent Space
Search [46.02102888864839]
本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。
我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
論文 参考訳(メタデータ) (2023-11-13T12:24:54Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - PEAR: Primitive enabled Adaptive Relabeling for boosting Hierarchical
Reinforcement Learning [30.533883667629887]
階層的強化学習は、複雑な長い地平線タスクを解く可能性がある。
プリミティブ・アダプティブ・アダプティブ・レバーベリング(PEAR)を提案する。
まず,いくつかの専門家による実験を適応的に実施し,効率的なサブゴール管理を実現する。
次に、強化学習(RL)と模倣学習(IL)を併用してHRLエージェントを共同最適化する。
論文 参考訳(メタデータ) (2023-06-10T09:41:30Z) - Scalable PAC-Bayesian Meta-Learning via the PAC-Optimal Hyper-Posterior:
From Theory to Practice [54.03076395748459]
メタラーニング文学の中心的な疑問は、目に見えないタスクへの一般化を保証するために、いかに正規化するかである。
本稿では,Rothfussらによって最初に導かれたメタラーニングの一般化について述べる。
PAC-Bayesian per-task 学習境界におけるメタラーニングの条件と程度について,理論的解析および実証事例研究を行った。
論文 参考訳(メタデータ) (2022-11-14T08:51:04Z) - GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP,
and Beyond [101.5329678997916]
対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。
本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。
低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
論文 参考訳(メタデータ) (2022-11-03T16:42:40Z) - Solving the Traveling Salesperson Problem with Precedence Constraints by
Deep Reinforcement Learning [59.14935871979047]
本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。
これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
論文 参考訳(メタデータ) (2022-07-04T14:31:47Z) - Common Information based Approximate State Representations in
Multi-Agent Reinforcement Learning [3.086462790971422]
我々は、分散化されたポリシーを構築可能な共通およびプライベートな状態表現を近似した汎用的な圧縮フレームワークを開発する。
その結果,「分散分散実行の分散学習」方式で,実用的に有用なディープMARLネットワーク構造の設計に光を当てた。
論文 参考訳(メタデータ) (2021-10-25T02:32:06Z) - COPS: Controlled Pruning Before Training Starts [68.8204255655161]
最先端のディープニューラルネットワーク(DNN)プルーニング技術は、トレーニング開始前にワンショットで適用され、プルーニングスコアと呼ばれる単一の基準の助けを借りてスパースアーキテクチャを評価する。
この作業では、単一プルーニング基準に集中するのではなく、任意のGASを組み合わせてより強力なプルーニング戦略を構築するためのフレームワークを提供します。
論文 参考訳(メタデータ) (2021-07-27T08:48:01Z) - Why Generalization in RL is Difficult: Epistemic POMDPs and Implicit
Partial Observability [92.95794652625496]
総合化は強化学習システムの展開における中心的な課題である。
限られた訓練条件から検査条件を特定できないように一般化することは、暗黙的な部分観察可能性をもたらすことを示す。
我々は、RLにおける一般化の問題を、部分的に観察されたマルコフ決定過程の解法として再考した。
論文 参考訳(メタデータ) (2021-07-13T17:59:25Z) - Encoding-dependent generalization bounds for parametrized quantum
circuits [1.2599533416395765]
データエンコーディングに使用する戦略に明示的に依存するPQCベースのモデルに対するバウンダリを導出する。
この結果は最適なデータエンコーディング戦略の選択を容易にする。
論文 参考訳(メタデータ) (2021-06-07T18:01:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。