論文の概要: Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?

• arxiv url: http://arxiv.org/abs/2210.12075v1
• Date: Fri, 9 Sep 2022 22:08:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-27 05:12:43.758970
• Title: Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?
• Title（参考訳）: 車両ルーティングにおける局所探索とクロスオーバーのためのニューラルネットワーク: オーバースキルの可能性?
• Authors: \'Italo Santana, Andrea Lodi and Thibaut Vidal
• Abstract要約: 我々は,Hybrid Genetic Search(HGS)を改善するために,グラフニューラルネットワーク(GNN)のヒートマップ形式での予測の利用を検討した。 ノード関連性の尺度を用いて,より高度な戦略を活用すれば,性能を大幅に向上できることを示す。 しかし,当初の期待とは裏腹に,ヒートマップは単純な距離測定よりも有意なアドバンテージを示さなかった。
• 参考スコア（独自算出の注目度）: 10.882329986831087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Extensive research has been conducted, over recent years, on various ways of enhancing heuristic search for combinatorial optimization problems with machine learning algorithms. In this study, we investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle Routing Problem (CVRP). The crossover and local-search components of HGS are instrumental in finding improved solutions, yet these components essentially rely on simple greedy or random choices. It seems intuitive to attempt to incorporate additional knowledge at these levels. Throughout a vast experimental campaign on more than 10,000 problem instances, we show that exploiting more sophisticated strategies using measures of node relatedness (heatmaps, or simply distance) within these algorithmic components can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures for these purposes. Therefore, we faced a common -- though rarely documented -- situation of overkill: GNNs can indeed improve performance on an important optimization task, but an ablation analysis demonstrated that simpler alternatives perform equally well.
• Abstract（参考訳）: 近年,機械学習アルゴリズムを用いた組合せ最適化問題に対するヒューリスティック探索の様々な方法に関する広範な研究が行われている。 本研究では,グラフニューラルネットワーク(gnns)からの予測をヒートマップとして利用し,キャパシタ付き車両経路問題(cvrp)に対する最先端アルゴリズムであるhybrid genetic search(hgs)を改善する。 HGSのクロスオーバーと局所探索のコンポーネントは改善された解を見つけるのに役立っているが、これらのコンポーネントは基本的に単純な欲求やランダムな選択に依存している。 これらのレベルで追加の知識を取り入れようという試みは直感的に思える。 1万以上の問題インスタンスに対する大規模な実験的キャンペーンを通じて、これらのアルゴリズムコンポーネント内のノード関連性(ヒートマップ、あるいは単に距離)を用いて、より高度な戦略を活用することで、パフォーマンスが大幅に向上することを示した。 しかし, 当初の期待に反して, ヒートマップはこれらの目的に対して単純な距離測定よりも有意な優位性を示しなかった。 gnnは確かに重要な最適化タスクでパフォーマンスを向上させることができますが、アブレーション分析によってより単純な代替案が等しく機能することを実証しました。

関連論文リスト

• Neural Networks for Vehicle Routing Problem [0.0]
  ルート最適化はニューラルネットワークの新たな課題と見なすことができる。 機械学習の最近の進歩は、複雑な問題に対処するための新しいツールセットを提供する。 ニューラルネットワークを応用する主な領域は、分類と回帰の領域である。
  論文  参考訳（メタデータ） (2024-09-17T15:45:30Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• Genetically Modified Wolf Optimization with Stochastic Gradient Descent for Optimising Deep Neural Networks [0.0]
  本研究の目的は、人口ベースメタヒューリスティックアルゴリズムを用いて、ニューラルネットワーク(NN)重み付けを最適化するための代替アプローチを分析することである。 Grey Wolf (GWO) と Genetic Modified Algorithms (GA) のハイブリッドをグラディエント・Descent (SGD) と組み合わせて検討した。 このアルゴリズムは、高次元性の問題にも対処しながら、エクスプロイトと探索の組み合わせを可能にする。
  論文  参考訳（メタデータ） (2023-01-21T13:22:09Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  著者らは、勾配のない探索手法が離散領域における最適解を提供するのに適していることを示した。 また、複数のローカル検索を使用することで、ローカル検索のパフォーマンスが向上することを示した。 提案したGA変種は,提案した問題を含む全てのベンチマークにおいて,最小平均コストであり,ICが構成成分よりも優れた性能を発揮することが観察された。
  論文  参考訳（メタデータ） (2022-02-02T08:27:11Z)
• Boosting Graph Search with Attention Network for Solving the General Orienteering Problem [7.0786689796236155]
  本稿では,ビームサーチと学習アルゴリズムを組み合わせたオリエンテーリング問題の解法を提案する。 我々は,ノード間の距離を入力とするアテンションネットワークを用いてアルゴリズムを取得し,強化学習フレームワークを用いて学習する。 提案手法は,幅広いベースラインを超えることができ,最適あるいは高度に専門化されたアプローチに近い結果が得られる。
  論文  参考訳（メタデータ） (2021-09-10T08:23:19Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood [6.85316573653194]
  キャパシタン化車両ルーティング問題(CVRP)に特化したHGS(Hybrid Genetic Search)の実装について紹介する。 この最先端のアルゴリズムは、Vidal et al. (2012)と同じ一般的な手法を用いており、また過去10年間に学んだ方法論的改善や教訓も含んでいる。
  論文  参考訳（メタデータ） (2020-11-23T21:37:49Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。 このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。 また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
  論文  参考訳（メタデータ） (2020-10-13T08:02:38Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• AutoML-Zero: Evolving Machine Learning Algorithms From Scratch [76.83052807776276]
  基本数学的操作をビルディングブロックとして使うだけで,完全な機械学習アルゴリズムを自動的に発見できることが示される。 汎用的な検索空間を通じて人間のバイアスを大幅に低減する新しいフレームワークを導入することでこれを実証する。 機械学習アルゴリズムをゼロから発見する上で、これらの予備的な成功は、この分野における有望な新しい方向性を示していると信じている。
  論文  参考訳（メタデータ） (2020-03-06T19:00:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。