論文の概要: LEO: Learning Efficient Orderings for Multiobjective Binary Decision
Diagrams
- arxiv url: http://arxiv.org/abs/2307.03171v1
- Date: Thu, 6 Jul 2023 17:52:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-07 12:55:43.489873
- Title: LEO: Learning Efficient Orderings for Multiobjective Binary Decision
Diagrams
- Title（参考訳）: LEO:多目的2値決定図のための効率的な順序付け学習
- Authors: Rahul Patel, Elias B. Khalil
- Abstract要約: 変数の順序付けは、緩和あるいは制限されたBDDから派生した境界の大きさや品質に大きな影響を与える可能性があることを示す。
列挙時間を削減する効率的な変数順序付けを見つけるための教師付き学習手法を提案する。
実験により、LEOは一般的な順序付け戦略やアルゴリズム構成よりも30～300%、PF列挙では10～200%高速であることが示されている。
- 参考スコア（独自算出の注目度）: 4.702456193042534
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Approaches based on Binary decision diagrams (BDDs) have recently achieved
state-of-the-art results for multiobjective integer programming problems. The
variable ordering used in constructing BDDs can have a significant impact on
their size and on the quality of bounds derived from relaxed or restricted BDDs
for single-objective optimization problems. We first showcase a similar impact
of variable ordering on the Pareto frontier (PF) enumeration time for the
multiobjective knapsack problem, suggesting the need for deriving variable
ordering methods that improve the scalability of the multiobjective BDD
approach. To that end, we derive a novel parameter configuration space based on
variable scoring functions which are linear in a small set of interpretable and
easy-to-compute variable features. We show how the configuration space can be
efficiently explored using black-box optimization, circumventing the curse of
dimensionality (in the number of variables and objectives), and finding good
orderings that reduce the PF enumeration time. However, black-box optimization
approaches incur a computational overhead that outweighs the reduction in time
due to good variable ordering. To alleviate this issue, we propose LEO, a
supervised learning approach for finding efficient variable orderings that
reduce the enumeration time. Experiments on benchmark sets from the knapsack
problem with 3-7 objectives and up to 80 variables show that LEO is ~30-300%
and ~10-200% faster at PF enumeration than common ordering strategies and
algorithm configuration. Our code and instances are available at
https://github.com/khalil-research/leo.
- Abstract（参考訳）: 双対決定図(BDD)に基づくアプローチは、最近、多目的整数プログラミング問題に対する最先端の結果を得た。
BDDの構築に使用される変数の順序付けは、そのサイズや、単一目的の最適化問題に対する緩和あるいは制限されたBDDから派生したバウンダリの品質に大きな影響を与える可能性がある。
我々はまず,多目的ナップサック問題に対するpareto frontier(pf)列挙時間に対する変数順序付けの類似性を示し,多目的bddアプローチのスケーラビリティを向上させる変数順序付けメソッドの導出の必要性を示唆する。
そこで我々は,小さな解釈可能かつ容易に計算可能な変数特徴セットにおいて線形な変数スコアリング関数に基づいて,新しいパラメータ構成空間を導出する。
ブラックボックス最適化を用いて構成空間を効率的に探索し、次元の呪いを回避し(変数数と目的数)、PF列挙時間を短縮する優れた順序付けを見つける方法を示す。
しかし、ブラックボックス最適化アプローチは、良好な変数順序付けによる時間の削減よりも大きい計算オーバーヘッドを伴います。
この問題を軽減するために、列挙時間を削減する効率的な変数順序付けを見つけるための教師付き学習手法LEOを提案する。
クナプサック問題の3～7の目的と最大80の変数によるベンチマークセットの実験では、LEOは一般的な順序付け戦略やアルゴリズム構成よりも30～300%、PF列挙では10～200%高速であることが示されている。
私たちのコードとインスタンスはhttps://github.com/khalil-research/leoで利用可能です。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - MORBDD: Multiobjective Restricted Binary Decision Diagrams by Learning
to Sparsify [19.821484909092913]
まず、問題に対するすべての実行可能なソリューションを表すグラフを構築するバイナリ意思決定図(BDD)に注目します。
機械学習(ML)を用いて、制限されたBDDが多目的最適化にどのように適応できるかを検討する。
MorBDDは、非常に小さな制限されたBDDを、優れた近似品質で、幅制限の制限されたBDDよりも優れ、よく知られた進化的アルゴリズムNSGA-IIを作るのに非常に効果的です。
論文 参考訳（メタデータ） (2024-03-04T21:04:54Z) - A Computationally Efficient Sparsified Online Newton Method [48.78646010774149]
Sparsified Online Newton (SONew) はメモリ効率の良い2次アルゴリズムである。
最大で30%の高速化,3.4%の妥当性向上,80%のトレーニング損失の相対的改善を実現しています。
論文 参考訳（メタデータ） (2023-11-16T18:44:22Z) - Large-Batch, Iteration-Efficient Neural Bayesian Design Optimization [37.339567743948955]
本稿では,BOの限界に対処するための新しいベイズ最適化フレームワークを提案する。
我々の重要な貢献は、高度にスケーラブルでサンプルベースの取得機能であり、非支配的な目的のソートを実行する。
我々は,ベイズ型ニューラルネットワークサロゲートと組み合わせることで,最小限の反復数でデータ集約環境に有効であることを示す。
論文 参考訳（メタデータ） (2023-06-01T19:10:57Z) - 3D Video Object Detection with Learnable Object-Centric Global
Optimization [65.68977894460222]
対応性に基づく最適化は3次元シーン再構成の基盤となるが、3次元ビデオオブジェクト検出では研究されていない。
オブジェクト中心の時間対応学習と特徴量付きオブジェクトバンドル調整を備えた、エンドツーエンドで最適化可能なオブジェクト検出器であるBA-Detを提案する。
論文 参考訳（メタデータ） (2023-03-27T17:39:39Z) - MBORE: Multi-objective Bayesian Optimisation by Density-Ratio Estimation [0.01652719262940403]
最適化問題は、しばしば計算的に、あるいは金銭的にコストがかかる複数の矛盾する目標を持つ。
単代理ベイズ最適化(BO)は、そのようなブラックボックス関数を最適化するための一般的なモデルベースのアプローチである。
BOREによるBOの先行研究を多目的設定に拡張する。
論文 参考訳（メタデータ） (2022-03-31T09:27:59Z) - Stratified Transformer for 3D Point Cloud Segmentation [89.9698499437732]
Stratified Transformerは、長距離コンテキストをキャプチャし、強力な一般化能力と高性能を示す。
不規則な点配置によって引き起こされる課題に対処するために,局所情報を集約する第1層点埋め込みを提案する。
S3DIS, ScanNetv2およびShapeNetPartデータセットにおける本手法の有効性と優位性を示す実験を行った。
論文 参考訳（メタデータ） (2022-03-28T05:35:16Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Variable Division and Optimization for Constrained Multiobjective
Portfolio Problems [8.056425814256116]
可変分割と最適化(D&O)は、進化的アルゴリズム(EA)で頻繁に使用されるアルゴリズム設計パラダイムです。
本稿では,多対象問題における部分変数のエリート選択法を提案する。
数学的プログラミングの助けを借りて、制約付き多目的ポートフォリオ問題で達成される。
論文 参考訳（メタデータ） (2021-01-21T11:08:23Z) - Learning the Step-size Policy for the Limited-Memory
Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。
入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。
ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
論文 参考訳（メタデータ） (2020-10-03T09:34:03Z) - MOPS-Net: A Matrix Optimization-driven Network forTask-Oriented 3D Point
Cloud Downsampling [86.42733428762513]
MOPS-Netは行列最適化のための新しい解釈可能な深層学習手法である。
我々はMOPS-Netが様々なタスクに対して最先端の深層学習手法に対して好適な性能が得られることを示す。
論文 参考訳（メタデータ） (2020-05-01T14:01:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。