一种求解资源约束项目调度问题的改进引力搜索算法  

An improved gravitational search algorithm for solving resource constrained project scheduling problem

作　　者：刘永利[1] 张晓阳 LIU Yongli;ZHANG Xiaoyang(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,Henan,China)

机构地区：[1]河南理工大学计算机科学与技术学院,河南焦作454000

出　　处：《河南理工大学学报（自然科学版）》2022年第4期126-133,共8页Journal of Henan Polytechnic University（Natural Science）

基　　金：国家自然科学基金资助项目(61872126)。

摘　　要：引力搜索算法虽然具有较强的搜索能力和较快的收敛速度,但是容易陷入局部最优,且求解精度并不尽如人意。针对具有资源和优先关系约束的资源约束项目调度问题,提出一种改进的引力搜索算法(improved gravitational search algorithm, IGSA)。该算法将向心力和混沌机制引入引力搜索算法中,一方面通过在不同寻优阶段对参数进行控制,平衡算法中粒子的探索能力与开发能力,防止算法陷入局部最优,提高解的精度和加快收敛速度;另一方面当随机数大于混沌序列的值时,对生成的解决方案执行插入或交换操作,增强算法的多样性。为了评估算法的有效性,在PSPLIB问题实例J30,J60,J90和J120上进行对比实验,结果表明,相较于对比算法,IGSA在求解RCPSP时能更快更准确地得到项目最小完工时间,且能充分利用资源,避免资源浪费。Although gravitational search algorithm has strong search ability and fast convergence speed, it is easy to fall into local optimum, and its solution accuracy is not satisfactory. For resourceconstrained project scheduling problems with resource constraints and priority relationship constraints, an improved gravitational search algorithm was proposed. This algorithm introduced the concept of centripetal force and chaotic mechanism into the gravitation search algorithm. By controlling the parameters in different optimization stages, the exploration ability and exploitation ability of the particles could be well balanced, so as to be prevented from falling into the local optimum, and the accuracy and convergence speed of the solution could be improved. When the random number was greater than the value of the chaotic sequence, insert or swap operations were performed on the generated solutions to enhance the diversity. In order to evaluate the effectiveness of the improved algorithm, comparative experiments were carried out on PSPLIB examples J30,J60,J90 and J120. Experimental results showed that, compared with the comparative algorithms, the proposed algorithm could get the minimum project completion time more quickly and accurately, and could make full use of resources to avoid resource waste.

关 键 词：改进引力搜索算法 混沌机制 资源约束项目调度问题 向心力 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]