基于Q—学习的超启发式模型及算法求解多模式资源约束项目调度问题

崔建双，吕 玥，徐子涵

(北京科技大学 经济管理学院，北京 100083)

0 引言

在以人工智能、生物信息科学以及智能决策为代表的众多学科领域中存在着大量的以大规模、多模态、非连续性为特征的组合优化问题，针对这类问题，传统的运筹优化方法难以奏效，因而多采用启发式或元启发式算法加以解决。这类方法大多基于直观经验或模拟自然现象，通过嵌入随机性因子，利用进化、群集、仿生等启发式技术，结合广域探查和局域搜索策略，在可接受的时空条件下获得问题的近优解。多年来先后涌现出许多优秀的元启发式算法，如遗传、进化、模拟退火、禁忌搜索、蚁群、粒子群、人工蜂群、人工免疫、混合蛙跳、人工鱼群等算法[1]。

在各种优化算法的应用实践中，不难观察到如下现象：

(1)同一种算法对于类型相近的问题或类型相同但数据不同的算例，在效率和效果上差异很大。为达到理想的优化目标，人们不得不进行算法定制。基于个人经验、尝试不同的参数、拓扑结构和搜索策略，缺乏理论层次的指导，导致算法应用成本居高不下。

(2)虽然不同算法的寻优策略各有千秋，但许多算法展现出相同或相似的实现机制，例如：受自然现象启发、利用群集智能、包含随机成分、不使用梯度信息、有若干可调参数等。这些现象无疑为开发通用型算法、实现算法软件重用、转换即用型算法等需求提供了契机。人们有理由提出并尝试各种算法融合技术，研发一类适应性更强且结果令人接受的超启发式算法。目前，在优化算法研究领域出现的诸如自适应技术[2]、通用算法软件框架[3]、混合元启发式[4]、超启发式[5]、优化算法推荐[6]、算法合成[7]等方法和技术无不以此为目标，寄希望于通过算法的自动动态匹配或混合技术，降低定制成本，改善应用效果。其中，超启发式(hyper-heuristic)算法与技术已成为当前一大研究热点。超启发式算法通过自动选择或生成一组启发式过程来解决各种优化问题，除了提升算法解决问题的效率之外，更重要的是追求算法的通用性和自适应性[8]。

本文提出一种基于强化学习技术的超启发式模型(Reinforcement Learning based Hyper-Heuristic Model, RLHM)，并在此基础上实现了一种基于Q—学习的超启发式算法。强化学习是机器学习的一个重要分支，通过与环境交互获得经验，量化为奖惩值并根据奖惩值来决定进一步的执行动作。在RLHM中，设计了高层启发式组件对低层启发式(Low Level Heuristic, LLH)算子的选择和移动接受策略。其中，LLH算子初步选择了经典的禁忌搜索(Tabu Search, TS)、粒子群优化(Particle Swarm Optimization，PSO)、人工蜂群(Artificial Bee Colony，ABC)和蚁群系统(Ant Colony System，ACS)四种具有异构机制的元启发式算子，并预留了灵活方便的扩展接口，包括同类算法不同参数的扩展和不同算法算子的扩展。高层策略使用Q—学习通过奖惩机制来对LLH算子和状态组合进行选择，在本文中，不同的状态对应不同的接受准则，LLH算子为下一步执行的动作，Q—学习作为高层策略选择的不单是LLH算子，而是状态—动作组合，通过对状态—动作组合的选择，使算法趋向于针对不同算例选择适合的动作，提高算法应用的效果。

本文设计的超启发式算法在LLH算子选择上采用元启发式算法，而非简单的交叉变异算子，因此LLH算子具有相对独立性，同时具备不依赖于特定问题的通用性。首先，其寻优机制的区别有益于实现大范围多样化搜索，充分利用TS大规模邻域搜索能力、大范围调节的PSO粒子飞行速度和位置、ABC良好的个体淘汰机制、ACS构建性的概率选择特长等；其次，不同组合优化问题的编码作为低层算子的基本组件可以预先确定，转换问题仅需要变换不同的编码组件；再次，LLH算子的扩充简单易行，如增加进化算子、模拟退火算子、异参算子等。算法利用Q—学习机制智能化地从低层多种元启发式算子中择优使用，充分发挥算子异构机制的多样性特征，实现了超启发式的概念。

为检验RLHM的应用效果，从多模式资源约束的项目调度问题(Multi-mode Resource-Constrained Project Scheduling Problem，MRCPSP)标杆算例库中选取1 608个不同规模的问题算例，与公开文献计算结果进行比较。实验结果充分表明了RLHM的竞争力和推广价值。

1 超启发式算法与Q—学习机制

1.1 超启发式算法文献综述

超启发式算法的提出源于各类启发式和元启发式算法存在的不足。正如引言中所指出的那样，不同算法各有优势和劣势，同时每一个具体问题都存在着算法“偏好”。超启发式算法的动机之一就是开发更普遍适用的算法，通过自动化设计和调整启发式算子更高效地解决搜索计算问题[5]。与手动算法定制不同，超启发式算法可被视为根据问题自动化定制算法[9]。因此，一个重要的目标是其通用性，基于一组易于实现的低级启发式方法生成质量可接受的解决方案[10]。

“超启发式”一词最早由DENZINGER等[11]提出，后由COWLING等[12]给出实质性定义。事实上，上世纪60年代超启发式思想已初露端倪，涉及到运筹学、计算机科学和人工智能等研究领域。代表性的研究成果表现在自动启发式排序[13]、自动规划系统[14-15]、进化算法中的自动参数控制[16]和自动学习启发式方法[17]等。早期阶段(2000年之前)的超启发式偏重于启发式自动设计，强调若干启发式规则或方法的组合优于仅使用单个独立的规则或方法。2000年之后，人们对超启发式算法的认识渐趋完善，陆续出现一些关于超启发式的综述性文献，BURKE等[8-9]和DRAKE等[10]归纳了超启发式算法的分类及研究现状(如图1)。超启发式本质上具有“学习”能力，其“学习”的含义在于算法能够从当前运行结果获得经验，并向着有利于解决问题的方向调整。根据学习过程中反馈信息的来源，超启发式可以分为“在线”和“离线”学习。前者依据即时状态提供的信息决定下一步的搜索走向，后者则依据以往经验决定下一步的搜索走向。

从目前公开发表的文献来看，大多数研究属于在线扰动(或称移动)的选择启发式，其模型由两个层次组成，如图2所示。低层包含问题的表示、评估函数和一组特定于问题的LLH算子，通过启发式扰动修改当前解；高层则控制LLH算子选择并依据既定规则判断是否接受所作的扰动选择[18-19]。可用的LLH算子选择方法包括简单随机、选择函数、禁忌搜索和强化学习等，而移动接受策略则包括仅改进、任何移动、Metropolis条件、模拟退火、延迟和Naive等[20-23]。在现实应用方面，超启发式算法已经取得了令人鼓舞的成果。文献[24]提出基于大洪水(Great Deluge，GD)策略的超启发式算法解决考试时间表问题；文献[25]用于解决城市公交路线问题(Urban Transit Routing Problem,UTRP)；文献[26]提出一种基于随机自动机网络的超启发式方法，该网络具有学习功能，可控制一组元启发式方法展开搜索。

1.2 强化学习与Q—学习

强化学习主要解决序贯决策问题。Q—学习是强化学习算法之一，专注于从交互中进行以目标为导向的学习。Q—学习过程主要包含学习体的3个联动元素：状态(state)、动作(action)和奖励(reward)，以获得最多累计奖励为目标。在没有任何先验信息的情况下，首先尝试做出一个动作得到反馈结果，根据反馈结果来调整下一步的动作，在该过程中选择特定情境下得到最大回报的动作。

假设S= [s1,s2, …,sn]表示学习体的n种可能的状态；A= [a1,a2,…,am]表示m个可能的动作。学习体在时刻t从状态st执行动作at之后进入新状态st+1，rt+1表示即时强化信号，即采取动作at后获得的奖励值(可正可负)。令α∈[0,1]表示用于权衡旧状态影响程度的学习率，该值越大，表明越重视以往学习的效果；γ∈[0,1]表示折扣因子，用于权衡奖励值对于新状态的影响程度，该值越大，表明越重视当前学习的效果。Q(st,at) 表示时刻t的Q值。将每个状态—动作对执行结束后被给予的Q值，记录在Q表中，通过如下Q函数式计算获得：

Qt+1(st,at)=(1-α)Q(st,at)+

α[rt+1+γmaxaQ(st+1,a)]。

Q—学习已被广泛用于各种能够从反馈中获得信息的应用场合。例如，目标转移Q—学习(Target Transfer Q-Learning, TTQL)[27]、超启发式算法自动设计[28]、机器人导航[29]、智能民居能源优化管理[30]、智能游戏控制[31]、动态跟踪控制[32]等。

1.3 超启发式与Q—学习

把Q—学习的奖惩机制与超启发式思想结合，通过评价低层算子的表现来决定下一步的算子选择，就可以实现基于Q—学习的超启发式算法。不少超启发式算法文献用到了Q—学习策略，但并未明确提及Q—学习。

SIM等[33]提出基于强化学习和禁忌搜索的模拟退火超启发式算法；ÖZCAN等[23]提出一种超启发式模型，利用所谓的“大洪水”策略作为移动接受方法；ZAMLI等[22]提出一种混合T—路测试生成策略，采用禁忌搜索作为其高级元启发式，并利用4种低级元启发自适应选择最合适的算法；FERREIRA等[35]提出一种“多臂强盗”选择机制策略(Multi-Arm Bandit, MAB)，使用CHeSC 2011[3]挑战赛改编的方法与其他20种超启发式方法进行了比较，其结果可以与挑战赛中最优超启发式方法获得的结果相媲美；DI GASPERO等[36]也提出了一种遵循Q—学习标准的超启发式模型，研究了立即强化方案的一些变体以及选择策略和学习函数的影响，提供了一类独特的状态和动作表示；MOSADEGH等[37]开发了一种超模拟退火算法，该算法使用Q—学习策略来选择启发式；张景玲等[34]设计了一种基于强化学习的超启发算法求解有容量车辆路径问题，算法使用强化学习中的深度Q神经网络算法构造选择策略，总体求解效果优于对比算法。

严格地看，Q—学习机制满足两个重要特征，即通过试错(trial-and-error)和延迟奖励(delayed reward)反复探索来实现自动化的与问题无关的搜索。相对于算法定制方法，基于Q—学习机制的超启发式算法的效率不一定更好，但其效果往往更佳，最主要的优点是摒弃了算法定制，提高了算法通用性水平。

2 RLHM及算法的实现

RLHM及其算法的实现基于如下两个目标：①算法具备不依赖于特定问题的通用性；②其寻优机制确保能够实现大范围、多样化的全局搜索和小范围的精细搜索。这两个目标都能够通过低层算子加以保证，因为这些算子都不是基于特定问题的启发式算法，而是通用性很强的元启发式算法。其搜索机理可以简单地表述为：利用Q—学习机制智能化地从低层元启发式算子群中择优使用，充分发挥群算子异构机制的多样化。多种优秀的元启发式算法与反馈—学习强化机制有机地整合在一起，具备灵活的可扩展性。

2.1 RLHM框架

在如图2所示模型的基础上，本文引入高层Q—学习策略之后得到如图3所示的RLHM框架。其中：低层预留了可扩展的算子接口，预设了多种组合优化问题编码和评估函数；高层针对Q表设计了可扩展的多种接受策略。为了增加多样性，接受策略采用随机选择方式获得，一旦选中了一种接受策略，就会根据低层评估函数提供的计算结果和全域最大Q值更新Q表，并进入下一轮动作(算子)选择。

2.2 状态—动作组合对

状态和动作是强化学习的两个要素，通过执行状态和动作的组合获得奖励，并帮助算法趋向选择回报最大的动作。将执行LLH算子看成是动作Action，把执行LLH算子之后的改进与否看成是状态State。仅改进接受和Naive接受是两种接受策略，前者要求计算结果有所改进才接受，拒绝未改进结果；后者则除了接受改进结果之外，以50%的概率接受未改进结果。如表1所示为RLHM算法中的接受策略。

表1 RLHM的接受策略

2.3 RLHM算法流程

RLHM算法流程参见算法1。为了使算法不陷入局优并增加全局搜索能力，在根据Q值大小选择状态—动作组合对时，采用了有保留的贪婪机制，即选择maxQ(S,A)状态下对应的动作，但若maxQ(S,A)<ε，则随机选择该状态下的一个动作，其中ε=0.3。状态—动作对确定后按照选择的动作执行优化，并及时更新最优值。下一步状态的确定根据执行当前状态—动作对后得到的解是否有所改进作为判断依据。Q值的更新按照前面给出的Q函数式执行。若优化后的种群得到改进，则给予奖励值r=10；否则，令r-2→r。重复以上迭代过程，直到可行解数量达到规定值(实验中设定为5 000次)为止。

算法1RLHM算法。

1: Initialization()

GlobalValue=min(fitnessinitial)

initial-state()和initial-action()

%随机指定一个初始状态和动作

2: While !Termination-Criteria Do

3: Select() %根据当前状态下Q值大小选择动作

4: Execution() %执行状态—动作组合

5: Update-Global-Value() %更新全局目标最优解

6: Determine-Next-State() %确定下一步状态

7: Update Q-value() %根据Q函数式更新Q表

8: End While

2.4 可行解数量的确定

算法1中的Execution()是执行LLH算子的过程。由于不同LLH算子的实现机制不同，完整地执行一次LLH算子所需时间不同。为了增加算法的多样性，使算法不至于过早收敛或陷入局优，每个LLH算子可设为运行有限的时间或者迭代次数。本算法将其设置为执行每个LLH算子时记录生成可行解的数量，达到规定数量后无条件跳出执行。

为便于与其他文献结果作出比较，本文通过实验确定无论执行哪一种LLH算子，每次可行解数量≤100，控制每个算例累计总可行解数量不超过5 000次。

2.5 LLH算子的设计

传统超启发式算法的LLH算子采用简单启发式序列，多依赖于问题，从而影响了算法的广泛适用性。RLHM的低层LLH算子均采用相对独立模块化的元启发式算法，并可根据问题需要随时扩充新的算法模块。例如，可以根据需要随时给定TS算法的不同参数，一组新的参数可以看成是一种新的算法。也可以增加新的元启发式算子，每一个新算法都是一个新的动作，Q表的规模也会随之扩大。针对相同的问题采用相同的编码格式，可大大提升算法的通用性。

RLHM算法初始集成了TS、PSO、ABC和ACS四种元启发式算法模块，各LLH算法参数设计如下：

(1)TS。TS的基础是邻域搜索算法。禁忌对象2-opt或3-opt邻域交换；限定邻域解最大数量、破禁策略、禁忌表长等参数。

(2)PSO。使用标准粒子群算法公式，参数学习因子c1、c2，惯性权重ω。本文粒子速度和位置的更新方式采用JARBOUI等[38]提出的方法。

(3)ABC。设计蜜蜂角色变换上限值Limit参数是关键，超过上限值予以淘汰。下一代蜂群的选择采用轮盘赌方式。

(4)ACS。本文在黄少荣[39]提出的蚁群算法基础上进行了改进。参数ρ、α、β和Q可调节，残留信息素更新采用蚁周模型。

3 实验结果及分析

3.1 MRCPSP的定义

minsn+2。

(1)

s.t.

si+di,mi≤sj， ∀(i,j)∈E；

(2)

(3)

(4)

mi∈Mi={i=1,…,|Mi|},∀i∈N；

(5)

s0=0；

(6)

si=int+，∀i∈N。

(7)

其中：式(1)表示最小化项目工期；式(2)表示活动之间遵从完成—开始时间约束关系，式中di,mi为活动i取模式mi时的执行时间；式(3)和式(4)分别表示可再生和不可再生资源约束；式(5)确保每一活动仅取一种模式；式(6)要求项目开始时间为0；式(7)假定所有活动的开始时间均为非负整数。

过去多年来，针对该NP—难问题已经提出了许多求解方法[41]。SPRECHER等[42]曾使用以分支定界为代表的精确算法求解该问题，但受搜索空间的制约，难以在合理的时间内解决规模较大的问题(迄今为止部分活动数量超过30的问题仍处于开放状态)。为此，业界大多求助于启发式[43-45]或元启发式算法，如遗传[46-47]，模拟退火[48-49]，粒子群[38,50]，禁忌搜索[51]，分布估计[52]，混合蛙跳[53]，差分进化[54]，蚁群优化[55]，分散搜索[56]，路径重连[57]等。

3.2 实验环境设置

实验采用MATLAB R2015b编程实现。从项目调度问题库 (Project Scheduling Problem Library, PSPLIB)[58]选取规模为J10、J20和J30不等的1 608个(各536个)MRCPSP算例作为实验数据集。采用DELL笔记本电脑，配置为：CPU Intel i7, 主频2.6 GHz，8 G内存。设计不同条件下的多个验证环节，并与当前公开文献提供的结果进行比较。

3.3 与最新文献中的计算结果的比较

将RLHM实验结果与文献[40]列出的多种用于求解MRCPSP的优化算法进行对比。这些算法大多都报告了J10和J20两组算例的结果。为了公平起见，本实验每组均选取全部536个算例，总计1 072个算例。表2列出了对比结果(表中算法名称以文献作者姓名缩写表示)，表中数据表示执行5 000次可行解得到的平均偏差值。

表2 与文献[35,40]列出的优化算法比较结果

从实验结果可以发现，RLHM算法是这些算法中表现最好的。由于公开文献缺乏关于J30算例的进一步报告，针对J30的536个算例，在此仅报告其计算结果(如表3)。RLHM算法对J30算例的计算结果表明有多达41个算例获得了比当前公开文献报告的已知最优解更好的结果。

表3 获得改进的J30算例

3.4 与元启发式算法计算结果的比较

RLHM算法实现了多种元启发式算子的择优使用，针对不同的算例充分利用了不同算子的优势。为了验证这一点，从PSPLIB[58]选取的J10、J20和J30算例中每组随机选取50个算例，共计150个算例，每个算例执行5 000次可行解，分别取各组算例的偏差均值做出比较。如图4所示为RLHM算法与分别独立执行的4种元启发式算法(TS、PSO、ABC、ACS)计算结果的比较。从图4可以看出，RLHM算法得到的目标偏差在3组算例中均小于其他4种元启发式算法，进一步验证了RLHM算法的优势。

3.5 与随机选择超启发式算法结果对比

RLHM算法高层采用了改进接受和Naive接受两种预先指定的状态，使用Q—学习指导LLH算子选择，与传统的随机机制选择(Random Heuristic Selection, RHS)LLH算子相比，效果明显有所改善。现设定两种算法的有关参数(终止迭代次数，LLH算子相关参数设置等)均一致，算例仍然采用J10，J20和J30不同规模150个算例进行计算，结果对比曲线如图5所示。

由图5可知，RLHM算法比RHS算法平均偏差更小。随着算例规模的增大，差距也在拉大。这说明RLHM算法中Q—学习机制在选择LLH算子时，随着问题规模越大，能力表现越突出。更主要的是RLHM算法没有刻意地去调整哪个参数以适应问题，而是利用Q—学习机制自动地选择各个算子，达到了超启发式算法的初衷。

3.6 扩充LLH算子及其影响

扩充LLH算子意味着增加新算子的数量，有助于改进搜索空间的多样性，从而增大全局优化的可能性。RLHM算法设计了两种增加LLH算子的可行方案：第一种方案是直接通过适当修改现有的元启发式算法并集成到低层LLH算子集中，正如图3低层左侧所示，将模拟退火算法、遗传算法、邻域搜索算法、混合蛙跳等元启发式算法都集成进来。这样的集成只需要前一个算子能够平滑地把本算子计算的结果传递给下一个算子。第二种方案是在现有的各算子基础上修改算法参数来获得新的算子。如PANDIRI等[59]曾根据参数值的不同组合改变算法的特性，有效地求解了k—互连多仓库多旅行商问题。对于一个算子的某个参数值来说，有时其可选的范围很大，也很灵敏，因此，初始可以根据经验选定几种典型的参数，作为不同算子使用，当然也可以自适应地调整不同参数的组合。

为了验证增加新LLH算子带来的效果，本文在前4个LLH算子基础上分别设计了两种实验方案：第一方案增加了遗传算子GA和模拟退火算子SA；第二方案改变了TS的禁忌表长度和PSO的学习因子c1,c2和惯性权重ω的值。

表4列出了不同算子(动作)数量下针对前述150个算例的计算结果。由表4可知，增加新动作带来的最重要的变化是缩短了计算时间(从4个算子的计算时间210 min下降到8个算子的107 min)。目标值平均偏差均有所下降，说明增加算子数量有助于及时跳出变化不大的局部搜索环节，提升算法效率和效果。

表4 不同算子数量下目标值差均值

3.7 LLH算子调用频度分析

一个算子的调用频度定义为执行过程中该算子被调用的次数与全体算子被调用次数之比。该值越大，说明该算子被调用的概率越大，因而可以说明算法对其依赖程度以及Q—学习的效果。如表5所示为执行150个算例时，LLH算子平均调用频度统计结果。

表5 LLH算子平均调用频度统计

从表5可以看出，算子从高到低调用频度分别是TS>PSO>ABC>ACS。这基本上符合单独应用这4种元启发式算法时的效果，也间接证明了RLHM算法在LLH算子选择上使用Q—学习进行智能选择的可靠性。其次，随着问题规模的增加，优秀算子被调用频率更大，但并没有放弃对其他算子的选择，从而说明了多样性的Q—学习带来的灵活性。

4 结束语

在优化算法研究领域，超启发式算法和技术已经成为当前一大研究热点，其目的是解决传统的元启发式算法机制单一和面向问题定制等不足，能够大大提升解决问题的通用性。从这一视角看，超启发式算法的研究是比发明新算法更有意义的一项工作，能够实现领域内不同策略和技术的交叉融合。

本文提出一种基于Q—学习的超启发式算法RLHM算法。首先，与传统的超启发式算法不同的是，低层算子不再采用简单的启发式序列，而是使用不同元启发式算法作为独立算子。元启发式算法不依赖于问题，而相同的问题可在不同元启发式算法上统一编码。其次，作为低层算子的元启发式算法可以随意扩充，而常见的组合优化问题的编码也可以根据不同的问题随时扩充，大大增加了算法的灵活性和通用性。再次，算法通过Q—学习的评价机制智能地选择适当状态—动作组合，从而使RLHM算法在LLH算子选择上具备较高的灵活性和可靠性。实验结果证明了RLHM算法的良好特性。未来的研究中，将继续增加高层算子的选择策略，进一步提高低层算子的计算效率，进而提高算法的整体通用性。