論文の概要: Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation
- arxiv url: http://arxiv.org/abs/2507.02381v1
- Date: Thu, 03 Jul 2025 07:23:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-04 15:37:15.869524
- Title: Running-time Analysis of ($μ+λ$) Evolutionary Combinatorial Optimization Based on Multiple-gain Estimation
- Title（参考訳）: 多利得推定に基づく(μ+λ$)進化的組合せ最適化の実行時間解析
- Authors: Min Huang, Pengxiang Chen, Han Huang, Tongli He, Yushan Zhang, Zhifeng Hao,
- Abstract要約: 本稿では,最適化問題に対するEAの実行時間を分析するためのマルチゲインモデルを提案する。
また、knapsack問題に対する(mu+lambda$)EAの場合、既知の結果よりも2つの厳密な時間複雑性上限を含む、進化最適化のランニングタイム結果も導入されている。
- 参考スコア（独自算出の注目度）: 12.810490884742784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. However, theoretical results regarding the $(\mu+\lambda)$ evolutionary algorithm (EA) for combinatorial optimization problems remain relatively scarce compared to those for simple pseudo-Boolean problems. This paper proposes a multiple-gain model to analyze the running time of EAs for combinatorial optimization problems. The proposed model is an improved version of the average gain model, which is a fitness-difference drift approach under the sigma-algebra condition to estimate the running time of evolutionary numerical optimization. The improvement yields a framework for estimating the expected first hitting time of a stochastic process in both average-case and worst-case scenarios. It also introduces novel running-time results of evolutionary combinatorial optimization, including two tighter time complexity upper bounds than the known results in the case of ($\mu+\lambda$) EA for the knapsack problem with favorably correlated weights, a closed-form expression of time complexity upper bound in the case of ($\mu+\lambda$) EA for general $k$-MAX-SAT problems and a tighter time complexity upper bounds than the known results in the case of ($\mu+\lambda$) EA for the traveling salesperson problem. Experimental results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is an effective tool for running-time analysis of ($\mu+\lambda$) EA for combinatorial optimization problems.
- Abstract（参考訳）: 進化的組合せ最適化の実行時解析は、進化的計算の基本的なトピックである。
しかし、組合せ最適化問題に対する$(\mu+\lambda)$進化アルゴリズム(EA)に関する理論的結果は、単純な擬ブール問題よりも比較的少ないままである。
本稿では,組合せ最適化問題に対するEAの実行時間解析のためのマルチゲインモデルを提案する。
提案モデルは平均ゲインモデルの改良版であり、これはシグマ代数条件下での適合差ドリフトアプローチであり、進化的数値最適化の実行時間を推定する。
この改善により、平均ケースと最悪のシナリオの両方において、確率的プロセスの最初のヒットタイムを推定するためのフレームワークが得られる。
また、一般的な$k$-MAX-SAT問題の場合のknapsack問題($\mu+\lambda$)のEA($\mu+\lambda$)のEA($\mu+\lambda$)のEA($\mu+\lambda$)のEAと、旅行セールスパーソン問題の場合のEA($\mu+\lambda$)のEA($\mu+\lambda$)のEA($\mu+\lambda$)のEA($\mu+\lambda$)のEA($)のEA($\mu+\lambda$)のEA($)のEA($\mu+\lambda$)のEA($)のEA($\mu+\lambda$)のEA($)のEA($\mu+\lambda$)のEA($)のEA($)のクローズドフォーム表現を含む、進化的組合せ最適化の新たな実行時結果も導入している。
実験結果から,実実行時間は理論的結果と一致し,複数ゲインモデルが組合せ最適化問題に対する(\mu+\lambda$)EAの実行時解析に有効なツールであることが確認された。
関連論文リスト
- Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization [12.810490884742784]
本稿では,反復中の集団の適応傾向を推定するマルチゲインモデルを提案する。
提案モデルは平均ゲインモデルの改良版であり,数値最適化のための進化的アルゴリズムの実行時間を推定するアプローチである。
論文 参考訳（メタデータ） (2025-01-13T01:24:36Z) - Overcoming Binary Adversarial Optimisation with Competitive Coevolution [1.104960878651584]
共進化アルゴリズム(CoEA)は、設計とテストがバイナリ結果をもたらす対向最適化問題において頻繁に用いられる。
本稿では,バイナリテストベースの最適化問題に対して,$(1,lambda)$ CoEA の厳密な実行時解析を行う。
論文 参考訳（メタデータ） (2024-07-25T08:44:23Z) - 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) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-02-23T08:07:54Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Convergence of Meta-Learning with Task-Specific Adaptation over Partial
Parameters [152.03852111442114]
モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。
本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
論文 参考訳（メタデータ） (2020-06-16T19:57:48Z) - 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) - Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
論文 参考訳（メタデータ） (2020-04-02T21:39:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。