DEED算法：解决大规模RCPSP问题的分布估计差异进化方法

本文主要探讨了一种创新的算法策略——带分布估计的差异演化算法（DEED），用于解决资源受限项目调度问题（RCPSP）。RCPSP是运筹学和管理科学中的核心问题，它涉及在满足时间和资源约束下，如何有效地安排项目活动，以实现项目最短工期。由于RCPSP属于NP-hard问题，传统的精确算法如分支定界法虽然理论上能求得最优解，但在处理大规模问题时计算复杂度极高，难以在实际应用中处理超过60个任务的项目。 为了克服这些问题，作者借鉴了差异进化算法（DE）的优势，DE是一种基于群体差异的全局并行搜索方法，其在求解RCPSP问题上已显示出一定的效果。然而，DE容易陷入局部最优解，特别是在处理大规模问题时，可能存在早熟现象，即算法过早停止在局部最优，未能找到全局最优解。 DEED算法旨在改进DE的这些局限性，它结合了分布估计算法（EDA），这是一种能获取问题解空间全局信息并揭示变量间关系的方法。通过EDA，DEED能够更好地理解解空间结构，指导搜索过程，预测最优解的分布，从而提高搜索效率和避免过早收敛。这使得DEED在保持DE快速收敛的同时，增强了全局搜索能力，能够在处理大规模RCPSP问题时提供更优的解决方案。 作者通过在标准问题库（PSPLIB）的单模式问题集中进行实验，将DEED与当前流行算法进行了比较，结果显示DEED算法在求解RCPSP问题上表现出较高的效率和有效性，尤其是在处理复杂和大规模问题时，能够在计算质量和计算速度之间取得良好的平衡。这篇论文提供了一种有效的算法改进策略，为RCPSP问题的求解提供了一个新的视角和实用工具。