論文の概要: Learning to repeatedly solve routing problems
- arxiv url: http://arxiv.org/abs/2212.08101v1
- Date: Thu, 15 Dec 2022 19:33:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-19 16:25:21.156760
- Title: Learning to repeatedly solve routing problems
- Title(参考訳): 経路問題を繰り返し解くための学習
- Authors: Mouad Morabit, Guy Desaulniers, Andrea Lodi
- Abstract要約: データのマイナーチェンジ後に問題の再最適化について学習した。
元のソリューションのエッジを考慮すれば、最適なソリューションに留まる確率の高いソリューションを予測し、修正することが目標です。
この解の偏差予測は問題の複雑さを減らし、解を高速化する。
- 参考スコア(独自算出の注目度): 5.08128537391027
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the last years, there has been a great interest in machine-learning-based
heuristics for solving NP-hard combinatorial optimization problems. The
developed methods have shown potential on many optimization problems. In this
paper, we present a learned heuristic for the reoptimization of a problem after
a minor change in its data. We focus on the case of the capacited vehicle
routing problem with static clients (i.e., same client locations) and changed
demands. Given the edges of an original solution, the goal is to predict and
fix the ones that have a high chance of remaining in an optimal solution after
a change of client demands. This partial prediction of the solution reduces the
complexity of the problem and speeds up its resolution, while yielding a good
quality solution. The proposed approach resulted in solutions with an
optimality gap ranging from 0\% to 1.7\% on different benchmark instances
within a reasonable computing time.
- Abstract(参考訳): 近年,NP-hard組合せ最適化問題に対する機械学習に基づくヒューリスティックスへの関心が高まっている。
開発した手法は多くの最適化問題に可能性を示している。
本稿では,データの小さな変更の後に問題を再最適化するための学習ヒューリスティックを提案する。
静的なクライアント(例えば、同じクライアント位置)と要求の変化によるキャパシットされた車両ルーティングの問題に注目する。
元のソリューションのエッジを考えると、目標は、クライアントの要求が変わった後、最適なソリューションに留まる確率の高いソリューションを予測し、修正することにあります。
この解の部分的な予測は、問題の複雑さを減少させ、解決をスピードアップさせ、優れた解を産み出す。
提案手法は、適切な計算時間内に異なるベンチマークインスタンス上で0\%から1.7\%までの最適性ギャップを持つ解を得た。
関連論文リスト
- An Expandable Machine Learning-Optimization Framework to Sequential
Decision-Making [0.0]
逐次的意思決定問題を効率的に解決する統合予測最適化(PredOpt)フレームワークを提案する。
本稿では,機械学習(ML)における逐次依存,実現可能性,一般化といった課題に対処し,インスタンス問題に対する最適解の予測を行う。
論文 参考訳(メタデータ) (2023-11-12T21:54:53Z) - Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。
本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
論文 参考訳(メタデータ) (2023-01-28T01:50:42Z) - Learning Adaptive Evolutionary Computation for Solving Multi-Objective
Optimization Problems [3.3266268089678257]
本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。
DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。
学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
論文 参考訳(メタデータ) (2022-11-01T22:08:34Z) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳(メタデータ) (2022-10-31T09:46:26Z) - Fast Re-Optimization of LeadingOnes with Frequent Changes [0.9281671380673306]
Doerrらによって提案された再最適化アプローチは、問題インスタンスがより頻繁な変更の傾向にある場合に限界に達することを示す。
本稿では,前ベスト周辺における欲求探索と現在ベスト解を補間するアルゴリズムの修正を提案する。
論文 参考訳(メタデータ) (2022-09-09T16:51:41Z) - Learning from Images: Proactive Caching with Parallel Convolutional
Neural Networks [94.85780721466816]
本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。
モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。
数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
論文 参考訳(メタデータ) (2021-08-15T21:32:47Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳(メタデータ) (2020-11-10T19:09:12Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。
最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。
我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
論文 参考訳(メタデータ) (2020-06-18T19:11:54Z) - Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated
Algorithm Selection [0.0]
トラベリング・サレスパーソン・プロブレム(TSP)は、最もよく知られたNPハード最適化問題の1つである。
我々は、不正確なTSPソルバの任意の動作に対処することで、既存のベンチマーク研究を拡張した。
その結果、解法の性能ランキングは、集中した近似品質に大きく依存していることが判明した。
論文 参考訳(メタデータ) (2020-05-27T11:36:53Z) - Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。
本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。
その結果, 直接使用法と比較して計算時間を2~5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
論文 参考訳(メタデータ) (2020-02-04T20:00:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。