論文の概要: Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2506.09404v1
• Date: Wed, 11 Jun 2025 05:17:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-13 06:35:02.505929
• Title: Synergizing Reinforcement Learning and Genetic Algorithms for Neural Combinatorial Optimization
• Title（参考訳）: ニューラルネットワーク最適化のための強化学習と遺伝的アルゴリズムの相乗化
• Authors: Shengda Gu, Kai Li, Junliang Xing, Yifan Zhang, Jian Cheng,
• Abstract要約: 本稿では,DRLの学習効率をGAのグローバル検索能力と相乗化するための進化的拡張機構を提案する。 EAMは、学習されたポリシーからソリューションを生成し、クロスオーバーや突然変異といったドメイン固有の遺伝子操作によってそれらを精製することで機能する。 EAMは、アテンションモデル、POMO、SymNCOのような最先端のDRLソルバとシームレスに統合できる。
• 参考スコア（独自算出の注目度）: 25.633698252033756
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems are notoriously challenging due to their discrete structure and exponentially large solution space. Recent advances in deep reinforcement learning (DRL) have enabled the learning heuristics directly from data. However, DRL methods often suffer from limited exploration and susceptibility to local optima. On the other hand, evolutionary algorithms such as Genetic Algorithms (GAs) exhibit strong global exploration capabilities but are typically sample inefficient and computationally intensive. In this work, we propose the Evolutionary Augmentation Mechanism (EAM), a general and plug-and-play framework that synergizes the learning efficiency of DRL with the global search power of GAs. EAM operates by generating solutions from a learned policy and refining them through domain-specific genetic operations such as crossover and mutation. These evolved solutions are then selectively reinjected into the policy training loop, thereby enhancing exploration and accelerating convergence. We further provide a theoretical analysis that establishes an upper bound on the KL divergence between the evolved solution distribution and the policy distribution, ensuring stable and effective policy updates. EAM is model-agnostic and can be seamlessly integrated with state-of-the-art DRL solvers such as the Attention Model, POMO, and SymNCO. Extensive results on benchmark problems (e.g., TSP, CVRP, PCTSP, and OP) demonstrate that EAM significantly improves both solution quality and training efficiency over competitive baselines.
• Abstract（参考訳）: 組合せ最適化問題は、その離散構造と指数関数的に大きな解空間のため、非常に難しい。 近年の深層強化学習(DRL)は,データから直接の学習ヒューリスティックスを実現している。 しかし、DRL法はしばしば、局所的な最適性に対する限られた探索と感受性に悩まされる。 一方、遺伝的アルゴリズム(GA)のような進化的アルゴリズムは、強いグローバル探索能力を示すが、典型的には非効率で計算集約的なサンプルである。 本研究では,DRLの学習効率をGAのグローバル検索能力と相乗化する汎用・プラグアンドプレイフレームワークであるEvolutionary Augmentation Mechanism (EAM)を提案する。 EAMは、学習されたポリシーからソリューションを生成し、クロスオーバーや突然変異といったドメイン固有の遺伝子操作によってそれらを精製することで機能する。 これらの進化した解は政策訓練ループに選択的に再注入され、探索と収束の促進が図られる。 さらに、進化した解分布と政策分布のKL分散の上限を確立する理論解析を行い、安定かつ効果的な政策更新を確実にする。 EAMはモデルに依存しないため、アテンションモデル、POMO、SymNCOといった最先端のDRLソルバとシームレスに統合できる。 ベンチマーク問題(例えば、TSP、CVRP、PCTSP、OP)の広範な結果から、EMAは競争ベースラインよりもソリューション品質とトレーニング効率の両方を著しく改善することが示された。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Genetic Algorithm enhanced by Deep Reinforcement Learning in parent selection mechanism and mutation : Minimizing makespan in permutation flow shop scheduling problems [0.18846515534317265]
  RL+GA法はフローショップスケジューリング問題(FSP)で特に検証された。 このハイブリッドアルゴリズムはニューラルネットワーク(NN)を導入し、Qラーニング(Q-learning)というオフ政治手法を使用する。 本研究は, プリミティブGAの性能向上におけるRL+GAアプローチの有効性を明らかにするものである。
  論文  参考訳（メタデータ） (2023-11-10T08:51:42Z)
• Reinforcement Learning-assisted Evolutionary Algorithm: A Survey and Research Opportunities [63.258517066104446]
  進化的アルゴリズムの構成要素として統合された強化学習は,近年,優れた性能を示している。 本稿では,RL-EA 統合手法,RL-EA が採用する RL-EA 支援戦略,および既存文献による適用について論じる。 RL-EAセクションの適用例では、RL-EAのいくつかのベンチマークおよび様々な公開データセットにおける優れた性能を示す。
  論文  参考訳（メタデータ） (2023-08-25T15:06:05Z)
• A Reinforcement Learning-assisted Genetic Programming Algorithm for Team Formation Problem Considering Person-Job Matching [70.28786574064694]
  解の質を高めるために強化学習支援遺伝的プログラミングアルゴリズム(RL-GP)を提案する。 効率的な学習を通じて得られる超ヒューリスティックなルールは、プロジェクトチームを形成する際の意思決定支援として利用することができる。
  論文  参考訳（メタデータ） (2023-04-08T14:32:12Z)
• Evolving Populations of Diverse RL Agents with MAP-Elites [1.5575376673936223]
  政策だけでなく,任意の強化学習(RL)アルゴリズムの利用を可能にするフレキシブルなフレームワークを導入する。 我々は,多数のロボット制御問題に対する広範な数値実験を通じて,我々のフレームワークがもたらすメリットを実証する。
  論文  参考訳（メタデータ） (2023-03-09T19:05:45Z)
• Direct Mutation and Crossover in Genetic Algorithms Applied to Reinforcement Learning Tasks [0.9137554315375919]
  本稿では、遺伝的アルゴリズム(GA)を用いて神経進化を適用し、最適な行動エージェントを生成するニューラルネットワークの重みを見つけることに焦点を当てる。 本稿では,データ効率と収束速度を初期実装と比較して改善する2つの新しい修正法を提案する。
  論文  参考訳（メタデータ） (2022-01-13T07:19:28Z)
• Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning [56.17667147101263]
  実世界のタスクでは、強化学習エージェントはトレーニング中に存在しない状況に遭遇する。 信頼性を確保するため、RLエージェントは最悪の状況に対して堅牢性を示す必要がある。 本稿では,Robust Hallucinated Upper-Confidence RL (RH-UCRL)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-18T16:50:17Z)

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

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