基于模拟遗传退火算法的RCPSP问题研究

RCPSP Study Based on Simulated Annealing and Genetic Algorithm

在资源有限项目调度问题中,针对可更新资源的单项目如何求得资源约束下的最短工期,提出了一种基于种群稳定度的遗传模拟退火算法。设计了一种满足任务前后约束的种群初始化方法,将种群进行交叉、变异产生新的种群后加入模拟退火算法,计算是否以新的种群替换当前新种群。提出了种群稳定度概念。为避免一般遗传算法的进化早熟现象,当种群稳定度超过给定的稳定度时应用模拟退火算法,通过多次试验设定种群稳定度。通过标准测试问题库中的数值验证表明,该算法能扩大解空间得到更优解,使收敛加快。

In order to find the shortest duration for a single project with renewable resources under resource constraints,a genetic simulated annealing algorithm based on population stability is proposed.A population initialization method which satisfies the demand of precedence constraints is developed from this algorithm.After the new population is generated by crossing and mutating,the simulated annealing algorithm is added to calculate whether the current population is replaced by a new population.Meanwhile,the concept of population stability is put forward.In order to avoid the prematurity of general genetic algorithm,simulated annealing algorithm should be applied when the population stability exceeds the given stability which is determined by several experiments.Finally,the numerical results of PSPLIB show that this algorithm can expand the solution space,optimize the solution and accelerate the convergence.