论文部分内容阅读
粒子群算法在仿真生物群体社会活动的基础上,通过模拟群体生物相互协同寻优能力,从而构造出一种新的智能优化算法。但粒子群算法本身来源于生物群体现象,其理论基础并不完备。而且由于其属于随机的近似优化算法,主要应用于连续区域,因此该算法存在早熟收敛和对离散性的问题难以应用的缺点。因此,对粒子群算法的理论分析、算法改进及离散性问题的研究具有重要意义的。本文在前人工作的基础上对标准粒子群算法和离散二进制粒子群算法进行分析、改进,获得以下结果:(1)粒子群算法是一种启发式随机优化算法,每个粒子追逐自身最优粒子和全局最优位置搜索,并且追逐时带有随机因素。粒子群算法在这种随机搜索过程中,粒子最终会收敛于群体最优粒子。本文在增加随机性和粒子最优点更新的条件下,理论上证明了粒子的轨迹收敛于群体最优粒子位置。根据分析的理论结果,进一步说明了算法权重选择的原理。(2)由于粒子轨迹最终收敛于群体最优粒子,本文定义一个粒子间的相似度概念,设计计算群体粒子的多样性的概念公式—聚集度—通过计算群体粒子与群体最优粒子的平均相似度,度量粒子群的多样性程度。根据群体聚集度及其与群体最优粒子相似度,每个粒子随机产生变异,由此,构造了一种对标准PSO算法的改进算法,提高算法的全局搜索能力、避免早熟收敛,有效地提高标准PSO算法的性能。(3)标准PSO算法的权重是平衡算法全局搜索与局部搜索能力的参数,其取值影响算法的性能。标准PSO算法的权重采用从早期偏大到晚期偏小的线性递减方法,但每个粒子的权重大小一样。本文根据粒子与群体最优粒子的相似度,对不同粒子赋予不同权重,使每个粒子的权重不同,并且随着算法迭代而动态变化,这样构造一种权重动态变化的粒子群算法。经仿真实验验证,该方法有效。(4)PSO算法的理论分析构造了一个数学模型,数学模型从数学角度清楚地体现算法本身的数学含义。本文利用此数学模型代替原始PSO算法速度及位置的更新公式,得到一种新的进化算法,并且分析新的进化算法参数的选择。新算法形式能直接体现PSO算法的数学思想。经仿真试验检验,新算法效果不会差于标准PSO算法。本文将新的算法应用于求解单交叉口信号灯的时间优化分配,实验仿真结果表明,本文的算法在静态环境下很有效的。(5)二进制离散PSO算法为求解二进制的离散组合优化问题而构造一种PSO算法。本文从位改变率、速度的期望值及遗传算法模式概念等三个方面对其进行分析。本文得到:二进制PSO算法不收敛于群体最优粒子,其位值随着迭代运行而越来越随机。因此,二进制PSO算法缺乏局部探测性且具有偏强的全局开拓性。本文对原始二进制PSO算法进行改进,使其产生符合PSO算法思想(跟随群体最优粒子)的形式。将改进的方法应用于求解0/1背包问题。通过实验对比,新改进的二进制PSO算法提高了原始二进制PSO算法的性能。