首页|期刊导航|郑州大学学报(理学版)|基于改进型深度Q网络求解图着色问题

基于改进型深度Q网络求解图着色问题OA

Solving Graph Coloring Problems Based on Improved Deep Q-network

中文摘要英文摘要

图着色问题(graph coloring problem,GCP)作为典型的 NP 难(NP-hard)组合优化问题,其在无线频谱分配、并行任务调度与资源配置等场景中具有广泛应用和深远影响.针对大规模、结构复杂的图所带来的计算瓶颈,提出一种基于改进型深度 Q 网络(dueling deep Q-network,DDQN)的强化学习求解框架,将图着色过程建模为马尔可夫决策过程,并设计了状态表达、动作定义和奖励机制,引导智能体在训练中高效减少颜色冲突并压缩颜色数.所采用的 DDQN 架构通过显式分离状态价值函数和动作优势函数,有效提升了策略评估精度和训练稳定性.在多个标准图基准数据集上实验结果表明,该方法在解的质量、颜色利用效率和收敛速度等关键指标上均显著优于传统启发式方法.该研究不仅为图着色问题提供了具备可扩展性和泛化能力的智能优化范式,也为复杂组合优化问题的强化学习建模与求解提供了新路径和理论支撑.

The graph coloring problem(GCP),a canonical NP-hard combinatorial optimization chal-lenge,has been critical in diverse application domains such as wireless spectrum allocation,parallel task scheduling,and resource optimization.To address the computational bottlenecks posed by large-scale and structurally complex graphs,a reinforcement learning framework based on an enhanced dueling deep Q-network(DDQN)was proposed.The graph coloring process was formulated as a Markov decision process,with carefully designed state representations,action definitions,and reward functions,to guide the agent in minimizing color conflicts and reducing the total number of colors during training.The adopt-ed DDQN architecture explicitly decoupled the state-value function from the action-advantage function,thereby improving policy evaluation accuracy and enhancing training stability.Extensive experiments were conducted on several standard benchmark graph datasets,and the results demonstrated that the proposed method significantly outperformed traditional heuristic algorithms in terms of solution quality,color utiliza-tion efficiency,and convergence speed.This study not only provided a scalable and generalizable intelli-gent optimization paradigm for the GCP but also offered a novel modeling and solution pathway for tack-ling complex combinatorial optimization problems via reinforcement learning.

宋家欢;王晓峰;丁红胜;胡思敏;锁小娜;颜冬

北方民族大学 计算机科学与工程学院 宁夏 银川 750021北方民族大学 计算机科学与工程学院 宁夏 银川 750021||北方民族大学 图形图像智能处理国家民委重点实验室 宁夏 银川 750021北方民族大学 计算机科学与工程学院 宁夏 银川 750021北方民族大学 计算机科学与工程学院 宁夏 银川 750021北方民族大学 计算机科学与工程学院 宁夏 银川 750021北方民族大学 计算机科学与工程学院 宁夏 银川 750021

信息技术与安全科学

图着色问题深度Q网络强化学习马尔可夫决策梯度下降组合优化

graph coloring problemdeep Q-networkreinforcement learningMarkov decision processgradient descentcombinatorial optimization

《郑州大学学报(理学版)》 2026 (6)

67-74,8

国家自然科学基金项目(62062001)宁夏自然科学基金项目(2024AAC03165)

10.13705/j.issn.1671-6841.2025094

评论