論文の概要: On Steady-State Evolutionary Algorithms and Selective Pressure: Why
Inverse Rank-Based Allocation of Reproductive Trials is Best
- arxiv url: http://arxiv.org/abs/2103.10394v1
- Date: Thu, 18 Mar 2021 17:27:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-19 15:34:47.607928
- Title: On Steady-State Evolutionary Algorithms and Selective Pressure: Why
Inverse Rank-Based Allocation of Reproductive Trials is Best
- Title(参考訳): 定常進化アルゴリズムと選択的圧力:なぜ逆ランクに基づく生殖実験が最適か
- Authors: Dogan Corus and Andrei Lissovoi and Pietro S. Oliveto and Carsten Witt
- Abstract要約: 我々は、定常EAのグローバル最適化能力に対する選択的な圧力の影響を分析する。
標準のバイモーダルベンチマーク関数2maxでは、均一な親選択を使用することで両方のオプティマを見つける確率の高い指数が得られることを厳密に証明します。
一方,最悪の個人を親として選択することは,合理的な人口規模に対して圧倒的な確率で効率的なグローバル最適化につながることを実証する。
- 参考スコア(独自算出の注目度): 9.290757451344673
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We analyse the impact of the selective pressure for the global optimisation
capabilities of steady-state EAs. For the standard bimodal benchmark function
\twomax we rigorously prove that using uniform parent selection leads to
exponential runtimes with high probability to locate both optima for the
standard ($\mu$+1)~EA and ($\mu$+1)~RLS with any polynomial population sizes.
On the other hand, we prove that selecting the worst individual as parent leads
to efficient global optimisation with overwhelming probability for reasonable
population sizes. Since always selecting the worst individual may have
detrimental effects for escaping from local optima, we consider the performance
of stochastic parent selection operators with low selective pressure for a
function class called \textsc{TruncatedTwoMax} where one slope is shorter than
the other. An experimental analysis shows that the EAs equipped with inverse
tournament selection, where the loser is selected for reproduction and small
tournament sizes, globally optimise \textsc{TwoMax} efficiently and effectively
escape from local optima of \textsc{TruncatedTwoMax} with high probability.
Thus they identify both optima efficiently while uniform (or stronger)
selection fails in theory and in practice. We then show the power of inverse
selection on function classes from the literature where populations are
essential by providing rigorous proofs or experimental evidence that it
outperforms uniform selection equipped with or without a restart strategy. We
conclude the paper by confirming our theoretical insights with an empirical
analysis of the different selective pressures on standard benchmarks of the
classical MaxSat and Multidimensional Knapsack Problems.
- Abstract(参考訳): 我々は、定常EAのグローバル最適化能力に対する選択的な圧力の影響を分析する。
標準バイモーダルベンチマーク関数 \twomax に対して、一様親選択を用いると指数関数ランタイムが高確率で、標準 (\mu$+1)~ea と (\mu$+1)~rls の両方を多項式サイズで見つけることができることを厳密に証明する。
一方,最悪の個人を親として選択することは,合理的な人口規模に対して圧倒的な確率で効率的なグローバル最適化につながることを実証する。
最悪の個人を常に選択することは局所視能から逃れるために有害な効果をもたらす可能性があるため、一方の斜面が他方よりも短い関数クラスに対して選択圧が低い確率的親選択演算子の性能を考える。
実験分析により,easの再現性と小型のトーナメントサイズが選択される逆トーナメント選択機能を備えたeasは, \textsc{twomax} の局所的オプティマから高い確率で効率良くかつ効果的に脱却できることを示した。
したがって、2つのオプティマを効率的に識別する一方で、一様選択(あるいはより強い選択)は理論上も実際にも失敗する。
そこで本研究では,群集が必須である文献から関数クラスにおける逆選択の力を示すとともに,再帰戦略の有無に関わらず,一様選択よりも優れているという厳密な証明や実験的な証拠を与える。
古典的マックスサット問題と多次元ナップサック問題の標準ベンチマークにおける異なる選択的圧力の実証分析により,理論的な知見を検証した。
関連論文リスト
- Localized Zeroth-Order Prompt Optimization [54.964765668688806]
そこで我々は,ZOPO(Localized zeroth-order prompt optimization)という新しいアルゴリズムを提案する。
ZOPOはニューラル・タンジェント・カーネルをベースとしたガウス法を標準ゼロ階次最適化に取り入れ、高速な局所最適探索を高速化する。
注目すべきは、ZOPOは最適化性能とクエリ効率の両方の観点から、既存のベースラインを上回っていることだ。
論文 参考訳(メタデータ) (2024-03-05T14:18:15Z) - Dynamic Incremental Optimization for Best Subset Selection [18.70844080355172]
最良のサブセット選択は、多くの学習問題に対する金の標準と見なされている。
主問題構造と双対問題構造に基づいて,効率的な部分集合双対アルゴリズムを開発した。
論文 参考訳(メタデータ) (2024-02-04T02:26:40Z) - Dual-Directed Algorithm Design for Efficient Pure Exploration [11.492736493413103]
有限の選択肢からなる逐次適応実験の文脈における純粋探索問題を考える。
サンプルの最適な割り当てに対する強い収束の概念の観点から、最適性の十分な条件を導出する。
我々のアルゴリズムは、$epsilon$-best-armの識別としきい値の帯域幅問題に最適である。
論文 参考訳(メタデータ) (2023-10-30T07:29:17Z) - Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential
Number of Optima [12.009357100208353]
本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。
EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
論文 参考訳(メタデータ) (2023-10-06T06:32:07Z) - Optimize-via-Predict: Realizing out-of-sample optimality in data-driven
optimization [0.0]
本稿では,データ駆動最適化の定式化について検討する。
我々は、規範的なソリューションを、そのようなデータセットを意思決定にマッピングする意思決定者ルールとして定義する。
本稿では,このようなサンプル外最適解に対して,サンプリングアルゴリズムと2分割探索アルゴリズムを組み合わせることで効率よく解ける最適化問題を提案する。
論文 参考訳(メタデータ) (2023-09-20T08:48:50Z) - Bayesian Optimization with Conformal Prediction Sets [44.565812181545645]
コンフォーマル予測(Conformal prediction)は、不確実な定量化手法であり、不特定モデルに対してもカバレッジを保証する。
本稿では,モデルの妥当性が保証された検索空間の領域にクエリを誘導する共形ベイズ最適化を提案する。
多くの場合、クエリのカバレッジはサンプル効率を損なうことなく大幅に改善できる。
論文 参考訳(メタデータ) (2022-10-22T17:01:05Z) - Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
統計的決定論の研究からシャノンエントロピーの一般化を考える。
まず,このエントロピーの特殊なケースがBO手順でよく用いられる獲得関数に繋がることを示す。
次に、損失に対する選択肢の選択が、どのようにして柔軟な獲得関数の族をもたらすかを示す。
論文 参考訳(メタデータ) (2022-10-04T04:43:58Z) - Optimizing Partial Area Under the Top-k Curve: Theory and Practice [151.5072746015253]
トップk曲線下部分領域(AUTKC)と呼ばれる新しい計量法を開発した。
AUTKCはより優れた識別能力を持ち、ベイズ最適スコア関数は条件付き確率に対して正しいトップKランクを与えることができる。
提案手法を最適化するために,実証的なサロゲートリスク最小化フレームワークを提案する。
論文 参考訳(メタデータ) (2022-09-03T11:09:13Z) - Model Selection in Batch Policy Optimization [88.52887493684078]
バッチポリシー最適化におけるモデル選択の問題について検討する。
我々は,任意のモデル選択アルゴリズムが競争力を得るために最適にトレードオフすべきという誤りの3つの源を同定する。
論文 参考訳(メタデータ) (2021-12-23T02:31:50Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳(メタデータ) (2021-06-05T09:16:28Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳(メタデータ) (2020-08-17T16:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。