2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

资源约束项目的改进差分进化参数控制及双向调度算法

项前 周亚云 吕志军

项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法. 自动化学报, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
引用本文: 项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法. 自动化学报, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
XIANG Qian, ZHOU Ya-Yun, LV Zhi-Jun. Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project. ACTA AUTOMATICA SINICA, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
Citation: XIANG Qian, ZHOU Ya-Yun, LV Zhi-Jun. Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project. ACTA AUTOMATICA SINICA, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728

资源约束项目的改进差分进化参数控制及双向调度算法


DOI: 10.16383/j.aas.c170728
详细信息
    作者简介:

    项前  东华大学机械工程学院副教授.主要研究方向为计算机集成制造系统, 计算智能. E-mail:xqsir@dhu.edu.cn

    吕志军   东华大学机械工程学院副教授.主要研究方向为专家系统, 智能检测.E-mail: lvzj@dhu.edu.cn

    通讯作者: 周亚云   东华大学机械工程学院硕士研究生.主要研究方向为计算机集成制造系统.本文通信作者.E-mail: zhouyayun@mail.dhu.edu.cn
  • 本文责任编委 付俊
  • 基金项目:

    国家重点研发计划 2017YFB1304000

    上海市科学技术委员会科研计划项目 17DZ2283800

Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project

More Information
    Author Bio:

    XIANG Qian   Associate professor at the College of Mechanical Engineering, Donghua University. His research interest covers computer integrated manufacturing system and computational intelligence

    LV Zhi-Jun    Associate professor at the College of Mechanical Engineering, Donghua University. His research interest covers expert system and intelligent detection

    Corresponding author: ZHOU YA-Yun    Master student at the College of Mechanical Engineering, Donghua University. Her main research interest is computer integrated manufacturing system. Corresponding author of this paper
  • Recommended by Associate Editor FU Jun
  • Fund Project:

    National Key R & D Program of China 2017YFB1304000

    Research Program of Shanghai Science and Technology Commission 17DZ2283800

  • 摘要: 针对资源约束项目调度组合优化难题, 提出一种改进的动态差分进化参数控制及双向调度算法.通过参数时变衰减与个体优劣评价, 自适应控制个体进化参数, 提高算法的收敛性能、勘探与开发最优解的能力; 基于动态差分进化(Dynamic differential evolution, DDE), 提出一种双向调度算法, 使用满足任务时序约束的优先数编码、交替正向反向调度, 结合标准化编码调整与精英保留的种群随机重建策略, 建立了一种高效稳健的双向编码调整机制.通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试, 并与其他文献算法比较最优解平均偏差率, 验证了所提算法的有效性与优越性.
    本文责任编委 付俊
    Recommended by Associate Editor FU Jun
  • 图  1  个体编码与任务调度顺序

    Fig.  1  Individual coding and task scheduling sequence

    图  2  动态差分进化参数控制及双向调度算法流程图

    Fig.  2  Flowchart of DDE parameter control and bidirectional scheduling algorithm

    图  3  J30系列不同DE方案性能比较

    Fig.  3  Comparison of the performance by different DE schemes for J30

    图  4  J3013不同DE方案收敛性能比较

    Fig.  4  Comparison of the convergent performance by different DE schemes for J3013

    表  1  J30系列不同测试方案结果比较

    Table  1  Comparison of the results by different test schemes for J30

    方案 DE类型 参数控制 调度算法 避免局部最优 标准化编码 平均偏差率
    $av\_dev\, (\%)$ bh
    成功率
    $success\, (\%)$
    平均代数
    $av\_gen$
    平均CPU时间
    $CPUTime$ (s)
    平均值 标准差
    1 DE 固定 正向 0.143 0.013 92.40 109 4.59
    2 DDE 固定 正向 0.143 0.021 92.42 90 2.54
    3 DDE 正态分布[21] 正向 0.142 0.015 92.46 89 2.62
    4 DDE 自适应 正向 0.050 0.011 96.94 53 1.56
    5 DDE 自适应 双向 0.027 0.005 98.25 27 2.22
    6 DDE 自适应 双向 0.065 0.013 96.00 44 1.14
    7 DDE 自适应 双向 0.016 0.005 98.90 22 1.91
    8 DDE 自适应 双向 0.008 0.003 99.35 13 0.93
    下载: 导出CSV

    表  2  显著性水平($\alpha=0.05)$下平均偏差率双总体t检验

    Table  2  Paired-sample t-test of the average deviation rate at the significance level of 0.05

    1 2 3 4 5 6 7 8
    1 1
    2 $\textbf{0.983}$ 1
    3 $\textbf{0.939}$ $\textbf{0.937}$ 1
    4 1.34$\, \times 10^{-12}$ 3.83$\, \times 10^{-10}$ 4.66$\, \times 10^{-12}$ 1
    5 6.69$\, \times 10^{-16}$ 1.98$\, \times 10^{-12}$ 4.33$\, \times 10^{-15}$ 1.38$\, \times 10^{-5}$ 1
    6 8.97$\, \times 10^{-11}$ 1.16$\, \times 10^{-8}$ 2.63$\, \times 10^{-10}$ 1.18$\, \times 10^{-2}$ 8.02$\, \times 10^{-8}$ 1
    7 1.30$\, \times 10^{-16}$ 4.06$\, \times 10^{-13}$ 8.40$\, \times 10^{-16}$ 5.81$\, \times 10^{-8}$ 3.64$\, \times 10^{-5}$ 1.50$\, \times 10^{-9}$ 1
    8 $ {\bf{2}}.{\bf{83}}\times {\bf{1}}{{\bf{0}}^{ - {\bf{17}}}}$ $ {\bf{1}}.{\bf{25}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{13}}}}$ $ {\bf{2}}.{\bf{03}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{16}}}}$ $ {\bf{1}}.{\bf{53}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ ${\bf{4}}.{\bf{69}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ $ {\bf{9}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{11}}}}$ $ {\bf{5}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{4}}}}$ 1
    下载: 导出CSV

    表  3  方案5与方案7性能比较

    Table  3  Comparison between scheme 5 and scheme 7

    Ⅰ类(36个实例) Ⅱ类(444个实例)
    平均偏差率 平均代数 平均偏差率 平均代数
    $av\_dev~(\%)$ $av\_gen$ $av\_dev~(\%)$ $av\_gen$
    方案5 0.346 285 0.001 6
    方案7 0.194 238 0.001 5
    下载: 导出CSV

    表  4  ADDE-BS算法结果

    Table  4  Results of ADDE-BS algorithm

    最大调度次数 5 000 50 000
    实例集 J30 J60 J90 J120 J30 J60 J90 J120
    $av\_dev~(\%)$ 0.04 1.32 2.88 25.37 $\textbf{0.01}$ 1.03 2.62 24.43
    $success~(\%)$ 97.44 79.58 76.67 30.00 $\textbf{99.35}$ 83.75 77.50 31.50
    $CPUTime$ (s) 0.40 6.78 16.24 86.92 $\textbf{0.93}$ 66.55 179.89 1 004.36
    下载: 导出CSV

    表  5  与其他文献算法平均偏差率(%)比较

    Table  5  Comparison of average deviation rate (%) with art-of-state algorithms

    J30 J60 J90 J120
    5 000 50 000 5 000 50 000 5 000 50 000 5 000 50 000
    本文ADDE-BS $\textbf{0.04}$ $\textbf{0.01}$ $\textbf{1.32}$ $\textbf{1.03}$ $\textbf{2.88}$ $\textbf{2.62}$ $\textbf{25.37}$ $\textbf{24.43}$
    DE[18] 2016 0.00 0.00 0.98 2.07 4.04 8.81 19.62 31.68
    ACO CRO[6] 2017 - - 11.40 11.40 12.21 12.21 26.53 26.51
    COAs[14] 2017 0.00 0.00 10.77 10.58 - - 32.35 31.23
    GA-Part[9] 2017 0.07 0.01 11.08 10.71 - - 33.36 31.81
    Heuristic[24] 2017 0.09 0.03 11.31 10.91 - - 34.08 32.52
    ReVNS[10] 2016 0.01 0.00 11.10 10.88 - - 33.36 32.21
    H-RPSO[7] 2016 0.03 0.01 10.23 10.11 - - 31.94 30.25
    GA-MBX[25] 2013 0.04 0.00 10.94 10.65 - - 32.89 31.30
    MAOA[26] 2015 0.06 0.01 10.84 10.64 - - 32.64 31.02
    PSO-HH[13] 2014 0.04 0.01 11.13 10.68 - - 32.59 31.23
    HGA[27] 2013 0.07 0.01 11.14 10.63 - - 32.75 30.66
    ASH[27] 2013 0.11 0.03 11.33 10.85 - - 33.54 31.97
    下载: 导出CSV
  • [1] Kolisch R, Hartmann S. Experimental investigation of heuristics for resource-constrained project scheduling: an update. European Journal of Operational Research, 2006, 174(1): 23-37 doi:  10.1016/j.ejor.2005.01.065
    [2] Kolish R, Sprecher A. PSPLIB-A project scheduling problem library. European Journal of Operational Research, 1997, 96(1): 205-216 doi:  10.1016/S0377-2217(96)00170-1
    [3] Hartmann S. A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 2002, 49(5): 433-448 doi:  10.1002/nav.10029
    [4] 邓林义, 林焰, 金朝光.采用优先规则的粒子群算法求解RCPSP.计算机工程与应用, 2009, 45(10): 40-44 doi:  10.3778/j.issn.1002-8331.2009.10.013

    Deng Lin-Yi, Lin Yan, Jin Chao-Guang. Priority rule-based particle swarm optimization for RCPSP. Computer Engineering and Applications, 2009, 45(10): 40-44 doi:  10.3778/j.issn.1002-8331.2009.10.013
    [5] 戴月明, 汤继涛, 纪志成.协同震荡搜索混沌粒子群求解资源受限项目调度问题.计算机应用, 2014, 34(6): 1798-1802 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201406060

    Dai Yue-Ming, Tang Ji-Tao, Ji Zhi-Cheng. Cooperative shock search particle swarm optimization with chaos for resource-constrained project scheduling problems. Journal of Computer Applications, 2014, 34(6): 1798-1802 http://d.old.wanfangdata.com.cn/Periodical/jsjyy201406060
    [6] Gonzalez-Pardo A, Del Ser J, Camacho D. Comparative study of pheromone control heuristics in ACO algorithms for solving RCPSP problems. Applied Soft Computing, 2017, 60: 241-255 doi:  10.1016/j.asoc.2017.06.042
    [7] Munlin M, Anantathanavit M. Hybrid radius particle swarm optimization. In: Proceedings of the 2016 IEEE Region 10 Conference (TENCON). Singapore: IEEE, 2016. 2180-2184
    [8] Valls V, Ballestín F, Quintanilla S. Justification and RCPSP: a technique that pays. European Journal of Operational Research, 2005, 165(2): 375-386 doi:  10.1016/j.ejor.2004.04.008
    [9] Zamani R. An evolutionary implicit enumeration procedure for solving the resource-constrained project scheduling problem. International Transactions in Operational Research, 2017, 24(6): 1525-1547 doi:  10.1111/itor.12196
    [10] Paraskevopoulos D C, Tarantilis C D, Ioannou G. An adaptive memory programming framework for the resource-constrained project scheduling problem. International Journal of Production Research, 2016, 54(16): 4938-4956 doi:  10.1080/00207543.2016.1145814
    [11] 黄志宇.具有资源约束的项目调度问题中的量子进化算法.计算机集成制造系统, 2009, 15(9): 1779-1787, 1822 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200909016

    Huang Zhi-Yu. Quantum-inspired evolutionary algorithm for resources constrainted project scheduling problem. Computer Integrated Manufacturing Systems, 2009, 15(9): 1779-1787, 1822 http://d.old.wanfangdata.com.cn/Periodical/jsjjczzxt200909016
    [12] 陆志强, 刘欣仪.考虑资源转移时间的资源受限项目调度问题的算法.自动化学报, 2018, 44(6): 1028-1036 doi:  10.16383/j.aas.2017.c160834

    Lu Zhi-Qiang, Liu Xin-Yi. Algorithm for resource-constrained project scheduling problem with resource transfer time. Acta Automatica Sinica, 2018, 44(6): 1028-1036 doi:  10.16383/j.aas.2017.c160834
    [13] Koulinas G, Kotsikas L, Anagnostopoulos K. A particle swarm optimization based hyper-heuristic algorithm for the classic resource constrained project scheduling problem. Information Sciences, 2014, 277: 680-693 doi:  10.1016/j.ins.2014.02.155
    [14] Elsayed S, Sarker R, Ray T, Coello C C. Consolidated optimization algorithm for resource-constrained project scheduling problems. Information Sciences, 2017, 418-419: 346-362 doi:  10.1016/j.ins.2017.08.023
    [15] 吴亮红, 王耀南.动态差分进化算法及其应用.北京:科学出版社, 2014. 1-7

    Wu Liang-Hong, Wang Yao-Nan. Dynamic Differential Evolution Algorithm and Its Applications. Beijing: Science Press, 2014. 1-7
    [16] Das S, Mullick S S, Suganthan P N. Recent advances in differential evolution-an updated survey. Swarm and Evolutionary Computation, 2016, 27: 1-30
    [17] Cheng M Y, Tran D H, Wu Y W. Using a fuzzy clustering chaotic-based differential evolution with serial method to solve resource-constrained project scheduling problems. Automation in Construction, 2014, 37: 88-97 doi:  10.1016/j.autcon.2013.10.002
    [18] Ali I M, Elsayed S M, Ray T, Sarker R A. A differential evolution algorithm for solving resource constrained project scheduling problems. In: Artificial Life and Computational Intelligence. Lecture Notes in Computer Science, Vol. 9592. Cham: Springer, 2016. 209-220
    [19] Ciupe A, Meza S, Orza B. Heuristic optimization for the resource constrained Project Scheduling Problem: a systematic mapping. In: Proceedings of the 2016 Federated Conference on Computer Science and Information Systems. Gdansk, Poland: IEEE, 2016. 619-626
    [20] Brest J, Greiner S, Boskovic B, Mernik M, Zumer V. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-657 doi:  10.1109/TEVC.2006.872133
    [21] Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(2): 398-417 doi:  10.1109/TEVC.2008.927706
    [22] Zhang J Q, Sanderson A C. JADE: adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958 doi:  10.1109/TEVC.2009.2014613
    [23] Qing A Y. Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems. IEEE Transactions on Geoscience and Remote Sensing, 2006, 44(1): 116-125
    [24] Chand S, Singh H K, Ray T. A heuristic algorithm for solving resource constrained project scheduling problems. In: Proceedings of IEEE Congress on Evolutionary Computation. San Sebastian, Spain: IEEE, 2017. 225-232
    [25] Zamani R. A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem. European Journal of Operational Research, 2013, 229(2): 552-559 doi:  10.1016/j.ejor.2013.03.005
    [26] Zheng X L, Wang L. A multi-agent optimization algorithm for resource constrained project scheduling problem. Expert Systems with Applications, 2015, 42(15-16): 6039-6049 doi:  10.1016/j.eswa.2015.04.009
    [27] Lim A, Ma H, Rodrigues B, Tan S T, Xiao F. New meta-heuristics for the resource-constrained project scheduling problem. Flexible Services and Manufacturing Journal, 2013, 25(1-2): 48-73 doi:  10.1007/s10696-011-9133-0
  • [1] 许美玲, 王依雯. 基于改进差分进化和回声状态网络的时间序列预测研究[J]. 自动化学报, 2019, 45(): 1-9. doi: 10.16383/j.aas.c180549
    [2] 陆志强, 刘欣仪. 考虑资源转移时间的资源受限项目调度问题的算法[J]. 自动化学报, 2018, 44(6): 1028-1036. doi: 10.16383/j.aas.2017.c160834
    [3] 张英杰, 龚中汉, 陈乾坤. 基于免疫离散差分进化算法的复杂网络社区发现[J]. 自动化学报, 2015, 41(4): 749-757. doi: 10.16383/j.aas.2015.c140018
    [4] 周晓根, 张贵军, 郝小虎. 局部抽象凸区域剖分差分进化算法[J]. 自动化学报, 2015, 41(7): 1315-1327. doi: 10.16383/j.aas.2015.c140680
    [5] 高维尚, 邵诚. 复杂非凸约束优化难题与迭代动态多样进化算法[J]. 自动化学报, 2014, 40(11): 2469-2479. doi: 10.3724/SP.J.1004.2014.02469
    [6] 徐汉川, 徐晓飞. 考虑资源置信度的跨企业项目鲁棒性调度算法[J]. 自动化学报, 2013, 39(12): 2176-2185. doi: 10.3724/SP.J.1004.2013.02176
    [7] 陈荣元, 林立宇, 王四春, 秦前清. 数据同化框架下基于差分进化的遥感图像融合[J]. 自动化学报, 2010, 36(3): 392-398. doi: 10.3724/SP.J.1004.2010.00392
    [8] 罗毅平, 夏文华, 刘国荣, 邓飞其. 时滞分布参数控制系统指数镇定的LMI方法[J]. 自动化学报, 2009, 35(3): 299-304. doi: 10.3724/SP.J.1004.2009.00299
    [9] 胡蓉, 钱斌. 一种求解随机有限缓冲区流水线调度的混合差分进化算法[J]. 自动化学报, 2009, 35(12): 1580-1586. doi: 10.3724/SP.J.1004.2009.01580
    [10] 李祖欣, 王万良, 成新民. 资源约束网络的优化带宽调度[J]. 自动化学报, 2009, 35(4): 443-448. doi: 10.3724/SP.J.1004.2009.00443
    [11] 陈海永, 王宏. 基于LMI的参数随机变化系统的概率密度函数控制[J]. 自动化学报, 2007, 33(11): 1216-1220. doi: 10.1360/aas-007-1216
    [12] 刘士新, 宋健海, 唐加福. 基于关键链的资源受限项目调度新方法[J]. 自动化学报, 2006, 32(1): 60-66.
    [13] 翟桥柱, 管晓宏, 郭燕, 孙岚, 范炜. 具有混合动态约束的生产系统优化调度新算法[J]. 自动化学报, 2004, 30(4): 539-546.
    [14] 毛宁, 陈庆新, 陈新. 支持虚拟企业建立的项目优化调度算法[J]. 自动化学报, 2001, 27(3): 387-391.
    [15] 潘红华, 苏宏业, 褚健. 自适应预测函数控制[J]. 自动化学报, 2000, 26(增刊B): 11-15.
    [16] 李为民, 黄田, D.J.Whitehouse. 数控铣削过程有约束广义预测控制解析算法[J]. 自动化学报, 1999, 25(6): 796-799.
    [17] 曾理, 王又钧. 用于数控机床的变参数控制系统[J]. 自动化学报, 1987, 13(3): 239-240.
    [18] 汪朝群. 带有不确定参数控制系统的模糊控制器设计[J]. 自动化学报, 1983, 9(4): 311-315.
    [19] 徐凤安. 高阶无静差采样控制系统的动态综合[J]. 自动化学报, 1982, 8(2): 154-162.
  • 加载中
图(4) / 表(5)
计量
  • 文章访问数:  1154
  • HTML全文浏览量:  103
  • PDF下载量:  28
  • 被引次数: 0
出版历程
  • 收稿日期:  2017-12-25
  • 录用日期:  2018-07-05
  • 刊出日期:  2020-02-20

资源约束项目的改进差分进化参数控制及双向调度算法

doi: 10.16383/j.aas.c170728
    基金项目:

    国家重点研发计划 2017YFB1304000

    上海市科学技术委员会科研计划项目 17DZ2283800

    作者简介:

    项前  东华大学机械工程学院副教授.主要研究方向为计算机集成制造系统, 计算智能. E-mail:xqsir@dhu.edu.cn

    吕志军   东华大学机械工程学院副教授.主要研究方向为专家系统, 智能检测.E-mail: lvzj@dhu.edu.cn

    通讯作者: 周亚云   东华大学机械工程学院硕士研究生.主要研究方向为计算机集成制造系统.本文通信作者.E-mail: zhouyayun@mail.dhu.edu.cn
  • 本文责任编委 付俊

摘要: 针对资源约束项目调度组合优化难题, 提出一种改进的动态差分进化参数控制及双向调度算法.通过参数时变衰减与个体优劣评价, 自适应控制个体进化参数, 提高算法的收敛性能、勘探与开发最优解的能力; 基于动态差分进化(Dynamic differential evolution, DDE), 提出一种双向调度算法, 使用满足任务时序约束的优先数编码、交替正向反向调度, 结合标准化编码调整与精英保留的种群随机重建策略, 建立了一种高效稳健的双向编码调整机制.通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试, 并与其他文献算法比较最优解平均偏差率, 验证了所提算法的有效性与优越性.

本文责任编委 付俊

English Abstract

项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法. 自动化学报, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
引用本文: 项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法. 自动化学报, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
XIANG Qian, ZHOU Ya-Yun, LV Zhi-Jun. Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project. ACTA AUTOMATICA SINICA, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
Citation: XIANG Qian, ZHOU Ya-Yun, LV Zhi-Jun. Improved Differential Evolution Parameter Control and Bidirectional Scheduling Algorithm for the Resource-constrained Project. ACTA AUTOMATICA SINICA, 2020, 46(2): 283-293. doi: 10.16383/j.aas.c170728
  • 资源约束项目调度问题(Resource-constrained project scheduling problem, RCPSP)是指在满足项目资源约束及项目任务开始时间顺序约束的前提下, 以项目的最小工期为目标, 安排最优的任务开始时间. RCPSP广泛存在于企业的设计、制造、生产管理等活动中, 属于组合优化难题, 倍受国内外学者关注.

    目前求解RCPSP的算法主要分三类[1]:适用于小规模、复杂度低的精确算法; 基于调度优先规则的启发式算法, 效率高但质量难以保证; 具有较好鲁棒性的元启发式算法, 如遗传算法、粒子群算法、蚁群算法、模拟退火、禁忌搜索、差分进化等, 适合于求解大规模组合优化问题.多年来, 以进化与群体智能为主的RCPSP元启发式算法研究不断涌现, 在个体编码表示、调度方案生成、进化机制改进、与其他算法结合使用等方面, 国内外学者进行了大量的研究, 并且积累了丰富的问题实例, 形成了著名的项目调度问题标准库(Project scheduling problem library, PSPLIB)[2]. Hartmann[3]较早地基于遗传算法, 研究了任务染色体表示、自适应进化参数控制及调度方法.邓林义等[4]通过优先规则粒子群表示与更新机制, 搜索优先规则和调度方案的最优组合.戴月明等[5]使用粒群算法, 通过优先数粒子表示与双向协同震荡搜索机制, 提升调度算法性能. Gonzalez-Pardo等[6]基于蚁群算法, 结合珊瑚礁优化算法控制搜索过程中产生的信息素, 取得满意的调度解. Munlin等[7]通过适应性变异与双向调整[8], 提出一种求解RCPSP的扩展粒子群算法(Hybrid radius particle swarm optimization, H-RPSO). Zamani[9]结合隐式枚举搜索加速技术, 使用遗传算法求解RCPSP. Paraskevopoulos等[10]通过存储每个任务的调度历史, 提出一种具有学习机制的响应式变量邻近搜索算法(Reactive variable neighbourhood search, ReVNS).黄志宇[11]将调度解量子表示方法与进化算法融合, 有效地提高了全局寻优能力.陆志强等[12]建立考虑资源转移时间RCPSP模型, 提出内嵌分支定界法的遗传算法, 在保证全局搜索能力的前提下提升局部搜索能力. Koulinas等[13]提出的RCPSP超启发式算法与Elsayed等[14]提出的组合式优化算法, 灵活地发挥了多种元启发式算法的优势, 算法在高层自适应优选元启发式算法种类及其算子, 在低层使用具体的元启发算法进行求解, 提高了算法的鲁棒性与解的质量.

    除了以上算法以外, 近年来, 差分进化算法(Differential evolution algorithm, DE)因其卓越的优化性能受到广泛关注, 其应用范围越来越广, 研究问题主要集中在单目标约束与无约束、大规模、多目标、动态优化以及与其他优化算法混合使用等[15-16].研究显示, DE算法已逐渐成为RCPSP研究的有力工具之一, Cheng等[17]在DE中使用混沌技术避免种群早熟, 使用模糊聚类技术加速算法收敛, 通过2个小规模任务案例测试, 验证了算法的有效性. Ali等[18]提出了一种个体优先数编码调整及改进变异操作的DE算法, 通过项目调度标准库PSPLIB中部分实例测试, 验证了算法的优越性能.然而, 与遗传算法、粒子群算法相比, 运用DE进行RCPSP的研究还相对较少[19].目前DE的相关理论分析还不够完善, 缺乏严谨的数学解释, 算法的性能优劣很大程度上取决于其控制参数的选择, 标准DE中, 通常依赖经验选择固定的变异缩放因子$F$与交叉概率$CR$等, 难以应对如PSPLIB中的不同实例问题.长期以来, DE进化参数适应性控制与算子改进一直是研究热点[16], Brest等[20]提出改进DE算法, 引入两个控制参数$\tau_1, \tau_2$来随机调整$F$和$CR$的值. Qin等[21]提出SaDE (Self-adaptive differential evolution)算法, 参考历史优质解的经验, 自适应选择变异策略, 自适应调整服从正态分布的$F$和$CR$, 平衡了算法对优质解的搜索与开发能力. Zhang等[22]提出DE/current-to-pbest变异策略, 建立了较差解的外部存档, 进化中自适应更新$F$与$CR.$

    综上所述各种元启发式算法, 在算法机制改进方面, 通常需要对算法参数或操作算子进行适应性调整, 或者与其他算法组合使用; 在个体编码方面, 需要充分利用问题自身的特征, 以减少对编码空间的贪婪搜索, 提高算法的收敛性能与求解质量.因此, 针对RCPSP, 本文提出一种改进的动态差分进化参数控制及双向调度算法, 通过参数时变衰减与个体优劣评价, 自适应控制个体进化参数, 设计满足时序约束的任务优先数编码与双向调度算法, 建立避免算法早熟的种群重建机制, 以提高算法的求解质量与收敛性能.通过PSPLIB中实例集测试与分析, 验证所提算法有效性.

    • 经典RCPSP中, 单个项目包括$ n $个任务或活动, 记$ s_i $为任务$ i $的开始时间, $ d_i $为任务$ i $的消耗工时$ (i = 1, 2, \cdots, n) $, $ r_{ik} $为任务$ i $对第$ k $类资源的需求量, $ R_k $为第$ k $类资源的总量$ (k = 1, 2, \cdots, K) $, 任务1和任务$ n $是虚拟任务, 分别代表项目的开始和结束, 且不消耗时间和资源, 即$ s_1 = 0 $, $ d_1 = d_n = 0 $, $ r_{1k} = r_{nk} = 0 $.对应的数学优化模型为

      $$ \begin{equation} {\pmb S} = (s_1, s_2, \cdots, s_n) \end{equation} $$ (1)
      $$ \begin{equation} \begin{split} {\rm min}\ f({\pmb S}) = \ &{\rm max}\{e_i\}, \ e_i = s_i+d_i, \\ &i = 1, 2, \cdots, n \end{split} \end{equation} $$ (2)
      $$ \begin{equation} {\rm s.t.}\ s_i\geq s_j+d_j, \ j\in P_i, \ i = 1, 2, \cdots, n \end{equation} $$ (3)
      $$ \begin{equation} \sum\limits_{i\in A(t)}^{\ } r_{ik}\leq R_k, \ k = 1, 2, \cdots, K, \ t\geq 0 \end{equation} $$ (4)

      其中, 式(1) $ {\pmb S} $为各任务开始时间$ s_i $组成的解向量; 式(2) $ f $为目标函数, 表示使所有任务完成的总工期最小, $ e_i $为任务$ i $的结束时间; 式(3)表示各任务开始时间顺序约束, 表示任务$ i $必须在其所有前序任务$ j $完成后才能开始执行, $ P_i $为任务$ i $的前序任务集合, $ s_j $为任务$ j $的开始时间, $ d_j $为任务$ j $的消耗工时; 式(4)为资源约束, 表示任务$ i $在执行中任一时刻$ t $对资源$ k $的使用量不超过许可用量$ R_k $, 其中$ A(t) $为$ t $时刻进行的任务集合.

    • 动态差分进化(Dynamic differential evolution, DDE)参数自适应控制方法包括两点:基于动态差分进化机制, 每代进化中及时更新目标个体动态产生新种群, 可加速算法收敛; 综合考虑参数衰减与个体目标值优劣评价, 自适应控制个体变异与交叉参数, 能有效控制种群的搜索与开发能力.

    • 标准差分进化算法中, 目标个体$ i $表示为矢量$ {\pmb X}_i^t = (x_{i1}^t, x_{i2}^t, \cdots, x_{in}^t), \; i = 1, 2, \cdots, NP $, 其中, $ NP $为种群规模, $ n $为优化变量个数, $ t $为进化代数.随机初始化种群后开始迭代进化过程, 如式(5)所示, 第$ t $代目标个体$ {\pmb X}_i^t $进行变异生成变异矢量$ {\pmb V}_i^t = (v_{i1}^t, v_{i2}^t, \cdots, v_{in}^t) $, 其中, 下标索引$ r_1 $, $ r_2 $, $ r_3 $为从集合$ \{1, 2, \cdots, NP\} $中随机选择的互不相同的整数, 且不等于目标个体的索引$ i $, 缩放因子$ F $作用是对扰动量$ {\pmb X}_{r_2}^t-{\pmb X}_{r_3}^t $进行比例缩放, 即控制个体的搜索范围.

      $$ \begin{equation} {\pmb V}_i^t = {\pmb X}_{r_1}^t+F({\pmb X}_{r_2}^t-{\pmb X}_{r_3}^t) \end{equation} $$ (5)

      如式(6)所示, 变异矢量$ {\pmb V}_i^t $与个体$ {\pmb X}_i^t $使用二项式交叉产生试验矢量$ {\pmb U}_i^t = (u_{i1}^t, u_{i2}^t, \cdots, u_{in}^t) $, 使得试验矢量至少有一个维度分量由变异矢量$ {\pmb V}_i^t $贡献, 其中, $ j = 1, 2, \cdots, n $, 随机整数$ j_{\rm rand}\in[1, n] $, 交叉率$ CR\in(0, 1) $.

      $$ u_{ij}^t = \left\{ {\begin{array}{*{20}{l}} {v_{ij}^t,}&{{\mathop{\rm rand}\nolimits} (0,1) \le CR或j = {j_{{\rm{rand }}}}}\\ {x_{ij}^t,}&{否则} \end{array}} \right. $$ (6)

      如式(7)所示, 个体选择阶段, 比较试验矢量$ {\pmb U}_i^t $与目标个体矢量$ {\pmb X}_i^t $的目标函数值, 挑选最优的进入下一代.

      $$ \begin{equation} {\pmb X}_i^{t+1} = \begin{cases} {\pmb U}_i^t, &\; \; f({\pmb U}_i^t)\leq f({\pmb X}_i^t)\\ {\pmb X}_i^t, &否则 \end{cases} \end{equation} $$ (7)

      标准DE每一代使用额外的存储空间缓存选择的个体, 当完成种群内所有个体的选择操作后, 才集体更新当前种群进入下一代.与标准DE的种群更新方式不同, 动态差分进化策略[23]选择的新个体及时替代旧目标个体, 并加入当前种群参与其他个体的进化.这种动态更新方式能及时利用新的进化成果, 从而加速了算法收敛.

    • 如式(8)所示, 给出了一种自适应参数控制方法, 在进化过程中考虑了参数时变衰减特性, 在种群内基于个体目标值的优劣, 对个体参数进行差异化调整与控制.

      $$ \begin{align} P_i(t) = P_{ l}+(P_{u}-&P_{ l})[\lambda\cdot\alpha(t)+(1-\lambda)\beta_{i})], \\ &0<\lambda<1 \end{align} $$ (8)
      $$ \begin{equation} \alpha(t) = \frac{T-t}{T} \end{equation} $$ (9)
      $$ \begin{equation} \beta_{i} = \begin{cases} \frac{f_i-f_{\rm min}}{f_{\rm max}-f_{\rm min}}, &\; \; f_{\rm max}\neq f_{\rm min}\\ 1, &否则 \end{cases} \end{equation} $$ (10)

      式$ (8)\sim(10) $中, $ P_i $表示个体$ i $参数$ F $或$ CR $; $ P_{u} $与$ P_{l} $分别代表参数$ F $或$ CR $值的上限与下限; $ \alpha(t) $是个体参数$ P_i $按进化代数$ t $线性衰减的系数; $ T $为允许最大进化代数; $ \beta_{i} $表示按目标函数值评价个体$ i $的优劣程度, $ \beta_{i}\in[0, 1] $, $ \beta_{i} $越小表示个体越优, 反之越差; $ \lambda $是对$ \alpha(t) $与$ \beta_{i} $加权平均的权重因子, 本文取$ \lambda = 0.5 $; $ f_i $为个体$ i $目标函数值, $ f_{\rm min} $为种群内最优(小)个体目标函数值, $ f_{\rm max} $为种群内最差(大)个体目标函数值.

      从进化过程来看, 种群进化初期一般希望具有较好的全局搜索能力, 而随着迭代次数的增加, 特别是在后期, 希望具有较好的局部开发能力.较大的$ F $产生扰动量大, 会扩大搜索范围, 较大的$ CR $会增加种群的多样性, 有利于全局搜索, 反之, 较小的$ F $会缩小搜索范围, 较小的$ CR $会减少种群的多样性, 这样虽会减缓进化, 但有利于稳定的局部开发.因此, 通过式(9)中的$ \alpha(t) $, 使用时变衰减的$ F $与$ CR $, 可以平衡搜索与开发能力.

      从个体在种群内的优劣表现来看, 在以最小化为目标的前提下, 目标函数值越小表示个体越优秀, 当个体目标函数值较小时, 希望算法更多地利用该优秀个体的信息进行局部开发, 需要使用较小的$ F $, 在该个体附近搜索较好解, 且使用较小的$ CR $, 增加当前优质解进入下一代的机会; 当个体目标函数值较大时, 应较少利用该个体信息, 使用较大的$ F $以扩大搜索范围, 增加获得更优解的机会, 且使用较大的$ CR $, 促进新个体结构产生, 增加种群多样性.因此, 通过式(10)中的$ \beta_{i} $, 个体根据自身目标函数值的优劣自适应调整参数, 有利于进化过程稳健地进行.

      根据以上分析, 与经典的参数控制方法相比, 考虑时变特性与个体优劣的自适应参数控制方法, 使种群获得稳健的搜索与开发能力, 减少了选择参数时的经验依赖性以及搜索时的盲目性, 有利于改进算法收敛性能.

    • 基于动态差分进化(DDE), 提出一种双向调度算法(Bidirectional scheduling algorithm), 建立了高效鲁棒的双向编码调整机制.使用满足时序约束的个体编码表示, 生成初始种群; 在交替的正向反向调度中引入标准化编码调整策略, 以减少冗余搜索并加速算法收敛; 采用精英保留的种群随机重建策略避免算法陷入局部最优, 进一步提高算法的求解质量与鲁棒性.

    • 初始种群采用随机数编码, 目标个体$ {\pmb X}_i $中任务$ k $的初始码值$ x_{ik}, \; k = 1, 2, \cdots, n $为0到1之间的随机数, 其大小表示任务$ k $的调度优先级, 越小表示越优先, 通过码值升序排列生成任务调度顺序.为了满足任务开始时间顺序约束, 需要对初始编码进行调整, 使任务$ k $的调度优先级高于其所有后继任务.以图 1为例, 任务有向图$ G $包括6个任务结点, 初始任务1和结束任务6为虚拟任务, 不消耗时间和资源, 对应于式(3)时序约束条件, 有向边表示任务之间的时序依赖关系, 根据RCPSP问题描述, 有向图$ G $中不存在任务循环依赖, 例如, 任务2的直接或间接后续任务是4、5、6.

      图  1  个体编码与任务调度顺序

      Figure 1.  Individual coding and task scheduling sequence

      算法1.满足时序约束的编码调整算法

      输入: $ n $个任务的有向图$ G $; 个体$ i $编码$ {\pmb X}_i = \{x_{ik}|k = 1, 2, \cdots, n\} $

      输出: 拓扑编码个体向量$ {\pmb X}_i $

      1: For 任务 $ k = 1 $ to $ \ n\ $ do

      2:   初始化任务$ k $的所有后继任务集合$ S = \emptyset $ (空集), 集合$ T = \{k\} $

      3:   Repeat

      4:    初始化临时空集合$ P = \emptyset $

      5:    For每个任务$ m\in T\ \ $do

      6:       从$ G $中搜索直接依赖于任务$ m $的任务集合$ S_m $

      7:      $ P\leftarrow P\cup S_m $

      8:    End For

      9:    $ S\leftarrow S\cup P $, $ T\leftarrow P $

      10:   Until $ T = \emptyset $

      11:   查找具有最小编码值的任务$ j\in S $, $ x_{ij} = {\rm min}\{x_{ir}|r\in S\} $

      12:   If$ \ \ x_{ik} > x_{ij} $ then 交换$ x_{ik} $与$ x_{ij} $

      13: End For

      14: Return $ {\pmb X}_i $

      个体用随机数数组表示, 任务编号对应于数组索引号.初始化种群时, 如果直接按照编码升序来重排任务编号, 那么生成的任务调度序列5-3-6-4-2-1将违背时序约束.因此, 在个体初始随机编码的基础上, 根据时序约束使用算法1进行编码调整, 形成满足时序约束的个体拓扑编码及任务调度序列1-3-2-4-5-6.除此以外, 变异与交叉操作产生的试验矢量, 由于随机性也可能不满足时序约束, 同样需要编码调整.

    • 从编码的随机性可以看出, 不同个体编码可能对应于同一个调度顺序, 即产生同一个调度解, 进化过程中会出现冗余搜索, 减缓寻优进程.因此, 在种群进化过程中, 采用一种简易的标准化编码调整策略, 具体思路是, 在个体评价产生调度可行解后, 对可行解中任务开始时间排序, 获得相应的任务执行顺序, 记任务$ i $的顺序号为$ k\; (k = 1, 2, \cdots, n) $, 则任务$ i $的标准化编码值为$ k/n $, 再使用此标准化编码调整原个体编码.该算法的优点是, 使得一个调度顺序或调度解对应于一种个体编码模式, 从而在进化过程中会不断缩小种群搜索空间, 加速DE算法的收敛.存在的缺点是, 个体标准化编码会降低种群的多样性, 易导致算法收敛早熟, 这一缺点会通过第3.4节中的技术得以补偿, 第4.1节中将对其效果进行验证.

    • 调度算法实质是对个体评价的过程, 即将编码转化为任务开始时间与项目总工期.首先, 个体编码映射为一个任务调度序列, 其次, 在满足式(3)与式(4)约束条件下, 使用串行调度策略逐个安排任务的开始时间, 最终, 按式(2)目标函数求得项目总工期.

      正向调度(Forward scheduling)指先安排前序任务再安排后继任务的调度方式.如图 1所示, 从虚任务1开始, 设置开始时间为$ s_1 = e_1 = 0 $, 根据任务调度顺序列1-3-2-4-5-6, 依次追尾插入每个任务$ i\; (i = 3, 2, 4, 5, 6) $, 在满足时序与资源约束的前提下, 安排任务$ i $的最早开始时间$ s_i = s_k+d_k $, 即任务$ i $的某个紧前任务$ k $的结束时间, 插入完毕后, 计算项目总工期为$ {\rm max}\{e_i = s_i+d_i\}-s_1 $, 开始时间$ s_i $按照任务编号升序排列成的向量, 生成对应于个体$ m $的一个可行调度解$ {\pmb S}_m = (s_{m1}, s_{m2}, \cdots, s_{mn}) $.

      反向调度(Backward scheduling)与正向调度的求解方向相反, 仍以图 1问题为例, 反向调度从调度序列1-3-2-4-5-6中最后一个任务$ n = 6 $开始, 设置任务$ n $的结束时间$ e_n = s_n = 0 $, 在满足时序与资源约束的前提下, 倒序逐个安排任务$ i\; (i = 5, 4, 2, 3, 1) $的最晚结束时间$ e_i = s_k $, 即任务$ i $的某个紧后任务$ k $的开始时间, 从而求得任务$ i $开始时间$ s_i = e_i-d_i $, 考虑到$ s_i $会出现负值, 在获得所有任务开始时间后, 通过$ s_i = s_i-{\rm min}\{s_i\}, i = 1, 2, \cdots, n $, 对$ s_i $进行修正使得$ s_i\geq0 $.除调度顺序引起的变化之外, 反向调度中目标总工期及可行调度解的算法与正向调度相同.

      根据Valls等[8]研究, 交替正向与反向调度, 通过双向编码调整可开发出更优的解, 但这样也意味着每个个体评价耗时更多.因此, 在交替正向反向调度中引入标准化编码调整策略, 从而兼顾求解质量与效率.基本思路如算法2所述, 通过交替进行正向与反向调度算法, 每次正(反)向调度完成后, 使用标准化编码方法, 将调度生成的开始时间解转化为标准化编码, 临时存储该标准码, 作为下一轮反(正)向调度的个体编码输入, 重复以上过程, 如果交替求解中能得到改进解, 即更短的项目总工期, 那么继续正反向交替调度, 否则退出循环, 在循环结束时, 使用标准化编码更新原个体码值.

      算法2.双向编码调整算法

      输入: 个体编码矢量$ {\pmb X}_i^t $

      输出: 调度解$ {\pmb S}_i^t = (s_1^t, s_2^t, \cdots, s_n^t) $以及总工期(目标值$ objective $)

      1:初始化计数变量$ k = 0 $, 临时向量$ {\pmb p} = {\pmb X}_i^t $, 目标值$ objective = +\infty $

      2: Repeat do

      3:    If$ \ \ k $为偶数$ \ $then

      4:     forward$ ({\pmb p}, out\ {\pmb S}_i^t, out\ objVal) $//正向调度

      5:    Else

      6:     backward$ ({\pmb p}, out\ {\pmb S}_i^t, out\ objVal) $//反向调度

      7:    End$ \ \ $If

      8:    If$ \ \ objVal\geq objective\ \ $then break

      9:    $ objective = objVal $

      10:   $ {\pmb p} = $ standardize$ ({\pmb S}_i^t)\ $//参见第3.2节标准化编码

      11:   $ k++ $

      12: End Repeat

      13: $ {\pmb X}_i^t = {\pmb p}\ // $个体编码标准化更新

    • 动态差分进化到一定代数后, 个体的多样性会下降易产生早熟现象.为了避免算法过早地停滞于局部最优解, 需要增加种群的多样性扩大搜索空间, 提高全局寻优能力.避免陷入局部最优的策略是, 在不超过最大迭代代数的范围内, 当种群个体平均目标函数值$ f_{\rm avg} $与种群最小目标函数值$ f_{\rm min} $之间差异$ \varepsilon = f_{\rm avg}-f_{\rm min} $很小, 而且最优目标值持续未改进超过一定代数时, 保留部分当前精英个体, 如保留排名前10$ \% $的优质个体, 对其他个体进行随机编码重建, 使得大部分个体逃离原先的生存地开辟新的搜索进程, 从而提高了算法的全局寻优能力与鲁棒性.

    • 本文算法的基本流程如图 2所示, 具体步骤如下:

      图  2  动态差分进化参数控制及双向调度算法流程图

      Figure 2.  Flowchart of DDE parameter control and bidirectional scheduling algorithm

      步骤1. 设置种群规模为$ NP $, 允许最大进化代数为$ T $, 初始迭代计数器变量$ t = 0 $; 初始化种群, 个体矢量的维数等于调度任务数$ n $, 每个个体先进行随机数编码, 再采用算法1进行编码调整;

      步骤2. 按照第3.3节中算法2, 计算种群中每个个体$ {\pmb X}_i^t $的目标函数值$ f({\pmb X}_i^t) $, 并获得对应的调度任务开始时间解$ {\pmb S}_i^t $, 根据目标值大小, 统计种群获得当前最优个体$ {\pmb X}_{\rm best}^t $、调度解$ {\pmb S}_{\rm best}^t $及最优目标值$ f_{\rm min} $ (即项目最短总工期, 以下亦简称为最优解);

      步骤3. 开始循环迭代, 判断是否满足终止条件, 即如果$ t $大于$ T $, 或者达到已知最优解(适用于已知最优解的测试实例), 或者全局最优解停滞未改进代数超过了上限$ M_1 $ (适用于最优解未知的问题, 如$ M_1 = 300 $代), 则退出循环至步骤8, 否则, 进行下一步;

      步骤4. 对种群中每一个个体$ {\pmb X}_i^t $循环执行步骤4.1~4.4, 生成第$ t+1 $代种群;

      步骤4.1. 从种群中随机抽取3个不同个体, 按式(8)获得动态自适应缩放因子$ F_i $, 按式(5)进行变异操作, 生成变异个体$ {\pmb V}_i^t $;

      步骤4.2. 按式(8)获得动态自适应交叉概率$ CR_i $, 按式(6)进行交叉操作, 生成试验个体$ {\pmb U}_i^t $;

      步骤4.3. 采用算法1对试验个体$ {\pmb U}_i^t $进行编码调整, 并且计算目标函数值$ f({\pmb U}_i^t) $, 获得调度解$ {\pmb S}_i^t $;

      步骤4.4. 按照式(7)进行选择操作生成下一代个体$ {\pmb X}_i^{t+1} $, 动态更新个体$ {\pmb X}_i^t $;

      步骤5. 根据目标值大小, 统计种群获得最优个体$ {\pmb X}_{\rm best}^{t+1} $、调度解$ {\pmb S}_{\rm best}^{t+1} $、种群最优目标值$ f_{\rm min} $、以及种群平均目标函数值$ f_{\rm avg} $;

      步骤6. 如果$ f_{\rm avg}-f_{\rm min}\leq\varepsilon, \; \varepsilon = 0.1 $, 且停滞未改进代数达到上限$ M_2\; (M_2 < M_1 $, 如$ M_2 = 100 $代), 则按第3.4节算法保留前$ 10 \% $精英个体, 其余个体重新随机创建, 并且重新评价和统计种群, 否则, 维持种群不变.

      步骤7. 令$ t = t+1 $, 转步骤3.

      步骤8. 输出当前种群最优个体$ {\pmb X}_{\rm best}^t $、调度解$ {\pmb S}_{\rm best}^t $及最优目标值$ f_{\rm min} $.

    • 为了验证本文所提自适应DDE参数控制与双向调度等算法, 采用项目调度标准库PSPLIB中2 040个RCPSP实例, 测试算法效果. PSPLIB按照项目任务数30、60、90、120, 分别设置了J30 (480个实例)、J60 (480个实例)、J90 (480个实例)、J120 (600个实例)四个系列.鉴于仅J30使用精确算法给出了全部最优解, 而J60、J90、J120只给出了部分实例的最优解下界, 因此, 先使用J30实例集测试所提算法有效性, 再使用J30、J60、J90、J120验证与比较算法性能.

    • 表 1所示, 设计了8种测试方案, 统一设置种群规模为50, 允许最大进化代数$ T = 1 000 $, 即最大调度求解次数不超过50 000;最大停滞代数$ M_1 = 1 000 $, $ M_2 = 100 $; 除方案1使用标准DE以外, 其余方案$ 2\sim8 $都使用动态差分进化(DDE); 方案$ 1\sim2 $采用相同的固定参数, 设置缩放因子$ F $为0.5、交叉概率$ CR $为0.5;方案3参照文献[21]的参数控制算法, 缩放因子$ F $服从均值为0.5、标准差为0.3的正态分布N $ (0.5, 0.3^2) $, 交叉概率$ CR $服从均值为0.5、标准差为0.1的正态分布N $ (0.5, 0.1^2) $; 方案$ 4\sim8 $采用本文提出的参数自适应调整方法, 缩放因子$ F = 0.1\sim2.0 $, 交叉概率$ CR = 0.1\sim0.95 $.试验计算机配置为Intel® Core$ ^{\rm TM} $/i5CPU/2.2 GHZ/4 GB内存, Windows10操作系统, 使用C#、Matlab作为编程及分析工具.

      表 1  J30系列不同测试方案结果比较

      Table 1.  Comparison of the results by different test schemes for J30

      方案 DE类型 参数控制 调度算法 避免局部最优 标准化编码 平均偏差率
      $av\_dev\, (\%)$ bh
      成功率
      $success\, (\%)$
      平均代数
      $av\_gen$
      平均CPU时间
      $CPUTime$ (s)
      平均值 标准差
      1 DE 固定 正向 0.143 0.013 92.40 109 4.59
      2 DDE 固定 正向 0.143 0.021 92.42 90 2.54
      3 DDE 正态分布[21] 正向 0.142 0.015 92.46 89 2.62
      4 DDE 自适应 正向 0.050 0.011 96.94 53 1.56
      5 DDE 自适应 双向 0.027 0.005 98.25 27 2.22
      6 DDE 自适应 双向 0.065 0.013 96.00 44 1.14
      7 DDE 自适应 双向 0.016 0.005 98.90 22 1.91
      8 DDE 自适应 双向 0.008 0.003 99.35 13 0.93

      类似于其他RCPSP研究中算法性能测评方法, 对于单个实例测试, 主要使用偏差率$ dev_i $评价算法准确性; 对于标准实例集系列, 主要使用平均偏差率$ av\_dev $、成功率$ success $评价算法性能.每个试验方案中, 每实例独立测试次数$ J = 10. $

      $$ \begin{equation} dev_i = \frac{BS_i-LB_i}{LB_i}\times100 \% \end{equation} $$ (11)
      $$ \begin{equation} av\_dev = \frac{1}{N}\sum\limits_{i = 1}^Ndev_i\times100 \% \end{equation} $$ (12)
      $$ \begin{equation} success = \frac{1}{J}\sum\limits_{j = 1}^J\frac{C_j}{N}\times100 \% \end{equation} $$ (13)

      式$ (11)\sim(13) $中, 偏差率$ dev_i $是单个实例$ i $目标解与已知最优解之间的相对误差, 平均偏差率$ av\_dev $是测试实例集中所有偏差率的平均值, 成功率$ success $是求解正确的实例数百分比.其中, $ i = 1, 2, \cdots, N, N $为测试实例总数, 如测试J30时$ N = 480 $; $ BS_i $为求解实例$ i $的目标最短工期; 值得注意的是, 对于J30系列, $ LB_i $为实例$ i $已知最优解, 对于J60、J90、J120系列, $ LB_i $为已给出的实例$ i $最优解或下界, 若尚未给出最优解或下界, $ LB_i $则取无资源约束时实例$ i $的最短工期; $ C_j\; (j = 1, 2, \cdots, J) $为第$ j $次测试时$ BS_i $等于$ LB_i $的实例数.除以上性能指标以外, 使用平均代数$ av\_gen $与平均CPU时间$ CPUTime $, 即平均每实例每次测试所需进化代数与运行时间, 来评价算法效率.

      表 1所示, 平均偏差率、成功率、平均代数及平均CPU时间等测试指标值, 反映了不同试验方案的算法性能.为了检验任意两个不同方案间性能差异是否显著, 针对关键性能指标平均偏差率, 设计双总体t检验, 显著性水平$ \alpha = 0.05 $, 零假设H0为两者平均偏差率相同, 备择假设H1为两者平均偏差率不同.如表 2所示, 三角矩阵行列序号表示方案代号, 单元格值为接受零假设H0的概率, 概率值越大表示对应两个方案间差异越小, 概率值越小表示对应两个方案间具有显著差异.

      表 2  显著性水平($\alpha=0.05)$下平均偏差率双总体t检验

      Table 2.  Paired-sample t-test of the average deviation rate at the significance level of 0.05

      1 2 3 4 5 6 7 8
      1 1
      2 $\textbf{0.983}$ 1
      3 $\textbf{0.939}$ $\textbf{0.937}$ 1
      4 1.34$\, \times 10^{-12}$ 3.83$\, \times 10^{-10}$ 4.66$\, \times 10^{-12}$ 1
      5 6.69$\, \times 10^{-16}$ 1.98$\, \times 10^{-12}$ 4.33$\, \times 10^{-15}$ 1.38$\, \times 10^{-5}$ 1
      6 8.97$\, \times 10^{-11}$ 1.16$\, \times 10^{-8}$ 2.63$\, \times 10^{-10}$ 1.18$\, \times 10^{-2}$ 8.02$\, \times 10^{-8}$ 1
      7 1.30$\, \times 10^{-16}$ 4.06$\, \times 10^{-13}$ 8.40$\, \times 10^{-16}$ 5.81$\, \times 10^{-8}$ 3.64$\, \times 10^{-5}$ 1.50$\, \times 10^{-9}$ 1
      8 $ {\bf{2}}.{\bf{83}}\times {\bf{1}}{{\bf{0}}^{ - {\bf{17}}}}$ $ {\bf{1}}.{\bf{25}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{13}}}}$ $ {\bf{2}}.{\bf{03}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{16}}}}$ $ {\bf{1}}.{\bf{53}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ ${\bf{4}}.{\bf{69}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{9}}}}$ $ {\bf{9}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{11}}}}$ $ {\bf{5}}.{\bf{62}} \times {\bf{1}}{{\bf{0}}^{ - {\bf{4}}}}$ 1

      分析各方案试验结果, 从表 1~2图 3中可以看出:

      图  3  J30系列不同DE方案性能比较

      Figure 3.  Comparison of the performance by different DE schemes for J30

      1) 比较方案1、2、3, 三者的平均偏差率、成功率基本相同或相近, 表 2中三者之间t检验接受零假设的概率值都超过$ 92 \% $, 从运行效率来看, 方案2、3的平均代数与平均CPU时间接近, 比方案1的效率高.由此表明, DDE与DE相比, 随机调整参数与固定参数相比, 都不能降低平均偏差率与提高成功率, 但方案2、3中DDE有助于加速算法收敛.

      2) 方案4与方案$ 1\sim3 $相比, 同样使用正向调度, 方案4使用了本文的DDE自适应参数控制方法.从求解质量来看, 方案4平均偏差率为$ 0.05 \% $, 成功率达到$ 96 \% $以上, 显著优于方案$ 1\sim3 $; 从获得最优解平均代数以及平均CPU时间来看, 方案4也比方案$ 1\sim3 $效率高.相比于方案$ 1\sim3 $的固定或随机调整参数策略, 方案4采用控制参数时变衰减, 平衡了全局搜索与局部开发能力; 基于个体目标值优劣评价, 实现个体参数差异化设置, 使个体能够更合理有效地搜索, 一定程度地克服了参数设置的经验性与个体搜索时的盲目性, 因此, 算法性能获得了显著提高.

      3) 方案5与方案4相比, 除调度算法不同之外, 其他参数设置相同.方案5使用交替正向反向调度, 平均偏差率为$ 0.027 \% $与成功率为$ 98.25 \% $, 均显著优于方案4.获得最优解的平均代数比方案4减少了约$ 50 \% $, 加快了进化的进程, 由于每个个体双向调整比正向调度消耗更多的时间, 算法平均CPU时间比方案4稍高.

      4) 相比于方案5, 方案6在个体调度结束时运用了个体标准化编码调整, 平均偏差率为$ 0.065 \% $, 成功率为$ 96.00 \% $, 求解质量下降, 但时间却大幅减少.究其原因, 个体标准化编码调整减少了个体编码结构模式, 收缩了搜索空间, 有利于提高寻优效率, 但明显的弱点是易导致算法局部收敛, 部分测试实例的优化进程出现停滞现象, 因而导致最优解平均代数增加.

      5) 相比于方案5, 方案7采用避免局部最优的策略, 通过触发种群重建与搜索重试, 获得平均偏差率0.016$ \% $, 成功率98.90$ \% $, 求解效率(平均22代, 1.91 s).方案7性能优于方案5的主要原因是, 当种群多样性极低且未达到已知最优解时, 方案5会出现搜索停滞直至用尽最大进化代数; 同样条件下, 方案7可能触发种群重建, 对种群进行大幅扰动, 增加了种群多样性与找到最优解的机会, 迭代可能会在达到最大进化代数之前结束, 因此, 方案7有利于提高实例集整体求解质量与效率.方案7的平均偏差率比方案6低, 但由于没有使用标准化编码调整, 搜索效率比方案6略低(用时1.91 s).

      6) 进一步分析避免局部最优策略的效果, 统计试验数据发现, 方案7共有36个实例165次测试触发了种群重建机制, 这36个实例相对较难求解或解质量不稳定, 将其归为第I类, 第I类共$ 36\times10 = 360 $次测试, 其中约$ 165/360 = 46 \% $的样本触发了种群重建, 其余444个实例归为第II类.如表 3所示, 按照I、II类别比较方案5与7的求解性能, 在第I类比较中, 方案7获得比方案5更低的平均偏差率与平均代数, 表明种群重建机制取得成效; 在第II类比较中, 实例相对容易求解, 方案5与7均无种群重建, 因而两者获得相似的优越性能.然而, 由于第I类测试占总样本的比例过小$ (165/4 800 = 3.4 \%) $, 因此, 就总体平均代数而言, 表 1中方案7 (22代)比方案5 (27代)略少, 而且两者的平均代数都较少.

      表 3  方案5与方案7性能比较

      Table 3.  Comparison between scheme 5 and scheme 7

      Ⅰ类(36个实例) Ⅱ类(444个实例)
      平均偏差率 平均代数 平均偏差率 平均代数
      $av\_dev~(\%)$ $av\_gen$ $av\_dev~(\%)$ $av\_gen$
      方案5 0.346 285 0.001 6
      方案7 0.194 238 0.001 5

      7) 从表 13图 3可看出, 方案8综合了方案6与7的优势, 采用方案6中标准化编码调整策略, 减少了平均CPU时间, 兼用方案7中避免局部最优策略, 一定程度地弥补了标准化编码调整的不足, 提高了解的质量.方案8组合了文中所有的算法, 获得了最低的平均偏差率均值($ 0.008 \% $)及标准差($ 0.005 \% $), 最高的成功率($ 99.35 \% $), 以及最高的求解效率(平均13代, 0.93 s).由表 2也可见, 检验方案8与方案$ 1\sim7 $平均偏差率差异显著, 均以极低概率接受零假设H0.由此表明, 方案8算法的准确性与稳定性显著优于其他方案.

    • 为了观察与比较不同算法方案的收敛性能, 选择难度较高的j3013组10个问题实例, 分别测试方案1、4、5、8的算法性能, 每实例独立运行10次.

      图 4所示, 横坐标为进化代数$t$, 纵坐标为目标函数值, 纵轴起点为实例的已知最优解, 对于每个问题实例, 在500进化代数以内, 每方案每代取最优解的平均值绘制进化曲线.方案1使用标准DE, 方案4使用DDE与自适应参数调整, 除j3013_9以外, 在j3013_2、3、4、6、8、10中, 进化后期方案4收敛性能优于方案1, 而在j3013_1、5中, 方案4收敛比方案1差, 综合表 2中方案4平均偏差率优于1的评测结果, 表明方案4中使用自适应参数控制, 取得了较好的收敛性能; 方案5采用了双向调度, 收敛性能显著优于方案1和方案4, 并搜索到了更优解, 表明双向调度比正向调度具有更快的收敛速度; 方案8的双向调度同时采用了标准化编码调整及避免局部最优策略, 收敛速度最快, 解的质量最好, 性能也最稳定, 除j3013_5、6、9以外, 500代内均求出了最优解.在j3013_9中, 进化初期方案8收敛速度比方案1快, 后期略低于方案1.由此分析得出, 方案8的收敛性能表现最佳.

      图  4  J3013不同DE方案收敛性能比较

      Figure 4.  Comparison of the convergent performance by different DE schemes for J3013

    • 基于第4.1节与第4.2节的分析, 方案8可总结为一种使用自适应DDE的双向调度算法(Adaptive dynamic differential evolution based bidirectional scheduling, ADDE-BS), ADDE-BS基于DDE, 是综合使用参数自适应控制、标准化编码调整及避免局部最优等策略的双向调度算法, 能获得最小的平均偏差率与较好的算法效率, 其综合性能最佳.

      表 4所示, 采用ADDE-BS算法, 针对J30、J60、J90、J120四个系列全部实例, 按最大调度次数不超过5 000与50 000, 分别统计平均偏差率(保留到小数点后两位)、成功率以及平均CPU运行时间.结果显示, 最大调度次数不超过50 000时, J30平均偏差率很小且不超过$ 0.01 \% $, 对于$ 99 \% $以上的问题实例, 算法都能稳定求得PSPLIB给出的标准最优解.比较性能指标可发现, 算法性能随着问题规模的加大而下降, 对于J30、J60等中小规模问题, 调度50 000次比调度5 000次具有更好的解质量, 而对于J90、J120等大规模问题, 调度50 000次与调度5 000次的解质量差异较小, 表明J90、J120问题在超过5 000次调度以后, 算法获得改进解的能力基本达到极限, 开始产生冗余搜索, 并且消耗大量的CPU时间.

      表 4  ADDE-BS算法结果

      Table 4.  Results of ADDE-BS algorithm

      最大调度次数 5 000 50 000
      实例集 J30 J60 J90 J120 J30 J60 J90 J120
      $av\_dev~(\%)$ 0.04 1.32 2.88 25.37 $\textbf{0.01}$ 1.03 2.62 24.43
      $success~(\%)$ 97.44 79.58 76.67 30.00 $\textbf{99.35}$ 83.75 77.50 31.50
      $CPUTime$ (s) 0.40 6.78 16.24 86.92 $\textbf{0.93}$ 66.55 179.89 1 004.36
    • 表 5中收集了最近几年其他文献的RCPSP算法平均偏差率, 算法覆盖了遗传、差分进化、粒子群、蚁群、多Agent优化等.

      表 5  与其他文献算法平均偏差率(%)比较

      Table 5.  Comparison of average deviation rate (%) with art-of-state algorithms

      J30 J60 J90 J120
      5 000 50 000 5 000 50 000 5 000 50 000 5 000 50 000
      本文ADDE-BS $\textbf{0.04}$ $\textbf{0.01}$ $\textbf{1.32}$ $\textbf{1.03}$ $\textbf{2.88}$ $\textbf{2.62}$ $\textbf{25.37}$ $\textbf{24.43}$
      DE[18] 2016 0.00 0.00 0.98 2.07 4.04 8.81 19.62 31.68
      ACO CRO[6] 2017 - - 11.40 11.40 12.21 12.21 26.53 26.51
      COAs[14] 2017 0.00 0.00 10.77 10.58 - - 32.35 31.23
      GA-Part[9] 2017 0.07 0.01 11.08 10.71 - - 33.36 31.81
      Heuristic[24] 2017 0.09 0.03 11.31 10.91 - - 34.08 32.52
      ReVNS[10] 2016 0.01 0.00 11.10 10.88 - - 33.36 32.21
      H-RPSO[7] 2016 0.03 0.01 10.23 10.11 - - 31.94 30.25
      GA-MBX[25] 2013 0.04 0.00 10.94 10.65 - - 32.89 31.30
      MAOA[26] 2015 0.06 0.01 10.84 10.64 - - 32.64 31.02
      PSO-HH[13] 2014 0.04 0.01 11.13 10.68 - - 32.59 31.23
      HGA[27] 2013 0.07 0.01 11.14 10.63 - - 32.75 30.66
      ASH[27] 2013 0.11 0.03 11.33 10.85 - - 33.54 31.97

      对于J30实例集, 目前研究中平均偏差率已极低基本接近于零[6].表 4中各种RCPSP算法研究结果显示, 5 000次与50 000次调度计算规模以内, 本文J30问题平均偏差率0.01已处于排行榜前列, 值得注意的是, 同样使用DE算法的文献[18]中, J30的平均偏差率为0.00, 但由于其仅测试了部分实例(16个J30, J60、J90及J120各15个), 而且没有明确给出这些实例代号, 因此, DE算法效果比较仅供参考. 50 000次调度计算规模以内, 其他文献中, J60问题解偏差率介于$ 10 \%\sim12 \% $之间, J120问题解偏差率介于$ 26 \%\sim32 \% $之间, 本文的J60、J90、J120平均偏差率已显著低于其他文献结果.由此表明, 对于不同规模的RCPSP, ADDE-BS具有较好的泛化求解能力, 并显示出一定的优越性.

    • 本文提出一种改进的动态差分进化参数控制及双向调度算法求解RCPSP.采用动态差分进化参数自适应控制, 克服了难以确定最佳变异与交叉参数的缺点, 提高了算法的收敛性能; 采用满足时序约束的任务优先数编码, 进化过程中采用交替正反向调度与标准化编码调整策略, 提高了优质解的开发能力, 加速了寻优进程; 采用基于精英保留的种群随机重建策略避免了算法局部收敛, 进一步提高了算法的求解质量与鲁棒性.使用PSPLIB标准问题实例库对文中算法进行了大量测试, 验证了其有效性.经与其他文献比较, 本文提出的RCPSP求解算法具有一定的优越性.如何结合多种元启发式算法, 提高大规模RCPSP的求解性能, 是下一步的研究方向.

参考文献 (27)

目录

    /

    返回文章
    返回