論文の概要: A threshold search based memetic algorithm for the disjunctively
constrained knapsack problem
- arxiv url: http://arxiv.org/abs/2101.04753v1
- Date: Tue, 12 Jan 2021 21:07:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-17 00:24:17.579964
- Title: A threshold search based memetic algorithm for the disjunctively
constrained knapsack problem
- Title（参考訳）: 差分制約付きknapsack問題に対するしきい値探索に基づくメメティックアルゴリズム
- Authors: Zequn Wei and Jin-Kao Hao
- Abstract要約: 可逆的制約付きクナプサック問題は、容量制約付きクナプサックにペア互換の項目のサブセットをパックすることである。
そこで我々は, DCKP を解くためのしきい値探索に基づくメメティクスアルゴリズムを提案し, メメティクスフレームワークとしきい値探索を組み合わせた高品質な解を求める。
- 参考スコア（独自算出の注目度）: 21.803219880299764
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The disjunctively constrained knapsack problem consists in packing a subset
of pairwisely compatible items in a capacity-constrained knapsack such that the
total profit of the selected items is maximized while satisfying the knapsack
capacity. DCKP has numerous applications and is however computationally
challenging (NP-hard). In this work, we present a threshold search based
memetic algorithm for solving the DCKP that combines the memetic framework with
threshold search to find high quality solutions. Extensive computational
assessments on two sets of 6340 benchmark instances in the literature
demonstrate that the proposed algorithm is highly competitive compared to the
state-of-the-art methods. In particular, we report 24 and 354 improved
best-known results (new lower bounds) for Set I (100 instances) and for Set II
(6240 instances), respectively. We analyze the key algorithmic components and
shed lights on their roles for the performance of the algorithm. The code of
our algorithm will be made publicly available.
- Abstract（参考訳）: 連結制約クナップサック問題は、クナップサック容量を満足しながら選択されたアイテムの総利益を最大化するように、容量制約クナップサックに対向するアイテムのサブセットを充填することを特徴とする。
DCKPは多くの応用があり、計算は困難である(NP-hard)。
本研究では, DCKP を解くためのしきい値探索に基づくメメティックアルゴリズムを提案し, メメティックフレームワークとしきい値探索を組み合わせた高品質な解を求める。
6340のベンチマークインスタンスの2セットに関する広範な計算的評価結果から,提案手法は最先端手法と比較して高い競合性を示す。
特に,セットi (100 インスタンス) とセットii (6240 インスタンス) について,24 と 354 において,最もよく知られた結果(新しい下限)がそれぞれ改善されていることを報告した。
我々は,アルゴリズムの重要成分を分析し,アルゴリズムの性能向上のためにその役割を明かす。
我々のアルゴリズムのコードは公開される予定だ。
関連論文リスト
- Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - An algorithm for clustering with confidence-based must-link and cannot-link constraints [0.0]
我々はPCCCアルゴリズム(Pairwise-Confidence-Constraints-Clustering)を導入する。
PCCCアルゴリズムは、オブジェクトのペアに提供された情報を考慮しながら、反復的にオブジェクトをクラスタに割り当てる。
既存のアルゴリズムとは異なり、我々のアルゴリズムは最大6万のオブジェクト、100のクラスタ、数百万のnot-link制約を持つ大規模インスタンスにスケールする。
論文 参考訳（メタデータ） (2022-12-29T19:21:33Z) - Combining K-means type algorithms with Hill Climbing for Joint
Stratification and Sample Allocation Designs [0.0]
これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。
それぞれのソリューションのコストを評価するのに 費用がかかります
上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
論文 参考訳（メタデータ） (2021-08-18T08:41:58Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z) - Probability Learning based Tabu Search for the Budgeted Maximum Coverage
Problem [26.209597575181775]
Budgeted Maximum Coverage Problem (BMCP) に対処する。
BMCPは、Set-Union Knapsack Problem (SUKP)と密接に関連している。
このNP-hard問題に対処するための確率学習に基づくタブサーチ(PLTS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-12T12:11:59Z) - An Empirical Process Approach to the Union Bound: Practical Algorithms
for Combinatorial and Linear Bandits [34.06611065493047]
本稿では、信頼度と予算設定の固定化において、純探索線形帯域問題に対する近似アルゴリズムを提案する。
サンプルの複雑性がインスタンスの幾何でスケールし、アームの数に縛られた明示的な結合を避けるアルゴリズムを提供する。
また,固定予算設定における線形帯域幅に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-21T00:56:33Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳（メタデータ） (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。