論文の概要: Breeding Diverse Packings for the Knapsack Problem by Means of
Diversity-Tailored Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2104.13133v1
- Date: Tue, 27 Apr 2021 12:26:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-02 06:47:59.521933
- Title: Breeding Diverse Packings for the Knapsack Problem by Means of
Diversity-Tailored Evolutionary Algorithms
- Title（参考訳）: 多様性を考慮した進化的アルゴリズムによるクナプサック問題の育種
- Authors: Jakob Bossek, Aneta Neumann, Frank Neumann
- Abstract要約: 我々はknapsack問題(KP)に対する進化的多様性の最適化について研究する。
我々のゴールは、KP のよく知られた FPTAS によって計算された初期近似解で、すべての利益が少なくとも$(mu+1)$-EA である解の集団を進化させることである。
- 参考スコア（独自算出の注目度）: 13.026567958569965
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In practise, it is often desirable to provide the decision-maker with a rich
set of diverse solutions of decent quality instead of just a single solution.
In this paper we study evolutionary diversity optimization for the knapsack
problem (KP). Our goal is to evolve a population of solutions that all have a
profit of at least $(1-\varepsilon)\cdot OPT$, where OPT is the value of an
optimal solution. Furthermore, they should differ in structure with respect to
an entropy-based diversity measure. To this end we propose a simple
$(\mu+1)$-EA with initial approximate solutions calculated by a well-known
FPTAS for the KP. We investigate the effect of different standard mutation
operators and introduce biased mutation and crossover which puts strong
probability on flipping bits of low and/or high frequency within the
population. An experimental study on different instances and settings shows
that the proposed mutation operators in most cases perform slightly inferior in
the long term, but show strong benefits if the number of function evaluations
is severely limited.
- Abstract（参考訳）: 実践においては、単一のソリューションではなく、適切な品質のリッチなソリューションセットを意思決定者に提供することが望ましいことが多い。
本稿では,knapsack問題(KP)に対する進化的多様性の最適化について検討する。
我々のゴールは、OPTが最適解の値である少なくとも$(1-\varepsilon)\cdot OPT$の利益を持つソリューションの集団を進化させることである。
さらに、エントロピーに基づく多様性尺度に関して構造的に異なるべきである。
この目的のために、KP に対するよく知られた FPTAS によって計算された初期近似解を持つ単純な $(\mu+1)$-EA を提案する。
異なる標準突然変異演算子の効果を調査し、集団内の低頻度および/または高頻度の反転ビットに強い確率を与えるバイアス付き突然変異とクロスオーバーを導入する。
異なるインスタンスと設定に関する実験的研究により、ほとんどのケースで提案された変異演算子は、長期的にはわずかに劣るが、機能評価が厳しく制限された場合に強い利点があることが示された。
関連論文リスト
- Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
論文 参考訳（メタデータ） (2023-12-07T15:55:58Z) - Evolutionary Multi-Objective Algorithms for the Knapsack Problems with
Stochastic Profits [13.026567958569965]
我々は、ある商品の利益に対する一定の信頼を保証するため、利益を伴うknapsack問題のバージョンを検討する。
利益率制約付きクナップサック問題の多目的定式化を導入し, 両目的性評価法を3つ設計する。
両設定のベンチマークにおいて,提案手法の有効性を示す。
論文 参考訳（メタデータ） (2023-03-03T03:28:51Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳（メタデータ） (2022-10-04T04:43:58Z) - Evolutionary Algorithms for Limiting the Effect of Uncertainty for the
Knapsack Problem with Stochastic Profits [14.352521012951865]
我々は、利益が不確実性を伴うクナプサック問題を考察する。
我々は、不確実性の影響を制限するために、尾の不平等に基づいて利益を扱う様々な方法を導入する。
論文 参考訳（メタデータ） (2022-04-12T07:56:50Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Analysis of Evolutionary Diversity Optimisation for Permutation Problems [17.268191781480745]
最もよく研究された置換問題の3つに対する進化的多様性最適化に関する研究
その結果、これらの問題に対する多くの突然変異演算子により、最大多様な個体群への収束が保証された。
QAPLIBおよび合成インスタンス上で、制約のない、制約のない環境で実験を行う。
論文 参考訳（メタデータ） (2021-02-23T03:13:26Z) - Optimal Off-Policy Evaluation from Multiple Logging Policies [77.62012545592233]
我々は,複数のロギングポリシからオフ政治評価を行い,それぞれが一定のサイズ,すなわち階層化サンプリングのデータセットを生成する。
複数ロガーのOPE推定器は,任意のインスタンス,すなわち効率のよいインスタンスに対して最小分散である。
論文 参考訳（メタデータ） (2020-10-21T13:43:48Z) - Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem [13.264683014487376]
多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。
単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
論文 参考訳（メタデータ） (2020-10-21T11:50:49Z) - Isotonic regression with unknown permutations: Statistics, computation,
and adaptation [13.96377843988598]
我々は、推定のミニマックスリスク(実証的な$L$損失)と適応の基本的な限界(適応度指数で定式化)について検討する。
バニラ時間プロシージャで可能な最小適応率を達成しつつ、最小限の最適化が可能なミルスキー分割推定器を提供する。
相補的な方向において、既存の推定器の自然な修正は、デシデラタの最適統計性能、計算効率、高速適応の少なくとも1つを満たすことができないことを示す。
論文 参考訳（メタデータ） (2020-09-05T22:17:51Z) - SGD with shuffling: optimal rates without component convexity and large
epoch requirements [60.65928290219793]
我々はRandomShuffle(各エポックの開始時のシャッフル)とSingleShuffle(1回だけシャッフル)を考える。
我々はこれらのアルゴリズムの最小収束速度をポリログ係数ギャップまで確立する。
我々は、すべての先行芸術に共通する欠点を取り除くことにより、RandomShuffleの厳密な収束結果をさらに強化する。
論文 参考訳（メタデータ） (2020-06-12T05:00:44Z) - Statistical Efficiency of Thompson Sampling for Combinatorial
Semi-Bandits [56.31950477139053]
半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討
我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。
この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
論文 参考訳（メタデータ） (2020-06-11T17:12:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。