组织进化算法在多模态资源受限项目调度中的应用

摘要

在社会经济飞速发展的当今社会,资源受限项目调度问题越来越受到人们的广泛关注,更多的学者尝试用不同的方法研究此类问题。多模态资源受限项目调度问题是其中一个典型的问题,它属于NP-hard问题范畴,目前已有学者应用模拟退火算法、遗传算法、粒子群算法等求解此类问题。本文将组织进化算法应用到多模态资源受限项目调度问题的求解中,本文主要研究内容如下:
　　1.密母算法是建立在模拟文化进化基础上的优化算法,它实质上是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体。提出了一种求解单模态资源受限项目调度问题的密母算法。通过遗传算法的交叉变异等操作实现了种群的全局搜索,而后又通过对每一代若干最优个体的单独变异实现了局部搜索,此外,还创新性的将一个服从幂律分布的无标度网络引入到问题的求解过程中,使进化过程中个体间信息交换更具有方向性,并让那些更具潜质的个体发挥更大的作用。对标准数据库PSPLIB中的J30和J60数据集的960个实例进行测试,并取得了良好的结果。
　　2.多模态资源受限项目调度问题是在单模态资源受限项目调度的基础上令每个任务的完成不仅仅只有一种方法,每种方法需要不同的资源并消耗不同的时间。我们用组织协同进化算法解决多模态资源受限项目调度问题,将个体划分为2个种群,每个种群包含若干组织,进化过程中两个种群独立进化,只有两个种群中的个体相互结合才可以形成完整的解。每一代进化后期将两个组织中的个体结合,通过一个局部搜索策略进一步提高算法的搜索效率。
　　3.在上一个工作的基础上,用组织进化算法解决多模态资源受限项目调度问题,进化过程中只有一个种群,每个种群包含若干组织,每个组织由若干个体组成,进化过程以组织为单位,每一代在全局范围内搜索完成后挑选出若干最优解,进行局部搜索来提高算法的效率。最终对PSPLIB中的数据集J10、J12、J14、J16、J18、J20和J30进行测试,并与其他算法相比较,从结果可以看出,本文的算法在求得最优解的正确率和平均偏差方面都有很好的表现。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 资源受限项目调度问题

1.2组织进化算法

1.3 论文结构安排

第二章 基于无标度网络的密母算法在单模态资源受限项目调度问题中的应用

2.1 引言

2.2 资源受限项目调度的简介

2.3 无标度网络

2.4 SFMA-RCPSPs

2.5 实验部分

2.6 本章小结

第三章 组织协同进化算法在多模态资源受限项目调度中的应用

3.1 引言

3.2 多模态资源受限项目调度问题

3.3 协同进化计算

3.4 OCCA-MRCPSPs

3.5 算法的流程

3.6 实验

3.7 本章小结

第四章 用于多模态资源受限项目调度问题的组织进化算法

4.1 算法中的组织

4.2 作用于成员的进化算子

4.3 作用于组织的算子

4.4 OEA-MRCPSPs的算法流程

4.5 实验部分

4.6 本章小结

第五章 总结与展望

5.1 本文工作总结

5.2 未来工作展望

致谢

参考文献

作者研究生期间的科研成果

作者研究生期间参与的科研项目