論文の概要: A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2108.10224v1
• Date: Tue, 17 Aug 2021 21:37:23 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-29 13:12:47.857226
• Title: A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem
• Title（参考訳）: 旅行セールスマン問題に対する機械学習による新しい構成的ヒューリスティック
• Authors: Umberto Junior Mele, Luca Maria Gambardella and Roberto Montemanni
• Abstract要約: 近年,機械学習(ML)を用いてTSP(Traking Salesman Problem)を解くシステムでは,実ケースシナリオにスケールアップしようとすると問題が発生する。 問題に対処するため、候補リスト(CL)の使用が提起されている。 この作業では、高い確率のエッジに対してのみ、ソリューションの追加を確認するために、マシンラーニングモデルを使用します。
• 参考スコア（独自算出の注目度）: 8.604882842499212
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios with several hundred vertices. The use of Candidate Lists (CLs) has been brought up to cope with the issues. The procedure allows to restrict the search space during solution creation, consequently reducing the solver computational burden. So far, ML were engaged to create CLs and values on the edges of these CLs expressing ML preferences at solution insertion. Although promising, these systems do not clearly restrict what the ML learns and does to create solutions, bringing with them some generalization issues. Therefore, motivated by exploratory and statistical studies, in this work we instead use a machine learning model to confirm the addition in the solution just for high probable edges. CLs of the high probable edge are employed as input, and the ML is in charge of distinguishing cases where such edges are in the optimal solution from those where they are not. . This strategy enables a better generalization and creates an efficient balance between machine learning and searching techniques. Our ML-Constructive heuristic is trained on small instances. Then, it is able to produce solutions, without losing quality, to large problems as well. We compare our results with classic constructive heuristics, showing good performances for TSPLIB instances up to 1748 cities. Although our heuristic exhibits an expensive constant time operation, we proved that the computational complexity in worst-case scenario, for the solution construction after training, is $O(n^2 \log n^2)$, being $n$ the number of vertices in the TSP instance.
• Abstract（参考訳）: 機械学習(ML)を用いてTSP(Traking Salesman Problem)を解くシステムは,数百の頂点を持つ実ケースシナリオにスケールアップしようとすると,問題が発生する。 問題に対処するため、候補リスト(CL)の使用が提起されている。 この手順は、解法作成中の探索空間を制限し、ソルバ計算の負担を軽減する。 これまでのところ、MLは、ソリューション挿入時にMLの好みを表すこれらのCLのエッジにCLと値を作成することに関わった。 有望ではあるが、これらのシステムはMLが何を学習し、ソリューションを作成するかを明確に制限していない。 したがって,探索的および統計的研究に動機づけられた本研究では,高確率のエッジに対してのみ,解への加算を確認するために機械学習モデルを用いる。 高確率エッジのCLが入力として使用され、MLは、そのようなエッジが最適解である場合と、そうでない場合を区別する。 . この戦略はより良い一般化を可能にし、機械学習と探索技術の間の効率的なバランスを生み出す。 私たちのML-Constructive Heuristicは、小さなインスタンスでトレーニングされています。 そして、品質を損なうことなく、大きな問題にも解決策を生み出すことができます。 この結果と古典的構成的ヒューリスティックスを比較し、1748都市までのTSPLIBインスタンスの性能を示す。 我々のヒューリスティックは、高価な一定時間操作を示すが、トレーニング後のソリューション構築における最悪のシナリオの計算複雑性は、$O(n^2 \log n^2)$であり、TSPインスタンスの頂点数$n$であることを示した。

関連論文リスト

• Skipping Computations in Multimodal LLMs [63.29737699997859]
  本研究では,マルチモーダル大言語モデル(MLLM)における推論時の冗長性について検討する。 ブロック全体,FFN,自己保持層をスキップするなど,計算をスキップするさまざまな手法を提案する。 本研究は,推定時に大量の計算を回避できることを実証した。
  論文  参考訳（メタデータ） (2024-10-12T09:21:45Z)
• Can Large Language Models Play Games? A Case Study of A Self-Play Approach [61.15761840203145]
  LLM(Large Language Models)は、インターネットからの広範なデータを利用して、幅広い事前知識を格納する。 Monte-Carlo Tree Search (MCTS)は、信頼性の高い意思決定ソリューションを提供する検索アルゴリズムである。 この研究は、ターンベースのゼロサムゲームを効率的に解決するために、MCTSセルフプレイでLLMを活性化させる革新的なアプローチを導入している。
  論文  参考訳（メタデータ） (2024-03-08T19:16:29Z)
• Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize [57.22851616806617]
  本手法は,文献から得られた4つの領域において,最先端の成果が得られることを示す。 提案手法は, 局所性仮定が破られた場合, 既存手法よりも200%近く性能が向上する。
  論文  参考訳（メタデータ） (2023-05-26T11:17:45Z)
• 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 Continuous and Integer L-shaped Heuristics Through Supervised Learning [4.521119623956821]
  混合整数線形二段階プログラムの解を高速化する手法を提案する。 我々は,第2段階の要求の高い問題を解決することを目的としている。 私たちの中核となる考え方は、オンラインソリューションの時間を大幅に削減し、第一段階ソリューションの精度を小さくすることです。
  論文  参考訳（メタデータ） (2022-05-02T13:15:32Z)
• The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights [59.93939636422896]
  ML4COは、キーコンポーネントを置き換えることで最先端の最適化問題を解決することを目的としている。 このコンペティションでは、最高の実現可能なソリューションを見つけること、最も厳密な最適性証明書を生成すること、適切なルーティング設定を提供すること、という3つの課題があった。
  論文  参考訳（メタデータ） (2022-03-04T17:06:00Z)
• Machine Learning Methods in Solving the Boolean Satisfiability Problem [72.21206588430645]
  本論文は, Boolean satisfiability problem (SAT) を機械学習技術で解くことに関する最近の文献をレビューする。 ML-SATソルバを手作り特徴を持つナイーブ分類器からNeuroSATのような新たなエンド・ツー・エンドSATソルバまで,進化するML-SATソルバについて検討する。
  論文  参考訳（メタデータ） (2022-03-02T05:14:12Z)
• Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer Programs [0.0]
  混合整数プログラミング(MIP)問題に対する現在の解法は、幅広い問題に対して良好に動作するように設計されている。 近年の研究では、機械学習(ML)をMIPソルバと統合してドメイン知識を注入し、最適性ギャップを効率的に閉じることが示されている。 本稿では、エントロピーの概念を用いて、最小限のトレーニングデータとチューニングで効率的にモデルを構築するオンラインソルバを提案する。
  論文  参考訳（メタデータ） (2022-02-07T18:52:56Z)
• Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
  プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。 私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
  論文  参考訳（メタデータ） (2021-04-19T14:35:14Z)
• Efficient time stepping for numerical integration using reinforcement learning [0.15393457051344295]
  機械学習とメタラーニングに基づくデータ駆動型タイムステッピング方式を提案する。 まず、1つまたは複数の基礎学習者(非滑らかまたはハイブリッドシステムの場合)はRLを使用して訓練されます。 次に、メタ学習者は(システムの状態に応じて)現在の状況に最適と思われる基礎学習者を選択する訓練を受ける。
  論文  参考訳（メタデータ） (2021-04-08T07:24:54Z)
• Graph Minors Meet Machine Learning: the Power of Obstructions [0.90238471756546]
  ニューラルネットワークのトレーニングに閉塞を用いることの有用性を示す。 実験により、障害のあるトレーニングによって収束に必要なイテレーションの数が大幅に減少することが示された。
  論文  参考訳（メタデータ） (2020-06-08T15:40:04Z)

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

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