論文の概要: 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%未満の改善をもたらす。
さらに,本手法は,木深くではノード選択に多様性が強調され,解集合が十分に大きくなった場合にも有効であることがわかった。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳(メタデータ) (2024-11-04T15:17:19Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳(メタデータ) (2024-06-21T05:57:08Z) - Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization [14.355588194787073]
多目的最適化は、競合する目的を1つのソリューションで最適化できない現実の多くのアプリケーションで見られる。
本稿では,多数の目的をカバーできるいくつかの代表解を見つけるために,新しいTchebycheff集合スカラー化法を提案する。
このようにして、それぞれの目的は、小さな解集合の少なくとも1つの解によってうまく対応できる。
論文 参考訳(メタデータ) (2024-05-30T03:04:57Z) - 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) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。