論文の概要: DiversiTree: Computing Diverse Sets of Near-Optimal Solutions to
Mixed-Integer Optimization Problems
- arxiv url: http://arxiv.org/abs/2204.03822v1
- Date: Fri, 8 Apr 2022 03:11:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-11 14:04:43.936446
- Title: DiversiTree: Computing Diverse Sets of Near-Optimal Solutions to
Mixed-Integer Optimization Problems
- Title(参考訳): DiversiTree: 混合整数最適化問題に対する準最適解の多元計算
- Authors: Izuwa Ahanor, Hugh Medal, Andrew C. Trapp
- Abstract要約: 本稿では,準最適解探索における多様性を強調することで,多様な解の集合を見つける方法を提案する。
その結果,本手法は最終解集合の多様性を著しく向上させることが示唆された。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While most methods for solving mixed-integer optimization problems seek a
single optimal solution, finding a diverse set of near-optimal solutions can
often be more useful. State of the art methods for generating diverse
near-optimal solutions usually take a two-phase approach, first finding a set
of near-optimal solutions and then finding a diverse subset. In contrast, we
present a method of finding a set of diverse solutions by emphasizing diversity
within the search for near-optimal solutions. Specifically, within a
branch-and-bound framework, we investigate parameterized node selection rules
that explicitly consider diversity. Our results indicate that our approach
significantly increases diversity of the final solution set. When compared with
existing methods for finding diverse near-optimal sets, our method runs with
similar run-time as regular node selection methods and gives a diversity
improvement of up to 140%. In contrast, popular node selection rules such as
best-first search gives an improvement of no more than 40%. Further, we find
that our method is most effective when diversity is emphasized more in node
selection when deeper in the tree and when the solution set has grown large
enough.
- Abstract(参考訳): 混合整数最適化問題を解くほとんどの方法は単一の最適解を求めるが、近似最適解の多様な集合を見つけることはより有用である。
多様な準最適解を生成するための最先端の手法は、通常二相アプローチを採り、まずは準最適解の集合を見つけ、次に多様な部分集合を見つける。
対照的に,準最適解探索における多様性を強調し,多様な解の集合を求める手法を提案する。
具体的には、分岐とバウンドのフレームワークにおいて、多様性を明示的に考慮するパラメータ化ノード選択ルールについて検討する。
その結果,本手法は最終解集合の多様性を著しく向上させることが示唆された。
提案手法は,既存手法と比較すると,通常のノード選択法と同じような実行時間で動作し,最大140%の多様性向上を実現している。
対照的に、best-first searchのような人気のあるノード選択ルールは40%未満の改善をもたらす。
さらに,本手法は,木深くではノード選択に多様性が強調され,解集合が十分に大きくなった場合にも有効であることがわかった。
関連論文リスト
- Rigorous Runtime Analysis of Diversity Optimization with GSEMO on
OneMinMax [13.026567958569965]
両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。
問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。
目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
論文 参考訳(メタデータ) (2023-07-14T09:43:29Z) - Optimizer Amalgamation [124.33523126363728]
私たちは、Amalgamationという新しい問題の研究を動機付けています。"Teacher"アマルガメーションのプールを、より強力な問題固有のパフォーマンスを持つ単一の"学生"にどのように組み合わせるべきなのでしょうか?
まず、勾配降下による解析のプールをアマルガメートする3つの異なるメカニズムを定義する。
また, プロセスの分散を低減するため, 目標を摂動させることでプロセスの安定化を図る。
論文 参考訳(メタデータ) (2022-03-12T16:07:57Z) - How to Fill the Optimum Set? Population Gradient Descent with Harmless
Diversity [34.790747999729284]
主損失関数の最適セット内における多様性スコアを最大化する二段階最適化問題を提案する。
提案手法は,テキスト・ツー・イメージ生成,テキスト・ツー・メッシュ生成,分子コンフォーメーション生成,アンサンブルニューラルネットワークトレーニングなど,さまざまなアプリケーション上で,多様なソリューションを効率的に生成できることを示す。
論文 参考訳(メタデータ) (2022-02-16T23:40:18Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。
代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。
データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
論文 参考訳(メタデータ) (2021-12-06T20:34:55Z) - An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
マルチモーダル最適化は高い適合性ソリューションを生み出し、品質の多様性は遺伝的中立性に敏感ではない。
オートエンコーダは表現型特徴を自動的に発見するために使用され、品質の多様性を備えたさらに多様なソリューションセットを生成する。
論文 参考訳(メタデータ) (2021-05-10T10:39:03Z) - Computing Diverse Sets of Solutions for Monotone Submodular Optimisation
Problems [13.026567958569965]
本稿では,サブモジュール最適化問題に対する多種多様な高品質解集合の計算手法を提案する。
まず, エントロピーによって測定された多様性について, グリーディサンプリング手法の多様化と解析を行った。
次に、進化的多様性最適化手法を導入し、解の集合の多様性をさらに改善する。
論文 参考訳(メタデータ) (2020-10-22T07:11:34Z) - Stochastic Optimization Forests [60.523606291705214]
標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。
概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
論文 参考訳(メタデータ) (2020-08-17T16:56:06Z) - Solution Subset Selection for Final Decision Making in Evolutionary
Multi-Objective Optimization [7.745468825770201]
最終的な意思決定の観点から,サブセットの選択について論じる。
定式化関数はIGD+インジケータと同じであることを示す。
論文 参考訳(メタデータ) (2020-06-15T06:26:58Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳(メタデータ) (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。