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