论文部分内容阅读
动态优化问题（Dynamic Optimization Problem，简称DOP）是现实社会中普遍存在的一类实际优化问题。相对于静态优化问题而言，DOP的目标函数或者约束条件会随着时间而变化。近年来，利用进化算法求解动态优化问题逐渐成为新的研究热点。微粒群优化算法（Particle Swarm Optimization，简称PSO）也称为粒子群优化算法，属于进化算法的一个分支，它模拟了生物界中鸟群、鱼群等群体性动物的觅食行为，具有算法简单、鲁棒性强等优点，在多个领域得到了成功的应用。PSO算法在静态优化问题中的研究已趋于成熟，且拥有良好的性能，但在动态优化问题中的研究还不够完善。 论文主要研究了PSO算法在求解动态优化问题过程中如何探测和响应环境的变化以及如何保持种群的多样性。论文的主要工作如下： ①对离散动态优化问题，本文提出了一种求解动态背包问题的离散微粒群优化算法（Dynamic Set-based Discrete PSO，简称DSDPSO）。DSDPSO算法是在求解集合组合问题的离散粒子群优化模型的基础上，引入了环境变化的探测以及环境变化后的响应机制。将DSDPSO算法和经典的自适应原对偶遗传算法在两个动态背包问题上进行对比实验。实验结果表明，DSDPSO算法在环境变化后能迅速找到最优解并稳定下来，并且找到的最优解为该重量约束下的标准最优解；在寻优时间上，DSDPSO算法的寻优时间约为与之比较的算法的寻优时间的0.5~0.7倍。因此，DSDPSO算法更适合于求解动态背包问题。 ②对连续动态优化问题，本文提出了一种基于记忆机制的聚类微粒群优化算法（Memory-based Clustering PSO，简称MCPSO）。当微粒群中出现某个个体的当前适应度高于其历史最优适应度时，将该个体中包含的有用信息传递给其余个体，为此，在MCPSO算法中改进了微粒群的学习更新机制。为了保持种群的多样性，在MCPSO算法中将记忆机制和多种群方法相结合，以便在环境变化后微粒群能有效地对搜索空间进行探索。为了让微粒群能在环境变化后及时做出响应，在MCPSO算法中引入了环境变化的探测以及环境变化后的响应机制。用标准动态优化测试问题——移动峰函数问题对算法进行验证，实验结果表明，MCPSO算法具有良好的鲁棒性以及较强的寻优能力。将MCPSO算法和经典的基于物种的微粒群优化算法进行对比实验，实验结果表明，MCPSO算法的离线误差明显小于与之比较的算法的离线误差。 ③将提出的DSDPSO和MCPSO算法分别应用于求解中国邮政的邮件配送问题和求解流水线上PCB的批量检测问题，两种算法均有效地解决了问题。