論文の概要: Analysis of the (1+1) EA on LeadingOnes with Constraints
- arxiv url: http://arxiv.org/abs/2305.18267v1
- Date: Mon, 29 May 2023 17:40:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-30 13:42:34.390364
- Title: Analysis of the (1+1) EA on LeadingOnes with Constraints
- Title(参考訳): 制約付きリードワンにおける(1+1)EAの解析
- Authors: Tobias Friedrich, Timo K\"otzing, Aneta Neumann, Frank Neumann,
Aishwarya Radhakrishnan
- Abstract要約: 進化的アルゴリズムが古典的LeadingOnes問題の制約されたバージョンをどのように最適化するかを検討する。
その結果,アルゴリズムの挙動は一様制約の制約境界に大きく依存していることがわかった。
- 参考スコア(独自算出の注目度): 17.800340821052462
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Understanding how evolutionary algorithms perform on constrained problems has
gained increasing attention in recent years. In this paper, we study how
evolutionary algorithms optimize constrained versions of the classical
LeadingOnes problem. We first provide a run time analysis for the classical
(1+1) EA on the LeadingOnes problem with a deterministic cardinality
constraint, giving $\Theta(n (n-B)\log(B) + n^2)$ as the tight bound. Our
results show that the behaviour of the algorithm is highly dependent on the
constraint bound of the uniform constraint. Afterwards, we consider the problem
in the context of stochastic constraints and provide insights using
experimental studies on how the ($\mu$+1) EA is able to deal with these
constraints in a sampling-based setting.
- Abstract(参考訳): 近年,制約問題に対する進化的アルゴリズムの作用の理解が注目されている。
本稿では,従来のLeadingOnes問題の制約バージョンを最適化するアルゴリズムについて述べる。
まず,古典的 (1+1) EA に対して決定論的濃度制約を課し,厳密な境界として $\Theta(n (n-B)\log(B) + n^2)$ を与える。
その結果,アルゴリズムの挙動は一様制約の制約境界に大きく依存していることがわかった。
その後, 確率的制約の文脈における問題を考察し, EA($\mu$+1) がサンプリングベースでこれらの制約にどのように対処できるかを実験的に検討して考察する。
関連論文リスト
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。
私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
論文 参考訳(メタデータ) (2024-05-25T08:09:36Z) - Structured Low-Rank Tensor Learning [2.1227526213206542]
構造制約のある部分的な観測から低ランクテンソルを学習する問題を考察する。
このようなテンソルの新たな分解法を提案し、より単純な最適化問題を導いた。
論文 参考訳(メタデータ) (2023-05-13T17:04:54Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳(メタデータ) (2022-10-27T17:59:09Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳(メタデータ) (2022-01-21T04:25:35Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Pareto Optimization for Subset Selection with Dynamic Partition Matroid
Constraints [16.691265882753346]
分割マトロイド制約下でのサブモジュラーあるいはモノトーン目的関数による部分集合選択問題について検討する。
このような問題に対して有効であることを示す単純な最適化手法であるPOMCに焦点をあてる。
我々の分析は特異な制約問題から分離し、複数の制約の問題にまで拡張する。
論文 参考訳(メタデータ) (2020-12-16T04:27:45Z) - Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint [11.228244128564512]
均一制約下での線形関数のクラスについて検討し、ランダム化局所探索(RLS)の期待最適時間について検討する。
RLS に対して $Theta(n2)$ の厳密な境界を証明し、(1+1) EA の既知上界を改善する。
論文 参考訳(メタデータ) (2020-10-21T10:42:39Z) - Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。
解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。
また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
論文 参考訳(メタデータ) (2020-09-21T14:26:48Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳(メタデータ) (2020-06-16T10:49:27Z) - A Constraint Driven Solution Model for Discrete Domains with a Case
Study of Exam Timetabling Problems [6.788217433800101]
知的制約処理進化アルゴリズム (ICHEA) のバリエーションは, ベンチマーク試験の時間変化問題を解決するために実証されている。
ICHEAはまず、与えられた制約をすべて段階的に満たすために結婚間クロスオーバー演算子を使用し、その後、ソリューションを最適化するために従来の演算子と拡張演算子の組み合わせを使用する。
論文 参考訳(メタデータ) (2020-02-08T06:53:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。