論文の概要: Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees

• arxiv url: http://arxiv.org/abs/2110.09332v1
• Date: Mon, 18 Oct 2021 14:00:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-19 21:29:39.399107
• Title: Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees
• Title（参考訳）: 理論的保証付き多目的進化アルゴリズムによる結果の多様化
• Authors: Chao Qian, Dan-Xuan Liu, Zhi-Hua Zhou
• Abstract要約: 両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
• 参考スコア（独自算出の注目度）: 94.72461292387146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a ground set of items, the result diversification problem aims to select a subset with high "quality" and "diversity" while satisfying some constraints. It arises in various real-world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi-objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, $1/2$. For more general matroid constraints, the GSEMO can achieve the asymptotically optimal polynomial-time approximation ratio, $1/2-\epsilon/(4n)$. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by Borodin et al. This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the state-of-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments.
• Abstract（参考訳）: 結果の多様化問題は、いくつかの制約を満たすとともに、高い「品質」と「多様性」のサブセットを選択することを目的としている。 ウェブベースの検索、文書要約、特徴選択など、様々な現実世界の人工知能アプリケーションに現れ、計算幾何学、データベース、ファイナンス、オペレーション研究など他の分野にも応用されている。 従来のアルゴリズムは主に欲求や局所探索に基づいている。 本稿では,二目的最大化問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA),すなわちGSEMOを用いて解くことを提案する。 我々はGSEMOが静的環境と動的環境の両方において(漸近的に)最適な理論的保証を達成できることを理論的に証明する。 濃度制約に対して、GSEMO は最適多項式時間近似比 1/2$ を達成することができる。 より一般的なマットロイドの制約に対して、GSEMO は漸近的に最適な多項式時間近似比 1/2-\epsilon/(4n)$ を達成することができる。 さらに、目的関数(すなわち品質と多様性の線形結合)が動的に変化するとき、GSEMOはこの近似比を多項式実行時間で維持することができ、ボロディンらによって提案された開問題に対処することができる。 これはまた、局所探索による動的最適化問題の解法よりもEAの優位性を示し、EAの突然変異演算子の動的変化に対する堅牢性を明らかにする。 web-based search, multi-label feature selection, document summarizationの応用実験では,静的および動的環境下でのgsemoの性能が最先端のアルゴリズム(すなわちgreedyアルゴリズムとローカル検索)よりも優れていることが示されている。

関連論文リスト

• Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
  進化的多様性最適化(EDO)を3つの対象関数 LOTZ$_k$ 上で証明する。 GSEMOが全てのパレート最適解の集合を$O(kn3)$期待反復で計算することを示す。 両多様性尺度に非常によく似た振る舞いを示す実証的な研究で、我々の理論分析を補完する。
  論文  参考訳（メタデータ） (2024-04-17T15:51:15Z)
• Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax [13.026567958569965]
  両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。 問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。 目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
  論文  参考訳（メタデータ） (2023-07-14T09:43:29Z)
• Multi-Objective GFlowNets [59.16787189214784]
  本稿では,多目的最適化の文脈において,多様な候補を生成する問題について検討する。 薬物発見やマテリアルデザインといった機械学習の多くの応用において、目標は、競合する可能性のある目標のセットを同時に最適化する候補を生成することである。 GFlowNetsをベースとした多目的GFlowNets(MOGFNs)を提案する。
  論文  参考訳（メタデータ） (2022-10-23T16:15:36Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  エネルギーシステムの最適化問題は、強い非線形系の挙動と複数の競合する目的のために複雑である。 場合によっては、提案された最適解は、物理的性質や安全クリティカルな操作条件に関連する明示的な入力制約に従う必要がある。 本稿では,ブラックボックス問題に対する制約付き多目的最適化のためのツリーアンサンブルを用いた新しいデータ駆動戦略を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:18:55Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。 我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。 我々は2つの異なる社会問題に対してアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2021-07-07T03:57:22Z)
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
  ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。 GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。 実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
  論文  参考訳（メタデータ） (2020-06-20T00:17:44Z)
• 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)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。