1、摘要粒子群优化算法(Particle Swarm Optimization，PSO)是由美国的Eberhart和Kennedy在1995年提出的一种高效的并行优化算法。由于该算法具有深刻的智能背景，且简单、易实现，因此，一经提出便引起了许多学者的广泛关注，并在短短的几年里出现了大量的研究成果，现已成为研究的热点。目前，已提出了多种PSO的改进算法，被广泛应用于函数优化、神经网络训练、模式分类、模糊系统控制等领域。但其应用大多是连续优化问题，很少被用来解决离散问题，而现实生活中的许多工程实例只能抽象出离散模型，如典型的旅行商问题(Traveling Salesman Problem，TSP)、加
2、工调度(Job-slmp)问题、最短路径问题等。最短路径问题是图论中的一个典范问题。从网络模型的角度看最短路径分析就是在指定网络的两节点间找一条阻碍强度最小的路径。最短路径问题的研究在汽车实时导航、应急救援等领域有广泛的应用。经典的Dijkstra算法是应用最短路径解决实际问题的理论基础。但是算法在具体的城市道路网络中执行的效率比较低，无法满足实时高效的应用需求，因此国内外很多学者开始了最短路径问题的粒子群优化算法研究。本文主要是研究在最短路径问题中的粒子群算法。文中给出了基于交换序的基本的粒子群算法，并在此基础上提出了一种改进的粒子群算法。基本的粒子群算法是在计算完粒子速度之后再更新粒子的位
3、置，改进算法则是计算粒子速度的同时更新粒子的位置。文中还引入自适应惯性权重的改进策略，使粒子在开始时惯性速度大，能快速的向最优值点运动，而在粒子迭代过程中惯性速度越来越小，从而使粒子能更好的接近最优值点。引入罚函数，把约束优化问题转化为无约束优化问题来解，从而减化求解过程。本文用实例对基本的粒子群算法和改进粒子群算法进行了对比分析，并得出了改进算法确实存在优势的结论。文中还对算法的主要参数如何取值进行了分析，并结合经验给出了总结。本文最后用实例验证了算法确实在执行了若干次迭代后收敛。程序的编程环境为Microsoft Visual Studio 2008,编程语言为C#。关键词： 粒子群算法
4、最短路径 约束优化 惯性权重 粒子群优化算法理论2.1粒子群优化算法基本定义群居昆虫以集体的力量觅食、御敌、筑巢，单个个体只能完成简单的认务，而由单个个体组成的群体却能完成复杂的认务，这种群体所表现出来的“智能”称为群体智能(Swarm Intelligence,SI)1。如蜜蜂采蜜、筑巢，蚂蚁觅食、筑巢等。从群居昆虫互相合作进行工作中得到启迪，研究其中的原理，以此设计新的算法被称为群智能算法2。粒子群优化算法是一种新兴的群智能优化算法，其思想来源于人工生命和演化计算理论，粒子在解空间根据所处的情况进行搜索，容易实现并且没有许多参数需要调整，另外收敛速度快，相对于遗传算法等更简单有效。PSO已
5、经得到众多学者的重视和研究3-4，在许多实际应用中被证明是有效的。国际上已有专门从事相关科研内容的研究组织以及进行学术交流和会议发布的网站和论坛。基本定义5定义1：（粒子） d-粒子p是维度为d的空间粒子，简称粒子；d称做粒子的维度，p=(x1,x2,.,xj,.xd)为d-粒子空间。定义 2：（粒子群） n-种群是n个粒子组成的群落（粒子允许重复），简称粒子群。N称为粒子群规模,Snp|pi=(xi,1,xi,2,xi,j,xi,d),in为n-种群空间。定义 3：（个性算子）粒子在d维解空间搜索的过程中，下一步的飞翔速度和到达的位置与粒子自身的飞翔速度有关，即V(t+1)=wV(t),该操
6、作称为个性算子。定义 4：（自意识算子）粒子在d维解空间搜索过程中，下一步的飞翔速度和到达的位置与粒子自身到当前为止所到达的最好位置有关。也就是说，粒子在d维解空间搜索的过程中受到粒子自身的经历影响，在整个飞翔过程中一直下意识地根据自身的经验调整飞行速度和方向，即Vi,j(t+1)=c1U(0,1)(Xi,j#(t)-Xi,j(t) (2-1)该操作称为自意识算子。C1是正常数，称为自意识学习因子；U(0,1)是0,1区间正态分布的随机数。定义 5：（群意识算子）粒子在d 维解空间搜索的过程中，下一步的飞翔速度和到达的位置与粒子群到当前为止所到达的最好位置有关。也就是说，粒子在d维解空间搜索过
7、程中受粒子群的经历影响，在整个飞翔过程中一直下意识得根据粒子群的经验调整飞行速度和方向，即 Vi,j(t+1)=c2U(0,1)(Xi,j*(t)-Xi,j(t) (2-2)该操作算子称为群意识算子。C2是正常数，称为群意识学习因子；U(0,1)是0,1区间正态分布的随机数。定义 6：（粒子种群多样性）粒子群中的粒子因在解空间飞行所到达的位置不同而搜索到不同的可行解，即因粒子的位置不同而表现出的多样性称为种群多样性。它是评价粒子群搜索可行解能力的重要尺度，由以下式给出： D= (2-3)其中，为粒子群的中心位置，它的第j维为i。2.2粒子群优化算法详细描述假设在一个群体中有popsize个粒子
8、,每个粒子是n维空间中的一个个体,不同的个体具有不同的位置 (j=1,2,popsize),不同的位置对应于不同的与优化目标函数值相关的个体适应度函数值fitness()。对于第j个粒子,以表示其位置,它在空间中以某个速度飞行,它所经历的最好位置为,也称为。群体中所有粒子所经历的最好位置为,也称为。若已知第k代第j个粒子的速度及位置,则第(k+1)代第j个粒子的速度及位置为: (2-4) (2-5)式中: 惯性权重系数,为迭代次数的函数,且随迭代次数线性减少,即 (2-6)这里,初始、终止惯性权重; 最大迭代代数;粒子自身加速度权重系数,一般在02之间取值;全局加速度权重系数,一般在02之间取
9、值;, 0,1范围内两个相互独立的、均匀分布的随机数,即,U(0,1)。 为了减少在搜索过程中粒子离开搜索空间的可能性,V通常被限定于一定的范围内,即-V。当然,亦可根据具体情况,将搜索空间限定于一定的范围内,即X。解优化问题的PSO流程图如下： 是否开 始初始化粒子群计算每个粒子新位置的适应值根据粒子适应值更新个体极值与全局极值根据(2-4)和(2-5)式,更新自己的速度和位置达到最大迭代次数数结 束 图 2-1 PSO流程图PSO的计算流程如下:Step1 初始化一群粒子(种群规模为popsize),包括随机位置和速 度,k=0;Step2 计算每个粒子的适应度值fitness();Ste
10、p3 对每个粒子,将其适应度值fitness()与其历史最好位置 的适应度值fitness()比较,若较好,则将其作为当前的最 好位置;Step4 对每个粒子,将其适应度值fitness()与全局所经历的最好位置的适应度值fitness()比较,若较好,则重新设置;Step5 用式(1)和式(2)计算和其中:(j=1,2,popsize);Step6若达到终止条件(通常为足够好的适应值或达到预设最大代数),则结束,返回当前全局最优个体即为结果;否则,k=k+1,转Step2。2.3粒子群优化算法特点PSO具有以下一些特点:(1)基本PSO算法最初是处理连续优化问题的。(2)类似于遗传算法，PS
11、O也是多点搜索。(3) 计算准确、效率高。(4)(2-4)式的第一项对应于多样化的特点，第二项、第三项对应于搜索过程中的集中化特点，因此这个方法在多样化和集中化之间建立均衡6。 PSO有全局版和局部版两种,全局版收敛快,但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟,假设每一个粒子在大小l的邻域内定为一个集合: (2-7)从Ni中选出最好的,将其位置作为lbest代替公式中的gbest,其他与全局版PSO相同。实验表明,局部版比全局版收敛慢,但不容易陷入局部最优7。在实际应用中,可以先用全局PSO找到大致的结果,再用局部PSO进行搜索。2.4 粒子群优化算法几何特性PSO中每个
12、优化问题的解都是搜索空间中的一个“粒子”状态。所有粒子都有一个适应函数决定的适应值，每个粒子还有一个速度直接影响它们飞翔的距离。粒子根据当前的自身情况和粒子群的情况在解空间中搜索。PSO初始化时将一群粒子的状态赋随机值（随机解），根据式2-4和式2-5来更新速度和新的位置。在式2-4中等式右边共有三项。第一项是粒子上一次的速度与惯性权重W的乘积，惯性权重W对优化性能的影响，发现较大的W值有利于跳出局部极小点，而较小的W值有利于算法收敛。第二项是粒子自身行为差异比较。第三项是粒子群体行为差异比较。后两项合称为粒子的“意识”部分。每次迭代后粒子运动状态如下图2-2所示，在整个解空间搜索中粒子呈正弦
13、曲线摆动2。X#(t)X(t)V(t)X(t+1)X*(t) 图2-2 粒子飞翔状况的几何表示从粒子群优化算法的几何分析可知，如果一个粒子当前的位置与该粒子的当前最优值一致，该粒子会因为它以前的速度和惯性权重不为零而远离最佳位置导致算法不能收敛；如果以前的速度非常接近零，粒子一旦赶上了粒子群的当前最佳粒子，种群多样性就会慢慢消失，所有的粒子将会停止移动，粒子群最优化出现停滞状态，不能搜索到满意解，这种情况大多导致早熟。因此目前尚需设计新型操作算子或者解决方案。粒子群优化算法是一类随机全局优化技术，PSO算法通过粒子间的相互作用发现复杂搜索空间中的最优区域。PSO的优势在于简单、容易实现且功能强
14、大。PSO已成为国际演化计算界研究的热点。目前已经发表不少该方面的研究论文，且有部分开源VB和C代码可供参考。有兴趣的读者，可深入阅读相关参考文献。2.5粒子群优化算法参数分析对PSO算法中参数分析如下: 在PSO算法中有3个权重因子:惯性权重w,加速常数C1和C2。惯性权重w使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速因子C1和C2代表将每个粒子推向pbest和gbest位置的统计加速项的权重。低的值允许粒子在被拉回之前可以在目标区域外徘徊，而高的值则导致粒子突然冲向或超过目标区域。如果没有后两部分，即C1=C2=0，粒子将一直以当前的速度飞行，直到到达边界。由于它
15、只能搜索有限的区域，所以很难找到好解。如果没有第一部分，即w=0，则速度只取决于粒子当前位置和其历史最好位置pbest和gbest，速度本身没有记忆性。假设一个粒子位于全局最好位置，它将保持静止。而其他粒子则飞向它本身最好位置pbest和全局最好位置gbest的加权中心。在这种条件下，粒子群将收缩到当前的全局最好位置，更像一个局部算法。在加上第一部分后，粒子有扩展搜索空间的趋势，即第一部分有全局搜索能力。这也使得w的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。如果没有第二部分，即C1=0,则粒子没有认知能力，也就是“只有社会”的模型在粒子的相互作用下，有能力达到新的搜索空间。它
16、的收敛速度比标准版本更快，但对复杂问题，则比标准版本更容易陷入局部优值点。如果没有第三部分，即C2=0,则粒子之间没有社会信息共享，也就是“只有认知”的模型。因为个体间没有交互，一个规模为m的群体等价于运行了m个单个粒子的运行，因而得到解的机率非常小。早期的试验将w固定为1，C1和C2固定为2，因此Vmax成为唯一需要调节的参数，通常设为每维变化范围的1020。引入惯性权重w可消除对Vmax的需要，因为它们的作用都是维护全局和局部搜索能力的平衡。这样，当Vmax增加时，可通过减小w来达到使得所需的迭代次数变小。从这个意义上看，可以将Vmax固定为每维变量的变化范围，只对w进行调节。研究发现较大
17、惯性权重w值有利于跳出局部极小点，而较小的惯性权重w有利于算法收敛，因此提出自适应调整w的策略，即随迭代的进行，线性减小w的值，对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而在后期有较高的开发能力以加快收敛速度。为此可将w设为随时间线性减小，例如由1.4到1.0，或由0.9到0.4,或由0.95到0.2等。Suganthan的实验表明，C1和C2为常数时可以得到较好的解，但不一定必须为2。Clere引入收缩因子K来保证收敛性: (2-8)式中，T=2/|2-s-sqrt(s*s-4s)|,s=w1+w2,w4。这对应于1-3式中一种特殊的参数组合，其中T即一种受w1和w2
18、限制的w，而C1Tw1和C2Tw2。这些参数也可以通过模糊系统进行调节。Shi和Eberhart提出一个模糊系统来调节w，该系数包括9条规则，有两个输入和一个输出，每个输入和输出定义了3个模糊集。一个输入为当前的全局最好适应值，另一个为当前的w,输出为w的变化。结果显示该方法能大幅度提高平均适应值。此外，群体的初始化也是影响算法性能的一个方法。Aageline对不对称的初始化进行了实验，发现PSO只是略微受影响。Ozcan和Mohan通过假设w1、C1和C2为常数、pbest和gbest为固定点进行理论分析，得到一个粒子随时间变化可以描述为波的运行，并对不同的感兴趣的区域进行轨迹分析。这个分析
19、被Kennedy的模拟结果支持。一个寻求优值位置的粒子尝试着操纵它的频率和幅度，以捕获不同的波。W可以看作是修改了感兴趣的区域的边界，而Vmax则帮助粒子跳到另外一个波。2.6粒子群优化算法收敛性分析因为引入了随机量的原因,PSO的收敛性分析一直是研究的难点。Clerc对式(1)和(2)中的参数进行了初步分析8,尽管有明显缺陷,但仍具重要意义。 首先,定义: 式（2-9）简化成： (2-10)其中, 。进一步简化系统,假设、c不变,且解空间仅一维,研究一个粒子,则式(2-3)、(2-4)式可变为状态方程的形式: (2-11) P和r是常数,通过对状态转移矩阵(4)的稳定性分析,即可得出粒子运动
20、稳定性的约束条件。其结论如下: 当式(2-4)和式(2-5)中参数满足约束条件: (2-12),4 (2-13)时,在假设条件下粒子运动轨迹稳定。在此基础上,Bergh9做了进一步分析,研究随机性对粒子轨迹的影响,在Lebesgue和Borel测度空间上对收敛性做了分析。 PSO算法求解最短路径问题4.1 PSO算法的中数据的表达方式(1)所有边的权值数据存储为如下的矩阵：其中, n为顶点的数目。(2)源点-汇点的最短路径存储：其中，中存放了源点或汇点在数组中的位置，是顶点的编号，n为项点的数目。例4.1：顶点数为5，项点编号依次为0，1，2，3，4，一条路径为03214,源点的0,汇点为1,
21、则存储为如下所示：25032144.2初始化粒子本文在粒子初始化时，首先根据图的信息生成一张表示顶点连接信息的NM表,然后由表的信息计算出一张NM的粒子随机生成的概率表,最后由概率表来随机生成粒子.4.2.1生成顶点信息表顶点信息表的样式如表4-1.表4-1顶点信息表0Num_0A0,1A0,2A0,Num_01Num_1A1,1A1,2A1,Num_12Num_2.N-2Num_N-2AN-2,1AN-2,Num_N-2N-1Num_N-1AN-1,1AN-1,Num_N-1其中的第一列分别给出了此列信息是编号为i的顶点的连接信息.Num_i,表示编号为i的顶点共有Num_i个邻接顶点.Ai
22、,j表示编号的i的顶点的第j 个相邻的顶点的编号.4.2.2生成概率表概率表的样式如表4-2所示.表4-2概率表0Num_0P0,1P0,2P0,Num_01Num_1P1,1P1,2P1,Num_12Num_2.N-2Num_N-2PN-2,1PN-2,Num_N-2N-1Num_N-1PN-1,1PN-1,Num_N-1前两列的含义与表4-3相同,这里这不在介绍,Pi,j表示编号的i的顶点的第j个相邻的顶点对应的概率和的值.假设Wi,j表示编号为i的顶点与它的第j 个相邻顶点所形成的边的权值,侧Wi,j表示它的倒数,在计算Pi,j时要先计算编号为i的顶点所有邻边的权值的倒数之和,记为sum
23、_i, 然后计算Wi,j/sum_i.Pi,j=4.2.3生成初始化的粒子在生成初始化的粒子是,选取源点作为起点,随机生成一个01之间的数x,从上面得到的顶点的概率表的起点所在的行中的第三列开始比较x与Pi,j的值,直到x小于Pi,j时取得第j 个相邻顶点的编号放入最短路径存储的数组中,然后把得到的新顶点作为起点重复上述过程,直到遍历完所有的顶点.4.3 PSO算法求解最短路径问题的模型定义4.1 ：设n个节点的最短路径问题的解序列为S=（）,i=1,n。定义交换子15SO（）为交换解S中的点，则=S+SO（）为解S经算子SO（）后的新解，这里的符号“+”赋予了新的含义。例4.1：有一个5个节
24、点的最短路径问题，其解为S=（1 3 5 2 4），交换算子为SO（1，2），则 =S+SO（1，2）=（1 3 5 2 4）+SO（1，2）=（3 1 5 2 4）。交换算子在存储形式如下： 其中 ，其中n为顶点数目。例：交换子为SS=（s1(5,2),s2(3,4)），则交换算子的存储形式为：00402定义4.2：一个或多个交换子的有序队列就是交换序，记作SS。 SS=S， （4-1）其中是交换子，它们之间的顺序是有意义的。交换序作用于一个最短路径解上意味着这个交换序中的所有交换子依次作用于该解上，即=S+SS=S+（）=（S+S （4-2）定义4.3：不同的交换序作用于同一解上可能产生相
25、同的新解，所有有相同效果的交换序列集合称为交换序的等价集17。定义4.4：若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。例行4.2：设两个交换序，按先后顺序作用于解S上，得到新解。假设另外有一个交换序作用于同一解S上，能够得到相同的解，可定义 =， （4-3）和属于同一个等价集，一般来说，不唯一。定义4.5：在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序17。可按如下的方法构造一个基本交换序，设给定两个解路径A和B，需要构造一个基本交换序SS，使得B+SS=A。 A：（1 2 3 4 5）；B（2 3 1 5 4）可以看出，A（1）=B（3）=1，所以第一
26、个交换子是SO（1，3），=B+SO（1，3），得到：（1 3 2 5 4）；A（20）=（3）=1，所以第二个交换子是SO（2,3）,=+SO(2,3),得到：（1 2 3 5 4）。同理，第三个交换子是SO（4，5），=+SO（4，5）=A。这样，就得到一个基本交换序：SS=A-B=（SO（1，3），SO（2，3），SO（4，5）。4.4求解最短路径问题的PSO算法基本PSO算法中的速度算式（1.1）已不适合最短路径问题，于是重新构造了速度算式： =(-)(-), (4-4)其中,(,0,1)为随机数，(-)表示基本交换序（-）中的所有交换子以概率保留；同理，（-）表示基本交换序（-）中的
27、所有交换子以概率保留。由此可以看出，的值越大，（-）保留的交换子就越多， 的影响就越大；同理，的值越大，（-）保留的交换子就越多，的影响就越大。求解最短路径问题的PSO算法步骤描述如下：（1）初始化粒子群，给每个粒子一个初始解和随机的交换序。（2）如果满足结束条件，转步骤（5）。（3）根据粒子当前位置计算下一新解: 1）计算（-）交换序。 2）计算(-)。 3）计算式4.4，并将转换为基本交换序。 4）计算搜索到的新解 5）如果找到一个更好得解，更新。（4）如果整个群体找到一个更好的解，更新，转步骤（2）。（5）显示结果。4.5粒子群优化的几种策略4.5.1改进策略一 由于离散量运算的特殊性，
28、对粒子的运动方程作了修改，因为速度的定义使位置的运动是一步到位的，公式4.4的第一项采用原有速度的意义已经不大了，由于惯性的主要作用是产生扰动，维持粒子群的多样性，没有它的作用PSO算法就将陷入早熟，为了解决这一问题，改进策略一中采用了扰动速度，它的每一维的速度的值采用随机方式产生，扰动的速度使算法在迭代的后期依然保持进化的能力，能有效的解决早熟收敛的影响；另外因为速度之间存在相互干扰的现象，为了使各个速度的作用不会相互干扰，采用分步计算速度和修改粒子位置的方式，修改后的运动方程如下： =+w （4-5）=+c1*rand()() (4-6)=+c2*rand()() (4-7)4.5.2近邻
29、搜索算子 对最短路径问题，传统的邻域产生函数包括互换、逆序、和插入等操作，他们大都随机方式产生一个状态，由于没有充分使用邻域知识，致使搜索的效率不高，由于最短路径的中必然包括而且在很在程度上包括了相邻顶点权重最短的边，所以可以用一个NM的矩阵K来存储各个顶点的近邻顶点排序表，里面的每一个元素的值表示对顶点i而言，第j近的顶点是，第一近的城市是，次近的城市是,依次类推，K作用所有粒子公共的知识序，能被所有粒子所感知，并以此来指导粒了的近邻搜索过程。在近邻搜索算子中，对第一维i上的顶点，如果它接下来要访问的顶点是第j 近的顶点，则依次以为下一维的速度，作用到此粒子上，看能不能减小路径长度，如果能，
30、则粒子进入新的位置，对所有的维数重复这个过程，因为搜索本身是有代价的，除了使算法运算速度变慢外，还可能使算法易于陷入早熟悉、停滞，为此定义搜索深度（depth）这个参数来控制在搜索时所考虑的顶点数，即速度中的下标j 还应小于depth.。4.5.3自适应惯性系数的改进策略粒子在解内不断地跟踪个体极值和全局极值进行搜索，直到达到规定的误差标准或搜索次数为止。粒子每一维飞行的最大速度不能超过算法设定的最大速度,设置较大的可以保证粒子种群的全局搜索能力，较小则粒子的局部搜索能力强。由于在搜索过程中有时会出现粒子在全局最优解附近出现“振荡”现象，为避免此问题，可以进行如下改进：随迭代次数增加，速度更新
31、公式中的加权因子w由最大因子线性减小到最小加权因子，即 (4-8)其中gen为当前迭代次数，为总的迭代次数。4.5.4对约束条件的优化 考虑目标函数如下： min Z= (4-9) s.t.Weight(i,j)0,i=0,.,n-1,j=0,n-1; (4-10) 罚函数19是在目标函数中加上一下惩罚项，以反映得到的解是否位于约束集中，通过广义的目标函数，使得算法在惩罚项作用下找到原问题的最优解。这样将一个有约束的优化问题，转化成一个无约束的优化问题，因此在改进的PSO算法中适应值函数修改为如下式： (4-11) 其中，M为自定义的一个大数，是最短路路径问题中达不到的大数。再通过全局搜索的P
32、SO算法“跳出局部最小”，最终收敛于全局最小。PSO算法求解最短路径问题的实现5.1绘图部分的实现5.1.1总的绘图界面 系统运行时的图如图5-1图所示：图5-1系统界面图5.1.2画点具体效果如图5-2和图5-3:图5-2画点工具栏图图5-3绘点5.1.3 画线 系统中有三种画线的方式，分别为画一条线段、画一条连续折线、画一组同一起点的射线。具体效果如图5-45-9所示：图5-4画线工具栏图5-5画线图5-6画连续折线图5-7连续折线效果图5-8画同一起点的一组射线图5-9画一组射线的效果5.1.4选择顶点 选取顶点的策略：当鼠标按下时，根据当前鼠标的坐标值（x,y）,用以（x,y）为中心的
33、长为20，宽为20的矩形区域来找点，如果在此区域中有点，则就标记这个点。选取点的目的主要是为连接两顶点、删除顶点、移动顶点服务的。具体效果图5-10和图5-11所示：图5-10选择顶点的工具栏图5-11选择顶点的效果5.1,5选择边 选择边的策略：当鼠标按下时记录下鼠标位置（x,y）,然后依次从边中找到编号为i的顶点的坐标（,）,编号为j 的顶点的坐标（,），计算顶点i与顶点j 之间的矩离记为C，顶点i与（x,y）和j 与（x,y）的矩离之和为A，设B=20，则如果，则就表示此边就是要选的边，然后标记此边。上面描述的含义就是如果鼠标落在以B/2为b,以C/2为c的椭圆内部，就先边。具体效果如图
34、5-12和图5-13所示：图5-12选取边的工具档图5-13选取边的效果5.1.6连接两顶点 连接两个顶点前，要先选取两个顶点，然后才能执行连接操作。连接可分为三种情况。第一种：两个没有边相连的点连接，此时要增加顶点的个数，并且增加连接的边。第二种：只有一个顶点没有边相边时，把没有边相连的顶点加入顶点序列，增加连接后的边。第三种：两个顶点全都有边相连时，只需增加边就可。具体效果如图5-14图5-17所示：图5-14选取连接的两顶点图5-15连接两顶点图5-16连接两顶点图5-17连接两顶点5.1.7顶点的移动 移动顶点的操作主要是为了对图形形状的修改，使用户对图形的整体结构有更直观的了解。具体
35、效果如图5-18和图5-19：图5-18移动顶点工具栏图5-19移动顶点效果5.1.8删除顶点和边 删除顶点和边主要是用来修改绘制的图形，可以使用户更方便的绘图。删除操作执行前必须要选择需要执行此操作的边和顶点。具体效果如图5-20图5-22所示：图5-20删除操作工具栏图5-21删除顶点图5-22删除边5.1.9取消所选 取消所选可以一次性取消所有已选择的顶点和边。具体效果如图5-23图5-25所示：图5-23取消所选工具栏图5-24取消顶点图5-25取消边5.1.10结束绘图 此操作用来使绘图工具栏无效，使分隔栏左侧部分有效，从面转入算法参数、图形标记和权值的输入状态。具体效果如图5-26
36、和图5-27所示：图5-26结束绘图5-27结束绘图效果5.1.11算法参数输入w_max为惯性系数最大值,w_min为惯性系数最小值，C1为粒子自身加速度权重系数，C2为全局加速度权重系数，M为自己设定的一个罚函数值。Same_max为在不更新全局最优值时最多迭代次数。图5-28参数输入栏5.1.12标记顶点和输入权值标记顶点就是给每个顶点输入具有一定含义的标记值，这样可以更好的用图来表达所代表的具体问题。输入时格式为：”i,lable;”其中i为要标记的顶点的编号，lable为标记的字符串。；表示结束，只有输入；后标记的内容才能生效。具体效果如图5-29和图5-30所示： 图5-29权图附
37、加信息输入栏图5-30标记顶点权值的输入格式为：”i,j,value;”,其中i,j分别为边的两个端点，value为权值。注意第次输入完value后必须以；结束。具体效果如图5-31：图5-31输入边的权重5.1.13起点和终点的设置起点和终点主要用来传递参数给算法。输入框如图5-32所示：图5-32起终点输入栏5.1.14按纽区 按下绘图完成按纽时工具栏就被屏蔽掉了，按下算法参数完成按纽时算法的参数就传递给算法，起始点完成、权值完成、输入完成的作用同上。按下输入完成时表示算法所需的数据输入完成，此时就可以生成粒子了，按下初始下按纽进行粒子的实始化操作，输出1用来输出基本粒子群算法的结果，输出
38、2用来输出改进方法的输出结果。 图5-33按纽区 图5-34输出区5.2自定义的输入输出方式（1）输出：当一次操作完成生成了如下图所示的结果，如果想保存此结果，可以在文件菜单中选择保存，然后选择保存位置和保存的文件名，最后点确定进行保存操作。假设操作完成后的图如图5-35所示：图5-35输入的完整图 执行完保存操作后的写入文件中的内容如图5-36所示：图5-36写入文件的格式(2)输入可以直接从文件菜单顶中选打开，然后找到要找开的文件名，点确定完成打开操作。完成后主可在绘图区看到上次保存的图。假设要打开的文件的内容如图5-37所示：图5-37要读取的文件格式 则执行完打开操作后绘图区显示内容如
39、图5-38：图5-38读取文件后生成的图5.3算法的实现5.3.1 PSO求解最短路径的数据流图 系统的数据流图如图5-39所示：信息显示调用相应的PSO算法进行计算带权图及参数优化控制面板（用户接口）带权图参数优化模型参数最佳适应值全局最优解显示面板(用户端)结果图539 PSO求解最短路径问题1层数据流程图5.3.2数据字典用户输入的数据包括：带权图、迭代次数、种群规模、惯性系数、起点、终点、维数等。表5-1 输入参数数据字典字段名标识类型取值范围种群规模numint迭代次数timeint最大更新速度vmaxint最大惯性系数w_maxdouble01起点startint终点endint最
40、小惯性系数w_mindouble01顶点标记point_stringstring0500权值ptopWeightdouble0500罚函数值Mint学习因子1C1double04学习因子2C2double045.3.3 PSO算法求解最短路径流程图设置参数值如下：w,c1,c2,dim, interaterDegree, edgtWeight，M，start,end等由edgtWeight生成邻接点的顺序表Graph，调用Initilize（），初始化粒了的位置和速度。计算,并分别与c1和c2执行依概率相乘，原位置与执行自定义的加操作，再与c1(,)执行同上操作，再与c2()执行同上操作。当前
41、值小于个体最优更新个体最优值计算完此次迭代中的所有粒子的适应值当前最优小于全局最优更新全局最优大于最大迭代次数END图540 PSO求解最短路径问题流程图5.3.4 PSO算法的实现主要数据结构：种群大小(particleAmount) 空间维数(dim)最大迭代次数(interaterDegree) 边的权重(edgtWeight)各粒子当前适应度值(particleFit)各粒最优适应度值(particleBestFit)各粒子位置(particleCurrentSolution) 各粒子速度(p_V) 各粒子的最佳位置(particleBestSolution) 全局最佳粒子位置(Bes
42、tArray)全局最佳粒子序号(allParticleBestIndex) 得到相近适应度值的迭代次数(getBestValue_time)主要函数： CreateGragph：生成NM的矩阵Graph来存储各个顶点的近邻顶点排序表。 GetFit：计算粒子当前的适应度值。 GetBestFit：计算机全局最优适应度值。 BeginWithStart：使每条路径都从起始点开始排起。OperatorDelete：计算（Pid-Xid）等交换序。OperatorPlus：进行交换操作。OperatorCheng：计算以概率保留交换序。核心代码如下：public void ParticleFly() int Array1 = new intdim + 2; int g_bestIndex = 0; for (int j = 0; j interaterDegree; j+) for (int i = 0; i particleAmount; i+)
