論文の概要: Towards Running Time Analysis of Interactive Multi-objective
Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2310.08384v2
- Date: Sun, 15 Oct 2023 08:25:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-17 10:29:52.570049
- Title: Towards Running Time Analysis of Interactive Multi-objective
Evolutionary Algorithms
- Title（参考訳）: 対話型多目的進化アルゴリズムの動作時間解析に向けて
- Authors: Tianhao Lu, Chao Bian, Chao Qian
- Abstract要約: 本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。
我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
- 参考スコア（独自算出の注目度）: 23.815981112784552
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms (EAs) are widely used for multi-objective
optimization due to their population-based nature. Traditional multi-objective
EAs (MOEAs) generate a large set of solutions to approximate the Pareto front,
leaving a decision maker (DM) with the task of selecting a preferred solution.
However, this process can be inefficient and time-consuming, especially when
there are many objectives or the subjective preferences of DM is known. To
address this issue, interactive MOEAs (iMOEAs) combine decision making into the
optimization process, i.e., update the population with the help of the DM. In
contrast to their wide applications, there has existed only two pieces of
theoretical works on iMOEAs, which only considered interactive variants of the
two simple single-objective algorithms, RLS and (1+1)-EA. This paper provides
the first running time analysis (the essential theoretical aspect of EAs) for
practical iMOEAs. Specifically, we prove that the expected running time of the
well-developed interactive NSGA-II (called R-NSGA-II) for solving the OneMinMax
and OneJumpZeroJump problems is $O(n \log n)$ and $O(n^k)$, respectively, which
are all asymptotically faster than the traditional NSGA-II. Meanwhile, we
present a variant of OneMinMax, and prove that R-NSGA-II can be exponentially
slower than NSGA-II. These results provide theoretical justification for the
effectiveness of iMOEAs while identifying situations where they may fail.
Experiments are also conducted to validate the theoretical results.
- Abstract（参考訳）: 進化的アルゴリズム(EA)は人口ベースの性質から多目的最適化に広く用いられている。
従来の多目的EA(MOEA)はパレートフロントを近似する大規模なソリューションを生成し、意思決定者(DM)が好むソリューションを選択するタスクを残している。
しかし、特に多くの目的やdmの主観的な好みが知られている場合、このプロセスは非効率で時間がかかります。
この問題を解決するために、対話型MOEA(iMOEA)は、決定を最適化プロセス、すなわちDMの助けを借りて人口を更新する。
広義の応用とは対照的に、iMOEAに関する理論的な研究は2つしか存在せず、2つの単純な単目的アルゴリズム RLS と (1+1)-EA の対話的変種しか考慮していない。
本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。
具体的には、OneMinMax と OneJumpZeroJump の問題を解くためのよく発達した対話型 NSGA-II (R-NSGA-II) のランニング時間は、それぞれ$O(n \log n)$ と $O(n^k)$ であり、従来の NSGA-II よりも漸近的に高速であることを示す。
一方、OneMinMaxの変種を示し、R-NSGA-IIがNSGA-IIよりも指数関数的に遅いことを証明した。
これらの結果は、iMOEAの有効性を理論的に正当化し、失敗する可能性のある状況を特定する。
理論的結果を検証する実験も行われている。
関連論文リスト
- EPS-MoE: Expert Pipeline Scheduler for Cost-Efficient MoE Inference [49.94169109038806]
本稿では,新しいパイプラインスケジューラであるEPS-MoEを紹介する。
その結果,既存の並列推論手法に比べて,プリフィルスループットが平均21%向上していることが判明した。
論文 参考訳（メタデータ） (2024-10-16T05:17:49Z) - LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
このフレームワークはMonte Carlo Tree Search (MCTS)と反復的なSelf-Refineを組み合わせて推論パスを最適化する。
このフレームワークは、一般的なベンチマークと高度なベンチマークでテストされており、探索効率と問題解決能力の点で優れた性能を示している。
論文 参考訳（メタデータ） (2024-10-03T18:12:29Z) - Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。
WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
論文 参考訳（メタデータ） (2024-07-18T02:46:06Z) - Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis [3.748255320979002]
一般的な進化的多目的アルゴリズム(EMO)は、単純な(G)SEMOアルゴリズムと同じ性能を保証する。
我々は、GSEMOがOneTrapZeroTrapを最適化するために少なくとも$nn$のフィットネス評価を必要とするのに対し、一般的なEMOアルゴリズムNSGA-II、NSGA-III、SMS-EMOAは、ジェノタイプ重複を避けるための軽度な多様性メカニズムで拡張されているが、期待されるフィットネス評価は$O(n log n)$である。
論文 参考訳（メタデータ） (2024-05-22T12:09:00Z) - Many-Objective Evolutionary Influence Maximization: Balancing Spread, Budget, Fairness, and Time [3.195234044113248]
インフルエンス・最大化(IM)問題は、情報伝達を最大限に広めることのできるグラフ内のノードの集合を見つけ出そうとする。
この問題はNPハードであることが知られており、通常は第2の目的を最適化する影響(スプレッド)を最大化して研究される。
本研究では,シードセットサイズの影響と最小化に基づいて,予算の公平性,コミュニティ,時間といったIM固有の目的関数を最適化した最初のケーススタディを提案する。
論文 参考訳（メタデータ） (2024-03-27T16:54:45Z) - Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives [16.904475483445452]
NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
NSGA-IIは多数の目的に対して効果が低いことを示す。
論文 参考訳（メタデータ） (2022-11-23T16:15:26Z) - Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II
(NSGA-II) using Binary or Stochastic Tournament Selection [27.270523212333018]
本稿では,LOTZ,OneMinMax,COCZを解くための標準NSGA-IIのランニング時間解析について述べる。
具体的には、LOTZが$O(n3)$、OneMinMaxとCOCZが$O(n2log n)$であることを示す。
また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
論文 参考訳（メタデータ） (2022-03-22T09:10:50Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z) - Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
本稿では、MoHAEAと呼ばれるハイブリッド適応進化アルゴリズム(HAEA)の拡張として、新しい多目的アルゴリズムを提案する。
MoHAEAは、MOEA/D、pa$lambda$-MOEA/D、MOEA/D-AWA、NSGA-IIの4つの状態と比較される。
論文 参考訳（メタデータ） (2020-04-29T02:16:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。