論文の概要: Runtime Analysis of Evolutionary Algorithms for Multiparty Multiobjective Optimization
- arxiv url: http://arxiv.org/abs/2501.16336v1
- Date: Thu, 09 Jan 2025 13:16:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-02 08:51:06.749605
- Title: Runtime Analysis of Evolutionary Algorithms for Multiparty Multiobjective Optimization
- Title（参考訳）: 多目的多目的最適化のための進化的アルゴリズムの実行時解析
- Authors: Yuetong Sun, Peilan Xu, Wenjian Luo,
- Abstract要約: 本稿では、双方向多目的最適化問題(BPMOP)における進化的アルゴリズムの予測ランタイムに関する最初の理論的解析について述べる。
その結果,MPMOPを解くために従来の多目的最適化アルゴリズムを用いることは,時間を要することと非効率であることがわかった。
擬ブール最適化のための共進化型多目的多目的言語(CoEMPMO)を提案する。
- 参考スコア（独自算出の注目度）: 0.8520624117635325
- License:
- Abstract: In scenarios where multiple decision-makers operate within a common decision space, each focusing on their own multi-objective optimization problem (e.g., bargaining games), the problem can be modeled as a multi-party multi-objective optimization problem (MPMOP). While numerous evolutionary algorithms have been proposed to solve MPMOPs, most results remain empirical. This paper presents the first theoretical analysis of the expected runtime of evolutionary algorithms on bi-party multi-objective optimization problems (BPMOPs). Our findings demonstrate that employing traditional multi-objective optimization algorithms to solve MPMOPs is both time-consuming and inefficient, as the resulting population contains many solutions that fail to achieve consensus among decision-makers. An alternative approach involves decision-makers individually solving their respective optimization problems and seeking consensus only in the final stage. While feasible for pseudo-Boolean optimization problems, this method may fail to guarantee approximate performance for one party in NP-hard problems. Finally, We propose coevolutionary multi-party multi-objective optimizers (CoEMPMO) for pseudo-Boolean optimization and shortest path problems within a multi-party multi-objective context, which maintains a common solution set among all parties through coevolution. Theoretical and experimental results demonstrate that the proposed \( \text{CoEMPMO}_{\text{random}} \) outperforms previous algorithms in terms of the expected lower bound on runtime for pseudo-Boolean optimization problems. Additionally, \( \text{CoEMPMO}_{\text{cons}}^{\text{SP}} \) achieves better efficiency and precision in solving shortest path problems compared to existing algorithms.
- Abstract（参考訳）: 複数の意思決定者が共通の決定空間内で機能するシナリオでは、それぞれが独自の多目的最適化問題(例えば、バーゲティングゲーム)に焦点を当て、その問題を多人数多目的最適化問題(MPMOP)としてモデル化することができる。
MPMOPを解くために多くの進化的アルゴリズムが提案されているが、ほとんどの結果は実証的なままである。
本稿では、双方向多目的最適化問題(BPMOPs)における進化的アルゴリズムのランタイムに関する最初の理論的解析について述べる。
以上の結果から,MPMOPを解くために従来の多目的最適化アルゴリズムを用いることは,意思決定者間でのコンセンサスを達成できないソリューションが多数存在するため,時間と効率の両立が困難であることが示唆された。
別のアプローチでは、意思決定者がそれぞれの最適化問題を個別に解決し、最終段階でのみコンセンサスを求める。
擬似ブール最適化問題に対して実現可能であるが、NPハード問題において、この手法は一方の当事者の近似性能を保証するのに失敗する可能性がある。
最後に,擬似ブール最適化のための共進化多目的最適化(CoEMPMO)を提案する。
理論的および実験的結果は、提案された \( \text{CoEMPMO}_{\text{random}} \) が、擬ブール最適化問題に対する実行時の期待下限の観点から、以前のアルゴリズムより優れていることを示している。
さらに、( \text{CoEMPMO}_{\text{cons}}^{\text{SP}} \) は、既存のアルゴリズムと比較して、最短経路問題の解法において、より良い効率と精度を達成する。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - Combining Kernelized Autoencoding and Centroid Prediction for Dynamic
Multi-objective Optimization [3.431120541553662]
本稿では,カーネル化された自己コード進化探索と遠近法に基づく予測を組み合わせた統一パラダイムを提案する。
提案手法は,多くの複雑なベンチマーク問題に対して,最先端の5つのアルゴリズムと比較する。
論文 参考訳（メタデータ） (2023-12-02T00:24:22Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳（メタデータ） (2023-01-28T01:50:42Z) - 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) - A survey on multi-objective hyperparameter optimization algorithms for
Machine Learning [62.997667081978825]
本稿では,多目的HPOアルゴリズムに関する2014年から2020年にかけての文献を体系的に調査する。
メタヒューリスティック・ベース・アルゴリズムとメタモデル・ベース・アルゴリズム,および両者を混合したアプローチを区別する。
また,多目的HPO法と今後の研究方向性を比較するための品質指標についても論じる。
論文 参考訳（メタデータ） (2021-11-23T10:22:30Z) - A novel multiobjective evolutionary algorithm based on decomposition and
multi-reference points strategy [14.102326122777475]
分解に基づく多目的進化アルゴリズム(MOEA/D)は、多目的最適化問題(MOP)を解く上で、極めて有望なアプローチであると考えられている。
本稿では,よく知られたPascoletti-Serafiniスキャラライゼーション法とマルチ参照ポイントの新たな戦略により,MOEA/Dアルゴリズムの改良を提案する。
論文 参考訳（メタデータ） (2021-10-27T02:07:08Z) - Batched Data-Driven Evolutionary Multi-Objective Optimization Based on
Manifold Interpolation [6.560512252982714]
バッチ化されたデータ駆動型進化的多目的最適化を実現するためのフレームワークを提案する。
オフザシェルフ進化的多目的最適化アルゴリズムがプラグイン方式で適用できるのは、非常に一般的である。
提案するフレームワークは, より高速な収束と各種PF形状に対する強いレジリエンスを特徴とする。
論文 参考訳（メタデータ） (2021-09-12T23:54:26Z) - A Decomposition-based Large-scale Multi-modal Multi-objective
Optimization Algorithm [9.584279193016522]
広範に使われているMOEA/Dアルゴリズムに基づく効率的なマルチモーダル多目的最適化アルゴリズムを提案する。
実験の結果,提案アルゴリズムは決定空間における解の多様性を効果的に維持できることが示された。
論文 参考訳（メタデータ） (2020-04-21T09:18:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。