差分进化算法求解资源投资问题

摘要

提前预测对项目的顺利实施起到非常关键的作用。项目调度问题就是在项目计划阶段进行的调度方案估计。项目调度问题属于复杂优化问题。项目调度问题主要分为资源受限项目调度问题和资源投资项目调度问题。资源受限项目调度问题的目标是在资源使用量有一定限制的前提下，最短化项目的工期；资源投资问题的目标是在项目完成工期一定的前提下，最小化项目的成本。
　　本论文研究的问题集中在资源投资项目调度问题上。项目的成本主要由使用资源造成，包括人力、物质。为了使问题模型更接近实际，需要不断的将问题模型复杂化，研究从单目标问题深化到多目标问题。
　　第一个研究工作的问题模型是带延迟的资源投资项目调度问题，该问题在允许项目完成时间可以超过规定时间的情况下，最小化项目花费的单目标问题。通过引入超期惩罚参数，选择项目工期合适但资源花费少的调度方案为最终结果，而不完全限制项目完成时间，对原有问题模型进行了改进。采用差分进化算法解决此问题，并对每代中比较好的解使用局部搜索算子以得到更好的解。通过测试实例的验证及与遗传算法的比较结果，可说明此算法对解决此问题是非常有效的。但这个问题是一个单目标优化问题。
　　对于大型项目，尤其是工期很长的，需要考虑货币的时间价值对于项目花费的影响，并将传统资源投资问题未涉及的外来资金进行考虑，同时资源是在提供使用和停止使用的时间段内才可用。基于这些因素，我的第二个研究工作就是将目标函数设为最大化项目的折现现金流。通过将项目整个过程中每个时间点的现金流折现到项目开始时刻得到此项目的折现现金流，这个值越大，项目最终的收益也就越大。采用差分进化算法的框架解决此问题，并结合两个局部搜索算子增强算法的寻优能力。通过与遗传算法的比较，差分进化算法在解决此问题上的优势非常明显。但是这个问题仍是一个单目标优化问题。
　　实际生活中，一个大型项目的进行中会出现多种多样的不确定干扰，导致项目工期的延迟或者资源的紧缺甚至崩溃。这个时候需要评价一个调度方案面对不确定因素时的抵抗能力，即调度方案的鲁棒性。鲁棒性越强，这个项目的抗干扰能力越强，可信度越高。所以第三个工作要考虑的不仅仅是工期短、花费少的，也要鲁棒性高的调度方案，进而将问题建模为随机资源投资项目调度问题，成为一个多目标优化问题。采用多目标差分进化算法，使用三阶段的变异策略以及拥挤熵选择非支配解，通过与其它多目标算法的比较能够看出此算法在解决此问题上具有明显的优势。
　　差分进化算法是一个简单快速的启发式优化算法。因此本文中的算法基本采用差分进化算法的框架进行设计。算子主要有变异、交叉、选择和局部搜索。变异是使目标个体加上另外两个个体的差异，产生变异的个体。交叉通过对变异个体和目标个体的处理，得到试验个体。比较试验个体和目标个体的适应度大小，适应度大的个体进入下一代。进而不断迭代，直到问题收敛。引入局部搜索算子是为了防止算法过早的局部收敛。已验证，算法能有效地解决复杂优化问题。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1资源投资项目调度问题

1.2差分进化算法

1.3论文的内容及安排

第二章 差分进化算法解决带延迟资源投资问题

2.1引言

2.2带延迟资源投资问题

2.3 DE-RIPT

2.4实验部分

2.5本章小结

第三章 差分进化算法解决最大化折现现金流的资源投资问题

3.1引言

3.2最大化折现现金流的资源投资问题

3.3 DE-RIPDCF

3.4实验部分

3.5本章小结

第四章 多目标差分进化算法解决随机资源投资项目调度问题

4.1引言

4.2随机资源投资项目调度问题

4.3 MODEA-SRIPSPs

4.4实验部分

4.5本章小结

第五章 总结与展望

5.1论文总结

5.2工作展望

参考文献

致谢

作者简介