论文部分内容阅读
资源受限项目调度问题作为一类典型的组合优化问题,理论上属于NP难题。本文结合文化算法和自适应遗传算法的优点,提出一种新的智能优化算法——文化遗传算法来求解资源受限项目调度问题。算法设置了两类空间:群体空间和信仰空间。各空间采用不同的自适应遗传算法进行独立进化,进化过程中利用同步式传输方式定期通过接受操作和影响操作来更新信仰空间和群体空间。为避免各空间的局部收敛问题,文中使用正弦函数和余弦函数自适应控制交叉概率和变异概率以保证群体的多样性。通过对标准数据库PSPLIB中的多个问题的仿真,结果表明:此算法在解决资源受限项目调度问题时不仅具有全局收敛性,而且在一定程度上具有较好的收敛速度。
As a typical combinatorial optimization problem, resource-constrained project scheduling problem is theoretically NP-hard problem. Based on the advantages of cultural algorithm and adaptive genetic algorithm, this paper proposes a new intelligent optimization algorithm - CGA to solve the resource-constrained project scheduling problem. The algorithm sets two types of space: group space and belief space. Each space uses different adaptive genetic algorithms to evolve independently. In the evolutionary process, synchronic transmission mode is adopted to update belief space and group space regularly by accepting operations and influencing operations. In order to avoid the local convergence problem in space, the crossover probability and mutation probability are adaptively controlled by using the sine function and the cosine function to ensure the diversity of the population. The simulation of several problems in the standard database PSPLIB shows that this algorithm not only has global convergence but also has a good convergence speed to some extent when it comes to solving the resource-constrained project scheduling problem.