論文の概要: An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2406.02118v1
- Date: Tue, 4 Jun 2024 08:59:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-05 17:11:25.879244
- Title: An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms
- Title（参考訳）: 多目的進化アルゴリズムにおける確率的スピードアップを実現するアーカイブ
- Authors: Chao Bian, Shengjie Ren, Miqing Li, Chao Qian,
- Abstract要約: アーカイブを使うことでMOEAのスピードアップを保証できることを示す。
2つの確立されたMOEAに対して、アーカイブを使用することで、期待される実行時間に加速がもたらされることを示す。
- 参考スコア（独自算出の注目度）: 22.123838452178585
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the area of multi-objective evolutionary algorithms (MOEAs), there is a trend of using an archive to store non-dominated solutions generated during the search. This is because 1) MOEAs may easily end up with the final population containing inferior solutions that are dominated by other solutions discarded during the search process and 2) the population that has a commensurable size of the problem's Pareto front is often not practical. In this paper, we theoretically show, for the first time, that using an archive can guarantee speed-ups for MOEAs. Specifically, we prove that for two well-established MOEAs (NSGA-II and SMS-EMOA) on two commonly studied problems (OneMinMax and LeadingOnesTrailingZeroes), using an archive brings a polynomial acceleration on the expected running time. The reason is that with an archive, the size of the population can reduce to a small constant; there is no need for the population to keep all the Pareto optimal solutions found. This contrasts existing theoretical studies for MOEAs where a population with a commensurable size of the problem's Pareto front is needed. The findings in this paper not only provide a theoretical confirmation for an increasingly popular practice in the design of MOEAs, but can also be beneficial to the theory community towards studying more practical MOEAs.
- Abstract（参考訳）: 多目的進化アルゴリズム(MOEA)の分野では、検索中に生成した非支配的なソリューションをアーカイブで保存する傾向にある。
これは
1)MOEAは,探索過程で廃棄された他の解に支配される劣る解を含む最終集団に容易に到達することができる。
2) 課題のパレートフロントの大きさのコンメンサブルな人口は実用的ではないことが多い。
本稿では,まず,MOEAの高速化を保証できることを示す。
具体的には、一般的に研究されている2つの問題(OneMinMaxとLeadingOnesTrailingZeroes)に対して、2つの確立されたMOEA(NSGA-IIとSMS-EMOA)に対して、アーカイブを使用することで、期待される実行時間に多項式加速度をもたらすことを証明している。
理由は、アーカイブでは人口の規模が小さな一定に減少し、パレートの最適解を全て発見する必要はないからである。
これは既存のMOEAの理論的研究とは対照的である。
本報告は,MOEAの設計において広く普及している実践の理論的確証を提供するだけでなく,より実践的なMOEAの研究において理論コミュニティにとって有益であることを示すものである。
関連論文リスト
- Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem [9.044970217182117]
NSGA-IIは最も顕著な多目的進化アルゴリズムである。
NSGA-IIは指数時間以下ではパレートフロントを計算できないことを示す。
論文 参考訳（メタデータ） (2024-11-15T07:50:40Z) - Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。
本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文 参考訳（メタデータ） (2024-01-19T07:40:24Z) - Towards Running Time Analysis of Interactive Multi-objective
Evolutionary Algorithms [23.815981112784552]
本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。
我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
論文 参考訳（メタデータ） (2023-10-12T14:57:47Z) - Endogenous Macrodynamics in Algorithmic Recourse [52.87956177581998]
対実説明(CE)とアルゴリズム・リコース(AR)に関する既存の研究は、静的環境における個人に主に焦点を当ててきた。
既存の方法論の多くは、一般化されたフレームワークによってまとめて記述できることを示す。
次に、既存のフレームワークは、グループレベルでの言論の内在的ダイナミクスを研究する際にのみ明らかとなるような、隠された対外的関係のコストを考慮に入れていないと論じる。
論文 参考訳（メタデータ） (2023-08-16T07:36:58Z) - Stochastic Population Update Can Provably Be Helpful in Multi-Objective
Evolutionary Algorithms [25.397640314100144]
人口更新は多目的進化アルゴリズムの鍵となるコンポーネントである。
人口の更新はMOEAの探索に有用であることを示す。
論文 参考訳（メタデータ） (2023-06-05T05:54:56Z) - MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with
Known Pareto Front [71.19090689055054]
多目的AI計画では、既知のPareto Frontsを示すベンチマークが不足している。
提案するベンチマーク生成器と専用ソルバは、結果のインスタンスの真のParetoを確実に計算する。
本稿では,制約された問題に対して最適な計画を示すとともに,制約された問題に対する一般的な問題を減らす方法を示す。
論文 参考訳（メタデータ） (2023-04-28T07:09:23Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
マルチオブジェクトパスプランナーは通常、パスの長さなどの単一の目的を最適化しながら、パスのアンサンブルを計算します。
本稿では、マルチオブジェクトコンフリクトベース検索(MO-CBS)という、いわゆる次元の呪いをバイパスする手法を紹介します。
論文 参考訳（メタデータ） (2021-01-11T10:42:38Z) - Geometric Entropic Exploration [52.67987687712534]
離散領域と連続領域の両方における状態ビジットの幾何認識シャノンエントロピーを最大化する新しいアルゴリズムを導入する。
私たちの重要な理論的貢献は、単純で新しいノイズコントラストの客観的関数を最適化する牽引可能な問題としてジオメトリ認識MSVE探索を鋳造することです。
実験では,他の深部RL探査手法と比較して,疎度な報酬を伴う複数のRL問題の解法におけるGEMの効率性を示した。
論文 参考訳（メタデータ） (2021-01-06T14:15:07Z) - Theory-Inspired Path-Regularized Differential Network Architecture
Search [206.93821077400733]
差分アーキテクチャサーチ(DARTS)における高速ネットワーク最適化に対するスキップ接続の影響と,他のタイプの操作に対する競争上の優位性について検討する。
i)操作間の不当競争を避けるために各操作に導入された差分群構造スパース二乗ゲートと,(ii)浅部より収束する深部アーキテクチャの探索を誘導するために用いられる経路深度正規化の2つの主要なモジュールからなる理論に着想を得た経路規則化DARTSを提案する。
論文 参考訳（メタデータ） (2020-06-30T05:28:23Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。