論文の概要: First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables

• arxiv url: http://arxiv.org/abs/2605.14836v1
• Date: Thu, 14 May 2026 13:42:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-15 21:45:34.850653
• Title: First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables
• Title（参考訳）: 多値決定変数に対する多目的進化アルゴリズムの最初の数学的実行解析
• Authors: Mingfeng Li, Zheng Cheng, Weijie Zheng, Benjamin Doerr,
• Abstract要約: 二項決定空間上で定義された問題は、多目的進化アルゴリズムの理論において集中的に研究されている。 有限値 $r > 2$ の値を取る決定変数を扱うMOEAには、今のところ数学的ランタイム解析は存在しない。 多値決定変数を扱う場合、古典的MOEAは重大な問題に遭遇しないことが示される。
• 参考スコア（独自算出の注目度）: 23.47753638129204
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number $r > 2$ of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an $r$-valued counterpart of the classic \oneminmax benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of $O(n^2 r^2 \log n)$ and a near-tight lower bound of $Ω(n^2 r (r + \log n))$. We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of $O(n^2 r (r + \log n))$, matching our lower bound (which also holds for this variant). Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.
• Abstract（参考訳）: 二項決定空間上で定義された問題は、多目的進化アルゴリズム(MOEA)の理論において集中的に研究されている。 対照的に、そのような問題が実際に行われているにもかかわらず、有限個の$r > 2$の値を取る決定変数を扱うMOEAに対しては、今のところ数学的ランタイム解析は存在しない。 この研究で、我々はこの研究ギャップを埋め始めます。 我々は,従来のSEMOアルゴリズムと単体長局所変異を併用した手法を用いて,古典的 \oneminmax ベンチマークの $r$-valued の Pareto を計算する方法を分析する。 このMOEAの人口でパレートフロントがカバーされるまでの関数評価の期待数について、上界は$O(n^2 r^2 \log n)$、下限は$Ω(n^2 r (r + \log n))$とする。 厳密な解のみを受け入れるアルゴリズムの変種を考えることで、これらの2つの境界の間の小さな余剰ギャップを閉じることができる。この変種に対して、我々は、下限に一致する$O(n^2 r (r + \log n))$の上限を示す(これは、この変種に対しても成り立つ)。 以上の結果から,複数値決定変数を扱う場合,従来のMOEAでは重大な問題が発生しないことが示唆された。 しかし、より複雑な人口動態を持つアルゴリズムの厳密な境界を得るためには、はるかに高度なツールが必要であるかもしれない。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm [9.966672345291707]
  本稿では,GSEMO(Global Simple Evolution Multi-Objective)アルゴリズムのダイナミクスについて検討する。 我々は、古典的なCountingOnesCountingZeros(COCZ)ベンチマークに対して、$Omega(n2 log n)$の下位境界を証明した。 我々の手法は他の古典的なベンチマークにまで拡張し、例えば、最初の$Omega(nk+1)$ lower bound for the OJZJ benchmark(英語版)などである。
  論文  参考訳（メタデータ） (2025-05-02T13:40:25Z)
• A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition [77.76727425995186]
  変分不等式(SVIs)の解決は、最適化の中心にある基礎的な問題である。 ほとんどの研究は、その難易度を損なう特定のサブクラスを彫刻することに重点を置いている。
  論文  参考訳（メタデータ） (2025-04-04T13:24:41Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• 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)
• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables [10.165640083594573]
  我々は、遺伝的ドリフトの既知の定量的解析を、多値変数の分布推定アルゴリズムに拡張する。 我々の研究は、バイナリEDAの理解が自然に多値設定にまで拡張されていることを示している。
  論文  参考訳（メタデータ） (2023-02-28T08:52:40Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [14.309243378538014]
  OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。 確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。 また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
  論文  参考訳（メタデータ） (2020-12-14T03:07:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。