論文の概要: Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2501.07000v1
• Date: Mon, 13 Jan 2025 01:24:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:28:05.707305
• Title: Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization
• Title（参考訳）: 進化的組合せ最適化の実行時間に対する多重利得推定
• Authors: Min Huang, Pengxiang Chen, Han Huang, Tonli He, Yushan Zhang, Zhifeng Hao,
• Abstract要約: 本稿では,反復中の集団の適応傾向を推定するマルチゲインモデルを提案する。 提案モデルは平均ゲインモデルの改良版であり,数値最適化のための進化的アルゴリズムの実行時間を推定するアプローチである。
• 参考スコア（独自算出の注目度）: 12.810490884742784
• License:
• Abstract: The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. Its current research mainly focuses on specific algorithms for simplified problems due to the challenge posed by fluctuating fitness values. This paper proposes a multiple-gain model to estimate the fitness trend of population during iterations. The proposed model is an improved version of the average gain model, which is the approach to estimate the running time of evolutionary algorithms for numerical optimization. The improvement yields novel results of evolutionary combinatorial optimization, including a briefer proof for the time complexity upper bound in the case of (1+1) EA for the Onemax problem, two tighter time complexity upper bounds than the known results in the case of (1+$\lambda$) EA for the knapsack problem with favorably correlated weights and a closed-form expression of time complexity upper bound in the case of (1+$\lambda$) EA for general $k$-MAX-SAT problems. The results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is more general for running-time analysis of evolutionary combinatorial optimization than state-of-the-art methods.
• Abstract（参考訳）: 進化的組合せ最適化の実行時解析は、進化的計算の基本的なトピックである。 現在の研究は主に、フィットネス値の変動による課題のため、単純化された問題に対する特定のアルゴリズムに焦点を当てている。 本稿では,反復中の集団の適応傾向を推定するマルチゲインモデルを提案する。 提案モデルは平均ゲインモデルの改良版であり,数値最適化のための進化的アルゴリズムの実行時間を推定するアプローチである。 この改良は、ワンマックス問題における (1+1) EA の場合における時間複雑性上界の簡単な証明、(1+$\lambda$) EA の (1+$\lambda$) EA の (1+$\lambda$) EA の (1+$\lambda$) EA の (1+$\lambda$) EA の (1+$-MAX-SAT の) EA の (1+$\lambda$) EA の (1+$\lambda$) EA の (1+$\lambda$) EA のケースにおける閉形式表現を含む、進化的組合せ最適化の新たな結果をもたらす。 その結果, 実用実行時間は理論結果と一致し, 複数ゲインモデルの方が, 進化的組合せ最適化の実行時解析において, 最先端の手法よりも一般的であることが示唆された。

関連論文リスト

• 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)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• Time Complexity Analysis of Evolutionary Algorithms for 2-Hop (1,2)-Minimum Spanning Tree Problem [20.624629608537894]
  2-Hop (1,2)-Minimum Spanning Tree problem (略MSTP) の制約付きバージョンを進化アルゴリズムの文脈で検討し、NPハードであることが示されている。 2-ホップスパンニングツリーの特別な構造に着想を得て、(1+1) EA はエッジベース表現の探索点を持ち、これは問題にはあまり自然とは思えず、期待する時間に上限を与えて$frac32$-approximate の解を得る。
  論文  参考訳（メタデータ） (2021-10-10T04:35:02Z)
• Batched Data-Driven Evolutionary Multi-Objective Optimization Based on Manifold Interpolation [6.560512252982714]
  バッチ化されたデータ駆動型進化的多目的最適化を実現するためのフレームワークを提案する。 オフザシェルフ進化的多目的最適化アルゴリズムがプラグイン方式で適用できるのは、非常に一般的である。 提案するフレームワークは, より高速な収束と各種PF形状に対する強いレジリエンスを特徴とする。
  論文  参考訳（メタデータ） (2021-09-12T23:54:26Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  我々は、容易で、拡張性があり、堅牢な進化的欲求アルゴリズム(AdaLead)を開発した。 AdaLeadは、様々な生物学的に動機づけられたシーケンスデザインの課題において、アートアプローチのより複雑な状態を克服する、驚くほど強力なベンチマークである。
  論文  参考訳（メタデータ） (2020-10-05T16:40:38Z)
• 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)
• Analysis of Evolutionary Algorithms on Fitness Function with Time-linkage Property [27.660240128423176]
  実世界のアプリケーションでは、多くの最適化問題には時間リンク性があり、すなわち、目的関数の値は現在の解と過去の解に依存する。 本稿では,時間連鎖関数の進化的アルゴリズムを厳格に解析する第一歩を踏み出した。
  論文  参考訳（メタデータ） (2020-04-26T07:56:40Z)
• Parameterized Complexity Analysis of Randomized Search Heuristics [16.759797540118665]
  この章では、ランダム化アルゴリズムのパラメータ化実行時間解析の理論を適用した多数の結果をまとめた。 NP-hard最適化問題の解法を課題とするランダム化検索の集合に対する主な結果と証明手法について概説する。
  論文  参考訳（メタデータ） (2020-01-15T03:43:56Z)

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

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