pso的离散算法

很多优化问题涉及到离散或二值的变量，典型的例子包括调度问题或路由问题。而PSO算法的更新公式和过程是面向连续空间并为其设计的，因此需要做一些修改使之适应离散空间的情况。编码的修改可能很简单，难点在于定义速度的意义和确定轨迹的变化。

Kennedy定义了第一个离散二进制版本的PSO算法。微粒使用二进制字符串进行编码。通过使用sigmoid函数，速度被限制在[0, 1]区间之内，并被解释为“概率的变化”。Yang对该方法在量子空间进行了扩展。

Mohan提出了几种二进制方法（直接方法、量子方法、正则方法、偏差向量方法以及混合方法），但是从有限的实验中没有得出什么结论。Clerc对一些专用于某些约束优化问题如TSP问题的PSO算法变种进行了试验，结果显示该方法比较有前途。Pang使用模糊矩阵来表示微粒的位置和速度，对PSO算法的算符进行了重定义，并将其应用到TSP问题的求解。Pampara将PSO算法与信号处理中的角调制技术结合起来，将高维二进制问题降维为一个在连续空间中定义的四维问题，并通过求解该四维问题来获得原问题的解。Afshinmanesh重新定义了离散PSO算法中的加法与乘法，并使用人工免疫系统中的阴性选择来实现速度限制Vmax。

Hu提出了一种改进PSO算法来处理排列问题。微粒被定义为一组特定值的排列，速度基于两个微粒的相似度重新定义，微粒根据由它们的速度所定义的随机率来变换到一个新的排列。引入了一个变异因子来防止当前的pBest陷入局部最小。在n皇后问题上的初步研究显示改进的PSO算法在解决约束满意问题方面很有前途。

Migliore对原始的二进制PSO算法进行了一些改进，提出了可变行为二进制微粒群算法（VB-BPSO）和可变动态特性二进制微粒群算法（VD-BPSO）。VB-BPSO算法按照连续PSO算法的速度更新公式的思想设计了一个新的速度更新公式，用来确定微粒位置向量每一位为1的概率。而VD-BPSO算法则是根据一定规则在两组不同参数确定的VB-BPSO算法之间切换。Migliore应用该算法设计出一种简单鲁棒的自适应无源天线。

Parsopoulos以标准函数为例测试微粒群优化算法解决整数规划问题的能力。Salman将任务分配问题抽象为整数规划模型并提出基于微粒群优化算法的解决方法。两者对迭代产生的连续解均进行舍尾取整后评价其质量。但是PSO算法生成的连续解与整数规划问题的目标函数评价值之间存在多对一的映射，以整型变量表示的目标函数不能准确反映算法中连续解的质量，而由此导致的冗余解空间与相应的冗余搜索降低了算法的收敛效率。

高尚采用交叉策略和变异策略，将PSO算法用来解决集合划分问题。赵传信重新定义了微粒群位置和速度的加法与乘法 *** 作，并将PSO算法应用到0/1背包问题求解中。EL-Gallad在PSO算法中引入探索和勘探两个算子，用于求解排序问题。Firpi提出了BPSO算法的一种保证收敛的版本（但是并未证明其保证收敛性），并将其应用到特征选择问题。

上述离散PSO算法都是间接的优化策略，根据概率而非算法本身确定二进制变量，未能充分利用PSO算法的性能。在处理整数变量时，PSO算法有时候很容易陷入局部最小。原始PSO算法的思想是从个体和同伴的经验进行学习，离散PSO算法也应该借鉴该思想。高海兵基于传统算法的速度—位移更新 *** 作，在分析微粒群优化机理的基础上提出了广义微粒群优化模型（GPSO），使其适用于解决离散及组合优化问题。GPSO 模型本质仍然符合微粒群优化机理，但是其微粒更新策略既可根据优化问题的特点设计，也可实现与已有方法的融合。基于类似的想法，Goldbarg将局部搜索和路径重连过程定义为速度算子，来求解TSP问题。

摘 要：，粒子群算法据自己的速度来决定搜索过程，只有最优的粒子把信息给予其他的粒子，整个搜索更新过程是跟随当前最优解的过程，所有的粒子还可以更快的收敛于最优解。由于微粒群算法简单，容易实现，与其它求解约束优化问题的方法相比较，具有一定的优势。实验结果表明，对于无约束的非线性求解，粒子群算法表现出较好的收敛性和健壮性。

关键词：粒子群算法；函数优化；极值寻优

0 引言

非线性方程的求根问题是多年来数学家努力解决的问题之一。长期以来，人们已找出多种用于解决方程求根的方法，例如牛顿法、弦割法、抛物线法等。然而，很多传统的方法仅能运用于相应的小的问题集，推广性相对较差。对于一个现实世界中的优化问题，必须尝试很多不同的方法，甚至要发明相应的新的方法来解决，这显然是不现实的。我们需要另外的方法来克服这样的困难。

粒子群算法是一种现代启发式算法，具有推广性强、鲁棒性高等特点[1]。该算法具有群体智能、内在并行性、迭代格式简单、可快速收敛到最优解所在区域等优点[2]。本文采用粒子群算法，对函数的极值进行寻优计算，实现了对函数的极值求解。

1 粒子群算法

11 基本原理

粒子群算法（PSO）是一种基于群体的随机优化技术，它的思想来源于对鸟群捕食行为的研究与模拟。粒子群算法与其它基于群体的进化算法相类似，选用“群体”和“进化”的概念，按照个体的适应度值进行 *** 作，也是一种基于迭代的寻优技术。区别在于，粒子群算法中没有交叉变异等进化算子，而是将每个个体看作搜索空间中的微粒，每个微粒没有重量和体积，但都有自己的位置向量、速度向量和适应度值。所有微粒以一定的速度飞行于搜索空间中，其中的飞行速度是由个体飞行经验和群体的飞行经验动态调整，通过追踪当前搜索到的最优值来寻找全局最优值。

12 参数选择

粒子群算法需要修改的参数很少，但对参数的选择却十分敏感。El-Gallad A, El-Hawary M, Sallam A, Kalas A[3]主要对算法中的种群规模、迭代次数和粒子速度的选择方法进行了详细分析，利用统计方法对约束优化问题的求解论证了这 3 个参数对算法性能的影响，并给出了具有一定通用性的3 个参数选择原则[4]。

种群规模：通常根据待优化问题的复杂程度确定。

最大速度：决定粒子在一次迭代中的最大移动距离,通常设定为不超过粒子的范围宽度。

加速常数：加速常数c1和c2通常是由经验值决定的，它代表粒子向pbest和gbest靠拢的加速项的权重。一般取值为：c1=c2=2。

中止条件：达到最大迭代次数或得到最小误差要求，通常要由具体问题确定。

惯性权重：惯性权重能够针对待优化问题调整算法的局部和全局搜索能力。当该值较大时有利于全局搜索，较小时有利于局部搜索。所以通常在算法开始时设置较大的惯性权重，以便扩大搜索范围、加快收敛。而随着迭代次数的增加逐渐减小惯性权重的值，使其进行精确搜索，避免跳过最优解。

13 算法步骤

PSO算法步骤如下：

Step1：初始化一个规模为 m 的粒子群，设定初始位置和速度。

初始化过程如下：

（1）设定群体规模m;

（2）对任意的i，s，在[-xmax, xmax]内均匀分布，产生初始位置xis；

（3）对任意的i，s，在[-vmax, vmax]内均匀分布，产生速度vis；

（4）对任意的i，设yi=xi，保存个体。

Step2：计算每个粒子的适应度值。

Step3：对每个粒子的适应度值和得到过的最好位置pis的适应度值进行比较，若相对较好，则将其作为当前的最好位置。

Step4：对每个粒子的适应度值和全局得到过的最好位置pgs的适应度值进行比较，若相对较好，则将其作为当前的全局最好位置。

Step5：分别对粒子的所在位置和速度进行更新。

Step6：如果满足终止条件，则输出最优解；否则，返回Step2。

14 粒子群算法函数极值求解

粒子群算法优化是计算机智能领域，除蚁群算法外的另一种基于群体智能的优化算法。粒子群算法是一种群体智能的烟花计算技术。与遗传算法相比，粒子群算法没有遗传算法的选择（Selection）、交叉（Crossover）、变异（Mutation）等 *** 作，而是通过粒子在解空间追随最优的粒子进行搜索。

粒子群算法流程如图所示：

粒子群为由n个粒子组成的种群X = (X1,X2,X3,…Xn)

第i个粒子表示一个D维向量Xi = (X1,X2,X3,…XD)T

第i个粒子的速度为Vi = (Vi1,Vi2,Vi3,…ViD)T

个体极值为Pi = (Pi1,Pi2,Pi3,…PiD)T

全局极值为Pg = (Pg1,Pg2,Pg3,…PgD)T

速度更新为，式中，c1和c2为其两个学习因子的参数值；r1和r2为其两个随机值。

位置更新为

2 粒子群算法应用举例

21 实验问题

这是一个无约束函数的极值寻优，对于Ackley函数，

其中c1=20，e=2 71289。

22 实验步骤

对于Ackley函数图形，选取一个凹峰进行分析，程序运行结果如图所示。

图1 Ackley函数图形

可以看出，选取区间内的Ackley函数图形只有一个极小值点。因此，对于该段函数进行寻优，不会陷入局部最小。采用粒子群算法对该函数进行极值寻优。

首先，进行初始化粒子群，编写的MATLAB代码如下：

% 初始化种群

for i=1:sizepop

x1 = popmin1 (popmax1-popmin1)rand;

% 产生随机个体

x2 = popmin2 (popmax2-popmin2)rand;

pop(i,1) = x1; % 保存产生的随机个体

pop(i,2) = x2;

fitness(i) = fun([x1,x2]); % 适应度值

V(i,1) = 0; % 初始化粒子速度

V(i,2) = 0;

end

程序运行后所产生的个体值为：

表1 函数个体值

然后，根据待寻优的目标函数，计算适应度值。待寻优的目标函数为：

function y = fun(x)

y=-20exp(-02sqrt((x(1)^2x(2)^2)/2))-exp((cos(2pix(1)) cos(2pix(2)))/2) 20 271289;

根据每一组个体，通过目标函数，得到的适应度值为：

表2 函数适应度值

搜索个体最优极值，即搜索最小的适应度值，我们可利用MATLAB绘图将所有个体的适应度值绘成plot图查看相对最小值。

图3 函数适应度plot图

从图中可看出，当个体=20时，得到相对最小值，在程序中，将其保存下来。

之后进行迭代寻优，直到满足终止条件。

最后，得到的最优值为：

图4 MATLAB运行得到结果

迭代后得到的运行结果图如下：

图5 迭代曲线图

23 实验结果

通过图5中可看出，该函数的寻优是收敛的，最优个体和实际情况较吻合。因此，采用粒子群算法进行函数极值寻优，快速、准确且鲁棒性较好。

3 结论

本文阐述了粒子群算法求解最化问题的过程，实验结果表明了该算法对于无约束问题的可行性。与其它的进化算法相比，粒子群算法容易理解、编码简单、容易实现。但是参数的设置对于该算法的性能却有很大的影响，例如控制收敛，避免早熟等。在未来的工作中，将努力于将其它计算智能算法或其它优化技术应用于粒子群算法中，以进一步提高粒子群算法的性能。

1 PSO收敛快，特别是在算法的早期，但存在着精度较低，易发散等缺点。加速系数、最大速度等参数太大，粒子可能错过最优解--------------->不收敛； 收敛的情况下，由于所有粒子都向最优的方向飞去，所有粒子趋向同一化（失去多样性）--------->使得 后期收敛速度明显变慢，搜索能力变弱 ，同时算法收敛到一定精度时，无法继续优化。

2 缺乏数学理论支持，PSO算法本质上是一种随机搜索算法，因此可靠性上让人存疑；

3 寻找一种好的拓扑结构，加强PSO算法的泛化能力；

4 平衡全局搜索和局部搜索能力；

（1）粒子群初始化：粒子群初始化对算法性能有一定的影响，分为粒子位置初始化和速度初始化。

         粒子群 位置 初始化的理想效果：初始种群尽可能 均匀覆盖整个 搜索空间。

         一、不推荐的初始化 ：a 均匀分布随机数

                                          缺点：1 对搜索空间的覆盖不够好；

                                                     2 当维度D增大时候，所有的粒子都倾向于靠近搜索空间的边缘：

                                     b 伪随机数初始化：造成粒子在参数空间的不均匀分布和聚集效应；

          二、推荐的初始化 ：a 基于centroidal voronoi tessellations (CVTs)的种群初始化方法（这东西是啥没搞懂）；

                                   b 采用正交设计方法对种群进行初始化；

                                   c 类随机采样方法中的sobol序列：使得粒子群在参数空间更加均匀；

                                   d Hammersley方法：感觉这个类似于类随机采样方法（具体我也没搞清楚）；

                                   e 将粒子建立为带电（positive charged）的模型，通过建立一个平衡方程，求解该方程的最小解获得粒子初始化位置；

                                   f 设置偏向的随机分布（推荐） ：即：我们通过对评价函数等一系列先验信息进行分析，得出最优解的可能存在空间范围，然后在这些范围内，着重撒点。就算再不济，也可以根据评价函数遵循Nearer is Better class（最优解更加可能在搜索空间的中心位置准则），在搜索空间的中心位置着重撒点。比如：

粒子群 速度 初始化：主要有如下五种方式：（根据实验表明，One-rand的效果最好。喂！！！这里One-rand的表达式是不是写错了啊？）

（2）领域拓扑：粒子的拓扑，决定了粒子所接受到的信息来源。

         一、全局模型gbest：最早的粒子群优化版本是全局PSO，使用全局拓扑结构，社会 只能 通过种群中， 最优的那个粒子 ，对每个粒子施加影响。

                                   1 优点：具有较快的收敛速度。

                                   2 缺点：粒子间的交流不够充分，但更容易陷入局部极值。

         二、局部模型lbest：采用每个粒子仅在一定的邻域内进行信息交换，，粒子之间的交流相对比较缓慢。

                                   1 优点：粒子更容易搜索问题空间中的不同地区。

                                   2 缺点：信息传递缓慢，设计相对复杂。

                                   3 分类：被动模型：微观领域、宏观领域、维度划分；主动模型。

                                   （1）微观邻域：细分到每个粒子。空间邻域(spatial neighborhood)、性能空间(performance space)邻域、社会关系邻域(sociometric neighborhood)。

                                            a 空间邻域：直接在搜索空间按粒子间的距离(如欧式距离)进行划分。在搜索初始阶段，将邻域定义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。

                                            b 性能空间领域：根据性能指标(如适应度、目标函数值)划分的邻域，如：适应度距离比值(fitness-distance-ratio)来选择粒子的相邻粒子。

                                            c 社会关系邻域： 按粒子存储阵列的索引编号进行划分，主要有：环形拓扑(ring or circle topology)、轮形拓扑(wheel topology)或星形拓扑(star topology)、塔形拓扑(pyramid topology)、冯－诺以曼拓扑(Von Neumann topology)以及随机拓扑(random topology)等。（随机拓扑往往对大多数问题能表现出较好的性能，其次是冯－诺以曼拓扑。）

                                   （2）宏观邻域：对群体进行划分。比如：使用簇分析将整个粒子群划分为多个簇，然后用簇中心代替带收缩因子PSO中的粒子历史最佳位置或群体历史最佳位置；根据粒子相似性动态地将粒子群体按种类划分为多个子种群，再以每个子种群的最佳个体作为每个粒子的邻域最佳位置；划分一个主群体，多个仆群体，仆群体进行独立的搜索，主群体在仆群体提供的最佳位置基础上开展搜索；每间隔一定代数将整个群体随机地重新划分；每个粒子除了自身和邻域最佳历史位置外，还学习邻域内其他粒子的 成功经验（只学好的，不学坏的） 等等；

                                   （3）维度划分：想法源自于：搜索空间维数较高时往往容易遭受“维数灾”的困扰。假设粒子群的整体维度为D，则可以将D划分成不同的部分，比如划分成k份，使用不同的群体，分别优化不同的维度。

                                   （4）主动模型：主动改变粒子邻域空间，避免碰撞和拥挤。比如：将粒子分为带电粒子和自然粒子，带电粒子接近会产生排斥；为每个粒子引入与邻近粒子距离成反比的自组织危险度，距离越近危险度越高，当危险度达到一定阈值，对粒子进行重新初始化，或者d开；为粒子赋一个半径，以检测两个粒子是否会发生碰撞，并且采取碰撞-d开方式将其分离。

（3）参数选择：三种参数：惯性权重或收敛因子、最大速度、两个加速因子。

         一、惯性权重：

                     a 惯性权重大：加强PSO 全局 搜索能力；惯性权重小：加强PSO 局部 搜索能力；

                     b 矛盾点：初始惯性权重大，局部搜索能力差，可能错过最优点；后期，惯性权重小，全局搜索能力不行，导致整个粒子群就陷入局部最优解。

                     c 优化方向：在适当的时候降低权重w，平衡全局和局部搜索能力；

                     d 优化建议：w随着更新代数的增加从09线性递减到04；

         二、压缩因子：

                     a 优势：惯性常数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足

                     b 优化建议：通常φ取41，χ得0729。

         三、最大速度的选择：为了抑制粒子更新的无规律的跳动，速度往往被限制在[-Vm,Vm]

                     a Vm增大，有利于全局 探索（exploration） ，但可能越过全局最优解；Vm减小，有利于局部 开发（exploitation） ，但可能陷入局部最优；

                     b 优化建议：一般设定为问题空间的10%~20%；或者动态调整Vm，比如：根据群体最佳适应和最差适应来进行调整；

         四、两个加速常数：加速常数C1和C2分别用于控制粒子指向自身或邻域最佳位置的运动。

                     a C1增大，粒子全局搜索能力好；C2增大，粒子向着最优靠拢局部能力好，但粒子会过早收敛；

                     b 优化建议：C1 = C2 = 20，并且C1+C2 <= 40;或者根据自适应调整，比如随着迭代次数增加，减小C1增大C2；

（4）混合法：PSO与其他方法结合。

                     这点我觉得，主要根据个人的学习积累来 *** 作。考虑方向：增加粒子群的局部搜索能力。

以上就是关于pso的离散算法全部的内容，包括:pso的离散算法、粒子群优化算法和多模态优化算法有什么区别、PSO优化方向等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！