論文の概要: Unsupervised Learning for Quadratic Assignment
- arxiv url: http://arxiv.org/abs/2503.20001v1
- Date: Tue, 25 Mar 2025 18:37:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-27 13:21:48.989611
- Title: Unsupervised Learning for Quadratic Assignment
- Title(参考訳): 二次アサインメントのための教師なし学習
- Authors: Yimeng Min, Carla P. Gomes,
- Abstract要約: PLUME検索は、非自己回帰的なアプローチで置換に基づく損失を用いて問題インスタンスから直接学習する。
本稿では,様々な最適化問題を含むNP-hard問題である代入問題に対して,その性能を評価する。
- 参考スコア(独自算出の注目度): 30.652280460904375
- License:
- Abstract: We introduce PLUME search, a data-driven framework that enhances search efficiency in combinatorial optimization through unsupervised learning. Unlike supervised or reinforcement learning, PLUME search learns directly from problem instances using a permutation-based loss with a non-autoregressive approach. We evaluate its performance on the quadratic assignment problem, a fundamental NP-hard problem that encompasses various combinatorial optimization problems. Experimental results demonstrate that PLUME search consistently improves solution quality. Furthermore, we study the generalization behavior and show that the learned model generalizes across different densities and sizes.
- Abstract(参考訳): 我々は、教師なし学習による組合せ最適化において、探索効率を向上させるデータ駆動型フレームワークであるPLUME検索を紹介する。
教師付き学習や強化学習とは異なり、PLUME検索は、非自己回帰的なアプローチで置換に基づく損失を使用して問題インスタンスから直接学習する。
本稿では,組み合わせ最適化問題を含む基本NPハード問題である2次代入問題に対して,その性能を評価する。
実験の結果,PLUME探索は解の質を継続的に改善することがわかった。
さらに,一般化の挙動を考察し,学習モデルが様々な密度や大きさにわたって一般化することを示す。
関連論文リスト
- EHOP: A Dataset of Everyday NP-Hard Optimization Problems [66.41749917354159]
Everyday Hard Optimization Problems (EHOP) は、自然言語で表されるNPハード最適化問題の集合である。
EHOPには、コンピュータサイエンスの教科書で見られる問題の定式化、実生活で起こりうる問題として着飾られたバージョン、逆ルールでよく知られた問題の変種が含まれている。
現状のLLMは、複数のプロンプト戦略にまたがって、実生活や逆転型よりも教科書問題を体系的に高精度に解決していることがわかった。
論文 参考訳(メタデータ) (2025-02-19T14:39:59Z) - Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。
本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
論文 参考訳(メタデータ) (2024-11-06T09:12:31Z) - On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
本研究では,(マルチモーダル)自己教師型表現学習のデータ予測タスクにおいて,連続領域における識別確率モデルについて検討する。
我々は、自己教師付き表現学習における現在のInfoNCEに基づくコントラスト損失の制限を明らかにするために一般化誤差解析を行う。
MISが要求する条件付き確率密度の和を近似する新しい非パラメトリック手法を提案する。
論文 参考訳(メタデータ) (2024-10-11T18:02:46Z) - Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
論文 参考訳(メタデータ) (2024-09-07T19:52:14Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳(メタデータ) (2022-05-31T09:51:48Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization
Problems [9.015720257837575]
入力-解対のサンプルから高品質な最適化解を推定することを目的として,空間間の回帰を考察する。
基礎学習にはPAC-Bayesianフレームワークを用いて学習エラー分析を行う。
我々は,合成データセットと実世界のデータセットの両方において,古典的な問題に対する高い励振実験結果を得た。
論文 参考訳(メタデータ) (2021-07-15T17:59:08Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳(メタデータ) (2021-07-15T02:13:03Z) - Reversible Action Design for Combinatorial Optimization with
Reinforcement Learning [35.50454156611722]
強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。
最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
論文 参考訳(メタデータ) (2021-02-14T18:05:42Z) - Incorporating Machine Learning to Evaluate Solutions to the University
Course Timetabling Problem [0.0]
そこで本研究では,教師あり学習アルゴリズムを用いて,大学授業の時間変化問題に対する評価関数の近似を求める方法について検討した。
従来の評価関数は教師付き学習回帰モデルと最大97%の時間で一致した。
論文 参考訳(メタデータ) (2020-10-02T07:44:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。