自适应混合蚁群算法在MRCPSP中的应用

计算机与现代化 ›› 2021, Vol. 0 ›› Issue (05): 38-43.

自适应混合蚁群算法在MRCPSP中的应用

(1.华北计算技术研究所系统三部，北京100083；2.华北计算技术研究所总体部，北京100083）

出版日期:2021-06-03 发布日期:2021-06-03
作者简介:闫森（1995—），男，山东菏泽人，硕士研究生，研究方向：计算机应用技术，E-mail: 13146076197@163.com；王玉玫（1962—），女，北京人，研究员，硕士生导师，研究方向：计算机应用技术，E-mail: wym_email@263.net。
基金资助:
国防科技创新特区H863计划项目（H863-01-zt-002-020）

Application of Improved Adaptive Hybrid Ant Colony Algorithm in MRCPSP

(1. Third Department of System, North China Institute of Computing Technology, Beijing 100083, China;

2. General Department, North China Institute of Computing Technology, Beijing 100083, China)

Online:2021-06-03 Published:2021-06-03

摘要/Abstract

摘要： 以多模式资源受限项目调度问题（Multi-mode Resource Constrained Project Scheduling Problem, MRCPSP）为背景，针对蚁群算法收敛速度和解的多样性之间的平衡问题，提出一种改进的自适应混合蚁群算法。该算法中参数的取值范围和变化幅度能够随算法的运行同步自适应调整，蚂蚁在取值区间内随机取参形成混合蚁群；在算法中引入先驱侦查蚁、带有排名因子的精英蚁群奖励机制和信息素上下限以优化信息素的更新策略。同时，对于MRCPSP问题中的工期不确定问题，基于模糊理论，利用该算法解出项目工期的估计值和模糊区间加以解决。最后，仿真结果表明，该算法与其他启发式项目调度优化算法相比，能够提高收敛速度和解的质量，较好地解决MRCPSP问题，因此有着较高的实际应用价值。

关键词: 自适应参数, 混合蚁群, 排名因子, 模糊理论

Abstract: Based on the background of Multi-mode Resource Constrained Project Scheduling Problem (MRCPSP), an adaptive hybrid ant colony algorithm is proposed to solve the balance problem between the convergence speed of ant colony algorithm and restraining the possibility of falling into the local optimum. The range of parameters can be adaptively adjusted synchronously with the operation of the algorithm and ants can obtain random parameter values in the parameter value range, forming a hybrid ant colony. The algorithm introduces the pioneer scout ant, reward mechanism of elite ant colony with ranking factor and upper and lower pheromone limits to optimize the pheromone update strategy. At the same time, the time uncertainty problem in MRCPSP can be solved by using this algorithm based on fuzzy theory. Finally, the simulation results show that, compared with other heuristic project scheduling optimization algorithms, this algorithm can improve the global search ability and the quality of solution, and better solve the MRCPSP problem, so it has higher practical application value.

Key words: adaptive parameter, hybrid ant colony, ranking factor, fuzzy theory

闫森, 王玉玫. 自适应混合蚁群算法在MRCPSP中的应用[J]. 计算机与现代化, 2021, 0(05): 38-43.

YAN Sen, WANG Yu-mei. Application of Improved Adaptive Hybrid Ant Colony Algorithm in MRCPSP[J]. Computer and Modernization, 2021, 0(05): 38-43.

参考文献［25］

［1］	POPPENBORG J, KNUST S. Modeling and optimizing the evacuation of hospitals based on the MRCPSP with resource transfers［J］. European Journal on Computational Optimization, 2016,4(3-4):349-380.
［2］	SPRECHER A, DREXL A. Solving multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm［J］. European Journal of Operational Research, 1998,107(2):431-450．
［3］	BUDDHAKULSOMSIRI J, KIM D S. Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting［J］. European Journal of Operational Research, 2007,178(2):374-390.
［4］	LING W, CHEN F. An effective shuffled frog-leaping algorithm for multi-mode resource-constrained project scheduling problem［J］. Information Sciences, 2011,181(20):4804-4822.
［5］	王为新,李原,张开富. 基于遗传算法的多模式资源约束项目调度问题研究［J］. 计算机应用研究, 2007(1):72-74.
［6］	黄少荣. 资源约束多模式项目调度的遗传算法研究［J］. 微电子学与计算机, 2011,28(9):165-168.
［7］	倪倩芸. 基于改进遗传算法的多模式资源受限项目调度问题研究［D］. 杭州：浙江工商大学, 2018.
［8］	MIKA M, WALIGRA G, W〖KG-3〗〖XCE.TIF;%90%90〗〖KG-8〗GLARZ J. Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models［J］. European Journal of Operational Research, 2005,164(3):639-668.
［9］	黄少荣. 折现流多模式资源约束项目调度问题研究［J］. 暨南大学学报(自然科学与医学版), 2015,36(4):357-362.
［10］	JARBOUI B, DAMAK N, SIARRY P, et al. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems［J］. Applied Mathematics and Computation, 2008,195(1):299-308.
［11］	陈龙,韩兆兰,崔健双. 求解多模式资源约束项目调度问题的离散粒子群算法［J］. 计算机应用, 2015,35(S2):101-105.
［12］	袁汪凰,游晓明,刘升. 动态学习机制的双种群蚁群算法［J］. 计算机科学与探索, 2019,13(7):1239-1250.
［13］	初梓豪,徐哲,李明,等. 随机多模式资源均衡问题建模与求解［J］. 工业工程, 2017,20(3):95-105.
［14］	张倩,王小胜,惠明晶. 工期-费用权衡问题的两个不确定机会约束规划模型［J］. 模糊系统与数学, 2020,34(3):70-78.
［15］	宁敏静,何正文,刘人境. 基于随机活动工期的多模式现金流均衡项目调度优化［J］. 运筹与管理, 2019,28(9):91-98.
［16］	LIU X F, ZHAN Z H, DENG J D, et al. An energy efficient ant colony system for virtual machine placement in cloud computing［J］. IEEE Transactions on Evolutionary Computation, 2018,22(1):113-128.
［17］	CHEN Z G, ZHAN Z H, LIU Y, et al. Multiobjective cloud workflow scheduling: A multiple populations ant colony system approach［J］. IEEE Transactions on Cybernetics, 2019,49(8):2912-2926.
［18］	ZHOU S Z, ZHAN Z H, CHEN Z G, et al. A multi-objective ant colony system algorithm for airline crew rostering problem with fairness and satisfaction［J］. IEEE Transactions on Intelligent Transportation Systems, 2020. DOI:10.1109/TITS.2020.2994-779.
［19］	MUTAR M L, BURHANUDDIN M A, HAMEED A S, et al. An efficient improvement of ant colony system algorithm for handling capacity vehicle routing problem［J］. International Journal of Industrial Engineering Computations, 2020,11(4):549-564.
［20］	刘中强,游晓明,刘升. 启发式强化学习机制的异构双种群蚁群算法［J］. 计算机科学与探索, 2020,14(3):460-469.
［21］	张永强,王晓东. 基于信息素更新和挥发因子调整改进蚁群算法［J］. 西安工程大学学报, 2016,30(3):400-404.
［22］	THOMAS S, HOOS H H. MAX-MIN ant system［J］. Future Generation Computer Systems, 2000,16(8):889-914.
［23］	黄少荣. 蚁群系统算法求解多模式资源约束项目调度问题［J］. 计算机应用与软件, 2012,29(8):153-155.
［24］	周袅,葛洪伟,苏树智. 基于信息素的自适应连续域混合蚁群算法［J］. 计算机工程与应用, 2017,53(6):156-161.
［25］	耿苏杰. 基于不确定性资源受限项目的预防调度研究［D］. 南京:南京理工大学, 2015.

[1]	姚征. 基于HISPAC医疗数据隐私保护模型[J]. 计算机与现代化, 2022, 0(09): 1-12.
[2]	蔡明，左勇安. 基于MapReduce的混合蚁群算法研究[J]. 计算机与现代化, 2016, 0(10): 6-.
[3]	王春刚. “质量工程”项目智能评价方法研究[J]. 计算机与现代化, 2011, 1(4): 142-144.
[4]	李波;阎浩. P2P网络中基于模糊理论的综合信任模型研究[J]. 计算机与现代化, 2011, 1(2): 0-64.