强化学习求解组合最优化问题的研究综述.docx_强化学习求解最优化问题资源-CSDN文库

版权申诉

文档资料

143 浏览量 2022-11-02 16:10:31 上传评论收藏 609KB DOCX 举报

资源详情

资源评论

在实际工程应用中,有一类优化问题需要从集合的所有组合中找出一个最

优方案或编排 , 这类离散空间中的优化问题称为组合最优化问题（ com-

binatorial optimization problem,COP ）

[1]

。组合最优化（ combinatorial

optimization,CO）的求解方法广泛应用于交通运输、管理、电力、航天、通信

等领域

[1]

,其快速求解具有重要的理论意义和实用价值。例如,车辆的调度、金融

资产的配置、仓库货物存储和运输路线的设计等实际问题都属于 COP 问题,随

着这些优化问题实例规模的不断增大和实例中动态及随机因素的增加,传统方

法的求解将耗费巨大的时间,问题结构一旦发生变化,传统方法需要重新搜索求

解,计算成本也会随之提高,快速求解这些优化问题变得十分困难。

近年来随着深度学习（deep learning,DL）技术在计算机视觉

[2]

、自然语

言处理

[3]

、语音识别

[4]

、推荐系统

[5]

等领域的广泛应用,特别是深度强化学习（deep

reinforcement learning,DRL）在 AlphaGo

[6]

、AlphaGo Zero

[7]

的成功应用,表明

在没有人类干预和指导的前提下,DL 和强化学习（reinforcement learning,RL）

的结合仍然能够取得很大的成功,甚至超越了人类经验的指导,具有快速求解、

泛化能力强、求解精度高等优势,为求解 COP 问题提供一个全新的思路方法。

鉴于此,近年来涌现出许多采用 RL 求解 COP 问题的新方法,即利用 RL 训练模

型的方法替代传统算法,让机器从算法中学习算法,从而快速且有效地解决实际

问题,适应现代科技的发展,进而满足人类生活需求。

业界相关的工作已经逐渐开展,如 2017 年 Hu 等人

[8]

采用 DRL 的方法求解

三维装箱问题;2018 年 Lin 等人

[9]

把 RL 应用在共享出行中的车辆管理和派单问

题上;2019 年 Mao 等人

[10]

将 RL 的方法应用在分布式集群任务调度中;2020 年

Mirhoseini 等人

[11]

又将 RL 应用到芯片布局设计中。这些研究都是通过 RL 的

方法解决实际生活中的 COP 问题,核心思路是：RL 序贯决策的功能与具有序

列决策性质的 COP 问题有天然的相似性

[12]

,RL 模型可以通过智能体与环境的

不断交互,自身逐步积累经验来获取问题的一个较优策略,在少量样本甚至无样

本的情况下,通过自学习的方式快速求解实际生活中的优化问题,从而得到优化

问题的解

[13]

,在求解过程中传统方法和新思路的流程如图 1 所示。

图 1

研究课题

[14]

,其中求解方法的选择显得尤为重要,本文会在 1.2 节对 COP 问题的

求解方法进行总结。

1.2 组合最优化问题求解方法概述

（1）传统方法

① 精确算法（ exact algorithm）

[16]

：枚举法、分支定界（ branch and

bound,BB）

[17]

、动态规划（dynamic programming,DP）

[17]

等均是通过不断迭

代的方式求解 COP 问题的全局最优解。

②近似算法（approximation algorithm）

[16]

：贪婪算法

[18]

、局部搜索

[19]

、

线性规划

[20]

等可以在多项式时间内来近似最优解,保证最坏情况下给出的解不

低于（最大化问题）最优解一定的倍数。

③（元）启发式算法（heuristic algorithm）

[21]

：遗传算法

[22]

、蚁群算法

[23,24]

、模拟退火算法

[25]

等均可以针对一般的 COP 问题求解。

上述方法通称为传统算法,以经典的 TSP 问题为例,其中枚举法和 DP 法求

解 TSP 问题的时间复杂度分别为 Ο(n!)和 Ο(n22n)

[1]

,随着实例问题规模的扩大,

该方法很难快速求解大规模的 TSP 问题,因此精确算法对求解 COP 问题规模

有一定的局限性;假定 P≠NP,一般形式的 TSP 问题是不可被近似的,设计近似算

法多数要考虑问题的特殊情况,因此近似算法对求解 COP 问题的条件有一定的

限制

[14]

;蚁群算法等可以快速求解 TSP 问题,但缺乏理论支撑以及无法保证解的

全局最优性,导致启发式算法很难保证求解的质量。

（2）基于机器学习的 COP 问题求解方法

①基于神经网络（neural network,NN）求解 TSP 问题：Hopfield 等人

[26]

提出一种 Hopfield 网络,首次尝试用机器学习（machine learning,ML）的方法

求解小规模的 TSP 问题,之后很多相关工作也相继出现,早期采用 NN 求解 COP

问题的文章可见 Smith

[27]

的综述。

②基于指向型网络（Pointer network,PN）

[28]

求解 COP 问题：Vinyals 等

人

[28]

针对 Seq2Seq

[29]

序列模型输入输出维度是固定的问题,对其改进,提出 PN

架构,并加入注意力机制（attention mechanism,AM）

[30]

使得序列模型不受输入

输出维度的限制。PN 架构为基于 ML 等新方法求解 COP 问题的工作奠定了很

好的理论基础。

③基于 DRL 求解 COP 问题：监督学习（supervised learning,SL）需要大

量标签,且 COP 问题的高质量标签不易获得。RL 使智能体与环境不断交互,通

过奖励值来激励学习得到数据,克服了 SL 中大量标签的花费问题。Zhang 等人

[31]

将 RL 应用到 NP-hard 的车间调度问题,Bello 等人

[32]

提出神经组合最优化模型

（neural combinatorial optimization,NCO）,为后续基于 RL 方法求解 COP 问

题的推进奠定了基础。

④基于 Transformer

[33]

框架求解 COP 问题：Transformer 框架延续了 AM

中编码 - 解码的结构 , 其网络架构均由自注意力机制和全连接层（ fully

connected,FC）组成,模型中多重注意力机制（multi- head attention,MHA）的

自注意力机制计算方法,增加更多计算层,以便提取到深层节点的特征信息,有

效克服信息丢失问题。

⑤基于图神经网络（graph neural networks,GNNs）

[34,35,36,37]

求解 COP 问

题：GNNs 近几年发展迅速,是一种将深度神经网络（deep neural network,DNN）

模型应用于解决图上相关任务的方法,通过低维的向量信息来表征图的节点及

拓扑结构,此方法可以很好地处理非欧几里德数据,有效抽取图结构中的关键节

点信息。

⑥基于 ML 与传统方法结合的求解方法：此方法求解 COP 问题主要是端

到端的输出解

[38]

。针对搜索过程中子问题不同的特性,Liberto 等人

[39]

提出 DASH

（dynamic approach for switching heuristics）架构,动态切换合适的启发算法

求解 COP 问题。He 等人

[40]

引入模仿学习（imitation learning,IL）,以 SL 的方

式得到自适应的节点搜索策略。此方法能够利用 ML 方法的优点,同时还能保证

传统方法的最优性。

近年来采用 ML 方法求 COP 的方法逐渐增多,其中 Bengio 等人

[41]

的综述

介绍了 ML 与 COP 求解的方法导论,说明 ML 方法可以求解部分 COP 问题,这

对 COP 问题的求解提供了部分理论支撑。文中表 1 分析并总结了基于 RL 的

COP 问题求解方法,图 2 汇总了求解 COP 问题的方法框架。

表 1 研究方法、求解问题、模型算法的分析与总结

Table 1 Analysis and summary of research methods, solving problems

and models

剩余35页未读，继续阅读

评论收藏

内容反馈

版权申诉

强化学习求解组合最优化问题的研究综述.docx

评论0

最新资源

强化学习求解组合最优化问题的研究综述.docx

评论0

最新资源

相关推荐

强化学习的神经组合优化.zip

强化学习（一个端到端的框架）解决车辆路径问题

基于强化学习的电动车路径优化研究

基于深度强化学习的组合优化研究进展.docx

大规模车辆路径问题的深度强化学习算法研究 mind map

阿里强化学习资料

强化学习在阿里的技术演进与业务创新

蚁群算法和强化学习的RL中的Sarsa结合，取得了不错的改进 为组合优化的探索提供了思路

热电联产系统智能经济调度：一种深度强化学习方法 关键词：热电联产，经济调度，深度强化学习，近端优化 一种热电组合(CHP)系统经

强化学习 阿里

RLCO-Papers:基于组合学习的强化学习论文集

论文研究-基于CARLA-PSO组合模型的智能控制器参数学习优化.pdf

基于强化学习技术的智能派单模型.zip

系统的深度优化

deepdow:深度学习优化投资组合

基于强化学习、蒙特卡洛树搜索的UCT算法智能围棋博弈系统源码(解决围棋死活问题)+项目说明.zip

drl4dypm:深度强化学习以实现动态组合管理

论文研究-基于LG-MMAS算法的制造云服务优化组合研究.pdf

应用强化学习算法求解置换流水车间调度问题

全国计算机等级考试二级Python真题及解析.docx

1000份ppt模版，PPT模板优秀PPT

matlab批量读取excel表格数据并处理画图

导入证书可以解决”无法建立到信任根颁发机构的证书链"问题。

OpenCv车辆识别训练模型

代码随想录知识星球精华-大厂面试八股文第二版v1.2.pdf

Vue-Element UI集成ECharts实现数据统计分析页代码部分(如果帮助到你，感谢关注点赞)

数学建模对乙醇偶合制备C4烯烃的问题研究

STM32F103C8T6中文数据手册

（头歌）计算机组成原理存储系统设计（HUST）1-7关答案

蚁群算法和强化学习的RL中的Sarsa结合，取得了不错的改进为组合优化的探索提供了思路

热电联产系统智能经济调度：一种深度强化学习方法关键词：热电联产，经济调度，深度强化学习，近端优化一种热电组合(CHP)系统经

强化学习阿里