APP下载

基于强化学习的组合优化综述

2021-09-28顾一凡

软件导刊 2021年9期
关键词:智能优化策略

顾一凡

(南京航空航天大学计算机科学与技术学院,江苏南京 210016)

0 引言

优化问题的主要重点在于在不同可能性中寻找当前问题的最优解或最佳配置。这一类问题通常被分成两种:具有连续变量的问题和具有离散变量的问题[1]。例如:在凸优化问题中的一个可行解通常属于实数空间,这样的解被称为一个连续优化的可行解,而查找一系列城市的游览路径则是离散的优化问题。一般而言,在离散空间中查找解的问题被称为组合优化(CO)问题。

当前RL 与CO 结合有两种不同方式:主体学习与联合学习方式。主体学习方式可通过智能体直接作出决定,该方法直接通过RL 策略构造问题的解或完整解的一部分,而不需要求解器的反馈。例如,在TSP 问题中,神经网络首先对智能体进行参数化处理,然后该神经网络逐步构建路径,将路径长度作为奖励来更新策略。联合学习方式则是与现存的求解器联合训练RL,使其可提升CO 问题的解在不同性能度量指标上的表现。例如,在混合整数线性方程(Mixed-Integer Linear Program,MILP)中,常用方法是“分支限界”,其在每一步都选择树子节点的分支规则,该方法可能会对树的整体大小及算法运行时间产生影响。另外,分支限界属于启发式方法,需要一些专家知识对参数进行调整。值得注意的是,可通过RL 智能体接收与运行时间成正比的奖励训练智能体学习节点选择策略。

通常来说,使用RL 解决CO 问题可看作是学习解决此类问题的策略,而不是使用运筹学中人为设定的方法,在该层次上可将其分为学习构造启发式以及改进启发式方法。……

登录APP查看全文

猜你喜欢

智能优化策略
超限高层建筑结构设计与优化思考
民用建筑防烟排烟设计优化探讨
关于优化消防安全告知承诺的一些思考
一道优化题的几何解法
例谈未知角三角函数值的求解策略
我说你做讲策略
智能前沿
智能前沿
智能前沿
智能前沿