論文の概要: Fast Re-Optimization of LeadingOnes with Frequent Changes

• arxiv url: http://arxiv.org/abs/2209.04391v1
• Date: Fri, 9 Sep 2022 16:51:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-12 12:31:16.149020
• Title: Fast Re-Optimization of LeadingOnes with Frequent Changes
• Title（参考訳）: 周波数変化を伴うリードワンの高速再最適化
• Authors: Nina Bulanova, Arina Buzdalova, Carola Doerr
• Abstract要約: Doerrらによって提案された再最適化アプローチは、問題インスタンスがより頻繁な変更の傾向にある場合に限界に達することを示す。 本稿では,前ベスト周辺における欲求探索と現在ベスト解を補間するアルゴリズムの修正を提案する。
• 参考スコア（独自算出の注目度）: 0.9281671380673306
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In real-world optimization scenarios, the problem instance that we are asked to solve may change during the optimization process, e.g., when new information becomes available or when the environmental conditions change. In such situations, one could hope to achieve reasonable performance by continuing the search from the best solution found for the original problem. Likewise, one may hope that when solving several problem instances that are similar to each other, it can be beneficial to ``warm-start'' the optimization process of the second instance by the best solution found for the first. However, it was shown in [Doerr et al., GECCO 2019] that even when initialized with structurally good solutions, evolutionary algorithms can have a tendency to replace these good solutions by structurally worse ones, resulting in optimization times that have no advantage over the same algorithms started from scratch. Doerr et al. also proposed a diversity mechanism to overcome this problem. Their approach balances greedy search around a best-so-far solution for the current problem with search in the neighborhood around the best-found solution for the previous instance. In this work, we first show that the re-optimization approach suggested by Doerr et al. reaches a limit when the problem instances are prone to more frequent changes. More precisely, we show that they get stuck on the dynamic LeadingOnes problem in which the target string changes periodically. We then propose a modification of their algorithm which interpolates between greedy search around the previous-best and the current-best solution. We empirically evaluate our smoothed re-optimization algorithm on LeadingOnes instances with various frequencies of change and with different perturbation factors and show that it outperforms both a fully restarted (1+1) Evolutionary Algorithm and the re-optimization approach by Doerr et al.
• Abstract（参考訳）: 現実世界の最適化シナリオでは、例えば、新しい情報が利用可能になったときや環境条件が変わったときなど、最適化プロセス中に解決するよう求められた問題インスタンスが変化することがある。 このような状況では、元の問題に対する最良のソリューションから検索を継続することで、合理的なパフォーマンスを達成できると期待できる。 同様に、互いに類似した複数の問題インスタンスを解く場合、第1の解決法によって第2のインスタンスの最適化プロセスが ``warm-start'''' になることも期待できる。 しかし、[Doerr et al., GECCO 2019]では、構造的に良い解を初期化しても、進化的アルゴリズムはこれらの優れた解を構造的に悪い解に置き換える傾向があり、結果として、同じアルゴリズムに対して優位な最適化時間がゼロから始まります。 Doerrらもこの問題を克服するための多様性のメカニズムを提案した。 彼らのアプローチは、前回のインスタンスの最良のソリューションの周辺で、現在の問題に対するベストソファーソリューションの周りの欲求検索のバランスをとる。 本研究では,Dierrらが提案する再最適化アプローチが,問題インスタンスがより頻繁な変化を起こす傾向にある場合に限界に達することを示す。 より正確には、ターゲット文字列が周期的に変化する動的LeadingOnes問題に、それらが立ち往生していることを示す。 そこで我々は,前ベスト周辺における欲求探索と現在ベスト解を補間するアルゴリズムの修正を提案する。 我々は,変化頻度や摂動要因の異なる先導者インスタンス上での平滑化再最適化アルゴリズムを実験的に評価し,完全な再スタート(1+1)進化アルゴリズムとdoerrらによる再最適化アプローチの両方よりも優れることを示した。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Learning to repeatedly solve routing problems [5.08128537391027]
  データのマイナーチェンジ後に問題の再最適化について学習した。 元のソリューションのエッジを考慮すれば、最適なソリューションに留まる確率の高いソリューションを予測し、修正することが目標です。 この解の偏差予測は問題の複雑さを減らし、解を高速化する。
  論文  参考訳（メタデータ） (2022-12-15T19:33:54Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  メタヒューリスティックス(Metaheuristics)は、古典的なアプローチでは解決できない難解な問題を解くために使用される普遍的な最適化アルゴリズムである。 本稿では,キャストに基づく新しい社会認知メタヒューリスティックの構築を目標とし,このアルゴリズムのいくつかのバージョンを時間遅延システムモデルの最適化に適用する。
  論文  参考訳（メタデータ） (2022-10-23T22:21:10Z)
• Enhanced Opposition Differential Evolution Algorithm for Multimodal Optimization [0.2538209532048866]
  現実の問題は、本質的には複数の最適値からなるマルチモーダルである。 古典的な勾配に基づく手法は、目的関数が不連続あるいは微分不可能な最適化問題に対して失敗する。 我々は,MMOPを解くために,拡張オポポジション微分進化(EODE)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-23T16:18:27Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
  ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。 すべての予測と最適化アプローチのボトルネックに対処する。 非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T19:09:12Z)
• Stochastic Optimization Forests [60.523606291705214]
  標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。 概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
  論文  参考訳（メタデータ） (2020-08-17T16:56:06Z)
• First Steps Towards a Runtime Analysis When Starting With a Good Solution [8.34061303235504]
  現実的な応用では、ランダムな解よりも優れた解を推測することができる。 我々は、異なるアルゴリズムがより良い初期解と全く異なる程度に利益を得ることを示す。 このことは、進化的アルゴリズムが良い初期解をうまく活用していることがまだ見つからないことを示唆している。
  論文  参考訳（メタデータ） (2020-06-22T11:46:42Z)
• 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)

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

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