論文の概要: Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from
Fitness Levels
- arxiv url: http://arxiv.org/abs/2311.10502v1
- Date: Fri, 17 Nov 2023 13:04:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-20 14:43:29.732766
- Title: Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from
Fitness Levels
- Title(参考訳): 裂け目進化アルゴリズムのフィトネスレベルからの着地時間推定の高速化
- Authors: Jun He, Siang Yew Chong and Xin Yao
- Abstract要約: 我々は、フィットネスレベルから線形の下と上の境界を構築するための新しい有向グラフ(グラフ)法を開発した。
ダイグラフ上の条件遷移確率を用いて、下界と上界を直接計算する。
我々の研究は、簡単なフィットネス機能にショートカットを使わずに対処することから、よりリアルなショートカット機能まで、フィットネスレベルメソッドを拡張しています。
- 参考スコア(独自算出の注目度): 5.175594369538569
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The fitness level method is an easy-to-use tool for estimating the hitting
time of elitist EAs. Recently, general linear lower and upper bounds from
fitness levels have been constructed. However, the construction of these bounds
requires recursive computation, which makes them difficult to use in practice.
We address this shortcoming with a new directed graph (digraph) method that
does not require recursive computation and significantly simplifies the
calculation of coefficients in linear bounds. In this method, an EA is modeled
as a Markov chain on a digraph. Lower and upper bounds are directly calculated
using conditional transition probabilities on the digraph. This digraph method
provides straightforward and explicit expressions of lower and upper time bound
for elitist EAs. In particular, it can be used to derive tight lower bound on
both fitness landscapes without and with shortcuts. This is demonstrated
through four examples: the (1+1) EA on OneMax, FullyDeceptive, TwoMax1 and
Deceptive. Our work extends the fitness level method from addressing simple
fitness functions without shortcuts to more realistic functions with shortcuts.
- Abstract(参考訳): フィットネスレベル法は、エリート主義EAの打つ時間を推定するための使い易いツールである。
近年,フィットネスレベルからの一般線形下限と上限が構築されている。
しかし、これらの境界の構築には再帰的な計算が必要であるため、実際にの使用は困難である。
線形境界における係数の計算を大幅に単純化し,再帰的計算を必要としない新しい有向グラフ(グラフ)法でこの問題に対処する。
この方法では、EAはグラフ上のマルコフ連鎖としてモデル化される。
ダイグラフ上の条件遷移確率を用いて下界と上界を直接計算する。
このダイアグラフ法は、エリートeasに対して下限と上限の直接的かつ明示的な表現を提供する。
特に、ショートカットなしで、両方のフィットネスランドスケープにしっかりとした下界を引き出すのに使うことができる。
これは、OneMax上の(1+1)EA、FullyDeceptive、TwoMax1、Deceptiveの4つの例で示される。
我々の研究は、簡単なフィットネス機能にショートカットを使わずに対処することから、よりリアルなショートカット機能まで、フィットネスレベルメソッドを拡張しています。
関連論文リスト
- Graph Pruning for Enumeration of Minimal Unsatisfiable Subsets [4.59143974279554]
バイナリ制約の最小不満足な部分集合(MUS)を見つけることは、過剰制約されたシステムの不適合性解析において一般的な問題である。
MUS列挙を高速化するために,学習モデルを用いて公式をプルーする手法を提案する。
論文 参考訳(メタデータ) (2024-02-19T20:03:45Z) - Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms [11.335004901064352]
フィットネスレベルから最も厳密な距離境界が構築され、初めて証明される。
異なる種類の線形境界に対する異なる適合度レベル手法の開発に使用できるフレームワークが確立されている。
論文 参考訳(メタデータ) (2023-09-02T07:42:57Z) - Provably Faster Gradient Descent via Long Steps [0.0]
短期的な目的値を増加させる長いステップは、長期的収束を確実に速くすることを示す。
勾配降下のより高速な$O(1/Tlog T)$レートを証明するための予想も、単純な数値検証と共に動機付けられる。
論文 参考訳(メタデータ) (2023-07-12T17:41:07Z) - Efficient Graph Laplacian Estimation by Proximal Newton [13.548925059656327]
グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。
いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
論文 参考訳(メタデータ) (2023-02-13T15:13:22Z) - Softmax-free Linear Transformers [101.01493387683898]
視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。
既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。
我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
論文 参考訳(メタデータ) (2022-07-05T03:08:27Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - Lower Bounds from Fitness Levels Made Easy [5.177947445379688]
Wegenerによるいわゆるフィットネスレベルの方法の2つの新しい変種を示す。
レベル離脱確率の他に、彼らはレベルが訪問される確率にのみ依存している。
より困難を伴わずに計算や推定が可能であることを示し,本手法を適用して以下の既知結果を再現する。
論文 参考訳(メタデータ) (2021-04-07T19:50:53Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。
このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。
また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
論文 参考訳(メタデータ) (2020-10-13T08:02:38Z) - Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。
本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。
実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
論文 参考訳(メタデータ) (2020-07-20T12:07:48Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。