論文の概要: MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning
to Sparsify
- arxiv url: http://arxiv.org/abs/2403.02482v1
- Date: Mon, 4 Mar 2024 21:04:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-06 16:59:36.933426
- Title: MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning
to Sparsify
- Title(参考訳): MORBDD: スパーシフィケーションの学習による多目的限定2値決定図
- Authors: Rahul Patel, Elias B. Khalil, David Bergman
- Abstract要約: まず、問題に対するすべての実行可能なソリューションを表すグラフを構築するバイナリ意思決定図(BDD)に注目します。
機械学習(ML)を用いて、制限されたBDDが多目的最適化にどのように適応できるかを検討する。
MorBDDは、非常に小さな制限されたBDDを、優れた近似品質で、幅制限の制限されたBDDよりも優れ、よく知られた進化的アルゴリズムNSGA-IIを作るのに非常に効果的です。
- 参考スコア(独自算出の注目度): 19.821484909092913
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In multicriteria decision-making, a user seeks a set of non-dominated
solutions to a (constrained) multiobjective optimization problem, the so-called
Pareto frontier. In this work, we seek to bring a state-of-the-art method for
exact multiobjective integer linear programming into the heuristic realm. We
focus on binary decision diagrams (BDDs) which first construct a graph that
represents all feasible solutions to the problem and then traverse the graph to
extract the Pareto frontier. Because the Pareto frontier may be exponentially
large, enumerating it over the BDD can be time-consuming. We explore how
restricted BDDs, which have already been shown to be effective as heuristics
for single-objective problems, can be adapted to multiobjective optimization
through the use of machine learning (ML). MORBDD, our ML-based BDD sparsifier,
first trains a binary classifier to eliminate BDD nodes that are unlikely to
contribute to Pareto solutions, then post-processes the sparse BDD to ensure
its connectivity via optimization. Experimental results on multiobjective
knapsack problems show that MORBDD is highly effective at producing very small
restricted BDDs with excellent approximation quality, outperforming
width-limited restricted BDDs and the well-known evolutionary algorithm
NSGA-II.
- Abstract(参考訳): 多目的意思決定において、ユーザは(制約された)多目的最適化問題(pareto frontier)に対する非支配的な解の集合を求める。
本研究では,完全多目的整数線形プログラミングの最先端手法をヒューリスティック領域に導入することを目的とする。
まず、問題に対するすべての実現可能な解決策を表すグラフを構築し、次にグラフをトラバースしてparetoのフロンティアを抽出する。
Paretoフロンティアは指数関数的に大きいため、BDD上でそれを列挙するのは時間を要する可能性がある。
単目的問題に対するヒューリスティックとしてすでに有効であることが示されている制限されたBDDが、機械学習(ML)を使用して多目的最適化にどのように適応できるかを考察する。
MLベースのBDDスペーサーであるMORBDDは、まずバイナリ分類器をトレーニングして、ParetoソリューションにコントリビュートしそうもないBDDノードを排除します。
多目的クナップサック問題に対する実験結果から、MORBDDは、近似品質に優れた、幅制限の制限されたBDDとよく知られた進化アルゴリズムNSGA-IIの非常に小さな制限されたBDDを生成するのに非常に効果的であることが示された。
関連論文リスト
- LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding
Linear Bandit Problem [4.666048091337632]
本稿では、Thresholding Linear Bandit(TLB)問題の固定予算設定のために設計された新しいアルゴリズムであるLinearAPTを提案する。
コントリビューションでは、LinearAPTの適応性、単純性、計算効率を強調しており、複雑なシーケンシャルな意思決定課題に対処するためのツールキットとして貴重なものとなっている。
論文 参考訳(メタデータ) (2024-03-10T15:01:50Z) - Learning Constrained Optimization with Deep Augmented Lagrangian Methods [60.94111369773497]
機械学習(ML)モデルは、制約付き最適化ソルバをエミュレートするために訓練される。
本稿では,MLモデルを用いて2つの解推定を直接予測する手法を提案する。
これにより、双対目的が損失関数であるエンドツーエンドのトレーニングスキームと、双対上昇法をエミュレートした原始的実現可能性への解推定を可能にする。
論文 参考訳(メタデータ) (2024-03-06T04:43:22Z) - Double-Bounded Optimal Transport for Advanced Clustering and
Classification [58.237576976486544]
本稿では,2つの境界内での目標分布の制限を前提としたDB-OT(Douubly bounded Optimal Transport)を提案する。
提案手法は,テスト段階における改良された推論方式により,良好な結果が得られることを示す。
論文 参考訳(メタデータ) (2024-01-21T07:43:01Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳(メタデータ) (2023-07-05T13:52:10Z) - BOtied: Multi-objective Bayesian optimization with tied multivariate
ranks [49.85896045032822]
非支配解と最高多変量階との自然な関係を示し、これは合同累積分布関数(CDF)の最外層線と一致する。
我々はCDFインジケータに基づくBOtiedと呼ばれる取得関数を提案する。
論文 参考訳(メタデータ) (2023-06-01T04:50:06Z) - Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees
with Continuous Features [5.663538370244174]
本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。
提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
論文 参考訳(メタデータ) (2022-06-23T17:19:29Z) - Meta-Learning Adversarial Bandits [49.094361442409785]
本研究の目的は,複数のタスクにまたがる帯域幅フィードバックを用いてオンライン学習を学習し,タスク間の平均性能を改善することである。
敵対的設定を最初に対象とするメタアルゴリズムとして,マルチアーム・バンディット(MAB)とバンディット・最適化(BLO)の2つの重要なケースに対して,特定の保証を設定するメタアルゴリズムを設計する。
我々の保証は、非正規化されたフォローザリーダーと乗法重みを組み合わせることで、オンラインで非滑らかで非Bシーケンスを学ぶのに十分であることを示すことに依存しています。
論文 参考訳(メタデータ) (2022-05-27T17:40:32Z) - Optimizing Binary Decision Diagrams with MaxSAT for classification [3.2894524838755608]
説明可能な人工知能への関心の高まりは、解釈可能な機械学習(ML)モデルの必要性を動機付けている。
近年、従来の手法の弱点を克服するために、そのようなモデルを計算するためのいくつかの正確な方法が提案されている。
本稿ではまず,最適なバイナリ決定図(BDD)を学習するためのSATモデルを提案する。
次に、符号化をMaxSATモデルに上げ、限られた深さで最適なBDDを学習します。
最後に、MaxSATモデルを介して見つけたBDDの互換性のあるサブツリーをマージする手法を導入することにより、フラグメンテーションの問題に取り組む。
論文 参考訳(メタデータ) (2022-03-21T23:17:37Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
アルゴリズムのような多目的A* (MOA*) は、そのノードに到達した非支配パスを追跡するために、検索中に任意のノードに「フロンティア」セットを保持する。
バランスの取れた二分探索木を利用して,これらのフロンティアを多目的に効率的に維持する手法を提案する。
論文 参考訳(メタデータ) (2022-02-18T02:54:58Z) - Improving the filtering of Branch-And-Bound MDD solver (extended) [11.728147523456702]
本稿では,多値決定図(MDD)に基づく制約最適化解法の効率向上のための2つのプルーニング手法を提案し,評価する。
Bergmanらによって提案されたブランチ・アンド・バウンド・フレームワークを採用している。
2016年、動的プログラムを最適に解く。
論文 参考訳(メタデータ) (2021-04-24T13:42:42Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳(メタデータ) (2021-04-14T09:22:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。