論文の概要: Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear
Functions
- arxiv url: http://arxiv.org/abs/2208.05670v1
- Date: Thu, 11 Aug 2022 07:05:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-12 13:07:31.030468
- Title: Runtime Analysis of the (1+1) EA on Weighted Sums of Transformed Linear
Functions
- Title(参考訳): 変換線形関数の重み付き和に対する(1+1)EAの実行時解析
- Authors: Frank Neumann and Carsten Witt
- Abstract要約: 2つの変換線型関数の重み付き和である目的関数のクラスについて検討する。
以上の結果から, (1+1) EA は, 関数の重複ビット数に依存する突然変異率を持つため, 期待時間 O(n log n) におけるこれらの関数に対する最適解が得られることがわかった。
- 参考スコア(独自算出の注目度): 13.264683014487376
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear functions play a key role in the runtime analysis of evolutionary
algorithms and studies have provided a wide range of new insights and
techniques for analyzing evolutionary computation methods. Motivated by studies
on separable functions and the optimization behaviour of evolutionary
algorithms as well as objective functions from the area of chance constrained
optimization, we study the class of objective functions that are weighted sums
of two transformed linear functions. Our results show that the (1+1) EA, with a
mutation rate depending on the number of overlapping bits of the functions,
obtains an optimal solution for these functions in expected time O(n log n),
thereby generalizing a well-known result for linear functions to a much wider
range of problems.
- Abstract(参考訳): 線形関数は進化的アルゴリズムのランタイム解析において重要な役割を担い、研究は進化的計算手法を分析するための幅広い新しい洞察と技術を提供した。
2つの変換線形関数の重み付き和である目的関数のクラスについて検討した。
その結果, (1+1) EA は関数の重なり合うビット数に依存する変異率を持ち, 期待時間 O(n log n) におけるこれらの関数に対する最適解を求め, 線形関数のよく知られた結果をより広い範囲の問題に一般化することを示した。
関連論文リスト
- Functional Bilevel Optimization for Machine Learning [36.081761044296904]
本稿では,関数空間上での内的目的を最小化する機械学習における二段階最適化問題に対する新たな機能的視点を提案する。
機能的二段階最適化問題に対して,スケーラブルで効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-29T15:22:03Z) - Benchmarking Differential Evolution on a Quantum Simulator [0.0]
微分進化(DE)はラストリギン関数やローゼンブロック関数などの関数の最小値を計算するために用いられる。
この研究は、古典的チューリングモデル計算で生成される候補個体を用いて、これらの関数にDE法を適用した結果の研究である。
論文 参考訳(メタデータ) (2023-11-06T14:27:00Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳(メタデータ) (2023-07-08T15:41:48Z) - Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
線形化ラプラス近似(LLA)はベイズニューラルネットワークの構築に有効で効率的であることが示されている。
ベイズ最適化におけるLLAの有用性について検討し,その性能と柔軟性を強調した。
論文 参考訳(メタデータ) (2023-04-17T14:23:43Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳(メタデータ) (2023-04-12T14:51:47Z) - Using Affine Combinations of BBOB Problems for Performance Assessment [0.9281671380673306]
本稿では,アフィン関数の組み合わせを用いて最適化アルゴリズムの挙動を解析する方法を示す。
特に,複合問題間の重み付けを変化させることで,付加的なグローバル構造の影響についての洞察を得ることができることを強調する。
論文 参考訳(メタデータ) (2023-03-08T13:37:55Z) - On Solution Functions of Optimization: Universal Approximation and
Covering Number Bounds [6.3291148076593355]
線形目標性(1)(LP)と近似可能なQP近似パワーの凸最適化関数解関数の表現可能性について検討する。
この結果から,制約付きプログラミングの特性の厳密な解析と,アルゴリズム設計や性能保証への示唆が得られた。
論文 参考訳(メタデータ) (2022-12-02T17:16:04Z) - Offline Reinforcement Learning with Differentiable Function
Approximation is Provably Efficient [65.08966446962845]
歴史的データを用いて意思決定戦略を最適化することを目的としたオフライン強化学習は、現実の応用に広く適用されている。
微分関数クラス近似(DFA)を用いたオフライン強化学習の検討から一歩踏み出した。
最も重要なことは、悲観的な適合Q-ラーニングアルゴリズムを解析することにより、オフライン微分関数近似が有効であることを示すことである。
論文 参考訳(メタデータ) (2022-10-03T07:59:42Z) - Multivariate functional group sparse regression: functional predictor
selection [2.0063942015243423]
無限次元の一般ヒルベルト空間の下で関数群スパース回帰の2つの方法を開発する。
アルゴリズムの収束と推定と選択の整合性を示す。
機能的磁気共鳴イメージング(fMRI)への応用は、ADHDとIQに関連する人間の脳の領域を明らかにする。
論文 参考訳(メタデータ) (2021-07-05T17:11:28Z) - Sequential Subspace Search for Functional Bayesian Optimization
Incorporating Experimenter Intuition [63.011641517977644]
本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。
標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。
シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
論文 参考訳(メタデータ) (2020-09-08T06:54:11Z) - Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
我々は,群不変特徴ベクトルが線形分類器を学習する際に十分な識別情報を含んでいることを証明した。
主成分分析やk平均クラスタリングにおいて,グループアクションを明示的に考慮する新たな特徴モデルを提案する。
論文 参考訳(メタデータ) (2019-06-05T07:15:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。