論文の概要: 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の有効性を理論的に正当化し、失敗する可能性のある状況を特定する。
理論的結果を検証する実験も行われている。
関連論文リスト
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [16.904475483445452]
本稿では,多目的最適化のためのSMS-EMOAの厳密な実行時解析を行う。
まず,二目的OJZJベンチマークの m-目的 mOJZJ 問題である多目的 mOJZJ 問題を提案する。
SMS-EMOAは、このベンチマークの全前面を、期待される数$O(M2 nk)$で計算する。
論文 参考訳(メタデータ) (2023-12-16T02:23:09Z) - 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) - A Simple Evolutionary Algorithm for Multi-modal Multi-objective
Optimization [0.0]
マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。
本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
論文 参考訳(メタデータ) (2022-01-18T03:31:11Z) - RoMA: Robust Model Adaptation for Offline Model-based Optimization [115.02677045518692]
入力出力クエリの静的データセットからブラックボックス目的関数を最大化する入力を探索する問題を考える。
この問題を解決するための一般的なアプローチは、真の客観的関数を近似するプロキシモデルを維持することである。
ここでの大きな課題は、検索中に逆最適化された入力を避ける方法である。
論文 参考訳(メタデータ) (2021-10-27T05:37:12Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳(メタデータ) (2021-10-18T14:00:22Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳(メタデータ) (2021-07-08T18:01:02Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳(メタデータ) (2020-06-15T02:57:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。