摘要
在智能领域，大部分问题都可以归结为优化问题。
常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。
本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。
根据分析结果,研究了一种基于量子的粒子群优化算法。
在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。
本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。
最后,对本文进行了简单的总结和展望。
关键词：粒子群优化算法最小二乘支持向量机参数优化适应度
目录
摘要 (I)
目录...................................................................................................................................................................... I I 1.概述.. (1)
1.1引言 (1)
1.2研究背景 (1)
1.2.1人工生命计算 (1)
1.2.2 群集智能理论 (2)
1.3算法比较 (2)
1.3.1粒子群算法与遗传算法(GA)比较 (2)
1.3.2粒子群算法与蚁群算法(ACO)比较 (3)
1.4粒子群优化算法的研究现状 (4)
1.4.1理论研究现状 (4)
1.4.2应用研究现状 (5)
1.5粒子群优化算法的应用 (5)
1.5.1神经网络训练 (6)
1.5.2函数优化 (6)
1.5.3其他应用 (6)
1.5.4粒子群优化算法的工程应用概述 (6)
2.粒子群优化算法 (8)
2.1基本粒子群优化算法 (8)
2.1.1基本理论 (8)
2.1.2算法流程 (9)
2.2标准粒子群优化算法 (10)
2.2.1惯性权重 (10)
2.2.2压缩因子 (11)
2.3算法分析 (12)
2.3.1参数分析 (12)
2.3.2粒子群优化算法的特点 (14)
3.粒子群优化算法的改进 (15)
3.1粒子群优化算法存在的问题 (15)
3.2粒子群优化算法的改进分析 (15)
3.3基于量子粒子群优化(QPSO)算法 (17)
3.3.1 QPSO算法的优点 (17)
3.3.2 基于MA TLAB的仿真 (18)
3.4 PSO仿真 (19)
3.4.1 标准测试函数 (19)
3.4.2 试验参数设置 (20)
3.5试验结果与分析 (21)
4.粒子群优化算法在支持向量机的参数优化中的应用 (22)
4.1支持向量机 (22)
4.2最小二乘支持向量机原理 (22)
4.3基于粒子群算法的最小二乘支持向量机的参数优化方法 (23)
4.4 仿真 (24)
4.4.1仿真设定 (24)
4.4.2仿真结果 (24)
4.4.3结果分析 (25)
5.总结与展望 (26)
5.1 总结 (26)
5.2展望 (26)
致谢 (28)
参考文献 (29)
Abstract (30)
附录 (31)
PSO程序 (31)
LSSVM程序 (35)
1.概述
1.1引言
最优化问题是在满足一定约束条件下，寻找一组参数值，使得系统的某些性能指标达到最大或者最小。
它广泛的存在于农业，国防，工程，交通，金融，能源，通信，材料等诸多领域。
最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。
国内外的实践证明，在同样条件下，经过优化技术的处理，对系统效率的提高，能耗的降低，资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大，这种效果也更加显著。
但随着处理对象规模的增大，优化问题也越来越复杂，而经典的优化技术对问题的约束比较大，如梯度下降法要求优化函数是可导等，因此，对于新型优化算法的研究具有重要的意义[1]。
1.2研究背景
1.2.1人工生命计算
人们从生命现象中得到启示，发明了许多智能的优化方法来解决复杂优化问题。
现在已有很多源于生物现象的计算技巧。
例如，人工免疫模拟生物免疫系统的学习和认知功能，人工神经网络是简化的大脑模型, 遗传算法是模拟基因进化的过程。
在计算智能(computational intelligence)领域有两种基于群体智能swarm intelligence的算法，粒子群优化算法(particle swarm optimization)和蚁群算法(ant colony optimization)。
蚁群优化算法模拟了蚂蚁群体在路径选择和信息传递方面的行为，而粒子群优化算法模拟群居动物觅食迁徙等群体活动中个体与群体协调合作的工作过程。
这类借鉴了模拟生命系统行为功能和特性的科学计算方法称为人工生命计算。
人工生命计算包括两方面的内容，研究如何利用计算技术研究生物现象和研究如何利用生物技术研究计算问题。
人工神经网络，粒子群优化算法，遗传算法，蚁群优化算法等都属于人工生命计算的范畴[2]。
本文详细介绍的粒子群优化算法是其中的一种新兴计算方法。
它同遗传算法类似，同属随机迭代优化工具。
同遗传算法等其他人工生命计算相比，粒子群算法概念简单，容易实现，调节参数较少。
目前粒子群算法越来越引起人们的关注。
1.2.2 群集智能理论
我们经常能够看到成群的鸟、鱼或其它生物，这些生物的聚集行为有利于它们觅食和逃避捕食者。
生物的群落动辄以十、百、千甚至万计，它们是如何迅速完成聚集、移动等行为呢?这些群落一般都不存在一个统一的指挥者，那么一定有某种潜在的能力或者规则保证了这些行为的同步。
科学家们普遍认为上述行为是基于不可预知的种群社会行为中的群集智能。
群集智能((Swarm Intelligence)指的是众多无智能的简单个体组成的群体，通过相互间的简单合作表现出智能行为的特性。
群居生物涌现的群集智能正越来越得到人们的重视，成为近年来人工智能研究的一个热点课题。
Millonasp在开发人工生命算法时提出了群集智能的概念，并提出五点原则[3]:
1）接近性原则:群体应能够实现简单的时空计算;
2）优质性原则:群体能够响应环境要素;
3）变化相应原则:群体不应把自己的活动限制在一个狭小的范围:
4）稳定性原则:群体不应每次随环境改变自己的模式;
5）适应性原则:群体的模式应在计算代价值得的时候改变。
1.3算法比较
1.3.1粒子群算法与遗传算法(GA)比较
为更清楚地认识PSO算法和GA算法，下面对两者做个简单比较。
PSO算法和GA算法的相同点:
(1)都属于仿生算法。
PSO算法主要模拟鸟类觅食、人类认知等社会行为而研究;GA算法主要借用生物进化中“适者生存”的规律。
(2)都属全局优化方法。
在解空间都随机产生初始种群，因而算法在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。
(3)都属随机搜索算法。
(4)隐含并行性。
搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。
(5)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。
(6)对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。
PSO算法和GA算法不同点:
(1) PSO算法有记忆，好的解的知识所有粒子都保存，而GA算法，以前的知识随着种群的改变被破坏。
(2)PSO算法中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单项信息共享机制。
而GA算法中，染色体之间相互共享信息，使得整个种群都向最优区域移动。
(3)GA算法的编码技术和遗传操作比较简单，而PSO算法相对于GA算法，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数、更少、实现更容易。
(4)在收敛性方面，GA算法己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计;而PSO算法这方面的研究还比较薄弱。
尽管己经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。
(5)在应用方面，PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA 算法除了连续问题之外，还可应用于离散问题。
1.3.2粒子群算法与蚁群算法(ACO)比较
PSO算法和ACO算法都是群体智能算法，为更清楚地认识PSO算法和ACO算法，下面对两者也做简单比较[4]。
PSO算法和ACO算法的相同点:
(1)都属于仿生算法。
PSO算法和ACO算法主要模拟觅食、人类认知等社会行为而提出。
(2)都属全局优化方法。
算法在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。
(3)都属随机搜索算法。
(4)都有记忆，好的解的知识所有粒子都保存。
(5)隐含并行性。
搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。
并且由于这种并行性，易在并行计算机上实现，以提高算法性能和效率。
(6)根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。
(7)对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。
PSO算法和ACO算法不同点:
(1) PSO算法中的粒子通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单项信息共享机制。
而ACO算法中，每个个体只能感知局部的信息，不能直接使用全局信息。
(2) PSO算法的编码技术和ACO算法操作比较简单，而PSO算法相对于ACO算法，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。
(3)在收敛性方面，ACO算法己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计;而PSO算法这方面的研究还比较薄弱。
尽管已经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。
(4)在应用方面，PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而全局ACO算法除了连续问题之外，还可应用于离散问题，比如TSP问题、工作车间调度等。
1.4粒子群优化算法的研究现状
1.4.1理论研究现状
在粒子群优化算法的理论研究方面，由于PSO算法对参数的选择没有规范，而且算法容易“早熟”，因此很多学者都对算法提出了改进。
有些学者对算法的收敛性进行了分析，对参数选择提出了好的建议;更多的学者则致力于研究算法的结构和性能的改善，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较等[5]。
在基本粒子群优化算法的基础上，Shi和Eberhart首次提出了惯性权重的概念，对基本算法中的速度更新公式进行修正。
惯性权重的引入更好地控制了粒子的开发((exploitation)和探索(exploration)，提高了算法性能。
惯性权重在多数情况下被设置为随时间递减的时变权重。
改进后的算法称为标准粒子群优化算法，为大多数研究者所使用。
之后，Kenned提出了簇丛分析(cluster analysis)的方法。
簇丛分析方法是在微粒群
体中选择一些微粒作为中心，再将离它最近的N个微粒和中心微粒作为一簇，然后计算每个簇的中心位置，并以这些中心位置来替换Pbest或者Gbest。
结果表明，用簇中心替换Pbest时，部分测试函数的解得到了较好的改进，其余的函数只是略微差一点。
如果用全局的簇中心替换Gbest时，几乎所有函数的结果都较差。
此外，簇丛分析的方法虽然使收敛速度有所加快，但同时引入了一些附加计算，通常需要标准PSO算法计算时间的74%-200%。
Angeline P. J.利用选择(selection)的方法改进PSO算法
[4]。
结果表明，改进后的方法提高了大部分函数的性能。
这是由于选择方法加快了对当前较好区域的开发过程，使得算法收敛速度加快，但也增加了陷入局部解的可能性。
标准粒子群优化算法有3个权重因子，这使得算法调整很自由，但也为找到最好的参数组合带来难度。
因此，Clerc提出一个简化的PSO算法，只有一个公式和一个社会/信心参数。
该算法定义了一个无希望((No-hope)收敛规则和一个重新希望(Re-hope)方法，以便不时地根据对目标函数的梯度估计和先前的初始化重新初始化群体位置，算法还考虑了粒子群体的引力中心(Gravity center)。
用该算法对一些函数进行测试得到了较好的结果。
1.4.2应用研究现状
粒子群优化算法最早应用于非线性连续函数的优化和神经元网络的训练，后来也被用于解决约束优化问题。
Eberhart用PSO算法来分析人类的帕金森综合症等颤抖类疾病。
Robinson等将PSO算法用于剖面波状喇叭天线的优化，并与GA的优化效果进行了比较，研究了二者混合应用的可行性[5]。
Ciuprina提出一种智能PSO (IntelligentPSO)用于电磁线圈尺寸的优化。
Abido将PSO算法用于解决最优功率通量(OPF)问题。
国内也有越来越多的学者关注PSO算法，将其应用于非线性规划、参数优化、车辆路径、约束布局优化、新产品组合投入、多目标优化等问题。
还有一些学者尝试将PSO算法应用于解决动态优化问题，也取得了较好的效果。
粒子群优化算法由于其算法简单，参数少，易于实现等特点，在连续非线性优化问题和组合优化问题中都表现出良好的效果。
基于以上研究成果，论文将在分析粒子群优化算法缺点的基础上对其做进一步的改进，以提高算法在复杂、高维情况下的优化性能，使算法能有效避免搜索过程中的
“早熟”问题，提高算法的稳定性，并且对最小二乘支持向量机的参数进行优化。
1.5粒子群优化算法的应用
粒子群优化((PSO)算法概念简单，易于实现，同时又有深刻的智能背景，既适合科学研究，又适合于工程应用。
由于该算法具有很强的通用性，而且无需问题的特殊信息，因此，算法一提出就吸引了广泛的关注，不断涌现出各种关于PSO算法应用的研究成果，有力地推动了PSO算法的应用研究。
1.5.1神经网络训练
粒子群优化算法最早最成功的应用就是在神经网络的训练领域。
在神经网络的训练中，主要包含3个方面:网络连接权重、网络拓扑结构、学习算法。
每个粒子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的。
与BP算法相比，使用PSO算法训练神经网络的优点在于不需要梯度信息，可使用一些不可微的传递函数。
多数情况下其训练结果优于BP算法，而且训练速度非常快[6]。
1.5.2函数优化
粒子群优化算法最直接的应用就是多元函数的优化问题，包括带约束的优化问题。
通常这些函数是非常复杂的，主要表现为规模大、维数高、非线性和不可微等特点，而且有的函数存在大量局部极值。
许多传统的确定性优化算法收敛速度较快，计算精度高，但对初值敏感，易陷入局部最小。
而一些具有全局性的优化算法，如遗传算法、模拟退火算法、进化规划等，受限于各自的机理和单一结构，对于高维复杂函数难以实现高效优化。
PSO 算法通过改进或结合其它算法，对高维复杂函数可以实现高效优化。
1.5.3其他应用
一般而言，粒子群优化算法与其他演化算法一样，能用于求解大多数优化问题。
除了以上领域外，PSO算法的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。
其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等。
总之，PSO算法的应用十分广泛，有着较好的发展前景。
目前PSO算法的应用研究尚处于初期，还有许多问题需要进一步的研究。
1.5.4粒子群优化算法的工程应用概述
以上阐述了粒子群优化算法在函数优化，神经网络训练和模糊系统控制等基本领域的应用。
实际的优化问题往往可以转化为上述问题进行求解。
下面简要介绍粒子群优化算法在一些实际应用领域的进展。
首先，日本的Fuji电力公司的研究人员将电力企业著名的RPVC(Reactive Power and Voltage Control)问题简化为函数优化问题，并使用改进的PSO算法进行优化求解。
与传统方法如专家系统、敏感性分析相比，实验产生的结果证明了PSO算法在解决该问题的优势。
其次，将PSO算法与BP算法相结合训练神经网络已用于对电动汽车燃料电池组实时充电情况的模拟。
对电动汽车燃料电池带电状况的模拟是电动汽车以及混合动力汽车技术发展过程中的重大课题。
实验证明相对于1996年Eberhart，Simpson和Dobbins的模拟方法，上述方法的模拟精确程度明显提高。
此外，PSO算法已被美国一家公司用于各种生物化学成分的优化组合，进而人工合成微生物。
与传统的工业优化方法比较，PSO产生合成结果的适应度是传统方法的两倍。
实验的优化过程充分显示了PSO算法的优越性：尽管一种劣质成分在一定的迭代次数内能够影响优化搜索的进程，但是PSO最后总能得到比较理想的合成结果。
这是因为PSO本质而言能够搜索到更大范围内的优化问题的解空间。
总的来说，粒子群优化算法与其他进化算法一样，可以解决几乎所有的优化问题，或者是可以转化为优化问题进行求解的问题。
其中最具应用前景的领域包括多目标问题的优化、系统设计、分类、模式识别、生物系统建模、规划、信号处理、决策和模拟等等。
目前，在模糊控制器的设计、图像分割、EEG信号模拟、语音识别、烧伤诊断以及探测移动目标等方面已经有成功应用的先例[7]。
2.粒子群优化算法
2.1基本粒子群优化算法
粒子群优化(Particle Swarm Optimization，简称PSO)算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解，它包含有进化计算和群集智能的特点。
起初Kennedy和Eberhart只是设想模拟鸟群觅食的过程，但后来发现PSO算法是一种很好的优化工具。
设想这样一个场景:一群鸟在空间中随机的搜索食物。
在这个区域里只有一块食物，所有的鸟都不知道食物在哪儿，但是它们知道自己当前的位置距离食物还有多远。
那么找到食物的最优策略是什么?最简单有效的方法就是搜寻目前距离食物最近的鸟的周围区域，通过鸟之间的集体协作与竞争使群体达到目的。
这是一种信息共享机制，在心理学中对应的是在寻求一致的认知过程中，个体往往记住它们的信念，同时考虑其它个体的信念。
当个体察觉其它个体的信念较好的时候，它将进行适应性地调整。
PSO算法就是从这种模型中得到启示并用于解决优化问题的。
如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中飞行的一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)，也是优化问题的一个解。
“食物”就是优化问题的最优解。
粒子的概念是一个折衷的选择，它只有速度和位置用于本身状态的调整，而没有质量和体积。
“群”(Swarm)的概念来自于人工生命，满足群集智能的五个基本原则。
因此PSO算法也可以看作是对简化了的社会模型的模拟，社会群体中的信息共享是推动算法的主要机制[8]。
2.1.1基本理论
Eberhart和Kennedy提出的基本粒子群优化算法可描述如下:设在一个D维的目标搜
索空间中，有m个粒子组成一个群落，第i个粒子的位置用向量X
i =[X
i1
,X
i2
，...，X
iD
]表
示，飞行速度用V
i =[V
i1
,V
i2
, ... ,V
iD
]表示，第i个粒子搜索到的最优位置为
Pi=[P
i1,P
i2
,… ,P
iD
] ,整个群体搜索到的最优位置为P
g
=[P
i1
,P
i2
, ...,P
iD
]，则用下式更新
粒子的速度和位置:
Vi(n+l)=Vi(n)+c
l r
l
(Pi-Xi(n))+c
2
r
2
(Pg-Xi(n)) (2-1)
Xi(n+1)=Xi(n)+Vi(n) (2-2)
式中，i=1,2,..., m，分别表示不同的粒子。
c
1 ,c
2
为大于零的学习因子或称作加速系
数，分别调节该粒子向自身己寻找到的最优位置和同伴已寻找到的最优位置方向飞行的最
大步长，通常情况下取c
l =c
2
=2 ; r
l
,r
2
为介于[[0,1]之间的随机数;n为迭代次数，即粒子
的飞行步数。
将V，限定一个范围，使粒子每一维的运动速度都被限制在[-Vmax.,Vmax]之间，以防止粒子运动速度过快而错过最优解，这里的Vmax根据实际问题来确定。
当粒子的飞行速度足够小或达到预设的迭代步数时，算法停止迭代，输出最优解。
从社会学的角度来看，公式(2-1)的第一部分是“记忆”项，是粒子先前的速度，表示粒子当前的速度要受到上一次速度的影响;公式第二部分是“自身认知”项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分，可以认为是粒子自身的思考;公式的第三部分是“群体认知”项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和信息共享。
粒子正是通过自己的经验和同伴中最好的经验来决定下一步的运动。
公式(2-1)中的第一部分起到了平衡全局和局部搜索能力的作用;第二部分使粒子拥有的局部搜索能力，能更好的开发解空间;第三部分体现了粒子间的信息共享，使粒子能在空间更广阔的探索;只有在这三个部分的共同作用下粒子才能有效的搜索到最好的位置。
2.1.2算法流程
基本粒子群优化算法的步骤描述如下:
步骤1:初始化粒子群，包括群体规模、粒子的初始速度和位置等;
步骤2:计算每个粒子的适应度(fitness)，存储每个粒子的最好位置Pbest:和fitness，并从种群中选择fitness最好的粒子位置作为种群的Gbest;
步骤3:根据方程(2-1)和((2-2)更新每个粒子的速度和位置;
步骤4:计算位置更新后每个粒子的适应度，将每个粒子的fitness与其以前经历过的最好位置时所对应的fitness比较，如果较好，则将其当前的位置作为该粒子的Pbest;
步骤5:将每一个粒子的适应度(fitness)与全体粒子所经历过的最好位置比较，如果较好，则将更新Gbest的值;
步骤6:判断搜索结果是否满足算法设定的结束条件(通常为足够好的适应值或达到预设的最大迭代步数)，如果没有达到预设条件，则返回步骤3;如果满足预设条件，则停止迭代，输出最优解。
图2-1 粒子群优化算法流程图
2.2标准粒子群优化算法
2.2.1惯性权重
在基本粒子群优化算法的基础上，Shi 等学者在1998年的进化计算的国际会议上发表了一篇论文《A modified particle swarm optimizer 》对前面的公式(2-1)进行了修正，引入惯性权重因子ω:
))(())(()()1(2211n X P r c n X P r c n V n V i g i i i i -+-+=+ω (2-3)
惯性权重。
是用来控制粒子以前速度对当前速度的影响，它将影响粒子的全局和局部搜索能力。
选择一个合适的ω可以平衡全局和局部搜索能力，这样可以使算法以最少的迭代次数，迅速找到最优解。
初始时，Shi 将ω取为常数，后来实验发现，动态的必能够获得比固定值更好的寻优结果。
因为较小的必可加强局部搜索能力，而较大的ω可加快收敛速度，所以通过调节ω可以达到收敛速度和局部搜索能力间的平衡[8]。
动态山可以在PSO 算法搜索过程中线性变化，也可根据PSO 算法性能的某个测度函数动态改变。
目前，采用较多的是Shi 建议的线性递减权值((linearlydecreasing weight, LDW)策略: max min
max max n n ωωωω--= (2-4)
式中，min .max ωω 分别为最大和最小惯性权重，n 为当前迭代步数，max n 为算法总的迭代次数。
ω常在[0.4,0.9]之间变化，随着迭代步数的增加而减小。
ω的线性变换使得算法在早期具有较快的收敛速度，而后期又有较强的局部搜索能力。
ω引入使PSO 算法性能有了很大提高，针对不同的搜索问题，可以调整全局和局部搜索能力，也使得PSO 算法能成功的应用于很多实际问题。
因此，采用公式(2-3)的粒子群优化算法被称为标准粒子群优化算法。
