摘要
针对资源受限项目调度问题,提出了一种新的双种群准粒子群算法。新算法基于粒子群的寻优原理,重新定义了粒子的位置更新公式,加入了多样性信息部分,并对公式中的位置差、标量与位置差的乘积以及位置和运算进行了重新定义。通过结合项目调度的问题特征,使用活动列表对粒子进行编码,设计一种新的双向路径重连实现位置的减法操作,使用选择实现位置差和标量的乘法操作,而使用均匀块交叉实现位置和操作,并提出正向粒子群和反向粒子群双种群并行进化的方式。通过实验设计的Taguchi方法求得了新算法的最优参数组合。对标准测试库PSPLIB的J30,J60和J120问题集和一个实际的装配项目案例进行了仿真测试,结果表明双种群准粒子群算法优于当前主要的基于粒子群的算法。通过与其他启发式算法进行比较,验证了算法的有效性。
To solve Resource-Constrained Project Scheduling Problem （RCPSP）, a new Double-Population Quasi Par- ticle Swarm Optimization （DPQ-PSO） was proposed. Based on the optimization principle of basic PSO, the position update formula was redefined by abandoning the velocity part and introducing a new component of diversity informa- tion. The subtraction between positions, the multiplication of a subtraction by scalar and the addition between posi- tions were also redefined. For the problem-specific characteristics of PCPSP, a particle was represented by an activi- ty list, and a new bidirectional path relinking was used to implement the subtraction. A selection operation was used to implement the scalar multiplication, and a new uniform block crossover was used to fulfill the addition. For the population diversity, a double-population parallel evolutionary mechanism was also incorporated in the algorithm. The Taguchi method of design-of-experiment was utilized to find out the best combinations of parameter values in DPQ-PSO. The simulation test for problem sets of J30, J60 and J120 in PSPLIB and a real assembly project case were conducted, and the results showed that DPQ-PSO was superior to the current PSO-based algorithms. The ef- fectiveness of proposed algorithm was also verified by comparing with some other heuristic algorithms.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2015年第9期2446-2457,共12页
Computer Integrated Manufacturing Systems
基金
国家科技支撑计划资助项目(2012BAF12B10)~~
关键词
资源受限项目调度
粒子群优化
双向路径重连
均匀块交叉
双种群进化
resource-constrained project scheduling particle swarm optimization bidirectional path relinking ~ uniformblock crossover^double-population evolution
