論文の概要: A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2307.07120v3
• Date: Sat, 28 Oct 2023 09:23:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-31 20:34:21.584695
• Title: A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem
• Title（参考訳）: min-max多重販売マン問題に対するハイブリッド遺伝的アルゴリズム
• Authors: Sasan Mahmoudinazlou and Changhyun Kwon
• Abstract要約: 本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。 新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。 我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
• 参考スコア（独自算出の注目度）: 0.9790236766474201
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) to minimize the length of the longest tour. The genetic algorithm utilizes a TSP sequence as the representation of each individual, and a dynamic programming algorithm is employed to evaluate the individual and find the optimal mTSP solution for the given sequence of cities. A novel crossover operator is designed to combine similar tours from two parents and offers great diversity for the population. For some of the generated offspring, we detect and remove intersections between tours to obtain a solution with no intersections. This is particularly useful for the min-max mTSP. The generated offspring are also improved by a self-adaptive random local search and a thorough neighborhood search. Our algorithm outperforms all existing algorithms on average, with similar cutoff time thresholds, when tested against multiple benchmark sets found in the literature. Additionally, we improve the best-known solutions for $21$ out of $89$ instances on four benchmark sets.
• Abstract（参考訳）: 本稿では,長期ツアーの長さを最小化するために,Multiple Traveling Salesman Problem (mTSP) を解くハイブリッド遺伝的アルゴリズムを提案する。 遺伝的アルゴリズムは、TSPシーケンスを個々の表現として利用し、動的プログラミングアルゴリズムを用いて、その個人を評価し、与えられた都市のシーケンスに対して最適なmTSPソリューションを求める。 新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。 生成した子孫のいくつかは、交差のない解を得るためにツアー間の交差点を検出して除去する。 これはmin-max mTSPに特に有用である。 生成した子孫は、自己適応型ランダム局所探索と完全近傍探索により改善される。 我々のアルゴリズムは、文献にある複数のベンチマークセットに対して、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回る。 さらに、4つのベンチマークセットで899ドルのインスタンスのうち21ドルで、最もよく知られたソリューションを改善します。

関連論文リスト

• Learning-guided iterated local search for the minmax multiple traveling salesman problem [13.924692115320553]
  本稿では, ミンマックス多旅行セールスマン問題に対する, 傾き駆動型局所探索手法を提案する。 提案アルゴリズムは,ソリューションの品質と実行時間の観点から,優れた結果が得られることを示す。 特に、32の既知の結果が新たに達成され、35の他のインスタンスで最もよく知られた結果と一致している。
  論文  参考訳（メタデータ） (2024-03-19T02:57:10Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone [0.8287206589886881]
  トラベル・セールスマン問題(TSPD)やフライング・サイドキック・トラベリング・セールスマン問題(FSTSP)と呼ばれる新たな交通問題が存在する。 本研究では,局所探索と動的プログラミングを取り入れたTSPDとFSTSPのハイブリッド遺伝的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-01T16:11:09Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
  本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。 提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
  論文  参考訳（メタデータ） (2020-05-05T08:34:58Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Multi-User Remote lab: Timetable Scheduling Using Simplex Nondominated Sorting Genetic Algorithm [1.0953917735844645]
  マルチユーザ遠隔実験室のスケジューリングは,提案アルゴリズムのマルチモーダル関数としてモデル化される。 提案アルゴリズムは,探索法としてSimplexアルゴリズム,局所最適点のソートにNSGAを用いる。
  論文  参考訳（メタデータ） (2020-03-26T02:31:50Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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