Fugu-MT 論文翻訳(概要): Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem

論文の概要: Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem

arxiv url: http://arxiv.org/abs/2007.05971v1
Date: Sun, 12 Jul 2020 12:11:59 GMT
ステータス: 処理完了
システム内更新日: 2022-11-11 05:46:34.855114
Title: Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem
Title（参考訳）: 予算最大カバレッジ問題に対するtabu探索に基づく確率学習
Authors: Liwen Li, Zequn Wei, Jin-Kao Hao and Kun He
Abstract要約: Budgeted Maximum Coverage Problem (BMCP) に対処する。 BMCPは、Set-Union Knapsack Problem (SUKP)と密接に関連している。このNP-hard問題に対処するための確率学習に基づくタブサーチ(PLTS)アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 26.209597575181775
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Knapsack problems are classic models that can formulate a wide range of applications. In this work, we deal with the Budgeted Maximum Coverage Problem (BMCP), which is a generalized 0-1 knapsack problem. Given a set of items with nonnegative weights and a set of elements with nonnegative profits, where each item is composed of a subset of elements, BMCP aims to pack a subset of items in a capacity-constrained knapsack such that the total weight of the selected items does not exceed the knapsack capacity, and the total profit of the associated elements is maximized. Note that each element is counted once even if it is covered multiple times. BMCP is closely related to the Set-Union Knapsack Problem (SUKP) that is well studied in recent years. As the counterpart problem of SUKP, however, BMCP was introduced early in 1999 but since then it has been rarely studied, especially there is no practical algorithm proposed. By combining the reinforcement learning technique to the local search procedure, we propose a probability learning based tabu search (PLTS) algorithm for addressing this NP-hard problem. The proposed algorithm iterates through two distinct phases, namely a tabu search phase and a probability learning based perturbation phase. As there is no benchmark instances proposed in the literature, we generate 30 benchmark instances with varied properties. Experimental results demonstrate that our PLTS algorithm significantly outperforms the general CPLEX solver for solving the challenging BMCP in terms of the solution quality.
Abstract（参考訳）: クナプサック問題は、幅広い応用を定式化できる古典的なモデルである。本研究では, 一般化した0-1knapsack問題であるBudgeted Maximum Coverage Problem (BMCP) を扱う。 BMCPは、非負の重量を持つ項目と、各項目が要素のサブセットから構成される非負の利益を持つ要素のセットが与えられたとき、選択された項目の総重量がクナップサック容量を超えず、関連する要素の総利益が最大となるように、容量制限されたクナップサックに項目のサブセットを詰めることを目的とする。要素が複数回カバーされている場合でも、各要素は1回カウントされる。 BMCPは、近年よく研究されているSet-Union Knapsack Problem (SUKP)と密接に関連している。しかし、SUKPの相反する問題として、BMCPは1999年初頭に導入されたが、その後はほとんど研究されていない。強化学習法と局所探索法を組み合わせることで,このnp-hard問題に対処するための確率学習ベースのタブサーチ(plts)アルゴリズムを提案する。提案アルゴリズムは,タブ探索フェーズと確率学習に基づく摂動フェーズという,2つの異なるフェーズを繰り返す。文献にはベンチマークインスタンスが提案されていないため、さまざまな特性を持つベンチマークインスタンスを30個生成する。実験結果から,PLTSアルゴリズムは解法品質の観点からBMCPを解く上で,一般的なCPLEX解法よりも優れていた。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。 CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-26T13:35:05Z)
Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
論文参考訳（メタデータ） (2022-10-08T05:11:47Z)
Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights [15.402666674186936]
本研究では,ランダム化探索アルゴリズム (RSA) と基本進化アルゴリズム (EA) のランタイム解析を行った。本稿では,重み相関と異なる種類の利益プロファイルが,確率制約条件下での両アルゴリズムの実行動作にどのように影響するかを示す。
論文参考訳（メタデータ） (2021-02-10T23:40:01Z)
A threshold search based memetic algorithm for the disjunctively constrained knapsack problem [21.803219880299764]
可逆的制約付きクナプサック問題は、容量制約付きクナプサックにペア互換の項目のサブセットをパックすることである。そこで我々は, DCKP を解くためのしきい値探索に基づくメメティクスアルゴリズムを提案し, メメティクスフレームワークとしきい値探索を組み合わせた高品質な解を求める。
論文参考訳（メタデータ） (2021-01-12T21:07:33Z)
Generalization in portfolio-based algorithm selection [97.74604695303285]
ポートフォリオベースのアルゴリズム選択に関する最初の証明可能な保証を提供する。ポートフォリオが大きければ、非常に単純なアルゴリズムセレクタであっても、過剰適合は避けられないことを示す。
論文参考訳（メタデータ） (2020-12-24T16:33:17Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文参考訳（メタデータ） (2020-06-22T17:58:54Z)
SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文参考訳（メタデータ） (2020-06-12T05:00:44Z)
The {0,1}-knapsack problem with qualitative levels [2.0943517417159763]
古典的なknapsack問題の変種は、各項目が整数の重みと定性的レベルと関連付けられていると考えられる。この関係が事前注文を定義することを示す。本研究では,非支配的な階数濃度ベクトルの集合全体を計算するための動的プログラミングアルゴリズムを提案する。
論文参考訳（メタデータ） (2020-02-12T09:00:29Z)
Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文参考訳（メタデータ） (2020-01-23T16:47:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。