論文の概要: Single- and Multi-Objective Evolutionary Algorithms for the Knapsack
Problem with Dynamically Changing Constraints
- arxiv url: http://arxiv.org/abs/2004.12574v2
- Date: Sun, 5 Jun 2022 05:45:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 04:46:11.314961
- Title: Single- and Multi-Objective Evolutionary Algorithms for the Knapsack
Problem with Dynamically Changing Constraints
- Title（参考訳）: 動的に制約が変化するKnapsack問題に対する単目的・多目的進化アルゴリズム
- Authors: Vahid Roostapour, Aneta Neumann, Frank Neumann
- Abstract要約: 古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。
この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
- 参考スコア（独自算出の注目度）: 13.896724650508087
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms are bio-inspired algorithms that can easily adapt to
changing environments. Recent results in the area of runtime analysis have
pointed out that algorithms such as the (1+1)~EA and Global SEMO can
efficiently reoptimize linear functions under a dynamic uniform constraint.
Motivated by this study, we investigate single- and multi-objective baseline
evolutionary algorithms for the classical knapsack problem where the capacity
of the knapsack varies over time.
We establish different benchmark scenarios where the capacity changes every
$\tau$ iterations according to a uniform or normal distribution. Our
experimental investigations analyze the behavior of our algorithms in terms of
the magnitude of changes determined by parameters of the chosen distribution,
the frequency determined by $\tau$, and the class of knapsack instance under
consideration. Our results show that the multi-objective approaches using a
population that caters for dynamic changes have a clear advantage on many
benchmarks scenarios when the frequency of changes is not too high.
Furthermore, we demonstrate that the diversity mechanisms used in popular
evolutionary multi-objective algorithms such as NSGA-II and SPEA2 do not
necessarily result in better performance and even lead to inferior results
compared to our simple multi-objective approaches.
- Abstract（参考訳）: 進化的アルゴリズムは、環境の変化に容易に適応できるバイオインスパイアされたアルゴリズムである。
実行時解析の分野での最近の結果は、(1+1)~EAやGlobal SEMOのようなアルゴリズムが動的一様制約の下で線形関数を効率的に再最適化できることを指摘している。
本研究では,knapsackの容量が時間とともに変化する古典的knapsack問題に対する,単目的および多目的のベースライン進化アルゴリズムについて検討した。
キャパシティが均一あるいは正規分布に応じて$\tau$イテレーション毎に変化する、さまざまなベンチマークシナリオを確立します。
実験では,選択した分布のパラメータによって決定される変化の大きさ,$\tau$で決定される周波数,検討中のknapsackインスタンスのクラスを用いて,アルゴリズムの挙動を解析した。
その結果,動的変化に対応する集団を用いた多目的アプローチは,変化頻度があまり高くない場合,多くのベンチマークシナリオにおいて明らかに有利であることがわかった。
さらに、nsga-iiやspea2のような一般的な進化的多目的アルゴリズムで使用される多様性メカニズムは必ずしも優れた性能をもたらすものではなく、単純な多目的アプローチに比べて劣る結果をもたらすことも示している。
関連論文リスト
- Using 3-Objective Evolutionary Algorithms for the Dynamic Chance Constrained Knapsack Problem [9.617143859697322]
動的制約付き制約付きクナプサック問題に対する3目的進化アルゴリズムの利用について検討する。
動的成分を同時に扱える3つの客観的定式化を導入し,制約に要求される信頼度に依存しない。
本分析では, 動的確率制約クナプサック問題に対処する上で, 2-対象の定式化よりも3-対象の定式化の利点を強調した。
論文 参考訳（メタデータ） (2024-04-09T04:47:01Z) - Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
我々は,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用した。
予測された擬似ポリノミカル時間内に最適解を計算することができることを示す。
論文 参考訳（メタデータ） (2022-07-28T12:15:33Z) - Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and
Stability [67.8426046908398]
汎用性と安定性は,実世界における強化学習(RL)エージェントの運用において重要な2つの目的である。
本稿では,アクター・クリティック・ロス関数の自動設計法であるMetaPGを提案する。
論文 参考訳（メタデータ） (2022-04-08T20:46:16Z) - Reproducibility and Baseline Reporting for Dynamic Multi-objective
Benchmark Problems [4.859986264602551]
本稿では,DMOPのパラメータのシミュレーション実験について述べる。
動的アルゴリズム評価のためのベースラインスキーマを導入する。
目的構築された動的アルゴリズムが有用であるために必要な最小限の能力を確立することができる。
論文 参考訳（メタデータ） (2022-04-08T15:50:17Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - AdaLead: A simple and robust adaptive greedy search algorithm for
sequence design [55.41644538483948]
我々は、容易で、拡張性があり、堅牢な進化的欲求アルゴリズム(AdaLead)を開発した。
AdaLeadは、様々な生物学的に動機づけられたシーケンスデザインの課題において、アートアプローチのより複雑な状態を克服する、驚くほど強力なベンチマークである。
論文 参考訳（メタデータ） (2020-10-05T16:40:38Z) - EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm
for Constrained Global Optimization [68.8204255655161]
EOSは実数値変数の制約付きおよび制約なし問題に対する大域的最適化アルゴリズムである。
これはよく知られた微分進化(DE)アルゴリズムに多くの改良を加えている。
その結果、EOSisは、最先端の単一人口自己適応Dアルゴリズムと比較して高い性能を達成可能であることが証明された。
論文 参考訳（メタデータ） (2020-07-09T10:19:22Z) - Optimising Monotone Chance-Constrained Submodular Functions Using
Evolutionary Multi-Objective Algorithms [15.389164392812276]
本稿では、確率制約付き部分モジュラー関数に対する進化的多目的アルゴリズムの最初の実行時解析について述べる。
本稿では,GSEMOアルゴリズムが最近解析されたgreedyアルゴリズムと同等の性能保証が得られることを示す。
論文 参考訳（メタデータ） (2020-06-20T00:17:44Z) - Stochastic batch size for adaptive regularization in deep network
optimization [63.68104397173262]
ディープラーニングフレームワークにおける機械学習問題に適用可能な適応正規化を取り入れた一階最適化アルゴリズムを提案する。
一般的なベンチマークデータセットに適用した従来のネットワークモデルに基づく画像分類タスクを用いて,提案アルゴリズムの有効性を実証的に実証した。
論文 参考訳（メタデータ） (2020-04-14T07:54:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。