资源受限项目调度问题的改进文化微粒群算法求解

【引言】资源受限项目调度( RCPSP) 是在满足项目紧前约束与资源约束的前提下，通过安排项目所有任务的开工时间达到最小化项目总工期的目的。RCPSP 是一个典型的NP-hard 问题，自20 世纪50 年代以来，一直都备受学者的关注，他们对RCPSP进行了大量的研究并取得了很多成果。在RCPSP 的求解方法上，从精确解法到满意解，从线性规划、非线性规划，发展到分支定界法直至现在的启发式算法，包括遗传算法、模拟退火算法、微粒群算法、蚁群算法等。在以上算法中，微粒群算法是一种应用在RCPSP 上比较成功的群智能算法。传统的微粒群算法在求解RCPSP 时，由于算法自身的局限，容易陷入局部寻优，出现早熟现象，使得优化结果与理想结果之间存在一定差距。文化算法是一种基于种群的多进化过程的计算模型，任何一种符合文化算法要求的进化算法都可以嵌入文化算法框架中。另外，由于文化算法中知识空间的自我演化机制限制，使得知识空间群体在自我演化时达到的效果并不理想，对下层主群体空间的有效影响作用减少，算法整体的全局搜索能力和运行效率受到一定影响。基于此，本文提出基于文化算法框架的改进文化微粒群算法( ICPSO) ，通过遗传算法的种群演化机制来改进知识空间的自我演化机制，使其在求解RCPSP 时可以减少粒子过早陷入局部最优的概率，能较好地解决RCPSP。