論文の概要: 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つの例で示される。 我々の研究は、簡単なフィットネス機能にショートカットを使わずに対処することから、よりリアルなショートカット機能まで、フィットネスレベルメソッドを拡張しています。

関連論文リスト

• Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms [11.335004901064352]
  フィットネスレベルから最も厳密な距離境界が構築され、初めて証明される。 異なる種類の線形境界に対する異なる適合度レベル手法の開発に使用できるフレームワークが確立されている。
  論文  参考訳（メタデータ） (2023-09-02T07:42:57Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components [30.33731479053404]
  限られたサポートの単純な部分モジュラ関数の和を最小化することは、機械学習に多くの応用がある。 我々は、和の成分が濃度ベースである場合の高速な手法を開発し、入力集合のサイズにのみ依存する。 この問題に対する最初の近似アルゴリズムを開発し、この近似はスパースグラフカット問題への還元により迅速に計算できる。
  論文  参考訳（メタデータ） (2021-10-28T02:36:55Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Lower Bounds from Fitness Levels Made Easy [5.177947445379688]
  Wegenerによるいわゆるフィットネスレベルの方法の2つの新しい変種を示す。 レベル離脱確率の他に、彼らはレベルが訪問される確率にのみ依存している。 より困難を伴わずに計算や推定が可能であることを示し,本手法を適用して以下の既知結果を再現する。
  論文  参考訳（メタデータ） (2021-04-07T19:50:53Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
  論文  参考訳（メタデータ） (2021-01-14T19:45:17Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。 このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。 また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
  論文  参考訳（メタデータ） (2020-10-13T08:02:38Z)
• Constraining Logits by Bounded Function for Adversarial Robustness [14.916447616855208]
  本稿では,ソフトマックス直前に新たな有界関数を追加することにより,対向ロバスト性を向上させる手法を提案する。 本手法は,敵対的トレーニングを伴わない逆摂動データセットに対する精度の点で,ロジット正規化手法に匹敵する。
  論文  参考訳（メタデータ） (2020-10-06T09:04:58Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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