粒子群算法基本原理【精品文档】(完整版)

4.1粒子群算法基本原理

粒子群优化算法[45]最原始的工作可以追溯到1987年Reynolds 对鸟群社会系统Boids （Reynolds 对其仿真鸟群系统的命名）的仿真研究 。通常，群体的行为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids 系统中采取了下面的三条简单的规则：

（1）飞离最近的个体(鸟)，避免与其发生碰撞冲突；

（2）尽量使自己与周围的鸟保持速度一致；

（3）尽量试图向自己认为的群体中心靠近。

虽然只有三条规则，但Boids 系统已经表现出非常逼真的群体聚集行为。但Reynolds 仅仅实现了该仿真，并无实用价值。

1995年Kennedy [46-48]和Eberhart 在Reynolds 等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中 。Kennedy 和Eberhart 在boids 中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy 和Eberhart 的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多种意义，于是作者用“粒子（particle ）”来称呼每个个体，这样就产生了基本的粒子群优化算法[49]。

假设在一个D 维搜索空间中，有m 个粒子组成一粒子群，其中第i 个粒子的空间位置为123(,,,...,)1,2,...,i i i i iD X x x x x i m ==，它是优化问题的一个潜在解，将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量i x 的优劣；第i 个粒子所经历的最好位置称为其个体历史最好位置，记为123(,,,...,)1,2,...,

i i i i i D P p p p p i m ==，相应的适应值为个体最好适应值 Fi ；同时，每个粒子还具有各自的飞行速度123(,,,...,)1,2,...,i i i i iD V v v v v i m ==。所有粒子经历过的位置中的最好位置称为全局历史最好位置，记为

123(,,,...,)D Pg Pg Pg Pg Pg =，

相应的适应值为全局历史最优适应值 。在基本PSO 算法中，对第n 代粒子，其第 d 维(1≤d ≤D )元素速度、位置更新迭代如式(4-1)、(4-2)：

11122()()n n n n n n id id id id gd id v v c r p x c r p x ω+=?+??-+??- (4-1) 1n n n id id id

x x v +=+ (4-2) 其中：ω为惯性权值；c1 和c2 都为正常数，称为加速系数；r1 和r2 是两个在[0, 1]范围内变化的随机数。第 d 维粒子元素的位置变化范围和速度变化范围分别限制为,min ,max ,d d X X ????和,min ,max ,d d V V ????。迭代过程中，若某一维粒子元素的id X 或id V 超出边界值则令其等于边界值。

粒子群速度更新公式(4-1)中的第 1部分由粒子先前速度的惯性引起，为“惯性”部分；第 2 部分为“认知”部分，表示粒子本身的思考，即粒子根据自身历史经验信息对自己下一步行为的影响；第 3部分为“社会”部分，表示粒子之间的信息共享和相互合作，即群体信息对粒子下一步行为的影响。

基本PSO 算法步骤如下：

（1）粒子群初始化；

（2）根据目标函数计算各粒子适应度值，并初始化个体、全局最优值；

（3）判断是否满足终止条件，是则搜索停止，输出搜索结果；否则继续下步；

（4）根据速度、位置更新公式更新各粒子的速度和位置；

（5）根据目标函数计算各粒子适应度值；

（6）更新各粒子历史最优值以及全局最优值；

（7）跳转至步骤3。

对于终止条件，通常可以设置为适应值误差达到预设要求，或迭代次数超过最大允许迭代次数。

基本的连续 PSO 算法中，其主要参数，即惯性权值、加速系数、种群规模和迭代次数对算法的性能均有不同程度的影响 。

惯性权值ω的取值对 PSO 算法的收敛性能至关重要。在最初的基本粒子群算法中没有惯性权值这一参数 。最初的 PSO 算法容易陷入局部最小，于是在

其后的研究中引入了惯性权值来改善PSO 算法的局部搜索能力，形成了目前常用的基本PSO算法形式。取较大的ω值使得粒子能更好地保留速度，从而能更快地搜索解空间，提高算法的收敛速度；但同时由于速度大可能导致算法无法更好地进行局部搜索，容易错过最优解，特别是过大的ω会使得PSO 算法速度过大而无法搜索到全局最优。取较小的ω值则有利于局部搜索，能够更好地搜索到最优值，但因为粒子速度受其影响相应变小从而无法更快地进行全局搜索，进而影响算法收敛速度；同时过小ω值更是容易导致算法陷入局部极值。因此，一个合适的ω值能有效兼顾搜索精度和搜索速度、全局搜索和局部搜索，保证算法性能。

加速系数c1 和c2 代表每个粒子向其个体历史最好位置和群体全局历史最好位置的移动加速项的权值。较低的加速系数值可以使得粒子收敛到其最优解的过程较慢，从而能够更好搜索当前位置与最优解之间的解空间；但过低的加速系数值则可能导致粒子始终徘徊在最优邻域外而无法有效搜索目标区域，从而导致算法性能下降。较高的加速系数值则可以使得粒子快速集中于目标区域进行搜索，提高算法效率；但过高的加速系数值则有可能导致粒子搜索间隔过大，容易越过目标区域无法有效地找到全局最优解。因此加速系数对PSO 能否收敛也起重要作用，合适的加速系数有利于算法较快地收敛，同时具有一定的跳出局部最优的能力。

对于速度更新公式(4-1)中，若c1 = c2 = 0，粒子将一直以当前的速度进行惯性飞行，直到到达边界。此时粒子仅仅依靠惯性移动，不能从自己的搜索经验和其他粒子的搜索经验中吸取有用的信息，因此无法利用群体智能，PSO 算法没有启发性，粒子只能搜索有限的区域，很难找到全局最优解，算法优化性能很差。若c = 0，则粒子没有认知能力，不能从自己的飞行经验吸取有效信息，只有社会部分，所以c 又称为社会参数；此时收敛速度比基本PSO 快，但由于不能有效利用自身的经验知识，所有的粒子都向当前全局最优集中，因此无法很好地对整个解空间进行搜索，在求解存在多个局部最优的复杂优化问题时比基本PSO 容易陷入局部极值，优化性能也变差。若c2 = 0，则微粒之间没有社会信息共享，不能从同伴的飞行经验中吸取有效信息，只有认知部分，所以 c 又称为认知参数；此时个体间没有信息互享，一个规模为m 的粒子群等价于m 个1单个粒子

的运行，搜索到全局最优解的机率很小。

PSO 算法中，群体规模对算法的优化性能也影响很大。一般来说，群体规模越大，搜索到全局最优解的可能性也越大，优化性能相对也越好；但同时算法消耗的计算量也越大，计算性能相对下降。群体规模越小，搜索到全局最优解的可能性就越小，但算法消耗的计算量也越小。群体规模对算法性能的影响并不是简单的线性关系，当群体规模到达一定程度后，再增加群体规模对算法性能的提升有限，反而增加运算量；但群体规模不能过小，过小的群体规模将无法体现出群智能优化算法的智能性，导致算法性能严重受损。

对于最大允许迭代次数，较大的迭代次数使得算法能够更好地搜索解空间，因此找到全局最优解的可能性也大些；相应地，较小的最大允许迭代次数会减小算法找到全局最优解的可能性。对于基本连续PSO 来说，由于缺乏有效的跳出局部最优操作，因此粒子一旦陷入局部极值后就难以跳出，位置更新处于停滞状态，此时迭代次数再增多也无法提高优化效果，只会浪费计算资源。但过小的迭代次数则会导致算法在没有对目标区域实现有效搜索之前就停止更新，将严重影响算法性能。此外，随机数可以保证粒子群群体的多样性和搜索的随机性。最大、最小速度可以决定当前位置与最好位置之间区域的分辨率(或精度)。如果最大速度（或最小速度）的绝对值过大，粒子可能会因为累积的惯性速度太大而越过目标区域，从而无法有效搜索到全局最优解；但如果最大速度（或最小速度）的绝对值过小，则粒子不能迅速向当前全局最优解集中，对其邻域进行有效地搜索，同时还容易陷入局部极值无法跳出。

因此，最大、最小速度的限制主要是防止算法计算溢出、改善搜索效率和提高搜索精度。基本PSO 算法中只涉及基本的加、减、乘运算操作，编程简单，易于实现，关键参数较少，设定相对简单，所以引起了广泛的关注，目前已有多篇文献对PSO 算法进行综述。

为了进一步提高基本PSO 算法的寻优性能，大量研究工作致力于对基本PSO 算法的改进，主要集中于：

（1）对PSO 算法更新公式参数、结构的改进

主要是对基本PSO 算法的速度、位置更新公式中的参数、结构进行调节和增加，以进一步提高算法的优化性能，如引入了惯性权值的PSO算法、自适应

惯性权值PSO]算法 、模糊自适应惯性权值 PSO 算法、带收缩因子的 PSO 算法、Kalman 粒子群算法、带邻域算子的PSO 算法、具有社会模式的簇分析 PSO 算法 、被动集合PSO 算法等等。

（2）多群、多项PSO 算法

多群PSO 算法即引入多个群体进行优化搜索 ；而多相 PSO 算法中多群体的各个群体对不同的搜索目标以不同的方式进行搜索 。

（3）混合 PSO 算法

混合 PSO 算法的基本思想就是将 PSO 算法与其它不同算法相结合，实现优势互补，从而进一步提高PSO 算法的寻优性能，如模拟退火PSO 算法 、GA-PSO 混合算法等等。

在工程应用中，目前PSO 算法在函数优化 、神经网络训练 、调度问题 、故障诊断 、建模分析 、电力系统优化设计 、模式识别 、图象处理 、数据挖掘 等众多领域中均有相关的研究应用报道，取得了良好的实际应用效果。

4.2离散二进制PSO 算法

离散二进制优化算法具有很多优势，首先对于纯组合优化问题的表达形式要求优化算法是离散的，其次二进制算法可以表达浮点数，因此也同样适用于连续空间的问题求解。

4.2.1 KBPSO 算法

PSO 算法最初是用来对连续空间问题进行优化的，为了解决离散优化问题Kennedy 和 Eberhart 于 1997 年在基本 PSO 的基础上提出了一种离散二进制 PSO （KBPSO ）算法。在 KBPSO 算法中，粒子定义为一组由0，1 组成的二进制向量。KBPSO 保留了原始的连续PSO 的速度公式(4-1)，但速度丧失了原始的物理意义。在 KBPSO 中，速度值vid 通过预先设计的 S 形限幅转换函数()id Sig v 转换为粒子元素id x 取“1”的概率。速度值id v 越大，则粒子元素位置id x 取1的可能性越大，反之则越小。

(完整word版)基本粒子群算法的原理和matlab程序

基本粒子群算法的原理和matlab程序 作者——niewei120（nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy和Eberhart提出，是一种通用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i ，p i=(p i1,p i2,....,p iQ)，i=1,2,3,....,n。所有粒子搜索到的最优值p g，p g=(p g1,p g2,....,p gQ)，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1]区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为1 。

粒子群优化算法介绍及matlab程序

粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置

第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。

粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。

(完整word版)基本粒子群算法的原理和matlab程序.doc

基本粒子群算法的原理和matlab 程序 作者—— niewei120 （nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy 和 Eberhart 提出，是一种通 用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远， 那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i，p i=(p i1 ,p i2 ,....,p iQ )， i=1,2,3,....,n 。所有粒子搜索到的最优值p g， p g=(p g1 ,p g2,....,p gQ )，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为 2 。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1] 区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为 1 。

粒子群算法简介和使用

粒子群算法 题目：求∑==10 12)(i i x x f 的最小值 1粒子群简介 粒子群优化算法PSO 也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。粒子群优化算法是由Kennedy 和Eberhart 通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。 PSO 算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则更为简单，它没有遗传算法的“交叉”和“变异” 操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。 2算法的原理 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 假设在一个D 维的目标搜索空间中，有N 个粒子组成一个群落，其中第i 个

粒子表示为一个D 维的向量 ),,,(21iD i i i x x x X =，N i ,,2,1 = 第i 个粒子的“飞行 ”速度也是一个D 维的向量，记为 ),,21i iD i i v v v V ，（= ，3,2,1 =i 第i 个粒子迄今为止搜索到的最优位置称为个体极值，记为 ),,,(21iD i i best p p p p =，N i ,,2,1 = 整个粒子群迄今为止搜索到的最优位置为全局极值，记为 ),,,(21gD g g best p p p g = 在找到这两个最优值时，粒子根据如下的公式(2.1)和( 2.2)来更新自己的速度和位置： ())(2211id gd id id id id x p r c x p r c v w v -+-+*= (2.1) id id id v x x += (2. 2) 其中：1c 和2c 为学习因子，也称加速常数，1r 和2r 为[0，1]范围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为“惯性”或“动量”部分，反映了粒子的运动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常221==c c 。D i ,,2,1 =。id v 是粒子的速度，],[max max v v v id -∈，max v 是常数，由用户设定用来限制粒子的速度。1r 和2r 是介于[0,1]之间的随机数。 探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全

粒子群算法基本原理

4.1粒子群算法基本原理 粒子群优化算法[45]最原始的工作可以追溯到1987年Reynolds 对鸟群社会系统Boids （Reynolds 对其仿真鸟群系统的命名）的仿真研究 。通常，群体的行为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids 系统中采取了下面的三条简单的规则： （1）飞离最近的个体(鸟)，避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则，但Boids 系统已经表现出非常逼真的群体聚集行为。但Reynolds 仅仅实现了该仿真，并无实用价值。 1995年Kennedy [46-48]和Eberhart 在Reynolds 等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中 。Kennedy 和Eberhart 在boids 中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy 和Eberhart 的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多种意义，于是作者用“粒子（particle ）”来称呼每个个体，这样就产生了基本的粒子群优化算法[49]。 假设在一个D 维搜索空间中，有m 个粒子组成一粒子群，其中第i 个粒子的空间位置为123(,,,...,)1,2,...,i i i i iD X x x x x i m ==，它是优化问题的一个潜在解，将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量i x 的优劣；第i 个粒子所经历的最好位置称为其个体历史最好位置，记为123(,,,...,)1,2,...,i i i i iD P p p p p i m ==，相应的适应值为个体最好适应值 Fi ；同时，每个粒子还具有各自的飞行速度123(,,,...,)1,2,...,i i i i iD V v v v v i m ==。所有粒子经历过的位置中的最好位置称为全局历史最好位置，记为

粒子群算法详解-附matlab代码说明

粒子群算法(1)----粒子群算法简介 一、粒子群算法的历史 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 所以CAS系统中的主体具有4个基本特点（这些特点是粒子群算法发展变化的依据）： 首先，主体是主动的、活动的。 主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。 环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。 最后，整个系统可能还要受一些随机因素的影响。 粒子群算法就是对一个CAS系统－－－鸟群社会系统的研究得出的。 粒子群算法（Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下：

粒子群算法(1)----粒子群算法简介

粒子群算法(1)----粒子群算法简介 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO.中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0，4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0，4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化

第一次更新位置 第二次更新位置

第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。

粒子群算法

t0=clock; >>citys=[565 575;25 185;345 750;945 685;845 655;880 660;25 230;525 1000;580 1175;650 1130;1605 620;1220 580;1465 200;1530 5;845 680;725 370;145 665;415 635;510 875;560 365;300 465;520 585;480 415;835 625;975 580;1215 245;1320 315;1250 400;660 180;410 250;420 555;575 665;1150 1160;700 580;686 595;685 610;770 610;795 645;475 960;95 260;875 920;700 500;555 815;830 485;1170 65;830 610;605 625;695 360;1340 725;1740 245]; >> n=size(citys,1); >> D=zeros(n,n); >> for i=1:n for j=1:n if i~=j D(i,j)=sqrt(sum(citys(i,:)-citys(j,:).^2)); else D(i,j)=1e-4; end end end >> m=31; >> alpha=1; >> beta=5; >>vol=0.2; >> Q=10;

>>Heu_F=1./D; >> Tau=ones(n,n); >> Table=zeros(m,n); >>iter=1; >>iter_max=100; >>Route_best=zeros(iter_max,n); >>Length_best=zeros(iter_max,1); >>Length_ave=zeros(iter_max,1); >>Limit_iter=0; >> while iter<=iter_max start=zeros(m,1); for i=1:m temp=randperm(n); start(i)=temp(1); end Table(:,1)=start; citys_index=1:n; for i=1:m for j=2:n tabu=Table(i,1:(j-1)); allow_index=~ismember(citys_index,tabu); allow=citys_index(allow_index)

粒子群优化算法及其应用研究【精品文档】(完整版)

摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度

目录 摘要...................................................................... I 目录....................................................................... II 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 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22)

粒子群算法论文

粒子群算法论文 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#

粒子群算法的寻优算法 摘要：粒子群算法是在仿真生物群体社会活动的基础上，通过模拟群体生物相互协同寻优能力，从而构造出一种新的智能优化算法。这篇文章简要回顾了粒子群算法的发展历史；引入了一个粒子群算法的实例，对其用MATLAB进行编程求解，得出结论。之后还对其中的惯性权重进行了延伸研究，对惯性权重的选择和变化的算法性能进行分析。 关键词：粒子群、寻优、MATLAB、惯性权重 目录：

1.粒子群算法的简介 粒子群算法（Particle Swarm Optimization）是一种新的智能优化算法。谈到它的发展历史，就不得不先介绍下传统的优化算法，正因为传统优化算法自身的一些不足，才有新智能优化算法的兴起，而粒子群算法（PSO）就是在这种情况下发展起来的。 粒子群算法的研究背景 最优化是人们在科学研究、工程技术和经济管理等领域中经常遇到的问题。优化问题研究的主要内容是在解决某个问题时，如何从众多的解决方案中选出最优方案。它可以定义为：在一定的约束条件下，求得一组参数值，使得系统的某项性能指标达到最优（最大或最小）。传统的优化方法是借助于优化问题的不同性质，通常将问题分为线性规划问题、非线性规划问题、整数规划问题和多目标规划问题等。相应的有一些成熟的常规算法，如应用于线性规划问题的单纯形法，应用于非线性规划的牛顿法、共扼梯度法，应用于整数规则的分枝界定法、动态规划等。列举的这些传统的优化算法能够解决现实生活和工程上的很多问题，但工业和科学领域大量实际问题的困难程度正在日益增长，它们大多是根本无法在可接受的时间内找到解的问题。这类优化问题的困难性不仅体现在具有极大的规模，更为重要的是，它们多数是非线性的、动态的、多峰的、具有欺骗性的或者不具有任何导数信息。因此，发展通用性更强、效率更高的优化算法总是需要的。 起源 在自然界中，鸟群运动的主体是离散的，其排列看起来是随机的，但在整体的运动中它们却保持着惊人的同步性，其整体运动形态非常流畅且极富美感。这些呈分布状态的群体所表现出的似乎是有意识的集中控制，一直是许多研究者感兴趣的问题。有研究者对鸟群的运动进行了计算机仿真，他们通过对个体设定简单的运动规则，来模拟鸟群整体的复杂行为。 1986 年 Craig ReynolS 提出了 Boid 模型，用以模拟鸟类聚集飞行的行为，通过对现实世界中这些群体运动的观察，在计算机中复制和重建这些运动轨迹，并对这些运动进行抽象建模，以发现新的运动模式。之后，生物学家Frank Heppner 在此基础上增加了栖息地对鸟吸引的仿真条件，提出了新的鸟群模型。这个新的鸟群模型的关键在于以个体之间的运算操作为基础，这个操作也就是群体行为的同步必须在于个体努力维持自身与邻居之间的距离为最优，为此每个个体必须知道自身位置和邻居的位置信息。这些都表明群体中个体之间信息的社会共享有助于群体的进化。

粒子群算法原理及在函数优化中的应用(附程序)

粒子群算法原理及其在函数优化中的应用 1粒子群优化(PSO)算法基本原理 1.1标准粒子群算法 假设在一个D 维的目标搜索空间中，有 m 个代表问题潜在解的粒子组成一 个种群x [X i ,X 2,...,X m ],第i 个粒子的信息可用D 维向量表示为 X i [X ii , X i2,..., X iD ]T ，其速度为V i [V ii ,V i2,...,V iD ]T 。算法首先初始化m 个随机粒 子，然后通过迭代找到最优解。每一次迭代中，粒子通过跟踪2个极值进行信息 交流，一个是第i 个粒子本身找到的最优解，称之为个体极值，即 P i [P il , P i2,...,厢]丁 ；另一个是所有粒子目前找到的最优解，称之为群体极值， 即P g [P gi ,P g2,..., P gD 「。粒子在更新上述2个极值后，根据式(1)和式(2)更新自 己的速度和位置。 t 1 t t t t t\ V i WV i C 1「1（P i X i ） C 2「2（P g X i ） 式中，t 代表当前迭代次数，「1,「2是在[0,1]之间服从均匀分布的随机数，C 1,C 2 称为学习因子，分别调节粒子向个体极值和群体极值方向飞行的步长， w 为惯性 权重，一般在0.1~0.9之间取值。在标准的PSO 算法中，惯性权重w 被设为常数, 通常取w 0.5。在实际应用中，x 需保证在一定的范围内，即x 的每一维的变化 范围均为[X min ,X max ],这在函数优化问题中相当丁自变量的定义域 1.2算法实现步骤 步骤1:表示出PSO 算法中的适应度函数fitness(x)；(编程时最好以函数的 形式保存，便丁多次调用。) 步骤2:初始化PSO 算法中各个参数(如粒子个数，惯性权重，学习因子， 最大迭代次数等)，在自变量x 定义域内随机初始化x ，代入fitness(x)求得适应 度值，通过比较确定起始个体极值P i 和全局极值P g 。 步骤3:通过循环迭代更新x 、p i 和p g : ① 确定惯性权重w 的取值(当w 不是常数时)。 ② 根据式(1)更新粒子的速度V ：1,若速度中的某一维超过了 V max ，则取为 V max - ③ 根据式(2)更新自变量x ,若x 的取值超过其定义域，则在其定义域内重新 初t 1 X i t t 1 X i V i

粒子群算法实例

粒子群算法解决函数优化问题 学院：信息科学与工程学院

目录 引言 (1) 一、问题描述 (2) 1.1 连续函数求最优值问题 (2) 1.2 粒子群算法 (2) 二、算法设计 (3) 2.1 流程框图 (3) 2.2 算法实现 (3) 2.3 参数选择 (4) 三、程序设计 (5) 3.1 编写程序 (5) 四、结果与分析 (6) 4.1 实验结果： (6) 4.2 分析： (7) 五、总结 (7)

引言 本文主要利用粒子群算法解决连续函数的最小值问题，粒子群优化是一种新兴的基于群体智能的启发式全局 搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。本文介绍了粒子群优化算法的基本原理，分析了其特点，并将其应用于函数优化问题求解。 求函数最优值问题，对此问题，传统的优化技术很容易陷入局部最优解，求得全局优化解的概率不高，可靠性低；为此，建立尽可能大概率的求解全局优化解算法是求解函数优化的一个重要问题。本文采用粒子群算法来解决这类问题。

一、问题描述 1.1 连续函数求最大值问题 本文主要选取一个三维函数，利用matlab 编写粒子群算法程序来求解它们 以验证遗传算法在解决函数优化问题中的有效性。本文选取的函数为：f=x(1).^2+x(2).^2+x(3).^2，求它的最小值。 1.2 粒子群算法 PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 假设在一个D 维的目标搜索空间中，有N 个粒子组成一个群落，其中第i 个粒子表示为一个D 维的向量 ) ,,,(21iD i i i x x x X =，N i ,,2,1 =。 第i 个粒子的“飞行 ”速度也是一个D 维的向量，记为 ) ,,21i iD i i v v v V ，（=，3 ,2,1 =i 。 第i 个粒子迄今为止搜索到的最优位置称为个体极值，记为 ) ,,,(21iD i i best p p p p =，N i ,,2,1 =。 整个粒子群迄今为止搜索到的最优位置为全局极值，记为 ) ,,,(21gD g g best p p p g = 在找到这两个最优值时，粒子根据如下的公式(1.1)和( 1.2)来更新自己的速度和位置： ()) (2211id gd id id id id x p r c x p r c v w v -+-+*= (1.1)

粒子群算法基本原理

4.1粒子群算法基本原理 粒子群优化算法昭最原始的工作可以追溯到1987年Reynolds对鸟群社会 系 统Boids （Reyn olds对其仿真鸟群系统的命名）的仿真研究。通常，群体的行 为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却 群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids系统中采取了下 面的三条简单的规则： （1 ）飞离最近的个体（鸟），避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则，但Boids系统已经表现出非常逼真的群体聚集行为。但Reynolds仅仅实现了该仿真，并无实用价值。 1995 年Kennedy [46-48]和Eberhart在Reynolds等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中。Kennedy和Eberhart在 boids中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy和Eberhart的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初 仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点"在数学领域具有多 种意义，于是作者用"粒子（particle ）"来称呼每个个体，这样就产生了基本 [49] 的粒子群优化算法。 假设在一个D维搜索空间中，有m个粒子组成一粒子群，其中第i个粒子 的空间位置为X （ x , x ,x，…,x ） i 1,2,..., m，它是优化问题的一个潜在解， i i1 i 2 i 3 iD 将它带入优化目标函数可以计算出其相应的适应值，根据适应值可衡量X的优 i

粒子群算法与遗传算法的比较

粒子群算法介绍 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度. 爬山法精度较高,但是易于陷入局部极小. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重 影响解的品质,而目前这些参数的选择大部分是依靠经验.1995 年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(Particle Swarm Optimization -PSO) 算法. 这种算法以 其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。 粒子群优化(Particle Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolutionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随 当前搜索到的最优值来寻找全局最优。 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士提出。源于对鸟群捕食的行为研究。 PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域 2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容： 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的. 现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局 部信息从而可能产生不可预测的群体行为 例如floys和boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计. 在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上. 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的 过程. 但后来发现PSO是一种很好的优化工具.

粒子群优化算法综述

粒子群优化算法 1. 引言 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究 PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍 同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域 2. 背景: 人工生命 "人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的容 1. 研究如何利用计算技术研究生物现象 2. 研究如何利用生物技术研究计算问题 我们现在关注的是第二部分的容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的. 现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为 例如floys 和boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计. 在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上. 粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具. 3. 算法介绍

粒子群算法介绍

1.介绍： 粒子群算法（Particle Swarm Optimization, PSO）最早是由Eberhart 和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 经过实践证明：全局版本的粒子群算法收敛速度快，但是容易陷入局部最优。局部版本的粒子群算法收敛速度慢，但是很难陷入局部最优。现在的粒子群算法大都在收敛速度与摆脱局部最优这两个方面下功夫。其实这两个方面是矛盾的。看如何更好的折中了。 粒子群算法主要分为4个大的分支： （1）标准粒子群算法的变形 在这个分支中，主要是对标准粒子群算法的惯性因子、收敛因子（约束因子）、“认知”部分的c1，“社会”部分的c2进行变化与调节，希望获得好的效果。 惯性因子的原始版本是保持不变的，后来有人提出随着算法迭代的进行，惯性因子需要逐渐减小的思想。算法开始阶段，大的惯性因子可以是算法不容易陷入局部最优，到算法的后期，小的惯性因子可以使收敛速度加快，使收敛更加平稳，不至于出现振荡现象。经过本人测试，动态的减小惯性因子w，的确可以使算法更加稳定，效果比较好。但是递减惯性因子采用什么样的方法呢？人们首先想到的是线型递减，这种策略的确很好，但是是不是最优的呢？于是有人对递减的策略作了研究，研究结果指出：线型函数的递减优于凸函数的递减策略，但是凹函数的递减策略又优于线型的递减，经过本人测试，实验结果基本符合这个结论，但是效果不是很明显。 对于收敛因子，经过证明如果收敛因子取0.729,可以确保算法的收敛，但是不能保证算法收敛到全局最优，经过本人测试，取收敛因子为0.729效果较好。对于社会与认知的系数c2,c1也有人提出：c1先大后小，而c2先小后大的思想，因为在算法运行初期，每个鸟要有大的自己的认知部分而又比较小的社会部分，这个与我们自己一群人找东西的情形比较接近，因为在我们找东西的初期，我们基本依靠自己的知识取寻

粒子群算法和蚁群算法的结合及其在组合优化中的应用e

2007年第2期空间电子技术收稿日期：2006-04-03；收修改稿日期：2006-04-30 粒子群算法和蚁群算法的结合及其在 组合优化中的应用 张长春苏昕易克初 （西安电子科技大学综合业务网国家重点实验室，西安710071） 摘要文章首次提出了一种用于求解组合优化问题的PAAA 算法。该算法有效地 结合了粒子群算法和蚁群算法的优点，先利用粒子群算法的随机性、快速性、全局性得到 初始信息素分布（即粗搜索），再利用蚁群算法的并行性、正反馈性、求解精度高等优点求 精确解（即细搜索）。将文中提出的算法用于经典TSP 问题的求解，仿真结果表明PAAA 算 法兼有两种算法的优点，同时抛弃了各自的缺点。该算法在时间效率上优于蚁群算法，在 求精效率上优于粒子群算法，是综合了两种算法长处的一种新的启发式算法，达到时间性 能和优化性能上的双赢，获得了非常好的效果。 主题词蚁群算法粒子群算法旅行商问题PAAA 0引言 近年来对生物启发式计算（Bio-inspired Computing ）的研究，越来越引起众多学者的关注和兴趣，产生了神经网络、遗传算法、模拟退火、粒子群算法、蚁群算法等许多用于解决复杂优化问题的新方法。然而，面对各种问题的特殊性和复杂性，每种算法都表现出了自身的优势和缺陷，都存在时间性能和优化性能不能兼得的矛盾。 粒子群优化（Particie Swarm Optimization ，PSO ）算法[1， 2]是由Eberhart 和Kennedy 于1995年提出的一种全局优化算法，该算法源于对鸟群觅食行为的模拟。它的优势在于：（1） 算法简洁，可调参数少，易于实现；（2） 随机初始化种群，具有较强的全局搜索能力，类似于遗传算法；（3）利用评价函数衡量个体的优劣程度，搜索速度快；（4）具有较强的可扩展性。其缺点是：不能充分利用系统中的反馈信息，求解组合优化问题的能力不强。 蚁群算法[3，4]（Ant Coiony Optimization ，ACO ） 是由意大利学者M.Dorigo ，V.Maniezzo 和A.Coiorni 于20世纪90年代初提出的一种新型的智能优化算法，已经被应用到TSP 问题[5，6]、二次分配问题、工 件调度问题、图着色问题等许多经典组合优化问题中，取得了很好的效果。它的优点是：（1）采用一种正反馈机制，通过信息素的不断更新，达到最终收敛于最优路径上的目的；（2）是一种分布式的优化方法，易于并行实现；（3）是一种全局优化的方法，不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；（4）适合于求解离散优化问题；（5）鲁棒性强。但由于在算法的初始阶段信息素匮乏，所以求解速度较慢。 文章将粒子群算法和蚁群算法有机地结合，提出了PAAA 算法。它利用粒子群算法的较强的全局搜索能力生成信息素分布，再利用蚁群算法的正反馈机制求问题的精确解，汲取各自的优势，以达空间电子技术 SPACE ELECTRONIC TECHNOLOGY !"