論文の概要: Not Just for Archiving: Provable Benefits of Reusing the Archive in Evolutionary Multi-objective Optimization
- arxiv url: http://arxiv.org/abs/2508.16993v1
- Date: Sat, 23 Aug 2025 11:25:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-26 18:43:45.290171
- Title: Not Just for Archiving: Provable Benefits of Reusing the Archive in Evolutionary Multi-objective Optimization
- Title（参考訳）: アーカイブに限らず:進化的多目的最適化におけるアーカイブの再利用のメリット
- Authors: Shengjie Ren, Zimin Liang, Miqing Li, Chao Qian,
- Abstract要約: 我々は,新たなソリューション生成の過程において,MOEAを再利用することで,アーカイブをさらに支援できることを解析的に示す。
本分析は、よく研究されているOneJumpZeroJump問題に適用されたSMS-EMOAに焦点をあてる。
また, アーカイブ・ソリューションの再利用は, 人口規模を直接利用するよりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 19.269008655837535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary Algorithms (EAs) have become the most popular tool for solving widely-existed multi-objective optimization problems. In Multi-Objective EAs (MOEAs), there is increasing interest in using an archive to store non-dominated solutions generated during the search. This approach can 1) mitigate the effects of population oscillation, a common issue in many MOEAs, and 2) allow for the use of smaller, more practical population sizes. In this paper, we analytically show that the archive can even further help MOEAs through reusing its solutions during the process of new solution generation. We first prove that using a small population size alongside an archive (without incorporating archived solutions in the generation process) may fail on certain problems, as the population may remove previously discovered but promising solutions. We then prove that reusing archive solutions can overcome this limitation, resulting in at least a polynomial speedup on the expected running time. Our analysis focuses on the well-established SMS-EMOA algorithm applied to the commonly studied OneJumpZeroJump problem as well as one of its variants. We also show that reusing archive solutions can be better than using a large population size directly. Finally, we show that our theoretical findings can generally hold in practice by experiments on four well-known practical optimization problems -- multi-objective 0-1 Knapsack, TSP, QAP and NK-landscape problems -- with realistic settings.
- Abstract（参考訳）: 進化的アルゴリズム(EA)は、広く存在する多目的最適化問題を解くための最も一般的なツールとなっている。
マルチオブジェクトEA(MOEA)では,検索時に生成した非支配的なソリューションをアーカイブで保存することへの関心が高まっている。
このアプローチはできる
1)人口変動の影響を緩和し、多くのMOEAにおいて共通の課題となる。
2) より小型で実用性の高い個体群を使用できる。
本稿では,新たなソリューション生成の過程において,MOEAを再利用することで,アーカイブをさらに支援できることを解析的に示す。
我々はまず、アーカイブとともに小さな人口規模を(生成プロセスにアーカイブされたソリューションを組み込まないまま)利用することは、ある問題で失敗する可能性があることを証明した。
そして、アーカイブの再利用がこの制限を克服し、予想される実行時間に対して少なくとも多項式の高速化をもたらすことを証明した。
我々の分析は、よく研究されているOneJumpZeroJump問題に適用されたSMS-EMOAアルゴリズムと、その変種の一つに焦点を当てている。
また, アーカイブ・ソリューションの再利用は, 人口規模を直接利用するよりも優れていることを示す。
最後に,本研究の理論的知見は,現実的な設定で,多目的の0-1 Knapsack, TSP, QAP, NKランドスケープ問題という,よく知られた4つの実用的最適化問題の実験によって,一般的には成り立つことを示す。
関連論文リスト
- When to Truncate the Archive? On the Effect of the Truncation Frequency in Multi-Objective Optimisation [6.391724105255245]
興味深いことに、新しいソリューションが生成されるとアーカイブを停止させるのが最善である傾向があるのに対して、無制限のアーカイブを考えると、最悪の場合があります。
本結果は,効率的なサブセット選択手法の開発の重要性を強調した。
論文 参考訳（メタデータ） (2025-04-02T03:33:49Z) - Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization [20.883780207120783]
アーカイブを利用することで,少人数で SPU ベースのMOEA 検索が大幅に高速化できることを示す。
具体的には、よく研究されている二目的問題OneJumpZeroを解決するために、SMS-EMOAとNSGA-IIの2つの確立されたMOEAのランニング時間を分析する。
論文 参考訳（メタデータ） (2025-01-28T06:21:38Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Maintaining Diversity Provably Helps in Evolutionary Multimodal Optimization [20.621635722585502]
解空間における解の多様性を考慮に入れた簡単な方法が進化的アルゴリズム(EA)の探索に有効であることを示す。
提案手法は,クロスオーバーで作業することで探索の促進に寄与し,予測走行時間において,マルチモーダルあるいは指数加速度がもたらされることを実証する。
論文 参考訳（メタデータ） (2024-06-04T17:52:14Z) - An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms [22.123838452178585]
アーカイブを使うことでMOEAのスピードアップを保証できることを示す。
2つの確立されたMOEAに対して、アーカイブを使用することで、期待される実行時間に加速がもたらされることを示す。
論文 参考訳（メタデータ） (2024-06-04T08:59:16Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメトリした線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳（メタデータ） (2020-08-12T08:52:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。