Fugu-MT 論文翻訳(概要): Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima

論文の概要: Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima

arxiv url: http://arxiv.org/abs/2310.04042v1
Date: Fri, 6 Oct 2023 06:32:07 GMT
ステータス: 処理完了
システム内更新日: 2023-10-10 01:26:29.790586
Title: Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential Number of Optima
Title（参考訳）: 2変量分布推定アルゴリズムは指数数のオプティマを見つけることができる
Authors: Benjamin Doerr and Martin S. Krejca
Abstract要約: 本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。 EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
参考スコア（独自算出の注目度）: 12.009357100208353
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Finding a large set of optima in a multimodal optimization landscape is a challenging task. Classical population-based evolutionary algorithms typically converge only to a single solution. While this can be counteracted by applying niching strategies, the number of optima is nonetheless trivially bounded by the population size. Estimation-of-distribution algorithms (EDAs) are an alternative, maintaining a probabilistic model of the solution space instead of a population. Such a model is able to implicitly represent a solution set far larger than any realistic population size. To support the study of how optimization algorithms handle large sets of optima, we propose the test function EqualBlocksOneMax (EBOM). It has an easy fitness landscape with exponentially many optima. We show that the bivariate EDA mutual-information-maximizing input clustering, without any problem-specific modification, quickly generates a model that behaves very similarly to a theoretically ideal model for EBOM, which samples each of the exponentially many optima with the same maximal probability. We also prove via mathematical means that no univariate model can come close to having this property: If the probability to sample an optimum is at least inverse-polynomial, there is a Hamming ball of logarithmic radius such that, with high probability, each sample is in this ball.
Abstract（参考訳）: マルチモーダル最適化のランドスケープで大規模なオプティマを見つけるのは、難しい作業です。古典的な集団に基づく進化的アルゴリズムは、通常は単一の解のみに収束する。これはニチング戦略を適用することで対処できるが、オプティマの数は人口規模によって自明に制限される。分布推定アルゴリズム(EDAs)は、集団ではなく、解空間の確率論的モデルを維持する代替手段である。そのようなモデルは、現実的な人口規模よりもはるかに大きい解を暗黙的に表すことができる。最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。楽なフィットネス風景で、指数関数的に多くのオプティマがある。二変量 eda の相互情報最大化入力クラスタリングは、問題固有の修正を伴わずに、エボムの理論的に理想的なモデルに非常によく似た振る舞いをするモデルを素早く生成し、指数的に多数のオプティマをそれぞれ同じ最大確率でサンプリングする。また、数学的な方法では、この性質を持つような一変量モデルが存在しないことを証明している: 最適点をサンプリングする確率が少なくとも逆ポリノミカルであれば、高い確率で各サンプルがこの球に入るような対数半径のハミング球が存在する。

関連論文リスト

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)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
Selection of the Most Probable Best [2.1095005405219815]
予測値ランキングと選択(R&S)問題では,すべてのk解のシミュレーション出力が,分布によって不確実性をモデル化可能な共通パラメータに依存する。我々は、最も確率の高い最適解 (MPB) を、分布に関して最適である確率が最も大きい解と定義する。最適化条件における未知の手段をその推定値に置き換えるアルゴリズムを考案し,シミュレーション予算が増加するにつれて,アルゴリズムのサンプリング比が条件を満たすことを証明した。
論文参考訳（メタデータ） (2022-07-15T15:27:27Z)
Efficient Approximation of Expected Hypervolume Improvement using Gauss-Hermite Quadrature [0.0]
ガウス・ハーマイト二次構造はモンテカルロの独立性および相関性のある予測密度に対する正確な代替物である。独立性および相関性のある予測密度に対するモンテカルロの正確な代替であることを示す。
論文参考訳（メタデータ） (2022-06-15T22:09:48Z)
An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文参考訳（メタデータ） (2022-05-17T15:28:46Z)
Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文参考訳（メタデータ） (2022-02-23T02:39:04Z)
Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
非滑らかな有限サム最小化は機械学習の基本的な問題である。本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
論文参考訳（メタデータ） (2021-11-06T07:29:55Z)
Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。局所探索のための政策勾配は、しばしばランダムな摂動から得られる。目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文参考訳（メタデータ） (2021-06-22T16:07:02Z)
Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文参考訳（メタデータ） (2021-04-14T19:21:59Z)
Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文参考訳（メタデータ） (2020-11-19T10:00:54Z)
Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文参考訳（メタデータ） (2020-04-23T05:00:21Z)

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

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