論文の概要: Multi-objective QUBO Solver: Bi-objective Quadratic Assignment
- arxiv url: http://arxiv.org/abs/2205.13399v1
- Date: Thu, 26 May 2022 14:48:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-27 15:03:34.585569
- Title: Multi-objective QUBO Solver: Bi-objective Quadratic Assignment
- Title（参考訳）: 多目的QUBOソルバー:双対象2次アサインメント
- Authors: Mayowa Ayodele and Richard Allmendinger and Manuel L\'opez-Ib\'a\~nez
and Matthieu Parizy
- Abstract要約: 商用QUBOソルバを多目的ソルバとしてサポートするアルゴリズムを拡張した最初の試みを示す。
提案した多目的DAアルゴリズムは、二目的の二次割当て問題に対して検証される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Quantum and quantum-inspired optimisation algorithms are designed to solve
problems represented in binary, quadratic and unconstrained form. Combinatorial
optimisation problems are therefore often formulated as Quadratic Unconstrained
Binary Optimisation Problems (QUBO) to solve them with these algorithms.
Moreover, these QUBO solvers are often implemented using specialised hardware
to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's
Quantum Annealer. However, these are single-objective solvers, while many
real-world problems feature multiple conflicting objectives. Thus, a common
practice when using these QUBO solvers is to scalarise such multi-objective
problems into a sequence of single-objective problems. Due to design trade-offs
of these solvers, formulating each scalarisation may require more time than
finding a local optimum. We present the first attempt to extend the algorithm
supporting a commercial QUBO solver as a multi-objective solver that is not
based on scalarisation. The proposed multi-objective DA algorithm is validated
on the bi-objective Quadratic Assignment Problem. We observe that algorithm
performance significantly depends on the archiving strategy adopted, and that
combining DA with non-scalarisation methods to optimise multiple objectives
outperforms the current scalarised version of the DA in terms of final solution
quality.
- Abstract（参考訳）: 量子および量子に着想を得た最適化アルゴリズムは、二進法、二進法、非制約形式で表される問題を解くために設計されている。
したがって、組合せ最適化問題は、これらのアルゴリズムで解くために、二次非制約バイナリ最適化問題(QUBO)として定式化されることが多い。
さらに、これらのQUBOソルバは、富士通のDigital Annealer(DA)やD-WaveのQuantum Annealerといった、膨大なスピードアップを達成するために、特別なハードウェアを用いて実装されることが多い。
しかし、それらは単一の目的の解法であり、多くの現実世界の問題には複数の相反する目的がある。
したがって、これらのQUBOソルバを使用する場合の一般的な実践は、そのような多目的問題を単一目的問題の列にまとめることである。
これらの解法の設計上のトレードオフのため、各スカラー化の定式化には局所的最適を求めるよりも多くの時間を要する可能性がある。
本稿では,商用のquboソルバをスカラライズに基づかない多目的解法としてサポートするアルゴリズムを拡張した最初の試みを示す。
提案された多目的daアルゴリズムは、二目的二次代入問題で検証される。
アルゴリズムの性能は採用されているアーカイブ戦略に大きく依存しており、daと非スカラー化法を組み合わせて複数の目的を最適化することで、最終的なソリューション品質の面で現在のdaのスカラ化バージョンを上回っている。
関連論文リスト
- Quantum Algorithms for Drone Mission Planning [0.0]
ミッションプランニングはしばしば、一連のミッション目標を達成するためにISR(Intelligence, Surveillance and Reconnaissance)資産の使用を最適化する。
このような解を見つけることはNP-Hard問題であり、古典的なコンピュータでは効率的に解けないことが多い。
我々は、現在の古典的手法に対してスピードアップを提供する可能性のある、短期量子アルゴリズムについて検討する。
論文 参考訳（メタデータ） (2024-09-27T10:58:25Z) - 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) - A Scale-Independent Multi-Objective Reinforcement Learning with
Convergence Analysis [0.6091702876917281]
多くのシーケンシャルな意思決定問題は、対立する可能性のある異なる目的の最適化を必要とする。
本稿では,Advantage Actor-Critic (A2C)アルゴリズムに基づいて,単エージェントスケール非依存型多目的強化学習を開発する。
次に、収束保証を提供する考案された多目的アルゴリズムに対して収束解析を行う。
論文 参考訳（メタデータ） (2023-02-08T16:38:55Z) - A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
量子および量子に着想を得た最適化アルゴリズムは、学術ベンチマークや実世界の問題に適用した場合に有望な性能を示す。
しかし、QUBOソルバは単目的解法であり、複数の目的による問題の解法をより効率的にするためには、そのような多目的問題を単目的問題に変換する方法を決定する必要がある。
論文 参考訳（メタデータ） (2022-10-20T14:54:37Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z) - Follow the bisector: a simple method for multi-objective optimization [65.83318707752385]
複数の異なる損失を最小化しなければならない最適化問題を考える。
提案手法は、各イテレーションにおける降下方向を計算し、目的関数の相対的減少を等しく保証する。
論文 参考訳（メタデータ） (2020-07-14T09:50:33Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳（メタデータ） (2020-02-20T17:07:08Z) - Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。
異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。
近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文 参考訳（メタデータ） (2019-12-30T08:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。