論文の概要: Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP*
Neighborhood
- arxiv url: http://arxiv.org/abs/2012.10384v2
- Date: Tue, 12 Oct 2021 16:27:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-22 01:45:53.193631
- Title: Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP*
Neighborhood
- Title（参考訳）: CVRPのハイブリッド遺伝的検索:オープンソース実装とSWAP*周辺
- Authors: Thibaut Vidal
- Abstract要約: キャパシタン化車両ルーティング問題(CVRP)に特化したHGS(Hybrid Genetic Search)の実装について紹介する。
この最先端のアルゴリズムは、Vidal et al. (2012)と同じ一般的な手法を用いており、また過去10年間に学んだ方法論的改善や教訓も含んでいる。
- 参考スコア（独自算出の注目度）: 6.85316573653194
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The vehicle routing problem is one of the most studied combinatorial
optimization topics, due to its practical importance and methodological
interest. Yet, despite extensive methodological progress, many recent studies
are hampered by the limited access to simple and efficient open-source solution
methods. Given the sophistication of current algorithms, reimplementation is
becoming a difficult and time-consuming exercise that requires extensive care
for details to be truly successful. Against this background, we use the
opportunity of this short paper to introduce a simple -- open-source --
implementation of the hybrid genetic search (HGS) specialized to the
capacitated vehicle routing problem (CVRP). This state-of-the-art algorithm
uses the same general methodology as Vidal et al. (2012) but also includes
additional methodological improvements and lessons learned over the past decade
of research. In particular, it includes an additional neighborhood called SWAP*
which consists in exchanging two customers between different routes without an
insertion in place. As highlighted in our study, an efficient exploration of
SWAP* moves significantly contributes to the performance of local searches.
Moreover, as observed in experimental comparisons with other recent approaches
on the classical instances of Uchoa et al. (2017), HGS still stands as a
leading metaheuristic regarding solution quality, convergence speed, and
conceptual simplicity.
- Abstract（参考訳）: 車両経路問題は、その実用的重要性と方法論的関心から、最も研究された組合せ最適化のトピックの1つである。
しかし、方法論的な進歩にもかかわらず、最近の多くの研究は、単純で効率的なオープンソースソリューションメソッドへのアクセスの制限によって妨げられている。
現在のアルゴリズムの洗練度を考えると、再実装は困難で時間のかかる作業となり、詳細が本当に成功するには広範囲の注意が必要である。
このような背景から,本稿では,キャパシタン化車両ルーティング問題(CVRP)に特化したハイブリッド遺伝子探索(HGS)の簡易-オープンソース-実装について紹介する。
この最先端のアルゴリズムは、Vidal et al. (2012)と同じ一般的な手法を用いており、また過去10年間に学んだ方法論的改善や教訓も含んでいる。
特に、SWAP*と呼ばれる追加の地区があり、この地区は2人の客を異なるルートで交換する。
本研究で強調したように,SWAP* の効率的な探索は局所探索の性能に大きく貢献する。
さらに、Uchoa et al. (2017) の古典的な例に関する他の実験的なアプローチと比較すると、HGS はソリューションの品質、収束速度、概念的単純性に関する主要なメタヒューリスティックである。
関連論文リスト
- POGEMA: A Benchmark Platform for Cooperative Multi-Agent Navigation [76.67608003501479]
主評価指標の基礎に基づいて計算された領域関連メトリクスの範囲を定義する評価プロトコルを導入・指定する。
このような比較の結果は、様々な最先端のMARL、検索ベース、ハイブリッド手法を含むものである。
論文 参考訳（メタデータ） (2024-07-20T16:37:21Z) - Boosting Exploration in Actor-Critic Algorithms by Incentivizing
Plausible Novel States [9.210923191081864]
Actor-critic (AC)アルゴリズムは、モデルなしの深層強化学習アルゴリズムのクラスである。
本稿では,国家の新規性の測定に基づく本質的な報酬による探索を促進する新しい手法を提案する。
可塑性新規状態のインセンティブ付き探索により、ACアルゴリズムはサンプル効率を向上し、従って訓練性能を向上させることができる。
論文 参考訳（メタデータ） (2022-10-01T07:07:11Z) - Neural Networks for Local Search and Crossover in Vehicle Routing: A
Possible Overkill? [10.882329986831087]
我々は,Hybrid Genetic Search(HGS)を改善するために,グラフニューラルネットワーク(GNN)のヒートマップ形式での予測の利用を検討した。
ノード関連性の尺度を用いて,より高度な戦略を活用すれば,性能を大幅に向上できることを示す。
しかし,当初の期待とは裏腹に,ヒートマップは単純な距離測定よりも有意なアドバンテージを示さなかった。
論文 参考訳（メタデータ） (2022-09-09T22:08:17Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳（メタデータ） (2022-05-31T09:51:48Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
機械学習は分岐のための有望なパラダイムとして登場した。
分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。
我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
論文 参考訳（メタデータ） (2022-05-28T06:08:07Z) - Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ
LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。
本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
論文 参考訳（メタデータ） (2022-05-24T20:51:37Z) - Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient
Methods [73.35353358543507]
SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。
本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。
本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
論文 参考訳（メタデータ） (2022-02-15T09:17:39Z) - Learning Enhanced Optimisation for Routing Problems [3.747361228408185]
L2GLS(Learning to Guide Local Search)は、ルーティング問題に対する学習ベースのアプローチである。
L2GLSは、局所探索(LS)演算子の強度とペナルティ項を組み合わせ、局所最適から逃れる。
L2GLSは、他の機械学習手法よりも大きなTSPとCVRPに対して、最先端の新たな結果が得られることを示す。
論文 参考訳（メタデータ） (2021-09-17T04:47:26Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and
Time Windows [31.512563458410963]
本稿では,この問題を解決するために,局所探索を効率的に行うメメティックアルゴリズム(MATE)を提案する。
MATEは最先端のアルゴリズムをすべて上回り、特に12インスタンス(合計65インスタンス)でよく知られた新しいソリューションを見つける。
論文 参考訳（メタデータ） (2020-11-12T12:06:11Z) - AutoML-Zero: Evolving Machine Learning Algorithms From Scratch [76.83052807776276]
基本数学的操作をビルディングブロックとして使うだけで,完全な機械学習アルゴリズムを自動的に発見できることが示される。
汎用的な検索空間を通じて人間のバイアスを大幅に低減する新しいフレームワークを導入することでこれを実証する。
機械学習アルゴリズムをゼロから発見する上で、これらの予備的な成功は、この分野における有望な新しい方向性を示していると信じている。
論文 参考訳（メタデータ） (2020-03-06T19:00:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。