論文の概要: Overcoming Binary Adversarial Optimisation with Competitive Coevolution
- arxiv url: http://arxiv.org/abs/2407.17875v1
- Date: Thu, 25 Jul 2024 08:44:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 14:38:10.827545
- Title: Overcoming Binary Adversarial Optimisation with Competitive Coevolution
- Title（参考訳）: 競合的共進化による二元対向最適化の克服
- Authors: Per Kristian Lehre, Shishen Lin,
- Abstract要約: 共進化アルゴリズム(CoEA)は、設計とテストがバイナリ結果をもたらす対向最適化問題において頻繁に用いられる。
本稿では,バイナリテストベースの最適化問題に対して,$(1,lambda)$ CoEA の厳密な実行時解析を行う。
- 参考スコア（独自算出の注目度）: 1.104960878651584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Co-evolutionary algorithms (CoEAs), which pair candidate designs with test cases, are frequently used in adversarial optimisation, particularly for binary test-based problems where designs and tests yield binary outcomes. The effectiveness of designs is determined by their performance against tests, and the value of tests is based on their ability to identify failing designs, often leading to more sophisticated tests and improved designs. However, CoEAs can exhibit complex, sometimes pathological behaviours like disengagement. Through runtime analysis, we aim to rigorously analyse whether CoEAs can efficiently solve test-based adversarial optimisation problems in an expected polynomial runtime. This paper carries out the first rigorous runtime analysis of $(1,\lambda)$ CoEA for binary test-based adversarial optimisation problems. In particular, we introduce a binary test-based benchmark problem called \Diagonal problem and initiate the first runtime analysis of competitive CoEA on this problem. The mathematical analysis shows that the $(1,\lambda)$-CoEA can efficiently find an $\varepsilon$ approximation to the optimal solution of the \Diagonal problem, i.e. in expected polynomial runtime assuming sufficiently low mutation rates and large offspring population size. On the other hand, the standard $(1,\lambda)$-EA fails to find an $\varepsilon$ approximation to the optimal solution of the \Diagonal problem in polynomial runtime. This suggests the promising potential of coevolution for solving binary adversarial optimisation problems.
- Abstract（参考訳）: 共進化的アルゴリズム(CoEA)は、テストケースをペアに設計するが、特に設計とテストがバイナリ結果をもたらすバイナリテストベースの問題において、逆最適化に頻繁に使用される。
設計の有効性は、テストに対するパフォーマンスによって決定され、テストの価値は、失敗する設計を特定する能力に基づいており、多くの場合、より洗練されたテストや改善された設計につながる。
しかし、CoEAは、解離のような複雑な、時には病理学的な振る舞いを示すことがある。
実行時解析を通じて、期待多項式ランタイムにおけるテストベース対角最適化問題を効率的に解けるかどうかを厳密に分析することを目的としている。
本稿では,バイナリテストベースの対数最適化問題に対して,$(1,\lambda)$ CoEA の厳密な実行時解析を行う。
特に,双対問題と呼ばれるバイナリテストベースのベンチマーク問題を導入し,この問題に対する競争力のあるCoEAの最初のランタイム解析を開始する。
数学的解析により、$(1,\lambda)$-CoEAは、十分に低い突然変異率と大きな子孫の集団サイズを仮定する期待多項式ランタイムにおいて、対角問題の最適解に対する$\varepsilon$近似を効率的に見つけることができることを示した。
一方、標準の$(1,\lambda)$-EAは多項式ランタイムにおける \Diagonal 問題の最適解に対する$\varepsilon$近似を見つけられなかった。
これは、二元対向最適化問題を解くための共進化の有望な可能性を示している。
関連論文リスト
- Bayesian Optimization for Non-Convex Two-Stage Stochastic Optimization Problems [2.9016548477524156]
知識に基づく獲得関数を定式化し,第1段と第2段の変数を協調的に最適化する。
可変型間の寸法と長さの差が2段階アルゴリズムの非効率性をもたらすことを示す。
論文 参考訳（メタデータ） (2024-08-30T16:26:31Z) - Theoretical Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict [4.8951183832371]
OneMaxMin$_k$ベンチマーククラスは、COCZとOneMinMaxの一般化版である。
2つの典型的な非MOEAアプローチ、スカラー化(重み付きサム法)と$epsilon$-constraint法が検討されている。
我々は、(G)SEMO、MOEA/D、NSGA-II、SMS-EMOAがパレートフロント全体を$O(maxk,1nln n)$でカバーできることを証明する。
論文 参考訳（メタデータ） (2024-08-08T04:09:52Z) - Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳（メタデータ） (2023-07-18T04:29:16Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
論文 参考訳（メタデータ） (2022-03-25T19:36:02Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
論文 参考訳（メタデータ） (2020-04-02T21:39:33Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。