論文の概要: A Study of Scalarisation Techniques for Multi-Objective QUBO Solving
- arxiv url: http://arxiv.org/abs/2210.11321v1
- Date: Thu, 20 Oct 2022 14:54:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 15:34:01.418807
- Title: A Study of Scalarisation Techniques for Multi-Objective QUBO Solving
- Title(参考訳): 多目的QUBO解法における拡張手法の検討
- Authors: Mayowa Ayodele, Richard Allmendinger, Manuel L\'opez-Ib\'a\~nez,
Matthieu Parizy
- Abstract要約: 量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In recent years, there has been significant research interest in solving
Quadratic Unconstrained Binary Optimisation (QUBO) problems. Physics-inspired
optimisation algorithms have been proposed for deriving optimal or sub-optimal
solutions to QUBOs. These methods are particularly attractive within the
context of using specialised hardware, such as quantum computers, application
specific CMOS and other high performance computing resources for solving
optimisation problems. These solvers are then applied to QUBO formulations of
combinatorial optimisation problems. Quantum and quantum-inspired optimisation
algorithms have shown promising performance when applied to academic benchmarks
as well as real-world problems. However, QUBO solvers are single objective
solvers. To make them more efficient at solving problems with multiple
objectives, a decision on how to convert such multi-objective problems to
single-objective problems need to be made. In this study, we compare methods of
deriving scalarisation weights when combining two objectives of the cardinality
constrained mean-variance portfolio optimisation problem into one. We show
significant performance improvement (measured in terms of hypervolume) when
using a method that iteratively fills the largest space in the Pareto front
compared to a n\"aive approach using uniformly generated weights.
- Abstract(参考訳): 近年,二次的非拘束バイナリ最適化 (QUBO) 問題の解決に対する研究の関心が高まっている。
物理に着想を得た最適化アルゴリズムがQUBOの最適解や準最適解の導出のために提案されている。
これらの手法は、最適化問題を解決するために量子コンピュータ、アプリケーション固有のCMOS、その他の高性能コンピューティングリソースなどの特別なハードウェアを使用するコンテキストにおいて特に魅力的である。
これらの解法は組合せ最適化問題のQUBO定式化に適用される。
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的ソルバである。
複数の目的を持つ問題解決をより効率的に行うためには、このような多目的問題を単一目的問題に変換する方法を決定する必要がある。
本研究では,濃度制約付き平均分散ポートフォリオ最適化問題の2つの目的を1つに組み合わせる際に,スカラー化重みを導出する手法を比較する。
一様生成重みを用いたn\"aiveアプローチと比較して,パレートフロントの最大空間を反復的に満たす手法を用いた場合,性能改善(ハイパーボリュームによる測定)が顕著である。
関連論文リスト
- Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳(メタデータ) (2024-06-11T19:59:05Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳(メタデータ) (2024-05-01T09:34:42Z) - Smooth Tchebycheff Scalarization for Multi-Objective Optimization [15.047246588148495]
多目的最適化問題は、目的が相反することが多く、単一のソリューションでは最適化できない、多くの実世界のアプリケーションで見られる。
勾配に基づく多目的最適化のための軽量で効率的なスムーズなTchebycheffスキャラライズ手法を提案する。
論文 参考訳(メタデータ) (2024-02-29T12:03:05Z) - Multi-Objective Optimization and Network Routing with Near-Term Quantum
Computers [0.2150989251218736]
我々は,多目的最適化問題を解くために,近距離量子コンピュータを応用できる手法を開発した。
量子近似最適化アルゴリズム(QAOA)に基づく実装に焦点を当てる。
論文 参考訳(メタデータ) (2023-08-16T09:22:01Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Evidence that PUBO outperforms QUBO when solving continuous optimization
problems with the QAOA [4.670374869377859]
量子アルゴリズムによる最適化問題の解決における中核的なステップは、問題の定式化である。
近年の研究では、多くの問題を自然の多項式非制約最適化形式でより効率的に解けることが示されている。
適切なベンチマーク関数の評価では、PUBOの定式化は一般により良い結果をもたらすが、キュービットは少ない。
論文 参考訳(メタデータ) (2023-05-05T09:37:48Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳(メタデータ) (2023-01-28T01:50:42Z) - Multi-objective QUBO Solver: Bi-objective Quadratic Assignment [0.0]
商用QUBOソルバを多目的ソルバとしてサポートするアルゴリズムを拡張した最初の試みを示す。
提案した多目的DAアルゴリズムは、二目的の二次割当て問題に対して検証される。
論文 参考訳(メタデータ) (2022-05-26T14:48:03Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳(メタデータ) (2020-07-14T09:50:33Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。