論文の概要: From Understanding Genetic Drift to a Smart-Restart Mechanism for
Estimation-of-Distribution Algorithms
- arxiv url: http://arxiv.org/abs/2206.09090v5
- Date: Fri, 3 Nov 2023 13:36:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 18:52:57.741963
- Title: From Understanding Genetic Drift to a Smart-Restart Mechanism for
Estimation-of-Distribution Algorithms
- Title（参考訳）: 遺伝的ドリフトの理解から分布推定アルゴリズムのスマートリスタート機構へ
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: 我々は,分布推定アルゴリズム(EDAs)のためのスマートリスタート機構を開発する。
遺伝的ドリフトのリスクが高い場合、実行を停止することで、適切なパラメーター条件下でEDAを自動的に実行します。
スマートリスタート機構は,文献で示唆されるものよりも,集団サイズに対してはるかに優れた値を見出すことを示す。
- 参考スコア（独自算出の注目度）: 16.904475483445452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Estimation-of-distribution algorithms (EDAs) are optimization algorithms that
learn a distribution on the search space from which good solutions can be
sampled easily. A key parameter of most EDAs is the sample size (population
size). If the population size is too small, the update of the probabilistic
model builds on few samples, leading to the undesired effect of genetic drift.
Too large population sizes avoid genetic drift, but slow down the process.
Building on a recent quantitative analysis of how the population size leads
to genetic drift, we design a smart-restart mechanism for EDAs. By stopping
runs when the risk for genetic drift is high, it automatically runs the EDA in
good parameter regimes.
Via a mathematical runtime analysis, we prove a general performance guarantee
for this smart-restart scheme. This in particular shows that in many situations
where the optimal (problem-specific) parameter values are known, the restart
scheme automatically finds these, leading to the asymptotically optimal
performance.
We also conduct an extensive experimental analysis. On four classic benchmark
problems, we clearly observe the critical influence of the population size on
the performance, and we find that the smart-restart scheme leads to a
performance close to the one obtainable with optimal parameter values. Our
results also show that previous theory-based suggestions for the optimal
population size can be far from the optimal ones, leading to a performance
clearly inferior to the one obtained via the smart-restart scheme. We also
conduct experiments with PBIL (cross-entropy algorithm) on two combinatorial
optimization problems from the literature, the max-cut problem and the
bipartition problem. Again, we observe that the smart-restart mechanism finds
much better values for the population size than those suggested in the
literature, leading to a much better performance.
- Abstract（参考訳）: 推定分布アルゴリズム(EDAs)は、優れた解を容易にサンプリングできる探索空間上の分布を学習する最適化アルゴリズムである。
ほとんどのEDAのキーパラメータはサンプルサイズ(集団サイズ)である。
集団サイズが小さすぎると、確率モデルの更新は少数のサンプルの上に構築され、遺伝的ドリフトの望ましくない影響をもたらす。
人口が多すぎると遺伝的ドリフトは避けられますが、プロセスは遅くなります。
集団の大きさが遺伝的ドリフトにどのように繋がるかの最近の定量的分析に基づいて、我々はEDAのためのスマートリスタート機構を設計する。
遺伝的ドリフトのリスクが高い場合に実行を停止することで、適切なパラメータで自動的にedaを実行します。
数学的な実行時解析により、このスマートリスタート方式の一般的な性能保証が証明される。
特に、最適パラメータ値が知られている多くの状況において、再起動スキームが自動的にこれらを見つけ出し、漸近的に最適な性能をもたらすことが示されている。
広範な実験分析も行っています。
4つの古典的なベンチマーク問題において,個体群の大きさが性能に与える影響を明らかに観察し,スマートリスタート方式が最適なパラメータ値で得られるものに近い性能をもたらすことを見出した。
また, 最適個体数に対する従来の理論に基づく提案は, 最適個体数とは程遠い可能性を示し, スマートリスタート方式によって得られた提案よりも明らかに性能が劣ることを示した。
また,2つの組合せ最適化問題,最大カット問題,分割問題についてもPBIL(クロスエントロピーアルゴリズム)を用いて実験を行った。
繰り返しになるが、スマートリスタート機構は文献で示唆されているものよりも人口規模に対してはるかに優れた値を見出すので、パフォーマンスが向上する。
関連論文リスト
- Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
オフライン優先最適化は、LLM(Large Language Model)出力の品質を向上・制御するための重要な手法である。
我々は、人間の介入なしに、新しい最先端の選好最適化アルゴリズムを自動で発見する客観的発見を行う。
実験は、ロジスティックと指数的損失を適応的にブレンドする新しいアルゴリズムであるDiscoPOPの最先端性能を示す。
論文 参考訳（メタデータ） (2024-06-12T16:58:41Z) - Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
一般化されたOneMax関数の最初のランタイム解析を提供する。
r-cGAはこのr値のOneMax問題を効率的に解くことを示す。
実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
論文 参考訳（メタデータ） (2024-04-17T10:40:12Z) - Improving genetic algorithms performance via deterministic population
shrinkage [9.334663477968027]
本稿では,遺伝的アルゴリズム(GA)の性能に対する簡易変数集団サイズ法の適用可能性に関する実証的研究について述べる。
それは、所定のスケジュールに従ってGAランの人口を減少させ、速度と重大度パラメータによって構成する。
その結果,SVPS-GAは性能を向上しながら解の質を保ちつつ,性能向上に要する評価回数を削減し,速度重大性の組合せを示した。
論文 参考訳（メタデータ） (2024-01-22T17:05:16Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Accelerating genetic optimization of nonlinear model predictive control
by learning optimal search space size [0.8057006406834467]
本稿では,最適空間サイズを学習することで,NMPCの最適化を高速化する手法を提案する。
提案手法を2つの非線形システムで比較し,他の2つのNMPC手法と比較した。
論文 参考訳（メタデータ） (2023-05-14T08:10:49Z) - A Particle-based Sparse Gaussian Process Optimizer [5.672919245950197]
本稿では,下降の動的過程を利用した新しいスワム・スワムベースのフレームワークを提案する。
このアプローチの最大の利点は、降下を決定する前に現在の状態についてより深い探索を行うことである。
論文 参考訳（メタデータ） (2022-11-26T09:06:15Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z) - From Understanding Genetic Drift to a Smart-Restart Parameter-less
Compact Genetic Algorithm [15.56430085052365]
遺伝的なドリフトのない体制では、実行期間は人口規模にほぼ比例する。
本稿では,遺伝的アルゴリズムのパラメータレスバージョンを提案する。
論文 参考訳（メタデータ） (2020-04-15T15:12:01Z) - Optimistic Exploration even with a Pessimistic Initialisation [57.41327865257504]
最適初期化は強化学習(RL)における効率的な探索のための効果的な戦略である
特に、正の報酬しか持たないシナリオでは、Q-値はその最低値で初期化される。
本稿では、ニューラルネットワークから楽観性の源を分離する、悲観的に初期化されたQ値に対する単純なカウントベースの拡張を提案する。
論文 参考訳（メタデータ） (2020-02-26T17:15:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。