浅议粒子群优化算法及其在神经网络中的应用

摘 要 粒子群优化(PSO)算法是一种新颖的演化算法,该算法通过粒子间的相互作用在复杂搜索空间中发现最优区域。PSO的优势在于简单而功能强大。本文介绍了基本的PSO算法、研究现状及其在神经网络中的应用,并探讨了未来的研究内容及发展方向。

关键词 粒子群优化算法;神经网络;人工生命;群智能

1 引言

许多群体生物的自适应优化现象不断给人类以启示,群居生物的群体行为使许多在人类看起来高度复杂的问题得到了完美的解决。自然界那些群居生物表现出来的智能让人惊叹不已,比如蜜蜂建造的巢穴结构庞大、复杂而精美;蚂蚁能够完成觅食、清扫、搬运等高效的工作等等。这种生物群体行为的奇妙之处在于个体都很简单,但他们却能协同工作,依靠群体的能力,发挥超出个体的智能,表现出极其复杂而有序的行为。这些奇妙的现象吸引着越来越多的学者进入到这个领域,研究这些简单的个体如何通过协作涌现出如此复杂而奇妙行为,通过计算机模拟来探索其中的可循规律,用于指导并解决一些常规方法没有解决的传统问题以及实际应用中出现的新问题 [1-3] 。这些研究孕育并产生了一门新兴的学科领域:群体智能(Swarm Intelligence)[1]。优化技术是一种以各种形式的数学处理方法为基础,用于求解各种工程问题优化解的应用技术,在诸多工程领域得到普遍的应用。鉴于实际工程问题的复杂性、约束性、非线性、多局部极小和建模困难等特点,寻找各种适合于工程实践需求的新型智能优化方法一直是许多学科的一个重要研究方向。群体智能作为一种新兴的智能计算技术已成为越来越多研究者的关注焦点,它与人工生命,特别是进化策略以及遗传算法有着特殊的联系。群体智能使得在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题的解决方案提供了基础。

2 PSO的产生与发展 2.1 微粒群算法的起源

微粒群算法[2]最初是为了图形化地模拟鸟群优美而不可预测的运动。自然界中,鸟群运动的主体是离散的,其排列看起来是随机的,但整体的运动却使它们保持着惊人的同步性,个体运动非常流畅而极富美感。研究者对鸟群的运动进行了计算机仿真,他们通过对个体设定简单的运动规则,来模拟鸟群整体的复杂行为。例如,1986年Craig Reynolds提出了Boid模型用以模拟鸟类聚集飞行的行为,通过对现实世界中这些群体运动的观察在计算机中复制重建这些运动轨迹,并对这些运动进行抽象建模以发现新的运动模式。上述模型关键在于对个体间距离的操作,即群体行为的同步性在于个体努力维持自身与邻居之间的距离为最优,为此每个个体必须知道自身位置和邻居的信息。生物社会学家Wilson E.O.认为 “至少从理论上,在搜索食物的过程中群体中的个体成员可以得益于所有其它成员的发现和先前的经历。当食物源不可预测地零星分布时,这种协作带来的优势是决定性的,远大于对食物的竞争带来的劣势。”以上两例说明,群体中个体之间信息的社会共享有助于进化。受上述鸟群运动模型的影响,社会心理学博士JamesK Ennedy和电子工程学博士Russell Eberhart于1995年提出了微粒群算法,微粒群算法是一种演化计算技术,在算法中,将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置,通过个体间的信息传递,导引整个群体向可能解的方向移动,增加发现较好解的可能性。群体中的鸟被抽象为没有质量和体积的“微粒”,通过这些“微粒”的相互协作和信息共享,其运动速度受到自身和群体的历史运动状态信息影响,以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响,较好地协调微粒本身和群体运动之间的关系,在复杂的解空间中寻找最优解。

2.2 微粒群算法的发展

微粒群算法自提出以来,已经历了许多变形和改进。包括数学家、工程师、物理学家、生物化学家以及心理学家在内的研究者对它进行分析和实验。到目前为止,国内外的研究者对微粒群算法的研究与发展,可以归纳为以下几个方面:[3]

(1) 参数选择与设计:在微粒群算法中存在几个显参数和隐参数,它们的值可被调整,以产生算法搜索问题空间的方式的变化。

(2) 种群拓扑结构:从19世纪40年代起的研究已经表明,组内的交流及最终组的性能要受社会网络结构的影响。于是,微粒群研究者提出了几种简单的社会结构,并对几种种群结构模型进行了分析与比较。全局最优模型(Gbest)和局部最优模型(Lbest) 是最常见的两种类型。

(3) 群体组织与进化[4]:社会心理学研究表明。人们的态度、信仰和行为倾向于朝同伴的方向变化,他们会根据自己所处群体的规范选择自己的意见和行为,受此启发,提出用簇来表示群体中的子种群,用簇中心代替最优值的算法模式。此外,为了保证群体的多样性,研究者将变异、繁殖和差异进化等思想引入微粒群,并提出了很多改进算法模式。

(4) 混合微粒群算法:将进化计算中的选择、交叉和变异等特性、混沌、免疫系统的免疫信息处理机制以及热力学中熵的概念等与微粒群算法中的寻优机制相结合,提出了相应的混合算法。

(5) 离散微粒群算法:微粒群算法最初是用来对连续函数进行优化的。而实际中许多问题是组合优化问题,因此,Kennedy和Eberhart博士在基本算法的基础上提出了一种离散二进制决策模型。

3 PSO的基本原理

PSO算法不像遗传算法那样对个体进行选择、交叉和变异操作,而是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子(点),这些粒子在搜索空间中以一定的速度飞行,并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整,即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小,从而形成群体寻优的正反馈机制。PSO算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域,并最终搜索、寻找到问题的最优解。设在一个d维的目标搜索空间中,有m个粒子组成一个群体,其中,在第t次迭代时粒子i的位置表示为Xi(t)=(xi1(t),xi2(t),...,xid(t)),相应的飞行速度表示为Vi(t)

=(vi2(t),vi2(t), ...,vid(t))。开始执行PSO算法时,首先随机初始化m个粒子的位置和速度,然后通过迭代寻找最优解,在每一次迭代中,粒子通过跟踪两个极值来更新自己的速度和位置:一个极值是粒子本身迄今搜索到的最优解,称为个体极值,表示为Pi(t)=(pi1(t),pi2(t),...,pid (t));另一个极值是整个粒子群到目前为止找到的最优解,称为全局极值,表示为Pg(t)=(pg1 (t),pg2(t),...,pgd(t))。在第(t+1)次迭代计算时,粒子i根据下列规则来更新自己的速度和位置[5]:

Vik(t+l)=ωVik(t)+c1randl(Pik(t)-Xik(t))+c2rand2(Pgk(t)-Xik(t)) (1)

Xik(t+l)=Xik(t)+Vik(t+l) (2)

式中ω为惯性权重,ω取大值可使算法具有较强的全局搜索能力,ω取小值则算法倾向于局部搜索。一般的做法是将ω初始取0.9并使其随迭代次数的增加而线性递减至0.4,这样就可以先侧重于全局搜索,使搜索空间快速收敛于某一区域,然后采用局部精细搜索以获得高精度的解;c1,c2为两个学习因子,一般取为2;randl和rand2为两个均匀分布在(0,l)之间的随机数;i=1,2,?,m; k=1,2,?,d。另外,粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度超过该维上的最大速度Vmax,则该维的速度被限制为最大速度。

4 PSO在神经网络中的应用

科学研究与工程实践中有一些多目标优化问题[5](Multi - objective Optimization Problems, MOPs)通常难以处理,实际问题常由多个相互冲突的指标组成,问题的解一般不是单个的最优解,而是一组非劣解,因而采用传统多目标优化方法通常无法解决。由于PSO算法的生命力在于工程应用,为此开拓新的PSO算法的应用领域特别是在解决多目标优化问题上是一项很有意义的工作。

4.1 神经网络训练

PSO用于神经网络的训练中[6],主要包含3个方面:连接权重、网络拓扑结构及传递函数、学习算法。各粒子包含神经网络的所有参数,通过迭代来优化这些参数,从而达到训练的目的。与BP 算法相比,使用PSO训练神经网络的优点在于不使用梯度信息,可使用一些不可微的传递函数。多数情况下其训练结果优于BP 算法,而且训练速度非常快。

PSO训练神经网络的流程图

4. 2 参数优化

PSO已广泛应用于各类连续问题和离散问题的参数优化。例如,在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果。

4. 3 组合优化

许多组合优化问题中存在序结构如何表达以及约束条件如何处理等问题,离散二进制版PSO不能完全适用。研究者们根据问题的不同,提出了相应问题的粒子表达方式,或通过“+ ”和“×”算子来解决不同问题。目前,已提出了多种解决TSP、VRP、网络路由选择以及车间作业调度等问题的方案。

4. 4 其它应用

除了以上领域外, PSO在电力系统、集成电路设计、多目标优化、自动目标检测、生物信号识别、智能决策调度、模糊系统辨识、计算机视觉、计算机辅助设计以及游戏训练等方面也取得了一定的成果。特别在材料学中的应用将是现在及未来大多数研究者们感兴趣的方向,如磨具配方,各种材料的诊断等[7]。

5 未来的研究及对PSO的展望

PSO算法是一个新的基于群体智能的进化算法,其研究刚刚开始,远没有像遗传算法和模拟退火算法那样形成系统的分析方法和一定的数学基础,有许多问题还需要进一步研究。

  (1) 算法分析与应用。PSO在实际应用中被证明是有效的, 但目前还没有给出收敛性、收敛速度估计等方面的数学证明,已有的工作还远远不够。

(2) 适用范围。PSO算法应用得最成功的是在进化神经网络方面,其它的一些应用许多还停留在研究阶段。

(3) 粒子群拓扑结构。不同的粒子群邻居拓扑结构是对不同类型社会的模拟,研究不同拓扑结构的适用范围,对PSO算法推广和使用有重要意义。

(4) 参数选择与优化。PSO算法中参数的选择依赖于具体问题,设计合适的参数需要经过多次试验。研究如何选择和设计参数,使其减少对具体问题的依赖,也将大大促进PSO算法的发展和应用。

(5) 与其它演化计算的融合。如何将其它演化的优点和PSO的优点相结合,构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。

参考文献

[1] 高 尚,杨静宇. 群智能算法及其应用.中国水利水电出版社,2006.

[2] 杨 维, 李歧强. 粒子群优化算法综述[J].中国工程科学,2004(6):87-94.

YANG Wei, LI Qi2qiang.Survey on particle swarm optimization algorithm [J]. Engineering Science, 2004(6): 87-94.

[3]李爱国, 覃 征, 鲍复民等. 粒子群优化算法[J ].计算机工程应用,2002(3) :1-3.

LI Aiguo, QIN Zheng, BAO Fumin,etal. Particle swarm op2timization algorithm [J]. Computation Eng Application, 2002(3):1-3.

[4] 王正志,薄 涛. 进化算法[M].长沙:国防科技大学出版社,2000.

WANG Z，！hengzhi, BO Tao. Manipulation algorithm [M].Changsha: National University of Defense Technology Publisher Press, 2000.

[5] Shi Y, Eberhart R C. A modified particle swarm optimizer [R] .IEEE International Conference of Evolutionary Computation, Anchorage, Alaska, May 1998.

[6] 张 燕, 汪 镭, 康 琦等.微粒群优化算法及其改进形式综述[J].计算机工程与应用, 2005, 41(2).

[7] 顾正彬 李贺军等.人工神经网络在复合材料研究中的应用.宇航计测技术,2003,23(4).