論文の概要: Representation-agnostic distance-driven perturbation for optimizing ill-conditioned problems

• arxiv url: http://arxiv.org/abs/2306.02985v1
• Date: Mon, 5 Jun 2023 15:54:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-06 14:01:54.200018
• Title: Representation-agnostic distance-driven perturbation for optimizing ill-conditioned problems
• Title（参考訳）: 問題最適化のための表現非依存距離駆動摂動
• Authors: Kirill Antonov, Anna V. Kononova, Thomas B\"ack, Niki van Stein
• Abstract要約: 局所性は、ランダムな検索でブラックボックス問題を効率的に最適化するために重要である。 このような最適化問題をより効率的に解くために、2つの突然変異演算子を提案する。 進化的アルゴリズムやランダム局所探索に適用した場合,両者の変異演算子により,ほとんどの関数の探索が高速化されることを実験的に示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Locality is a crucial property for efficiently optimising black-box problems with randomized search heuristics. However, in practical applications, it is not likely to always find such a genotype encoding of candidate solutions that this property is upheld with respect to the Hamming distance. At the same time, it may be possible to use domain-specific knowledge to define a metric with locality property. We propose two mutation operators to solve such optimization problems more efficiently using the metric. The first operator assumes prior knowledge about the distance, the second operator uses the distance as a black box. Those operators apply an estimation of distribution algorithm to find the best mutant according to the defined in the paper function, which employs the given distance. For pseudo-boolean and integer optimization problems, we experimentally show that both mutation operators speed up the search on most of the functions when applied in considered evolutionary algorithms and random local search. Moreover, those operators can be applied in any randomized search heuristic which uses perturbations. However, our mutation operators increase wall-clock time and so are helpful in practice when distance is (much) cheaper to compute than the real objective function.
• Abstract（参考訳）: 局所性はランダムな探索ヒューリスティックスを用いてブラックボックス問題を効率的に最適化するための重要な特性である。 しかし, 実用的応用においては, この性質がハミング距離に関して維持されるような, 候補解の遺伝子型エンコーディングを常に見つけることは不可能である。 同時に、局所性特性を持つ計量を定義するためにドメイン固有の知識を使用することもできる。 このような最適化問題をより効率的に解くために、2つの突然変異演算子を提案する。 第1のオペレータは距離に関する事前の知識を仮定し、第2のオペレータは距離をブラックボックスとして使用する。 これらの演算子は、与えられた距離を用いる紙関数で定義された最良のミュータントを見つけるために分布アルゴリズムの推定を適用する。 擬似ブール問題と整数最適化問題に対して, 2つの突然変異演算子が, 進化的アルゴリズムやランダム局所探索に適用した場合のほとんどの関数の探索を高速化することを示した。 さらに、これらの演算子は摂動を用いた任意のランダムな探索ヒューリスティックに適用できる。 しかし、変異演算子は壁時計時間を増やすため、実際の目的関数よりも距離が(かなり)安価である場合に有用である。

関連論文リスト

• Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions [8.382710169577447]
  ビットストリング符号化における遺伝的演算子の非線形性を最適化する効果について検討する。 オペレータが提供できる可能性のある変更の範囲を観察することで、この情報を使用して、より効果的な遺伝子操作子の組み合わせを設計することができる。
  論文  参考訳（メタデータ） (2023-02-12T10:34:01Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。 また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
  論文  参考訳（メタデータ） (2022-05-05T06:43:46Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence [29.189409618561964]
  我々は単調演算子を用いた変分不等式の新しい適応アルゴリズムを開発した。 我々のアルゴリズムは未知の問題パラメータに自動的に適応する。 我々のアルゴリズムは普遍的であり、同時に最適な収束率を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-15T14:44:26Z)
• Evolutionary Algorithms with Self-adjusting Asymmetric Mutation [0.0]
  ゼロビットと1ビットを異なる方法で扱うことができる非対称突然変異演算子を解析する。 マッチングビット数を表す関数のクラスOneMax$_a$に対して、改善された実行結果を示す。
  論文  参考訳（メタデータ） (2020-06-16T13:16:50Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
  大きな探索空間では、アルゴリズムは関数の最適値に達する前に、いくつかの低関数値領域を通過する。 このコールドスタートフェーズの1つのアプローチは、最適化を加速できる事前知識を使用することである。 本稿では,関数の事前分布を通じて,関数の最適性に関する事前知識を示す。 先行分布は、探索空間を最適関数の高確率領域の周りに拡張し、最適関数の低確率領域の周りに縮小するようにワープする。
  論文  参考訳（メタデータ） (2020-03-27T06:18:49Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。 提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
  論文  参考訳（メタデータ） (2020-02-16T04:57:52Z)

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

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