摘 要粒子群优化(PSO)算法是一种新颖的演化算法，该算法通过粒子间的相互作用在复杂搜索空间中发现最优区域。PSO的优势在于简单而功能强大。本文介绍了基本的PSO算法、 研究 现状及其在神经 网络 中的 应用 ，并探讨了未来的研究 内容 及 发展 方向。
关键词粒子群优化算法；神经网络；人工生命；群智能
许多群体生物的自适应优化现象不断给人类以启示，群居生物的群体行为使许多在人类看起来高度复杂的 问题 得到了完美的解决。 自然 界那些群居生物表现出来的智能让人惊叹不已，比如蜜蜂建造的巢穴结构庞大、复杂而精美；蚂蚁能够完成觅食、清扫、搬运等高效的工作等等。这种生物群体行为的奇妙之处在于个体都很简单，但他们却能协同工作，依靠群体的能力，发挥超出个体的智能，表现出极其复杂而有序的行为。这些奇妙的现象吸引着越来越多的学者进入到这个领域，研究这些简单的个体如何通过协作涌现出如此复杂而奇妙行为，通过 计算 机模拟来探索其中的可循 规律 ，用于指导并解决一些常规 方法 没有解决的传统问题以及实际应用中出现的新问题[1-3]。这些研究孕育并产生了一门新兴的学科领域：群体智能(Swarm Intelligence)[1]。优化技术是一种以各种形式的数学处理方法为基础，用于求解各种工程问题优化解的应用技术，在诸多工程领域得到普遍的应用。鉴于实际工程问题的复杂性、约束性、非线性、多局部极小和建模困难等特点，寻找各种适合于工程实践需求的新型智能优化方法一直是许多学科的一个重要研究方向。群体智能作为一种新兴的智能计算技术已成为越来越多研究者的关注焦点，它与人工生命，特别是进化策略以及遗传算法有着特殊的联系。群体智能使得在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
微粒群算法[2]最初是为了图形化地模拟鸟群优美而不可预测的运动。自然界中，鸟群运动的主体是离散的，其排列看起来是随机的，但整体的运动却使它们保持着惊人的同步性，个体运动非常流畅而极富美感。研究者对鸟群的运动进行了计算机仿真，他们通过对个体设定简单的运动规则，来模拟鸟群整体的复杂行为。例如，1986年Craig Reynolds提出了Boid模型用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运动的观察在计算机中复制重建这些运动轨迹，并对这些运动进行抽象建模以发现新的运动模式。上述模型关键在于对个体间距离的操作，即群体行为的同步性在于个体努力维持自身与邻居之间的距离为最优，为此每个个体必须知道自身位置和邻居的信息。生物 社会 学家Wilson E.O.认为 “至少从 理论 上，在搜索食物的过程中群体中的个体成员可以得益于所有其它成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。”以上两例说明，群体中个体之间信息的社会共享有助于进化。受上述鸟群运动模型的 影响 ，社会心 理学 博士JamesK Ennedy和 电子 工程学博士Russell Eberhart于1995年提出了微粒群算法，微粒群算法是一种演化计算技术，在算法中，将鸟群运动模型中的栖息地类比于所求问题解空间中可能解的位置，通过个体间的信息传递，导引整个群体向可能解的方向移动，增加发现较好解的可能性。群体中的鸟被抽象为没有质量和体积的“微粒”，通过这些“微粒”的相互协作和信息共享，其运动速度受到自身和群体的 历史 运动状态信息影响，以自身和群体的历史最优位置来对微粒当前的运动方向和运动速度加以影响，较好地协调微粒本身和群体运动之间的关系，在复杂的解空间中寻找最优解。
微粒群算法自提出以来，已经历了许多变形和改进。包括数学家、工程师、物理学家、生物化学家以及心理学家在内的研究者对它进行 分析 和实验。到 目前 为止，国内外的研究者对微粒群算法的研究与发展，可以归纳为以下几个方面：[3]
(1) 参数选择与设计：在微粒群算法中存在几个显参数和隐参数，它们的值可被调整，以产生算法搜索问题空间的方式的变化。
(2) 种群拓扑结构：从19世纪40年代起的研究已经表明，组内的交流及最终组的性能要受社会网络结构的影响。于是，微粒群研究者提出了几种简单的社会结构，并对几种种群结构模型进行了分析与比较。全局最优模型(Gbest)和局部最优模型(Lbest) 是最常见的两种类型。
(3) 群体组织与进化[4]：社会心理学研究表明。人们的态度、信仰和行为倾向于朝同伴的方向变化，他们会根据自己所处群体的规范选择自己的意见和行为，受此启发，提出用簇来表示群体中的子种群，用簇中心代替最优值的算法模式。此外，为了保证群体的多样性，研究者将变异、繁殖和差异进化等思想引入微粒群，并提出了很多改进算法模式。
(4) 混合微粒群算法：将进化计算中的选择、交叉和变异等特性、混沌、免疫系统的免疫信息处理机制以及热力学中熵的概念等与微粒群算法中的寻优机制相结合，提出了相应的混合算法。
(5) 离散微粒群算法：微粒群算法最初是用来对连续函数进行优化的。而实际中许多问题是组合优化问题，因此，Kennedy和Eberhart博士在基本算法的基础上提出了一种离散二进制决策模型。
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，则该维的速度被限制为最大速度。
科学 研究与工程实践中有一些多目标优化问题[5](Multi - objective Optimization Problems， MOPs)通常难以处理，实际问题常由多个相互冲突的指标组成，问题的解一般不是单个的最优解，而是一组非劣解，因而采用传统多目标优化方法通常无法解决。由于PSO算法的生命力在于工程应用，为此开拓新的PSO算法的应用领域特别是在解决多目标优化问题上是一项很有意义的工作。
转贴于论文联盟 http://www.lwlm.com
关键词粒子群优化算法；神经网络；人工生命；群智能
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算法的应用领域特别是在解决多目标优化问题上是一项很有意义的工作。
转贴于论文联盟 http://www.lwlm.com
收藏