微粒群算法的改进与应用研究

论文摘要

微粒群算法作为一种全局优化算法,由于其易用性和良好的性能,已经引起了越来越多的研究者的注意。目前关于微粒群算法的研究主要集中于三个方面,微粒群算法的理论分析、微粒群算法的改进研究和微粒群算法的应用。本文分析了算法的运行过程,介绍了随机因素对算法的作用,并给出了消除随机因素来简化算法的思路。针对算法的早熟问题,提出了一些改进方法,并进行了微粒群算法在流水作业调度问题中的应用研究,所做的主要工作如下：(1)在标准微粒群算法中,随机因子保证了算法的性能,但是给算法的理论分析带来了困难。本文分析了随机因子在微粒群算法中的作用,给出了一种等价方法,该算法性能同标准微粒群算法近似,表明了该等价方法的正确性。为了消除随机因素,进一步提出了一种采用启发式策略进行维选择的方法,该算法可以保证求解问题的能力,说明将微粒群算法确定化是可行的。(2)微粒群算法中随着进化过程种群的多样性迅速降低,出现所谓的“早熟”现象,使算法收敛于局部最优解。本文基于对微粒群进化过程的分析,提出了两种改进算法。一种方法是将基于微粒相似性的变异操作引入到微粒群算法中,可以增加种群的多样性,能够发现在一般的进化过程不可能找到的解,实验表明这种方法在一些复杂的多峰函数问题上能够取得很好的结果。另一种方法是将具有很强的全局搜索能力的微粒群算法和局部搜索能力较强的极值优化方法结合,发挥两者的优点,克服“早熟”现象,实验结果证明了该方法比标准的微粒群算法的性能有明显的提高。(3)流水作业调度问题(FSSP)是一种NP类问题,本文给出了利用微粒群算法求解FSSP的方法,并采用两种不同的编码方法,实验表明采用实数编码的方法比采用直接在问题的解空间中使用整数编码的方法的性能更好。文中提出的一些微粒群算法的改进算法也被应用到FSSP中,实验结果说明了这些改进算法可以提高解决实际问题的能力。

论文目录

• 摘要
• ABSTRACT
• 1 引言
• 1.1 研究背景
• 1.2 微粒群算法的研究现状
• 1.3 课题的研究意义
• 1.4 本文的主要工作
• 1.5 本文的组织结构
• 2 微粒群算法的相关研究工作
• 2.1 微粒群算法的理论分析
• 2.2 微粒群算法的变体与改进研究
• 2.3 微粒群算法的应用
• 2.4 本章小结
• 3 微粒群算法中的随机因素与消除方法
• 3.1 微粒群算法中的随机因素分析
• 3.2 随机选择维更新的微粒群算法（PSORDS）
• 3.3 采用启发式策略进行维选择的微粒群算法（PSOHDS）
• 3.4 本章小结
• 4 微粒群算法的改进
• 4.1 基于微粒相似度进行变异操作的微粒群算法
• 4.2 微粒群算法和极值优化相结合的混合算法PSO-EO
• 4.3 本章小结
• 5 使用微粒群算法求解流水作业调度问题
• 5.1 流水作业调度问题简介
• 5.2 采用标准微粒群算法求解FSSP
• 5.3 采用基于微粒相似度进行变异操作的微粒群算法求解FSSP
• 5.4 采用实数编码的PSO-EO算法求解FSSP
• 5.5 本章小结
• 6 总结与展望
• 6.1 本文的工作总结
• 6.2 进一步的研究工作
• 致谢
• 攻读硕士期间的主要成果
• 参考文献