論文の概要: Estimation-of-Distribution Algorithms for Multi-Valued Decision
Variables
- arxiv url: http://arxiv.org/abs/2302.14420v1
- Date: Tue, 28 Feb 2023 08:52:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-01 17:20:05.615090
- Title: Estimation-of-Distribution Algorithms for Multi-Valued Decision
Variables
- Title（参考訳）: 多値決定変数の分布推定アルゴリズム
- Authors: Firas Ben Jedidia, Benjamin Doerr, Martin S. Krejca
- Abstract要約: 分布推定アルゴリズムは多値問題に適応可能であることを示す。
我々の研究は、EDAを多値問題に適応させることが可能であることを示し、主要なパラメータをどう設定するかをアドバイスする。
- 参考スコア（独自算出の注目度）: 8.34061303235504
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: With apparently all research on estimation-of-distribution algorithms (EDAs)
concentrated on pseudo-Boolean optimization and permutation problems, we
undertake the first steps towards using EDAs for problems in which the decision
variables can take more than two values, but which are not permutation
problems. To this aim, we propose a natural way to extend the known univariate
EDAs to such variables. Different from a naive reduction to the binary case, it
avoids additional constraints.
Since understanding genetic drift is crucial for an optimal parameter choice,
we extend the known quantitative analysis of genetic drift to EDAs for
multi-valued variables. Roughly speaking, when the variables take $r$ different
values, the time for genetic drift to become significant is $r$ times shorter
than in the binary case. Consequently, the update strength of the probabilistic
model has to be chosen $r$ times lower now.
To investigate how desired model updates take place in this framework, we
undertake a mathematical runtime analysis on the $r$-valued LeadingOnes
problem. We prove that with the right parameters, the multi-valued UMDA solves
this problem efficiently in $O(r\log(r)^2 n^2 \log(n))$ function evaluations.
Overall, our work shows that EDAs can be adjusted to multi-valued problems,
and it gives advice on how to set the main parameters.
- Abstract（参考訳）: 疑似ブール最適化と置換問題に焦点をあてた分布推定アルゴリズム(EDAs)に関するすべての研究により、決定変数が2つ以上の値を取ることができるが、置換問題ではない問題にEDAを使用するための第一歩を踏み出した。
この目的のために、既知の単変数EDAをそのような変数に拡張する自然な方法を提案する。
バイナリケースへのナイーブな還元とは異なり、追加の制約を回避する。
遺伝的ドリフトの理解は最適なパラメータ選択に不可欠であるため、遺伝的ドリフトの既知の定量分析を多値変数のEDAに拡張する。
大まかに言えば、変数が異なる値 r$ を取るとき、遺伝的ドリフトが重要になる時間は二項の場合よりも r$ 倍短い。
そのため、確率モデルの更新強度は、現在$r$よりも低く選択する必要がある。
このフレームワークでモデル更新がどの程度望ましいかを調べるため、$r$-valued LeadingOnes問題に関する数学的ランタイム解析を実施します。
適切なパラメータを用いて、multi-valued UMDAは、$O(r\log(r)^2 n^2 \log(n))$関数評価において、この問題を効率的に解く。
全体としては、edasが多値問題に適応できることを示し、メインパラメータの設定方法に関するアドバイスを提供します。
関連論文リスト
- 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) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both
Worlds in Stochastic and Deterministic Environments [48.96971760679639]
マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。
環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。
モデルに基づく手法では、MVPアルゴリズムの変種を設計する。
特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
論文 参考訳（メタデータ） (2023-01-31T06:54:06Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - An Application of a Multivariate Estimation of Distribution Algorithm to
Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。
より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。
我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文 参考訳（メタデータ） (2022-05-17T15:28:46Z) - Iterative Feature Matching: Toward Provable Domain Generalization with
Logarithmic Environments [55.24895403089543]
ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。
我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-18T04:39:19Z) - Distributionally Robust Optimization with Markovian Data [8.126833795693699]
本研究では,不確実な問題パラメータの確率分布が不明なプログラムについて検討する。
本稿では,問題の目的関数と最適解を推定するために,データ駆動型分布法を提案する。
論文 参考訳（メタデータ） (2021-06-12T10:59:02Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
量子化のための乗算器の交互方向法(texttADMM-Q$)アルゴリズムの性能について検討する。
不正確な更新ルールを処理できる$texttADMM-Q$のいくつかのバリエーションを開発しています。
提案手法の有効性を実証的に評価した。
論文 参考訳（メタデータ） (2020-09-08T01:58:02Z) - The Univariate Marginal Distribution Algorithm Copes Well With Deception
and Epistasis [9.853329403413701]
陰性な発見はUMDAのパラメータの不運な選択によって引き起こされることを示す。
この結果から,UMDAは進化的アルゴリズムよりも局所最適に対処できることが示唆された。
論文 参考訳（メタデータ） (2020-07-16T12:07:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。