粒子群算法(Particle swarm optimization, PSO)是基于种群的优化算法。由于其具有快速收敛和操作简单等特点,在工程、经济管理等诸多领域得到广泛应用,成为智能计算领域研究的新热点。
然而,与其它进化算法一样,PSO也有早熟收敛现象;同时,由于要解决的实际问题,大多都包含约束条件,或者含有多个目标的优化问题,而PSO在提出时,仅针对单目标优化问题,不具备处理约束条件和多目标的机制。鉴于这些不足,本论文的主要研究工作如下,
(1)对粒子的运动轨迹和PSO的收敛性进行分析
首先,构造线性离散动态系统方程,对单个粒子的状态变化进行分析;其次,采用李亚普诺夫意义下稳定的充分必要条件,给出粒子运动稳定的条件,为算法的改进提供理论支持。
(2)提出两种改进的单目标粒子群算法
①提出基于动态邻居和广义学习的粒子群算法(DNMPSO)。首先,提出一种动态邻居拓扑结构,并分析了这种结构的优势及动态邻居拓扑结构重新构建的间隔代数对算法的影响;其次,提出一种广义学习策略,从搜索行为上对其进行分析;然后,对种群陷入局部最优解的原因进行分析,提出一种水平水合变异操作,使每个粒子能更好的进行局部搜索,提升种群向全局最优解飞行的概率;最后,为进一步提升DNMPSO算法求解复杂优化问题的能力,引入局部搜索算法,并对局部搜索算法的实现进行了分析。仿真结果表明DNMPSO在求解精度和鲁棒性方面具有一定优势。
②提出基于K均值聚类的动态多种群粒子群算法(KDMSPSO)。首先,提出一种基于K均值聚类算法构建多种群策略,为增强子群间的信息交流,采取动态组建子群策略;其次,对种群多样性进行分析,以确定动态多种群的优势所在,并分析动态多种群的重新构建代数对算法的影响;然后,通过对粒子学习样本的分析,提出一种改进的学习策略,即“社会部分”学习样本不是种群中运行最优的粒子,而是粒子所在子群的中心粒子;最后,考虑到动态多种群KDMSPSO算法的优势,将其用来求解带有约束条件的优化问题,为实现对约束条件的处理,研究每个子群的任务分配策略(将约束条件看作任务),每个子群成员确定策略,粒子间的优劣比较规则,进而提出一种求解约束优化问题的改进粒子群算法(DMCPSO)。仿真结果表明DMCPSO算法用较少的函数评价次数可获得较优的最优解。
(3)提出两种多目标粒子群算法,并提出三种提升算法运行效率的策略
①提出ACG-MOPSO算法。首先,分析PSO求解多目标优化问题的关键点(学习样本的选取和外部存档的规模控制),针对两个关键问题的解决,采用自适应网格对粒子的密度信息和拥挤距离进行研究,并研究外部存档规模控制策略;其次,研究如何通过密度信息和拥挤距离信息来确定全局最优粒子作为“社会部分”的学习样本;然后,从如何充分利用每个粒子历史最优位置的信息角度出发,研究粒子自身最优位置更新策略;最后,提出一种基于自适应网格和拥挤距离的多目标粒子群算法(ACG-MOPSO)。仿真结果表明ACG-MOPSO算法在处理Pareto前沿为凸、凹、不连续和多峰问题时,在解的多样性和收敛性上相比其它算法有更好的表现。
②提出εDMOPSO算法。为提升PSO求解多目标优化问题的效率,采用一种对经典的Pareto占优关系改进的ε占优来研究粒子间的优劣,该方法不仅保证外部存档中非劣解的收敛性和分布性,而且能根据ε取值自动限制外部档案的规模,不需额外策略,极大地提升了算法的运行效率。并对DNMPSO算法的广义学习策略进行修改以适应多目标优化问题,使得种群多样性得到提升,进而提升种群向真实Pareto前沿飞行的概率。仿真结果表明εDMOPSO算法相比其它算法获得了较高的运行效率和质量更高的非劣解。
③提出改进算法运行效率的三种策略。首先,提出并分析种群正交初始化,对远离Pareto前沿的所有非劣解的变异操作,对Pareto前沿的边界点和稀疏部分采取基于均匀设计的交叉操作三种策略;其次,研究三种策略的混合作用,即正交初始化+变异操作,正交初始化+均匀交叉操作,正交初始化+变异操作+均匀交叉操作;最后,在ACG-MOPSO和εDMOPSO算法中引入三种策略,并在有代表意义的高维测试函数DTLZ1,DTLZ2,DTLZ3和DTLZ7上进行仿真实验,并对实验结果从统计学角度进行分析。仿真结果表明这些策略在提升解的分布性和收敛性方面有积极的作用。
(4)本文提出的几种改进PSO在解决实际问题中的应用研究DNMPSO算法在土壤水分运动曲线的Van Genuchten方程中的应用;研究基于K均值聚类策略并带有约束处理技术的粒子群算法(DMCPSO)求解带有资产数量和边界约束的CCMV模型;研究εDMOPSO算法求解带有风险约束的投资组合模型。仿真结果表明本文提出的改进算法能有效地求解上述三个实际问题。
