論文の概要: Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
- arxiv url: http://arxiv.org/abs/2107.06870v1
- Date: Fri, 9 Jul 2021 07:36:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-18 13:12:30.956351
- Title: Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
- Title（参考訳）: 旅行セールスマン問題の強化型ハイブリッド遺伝的アルゴリズム
- Authors: Jiongzhi Zheng and Menglei Chen and Jialun Zhong and Kun He
- Abstract要約: 有名なNPハードトラベリングセールスマン問題(TSP)に対する強力な強化ハイブリッド遺伝的アルゴリズム(RHGA)を提案する。
RHGAは強化学習技術と有名なエッジアセンブリクロスオーバー遺伝的アルゴリズム(EAX-GA)とLin-Kernighan-Helsgaun局所探索を組み合わせた。
都市数は1,000, 85,900都市で, 良く知られた, 広く利用されているベンチマーク138都市を対象に, 提案手法の優れた性能を実証した。
- 参考スコア（独自算出の注目度）: 4.92025078254413
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a powerful Reinforced Hybrid Genetic Algorithm (RHGA) for the
famous NP-hard Traveling Salesman Problem (TSP). RHGA combines reinforcement
learning technique with the well-known Edge Assembly Crossover genetic
algorithm (EAX-GA) and the Lin-Kernighan-Helsgaun (LKH) local search heuristic.
With the help of the proposed hybrid mechanism, the genetic evolution of EAX-GA
and the local search of LKH can boost each other's performance. And the
reinforcement learning technique based on Q-learning further promotes the
hybrid genetic algorithm. Experimental results on 138 well-known and widely
used TSP benchmarks, with the number of cities ranging from 1,000 to 85,900,
demonstrate the excellent performance of the proposed method.
- Abstract（参考訳）: 本稿では,NPハードトラベリングセールスマン問題(TSP)に対する強力な強化ハイブリッド遺伝的アルゴリズム(RHGA)を提案する。
RHGAは強化学習技術と有名なエッジアセンブリクロスオーバー遺伝的アルゴリズム(EAX-GA)とLin-Kernighan-Helsgaun(LKH)局所探索ヒューリスティックを組み合わせた。
提案したハイブリッド機構の助けを借りて、EAX-GAの遺伝的進化とLKHの局所探索により、互いのパフォーマンスが向上する。
また、q学習に基づく強化学習技術は、ハイブリッド遺伝的アルゴリズムをさらに促進する。
128のよく知られたTSPベンチマーク実験の結果,1,000から85,900都市を対象に,提案手法の優れた性能を示した。
関連論文リスト
- Evolutionary Approach to S-box Generation: Optimizing Nonlinear Substitutions in Symmetric Ciphers [19.65010496906351]
本研究では,対称鍵暗号における非線形置換箱(Sボックス)生成における遺伝的アルゴリズムの適用について検討した。
本稿では,遺伝的アルゴリズムとWalsh-Hadamard Spectrum (WHS)コスト関数を組み合わせることで,非線形性104。
提案手法は, 平均49,399回, 100%の成功率で, 最もよく知られた手法と同等の性能を実現する。
論文 参考訳（メタデータ） (2024-07-03T21:15:24Z) - Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic
Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
遺伝的アルゴリズム(GA)は最適化問題の解法における効率性で知られている。
本稿では遺伝子工学の概念からインスピレーションを得るため,遺伝子工学アルゴリズム(GEA)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-28T13:05:30Z) - Massively Parallel Genetic Optimization through Asynchronous Propagation
of Populations [50.591267188664666]
Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。
提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。
Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
論文 参考訳（メタデータ） (2023-01-20T18:17:34Z) - A Genetic Quantum Annealing Algorithm [0.0]
遺伝的アルゴリズム(英: genetic algorithm, GA)は、遺伝的・自然選択の原理に基づく探索に基づく最適化手法である。
本稿では,量子アニールからの入力により古典的GAを向上するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-09-15T16:59:55Z) - 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) - Hybrid Random Features [60.116392415715275]
ハイブリッドランダム特徴(HRF)と呼ばれるソフトマックスとガウス核の線形化のための新しいランダム特徴法を提案する。
HRFは、カーネル推定の品質を自動的に適応し、定義された関心領域の最も正確な近似を提供する。
論文 参考訳（メタデータ） (2021-10-08T20:22:59Z) - Hybrid Henry Gas Solubility Optimization Algorithm with Dynamic
Cluster-to-Algorithm Mapping for Search-based Software Engineering Problems [1.0323063834827413]
本稿ではHenry Gas Solubility Optimization(HGSO)アルゴリズムの新しい変種であるHGSO(Hybrid HGSO)について述べる。
前者とは異なり、HHGSOは異なるメタヒューリスティックアルゴリズムを提供する複数のクラスタを同じ集団内で共存させることができる。
HHGSOは、適応的な切替係数を持つペナル化および報酬モデルによる動的クラスタ-アルゴリズムマッピングを発明し、メタヒューリスティックなハイブリダイゼーションのための新しいアプローチを提供する。
論文 参考訳（メタデータ） (2021-05-31T12:42:15Z) - Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm
for the Traveling Salesman Problem [12.851149098610096]
VSR-LKHという可変戦略強化手法を提案する。
3つの強化学習法(q-learning, sarsa, monte carlo)とlin-kernighan-helsgaun(lkh)と呼ばれるよく知られたtspアルゴリズムを組み合わせる。
VSR-LKHはLKHの柔軟性のない操作を置き換え、強化学習によって各探索ステップで選択を学習する。
論文 参考訳（メタデータ） (2020-12-08T14:58:36Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z) - Plug-And-Play Learned Gaussian-mixture Approximate Message Passing [71.74028918819046]
そこで本研究では,従来のi.i.d.ソースに適した圧縮圧縮センシング(CS)リカバリアルゴリズムを提案する。
我々のアルゴリズムは、Borgerdingの学習AMP(LAMP)に基づいて構築されるが、アルゴリズムに普遍的な復調関数を採用することにより、それを大幅に改善する。
数値評価により,L-GM-AMPアルゴリズムは事前の知識を必要とせず,最先端の性能を実現する。
論文 参考訳（メタデータ） (2020-11-18T16:40:45Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。