随机粒子群优化（共10篇）
随机粒子群优化 篇1
为了解决复杂非线性和多维空间全局寻优问题,许多学者对粒子群算法进行了改进,主要包括初始解的优化[1]、公式参数的优化[2—4]、公式形式的优化[5,6]、粒子群体划分以及不同粒子群或不同层次粒子群之间通讯的优化[7]。粒子群算法优异的性能来自于其仿生学基础,但由于目前对粒子群算法的改进缺少细致化仿生基础,因而改进效果并不明显。本文将飞鸟寻食等细致化行为特征融入算法,即利用飞鸟随机落地后摆动前行寻食,若找不到即飞走,然后随机落到另外的地点重新进行摆动前行寻食,直至达到目标为止的行为特征为基础,提出了随机点摆动前行模式的改进优化算法。该算法通过飞鸟视角参数和视野设定参数,进行初步寻优与细致寻优,以及超范围(跳出)飞走寻优等方法,保证了随机点摆动前行寻优算法的全局最优性及收敛性。
1基于随机点摆动前行模式的改进粒子群优化算法原理
改进算法不沿用经典算法[1—6],而是在细致化仿生基础上提出新的优化算法。该算法通过飞鸟寻食过程中的视角参数和视野设定参数,进行初步寻优与细致寻优,以及超范围(跳出)飞走寻优等方法,保证了随机点摆动前行寻优算法的全局最优性及收敛性。
具体算法原理如下:
设目标函数为max F(P)(或F(p)>y0),算法描述如下:
(1)确定搜索域D,D为一n维空间。
(2)确定搜索起点S,S∈D,行进角度Ω={ω1,ω2,…,ωn},ωi表示行进方向与第i个坐标轴的交角。
(3)确定搜索参数,包括下面几个:
(1)视角α,即搜索时,“眼睛”看到的范围角度。角度取样数目N。即在视角内,进行观察选取的角度的个数。角度取样数目N越大,搜索越细致,但速度亦慢。
(2)视野L,即搜索时“眼睛”能看到的最远距离。
(3)径向取样点距X;
这里u表示径向取样数,视野L一定的条件下,径向取样数u越大,搜索越细致,但速度亦慢。选取不宜过大,但亦不宜过小,应根据具体问题和寻优要求而定。
(4)计算初始取样点集P'。
设当前点(观察所在点)为:
则初始取样点集:
X与N为前面假设中的径向取样点距和角度取样数目。
若设D为二维空间,视角,角度取样数目为4,则3,4中的几个概念如图1所示。
视角α=2π时,表明对观察所在点周边都进行探查。
(5)计算(本次迭代)取样点集P。
设进行过细致寻优(“细致寻优”在第7步进行说明)的空间为Z,则取样点集为:
(6)寻优,即在P(可视范围)中找到使目标函数值最大的取样点py。
py=(p
(7)细致寻优(可以根据要求设定进行一次细致寻优或多次细致寻优)。
解决现实问题时,目标函数往往是连续的或是趋于连续(存在间断点,(1)其余部分是连续的;或:(2)考虑δx足够小而不是δx→0去判断连续,即总体、形象来看是连续的,如山势)的,因此,在py邻域内可能还存在使目标函数值更大的点,细致寻优是为了找到这样的点,方法是合理设定邻域,在邻域中确定细密的采样点,考查这些采样点的目标函数值。即在特定的邻域内加密搜索。
① 触发条件:pi=py,即发现使目标函数值最大的取样点py与观察所在点重合时进行细致寻优。
② 邻域的确定:
设py点在上次迭代(对于迭代中的第一个点,其邻域需要单独定义)中对应的参数为:m=m0(视角),v=v0(视野)。
则定义邻域Δpy为由以下视角区间和视野区间封闭的区域:
视角区间为:
视野区间为:
③ 增加密度搜索的确定。
参数分为两个:视角加密参数e和视野加密参数r,e,r为自然数。分别描述对于1)中视角区间和视野区间的划分情况,分别表示将视角细密划分为e份和将视野平均划分为r份,形成er个加密搜索点(如图 2,加密搜索点在由其相邻点围成的区域之内)。
④ 细致寻优迭代次数的确定。
细致寻优迭代次数参数c,c为自然数,用来描述进行几次细致寻优。例如c=2,表示进行一次细致寻优找到使目标函数值最大的取样点后对于该取样点后再进行一次细致寻优。
对应于上面图 1(使用对应假设),将细致寻优中的几个概念图示说明如下:
⑤ 在细密的采样点中继续寻优,找到(本次迭代)最优点Ph,查询既有最优点纪录,若Ph优于既有纪录,则记录最优点Ph;更新细致寻优空间Z。
⑥ 细致寻优迭代次数达到设定次数后,结束本次细致寻优,转至(8)。
(8)前进新取样点(确定新起始点)。
分为三种情况(如果进行了细致寻优则使用Ph代替Pk):
① S=Pk,需要跳出局部极值,随机选取新的起始点。这时设置参数R表示最大跳出次数,在跳出次数不超过R的情况下:
S=random(D),S∉Z否则跳出。
② S≠Pk且ΔPk⊄Z,前进至Pk,即取S=Pk。
③ S≠Pk且ΔPk⊂Z,跳出,S=random(D),S∉Z。
确定新的起始点后,根据两点坐标,更新行进方向Ω,至4继续迭代。
(9)退出机制。
可以选择通过以下方法判定算法结束:
① 达到优化目标,如对应于F(p)>y0类的问题找到的F(Ph)>y0;
② 跳出局部极值次数超过R;
③ 已经对整个搜索域进行过细致寻优,即Z=D;
④ 超过设置最大运算时间。
(10)算法结果。
既有最优点纪录中的点即为所求。当然,对于Ph>y0类的问题可能无解。
2 基于随机点摆动前行模式的改进粒子群优化算法流程
IPSO算法流程如图3所示。
3 算例
已知二元函数:
其中0≤x≤20,0≤y≤20(实际问题中的函数可能是未知或难以求得的,有些可能既使知道其表达式,也难以求其驻点以求解,这里由于只是作为算例,给出了函数表达式,且该函数的极值易于求得),函数曲面图与等高线图如图4、图5所示。求max f(x,y)。
设定搜索域D={(x,y)|0≤x≤20,0≤y≤20},搜索起点S={0,0},行进角度
3.1 数学方法求准确解
分析可知,函数z=f(x,y)在x=6,y=12时取得最大值10。
3.2 算法计算结果
运算结果:5次跳出后,在点(5.807 286 457 909 43,12.0173 381 886 294 93)处取得最大值:9.975 5(跳出2次后获得)。在改变了部分参数(改动为:视角α=2π,细致寻优迭代次数参数c=3)后,在点(5.987 156 23,12.002 879 21)处取得最大值:9.999 9(跳出2次后获得)。该寻优方法取得了较好的效果。两次运算图形界面分别如图6、图7所示,图中线条表示寻优路径。
4 结论与讨论
基于随机点摆动前行模式的改进粒子群优化算法可以实现复杂的非线性和多维空间寻优问题。其优点在于基于细致化仿生学原理,合理配置参数能迅速求解;可以适用于不连续的多维曲面;可有效跳出局部最优,寻求到全局最优值。数值算例显示随机点摆动前行寻优算法具有效率高、精度高的特点。与经典粒子群算法模拟鸟群捕食行为不同,本文算法利用了飞鸟随机落地然后摆动前行寻食,没有像经典粒子群算法中鸟群之间存在信息传递,然后在"好消息"的指引下线性奔向食源的做法。由于存在随机点摆动,在其视野及视角范围内,最优解一般不会漏掉,因而,此方法一定能够得到全局近似最优解。这也有效的克服了粒子群算法随着迭代次数的增加容易陷入局部最优的缺点。当然,基于随机点摆动前行模式的改进粒子群优化算法也存在着只能不断逼近而不能求得真正的最优解的缺点。由于在随机点摆动前行寻优模型中,飞鸟视角、飞鸟视野以及细致加密参数等的设定不能覆盖全域,因而一定存在着最优点精度误差。
基于随机点摆动前行模式的改进粒子群优化算法作为一种新的优化算法具有独特的优点,也存在着一定的局限性。其进一步的研究方向有如下几点:一是随机点摆动前行寻优模型中参数的科学设定;二是提高算法的效率问题;三是寻优与细致寻优以及超范围(跳出)飞走等方法问题;四是本算法与其它优化算法的比较及融合等问题。
摘要：基于飞鸟寻食细致化仿生,提出了一种新的基于随机点摆动前行模式(RSFM)的改进粒子群算法原理,设计了改进粒子群算法流程,并利用算例展示了该算法的具体使用方法与计算效果。
关键词：粒子群算法,改进粒子群算法,飞鸟寻食,随机点摆动前行模式(RSFM),算法
随机粒子群优化 篇2
基于粒子群算法的并联机构结构参数优化设计
介绍了粒子群优化算法的原理和实现方法,分析了该算法的主要参数对搜索性能的`影响,并把粒子群算法用于六自由度的并联机构的参数优化设计中,取得了较好的效果,试验证明,粒子群算法是一种有效的优化方法,适用于大型复杂结构的优化设计.
作 者：孙凡国 黄伟 KONG Fan-guo HUANG Wei 作者单位：五邑大学,机电工程系,广东,江门,529020刊 名：机械设计与研究 ISTIC PKU英文刊名：MACHINE DESIGN AND RESEARCH年，卷(期)：22(3)分类号：V221.6关键词：粒子群优化算法 进化计算 优化设计
随机粒子群优化 篇3
关键词：计算机神经网络；粒子群优化算法；应用
中图分类号：TP183
粒子群优化算法是一种相对简单、有效的随机全局优化技术，通过对粒子群优化算法进行相应的改进，以此确保其收敛性，然后再将粒子群优化算法应用到神经网络的学习训练中，能够更有效的找出最优化解。粒子群优化算法和遗传算法相比，粒子群优化算法并没有遗传算法复杂的交叉、变异以及编码，而是对粒子所在解空间的具体位置进行搜索，不需要对众多的参数进行调整，其收敛速度相对较快。
1 粒子群优化算法的基本原理以及优化改进
1.1 粒子群吧优化算法的基本原理
PSO中，每一个优化问题的解都是搜集空间中的一个“粒子”的状态，粒子群优化算法是对群体的全局进行考虑，通过迭代搜寻选取最优值，通过将系统转化成一组随机的例子，由于例子在解空间追随最优的例子进行凑所，所以粒子群优化算法是一种具有全局寻优能力的优化工具。例子群优化算法的基本原理表现为：假设在一个D维的目标搜集中间中，由N个不同的粒子组成了一个特定的群体，其中第i个粒子表示成其在这个D维空间中的向量（xi），也就是该粒子在D为空间中的位置，每一个粒子的位置都存在一个特定的解，通过将xi带入到相应的目标函数中，通过适当的函数计算就能得到其适应度值，然后根据该xi适应度值的大小，以此衡量xi的优劣程度。其中，第i个粒子飞行的速度表示D维中的另一个向量，表示为vi，将在D维空间中搜索到的第i个粒子的最有位置记录为pi，则整个粒子群搜索到的最有位置pi的粒子群优化算法表现为：公式一：vi=ci+c1r1（pi-xi）+c2r2（pg-xi）；公式二：vik+1=vik+c1×rand（）×（pbest-xik）+c2×rand（）×（gbest-xik）；公式三：xi=xi+vi，其中i=1，2，…N；r1和r2为学习因子，rand（）表示介于[0，1]之间的随机常数，c1和c2表示为非负常数。其中迭代的终止条件是根据选择的最大迭代次数决定的，表示的为第i个李在迄今为止搜索到的最优化位置应该满足的适应度的最小值。
从社会学角度方面来说，粒子群优化算法公式中的表示的是粒子的记忆项以及自身认知项，能够表示上次速度的方向以及大小对粒子造成的影响，还能够将当前的指向粒子当作自身的最优化矢量，以此表示粒子的动作来源于自身的经验，能够反映粒子之间的协同作用以及知识共享，粒子能够根据粒子群中相邻粒子的最好经验，然后再结合自身的经验，以此来决定自身的下一步运动，从而形成PSO的标准形式。
1.2 粒子群优化算法的改进
粒子群粒子群优化算法需要用户确定的参数相对较少，并且其操作相对简单，因此该种方法使用起来非常方便，但是，由于粒子群优化算法容易陷入局部极值点，导致搜索的收敛性相对较低，并且粒子群优化算法的收敛性分析已经收到众多学者的重视，因此，为了增强粒子群优化算法的收敛性，可以将抗体多样性保持机制引入到粒子群优化算法中，其步骤表现为：首先，确定参数值，记忆粒子个数M，即常数因子c1和c2粒子群的个数N，粒子的浓度概率选择阀值Pi，其随机产生的N个粒子xi的飞行速度表示为vi，以此计算粒子的适应度函数值；根据公式计算粒子的选择概率，将粒子群体中前M个最大适应度的粒子当作记忆细胞进行储存，将概率大于Pi的粒子根据相应的方法进行计算，从而把M个记忆细胞替换成适应度最差的M个粒子，以此形成全新的粒子群，最终判断其能付满足相应的选择条件，如果满足输出适应度值最好的要求，则选定该粒子。由此可见，通过上述的方法对粒子群优算法进行改进，能够保证粒子群优化算法的精确性，并且通过实践证明，经过改进后的粒子群优化算法，其计算机的仿真结果显示，该种粒子群优化算法的收敛速度明显优于没有改进的粒子群优化算法的收敛速度。
2 粒子群优化算法在计算机审计网络中的应用
计算机神经网络能够模拟大脑的思维能力，然后通过对各种数据进行分析，从而建立其相应的数学模型，计算机神经网络中除了包含许多处理器以外，还包含了许多与人脑神经相似的节点，这些节点按照一定的规律进行连接。如果将计算机神经网络中的每一个过程都细分为若干个微程序，并且将所有的微程序都交付于处理器进行处理，那么处理器处理所有的微程序的过程，就是一条微程序的处理流水线，这样计算机处理信息的速度也将会显著的提高。粒子群优化算法在计算机神经网络中的应用，包括的内容有组合优化、参数优化、神经网络训练、学习算法、网络拓扑结构和传递函数、链接权重等，通过把个体转化成微粒，其中包括计算机神经网络中的所有能够用到的参数，然后经过一些列的复杂、重复的程序，最终达到最终的训练目标。相对于传统的神经训练法来说，由于BP算法需要可微的函数以及梯度信息等大量的数据，只有通过大量的计算才能得到相应的训练结果，其运行难度较大、程序相对复杂，而采用离子群优化算法，其处理信息的速度显著的提升，能够有效的克服其运行效率低的问题。粒子群优化算法在计算机神经系统网络中的应用，主要表现在两个方面：其一，粒子区优化算法在参数优化中的应用，能够通过解决计算机神经网络中的各种离散型问题，从而进行参数优化；其二，粒子群优化算法在组合优化中的应用，其中典型的应用表现为其在工程经济问题中的应用，其能够通过将各种资源进行科学的组合，通过设置一定的约束条件对这些组合进行排序，通过不断的尝试最终能够找到最有效的解决方案，然后合理的利用所有的组合实现经济效益的最大化。此外，粒子群优化算法不仅能够应用在计算机神经网络中，还能够应用在更多的领域中，例如软件编辑、游戏开发、电力系统等领域中。
3 结束语
文章对计算机神经网络中粒子群优化算法的应用进行了研究，对粒子群优化算法进行了相应的改进，有效的提高了粒子群优化算法的收敛速度。将粒子群优化算法应用在计算机神经网络中，其操作相对简单，比较容易实现，并且其还能够更快的收敛于最优解，有效的克服了传统遗传算法缺点。因此，在计算机神经网络学习训练中，广泛的推广和应用粒子群优化算法具有很大的现实意义。
参考文献：
[1]丁玲，范平，闻彬.粒子群优化算法在计算机神经网络中的应用[J].理论与算法，2013（17）：39-41.
[2]曹大有.一种免疫粒子群优化算法及在小波神经网络学习中的应用[J].计算机应用于软件，2009（06）：189-192.
[3]刘爱军，杨育，李斐.混沌模拟退火粒子群优化算法研究及应用[J].浙江大学学报（工学版），2013（10）：1722-1729.
[4]虞斌能，焦斌，顾幸生.改进协同粒子群优化算法及其在Flow Shop调度中的应用[J].华东理工大学学报（自然科学版），2009（03）：468-474.
[5]刘宝宁，章卫国，李广文.一种改进的多目标粒子群优化算法[J].北京航空航天大学学报，2013（04）：458-473.
作者简介：张小军（1980.01-），男，河南人，讲师，研究方向：云计算，数据挖掘，通信技术。
多种群粒子群分层进化优化算法 篇4
粒子群优化算法 (Partical Swarm Optimization Algorithm, PSO) 是由美国学者Kenndy和Eberhart于1995年提出的一种群体智能优化算法[1], 现已广泛应用于科学和工程领域。但它存在收敛速度慢、容易陷入局部最优值的缺陷。本文介绍的多种群粒子群分层进化算法, 对具有不同适应度值的粒子采取不同的进化方式, 加快了算法收敛的速度和精度。
2 多种群粒子群分层进化优化算法
2.1 标准PSO
用标准PSO求解时, 先初始化一群随机粒子, 通过让粒子不断更新自己的位置, 来找到函数的最优解。在每次更新中, 粒子通过两个“极值”来调整自己的位置:粒子本身取到的最优值Pbest和粒子群找到的最优值Gbest。更新公式为:
其中, c为加速因子, rand () 是0-1之间的随机函数。
2.2 算法改进
美国的Shi和Eberhart引入惯性权重的概念[2], 将更新公式变为:
通过惯性权重w来控制前一速度对当前速度的影响。文献[3,4]基于控制理论分层控制的思想, 把PSO用于多种群2层优化, 文献[5]提出把粒子群分成两部分, 让粒子分别朝向最好最坏方向飞行。本文提出的分层进化让适应度值优的粒子采取较小的w值, 增加其局部搜索能力;让适应度值差的粒子采取较大w值, 增加其全局搜索能力, 并让适应度值特别差的用好的粒子代替, 便于粒子更快更好的找到最优值。
2.3 算法流程
Step 1.初始化n个种群, 每个种群m个粒子, 每个粒子记为Xij, 即第i个子群的第j个粒子;
Step 2.计算粒子的适应度值, 找出个体最优Xijbest、子群最优Li和种群最优G;
Step 3.根据不同适应度值将粒子分成不同层次, 对不同层次的粒子分别采取不同的惯性权重ωi, 将适应度值特别差的粒子用好的粒子替换;
Step 4.按如下公式逐个更新粒子:
Step 5.达到迭代次数或误差要求结束, 否则转Step2。
3 算法验证
为了比较算法的性能, 取Sphere、Ackley、Rastrigin、Griewank四个基准函数进行测试, 并与粒子群算法进行比较。四个函数形式为:
实例中取3个粒子群, 每群30个粒子, 每个粒子设定为3维, c1, c2, c3均取2, w按分层取得
对于适应度值与最优值差值大于10000的用最优粒子代替, 基本PSO中取w=0.7, 其他参数一样, 让每个函数分别运行100遍, 迭代90000次, 两种算法最优适应度值的平均值分别为[0.045064 0.68787 0.24894 0.14151], [0.259410.69659 0.26889 0.12891]。四个函数里边三个比基本粒子群寻到的结果要优, 两个算法的结果图像如图1、图2所示。
4 结论
本文提出的粒子群分层进化方法让具有不同适应度值的粒子取不同的惯性权重, 独立的改变自己的速度和位置, 这比基本粒子群对所有粒子采取相同操作更具针对性, 能让粒子更快更好的收敛到最优值, 通过对测试函数进行计算的结果图像很好地显示了粒子朝最优值逼近的趋势。但用来进行划分的适应度值的区间还有待进一步研究, 本文只是根据经验提出, 希望以后能有一种更好的划分适应度值的理论方法。
参考文献
[1]Kennedy J, Eberhart R C.Particle Swarm Optimization[C].IEEE International Conference on Neural Networks, Piscataway:IEEE Service Center, 1995:1942-1948.
[2]Shi Y, Eberhart R C.A Modified Particle Swarm Optimizer[C].IEEE World Congress on Computational Intelligence, 1998:69-73
[3]吕林, 罗绮, 刘俊勇等.一种基于多种群分层的粒子群优化算法[J].四川大学学报 (工程科学版) .2008;40 (5) :171-176
[4]吕林, 罗绮, 刘俊勇等.基于多种群分层粒子群优化的配电网络重构[J].电网技术.2008;2 (32) :42-45
随机粒子群优化 篇5
将粒子群优化的BP神经网络作为模型,参考自适应控制系统的控制器,把参考模型输出与系统实际输出的均方误差作为PSO-BP神经网络的适应函数,通过PSO算法强大的搜索性能使自适应控制系统的`均方误差最小化.仿真实例结果表明,基于粒子群优化算法的BP神经网络自适应控制系统收敛快、精度高,有较好的网络的泛化和适应能力,能够很好地控制系统的输出跟随参考模型的输出.
作 者：陈聆 闫海波 毛万标 CHEN Ling YAN Hai-bo MAO Wan-biao 作者单位：陈聆,CHEN Ling(成都理工大学信息管理学院,数学地质四川省重点实验室,成都,610059)
闫海波,YAN Hai-bo(新疆财经学院,乌鲁木齐,830012)
毛万标,MAO Wan-biao(西昌卫星发射中心技术部,四川,西昌,615000)
粒子群优化的模糊特征 篇6
粒子群优化是由美国社会心理学家Kenndy和电气工程师Eberhar于1995年提出的一种基于种群的仿生优化方法[1,2],与蚁群优化、蛙跳优化等组成了群智能大家庭。近年来,粒子群优化得到了国内外研究学者的关注,研究方向不断聚焦,新研究课题层出不穷,成果不断出现,专门讨论粒子群优化(或以粒子群优化为主的群智能)的著作有10余部,在中国知识资源总库中以“粒子群”为标题搜索到的相关博士论文有48篇,在收录欧美国家2 000余所知名大学的优秀博硕士论文的PQDT学位论文全文库中以“particles swarm”为题名搜索到博士论文有14篇,国内外粒子群优化研究者进行了综述[3,4,5,6,7]。
粒子群优化是一种典型的群智能优化技术,因其模型简单,参数较少,易于实现等优势,在不同的工程领域得到了广泛的应用。粒子群优化的研究对象属性越来越复杂,优化参数和变量逐渐增多,人为主观因素不断加强,再加之仿生方法本身的模糊不确定性,粒子群体行为中的模糊特征越来越明显。本文从粒子群优化方法本身、优化设计、工程对象属性和模糊建模优势等方面,探讨粒子群优化方法的模糊特征。
1 粒子群优化理论研究
由于粒子群优化理论研究的实际困难,研究者需要简化粒子群优化模型,或提出一些假设条件,以方便粒子群优化理论的研究。常见的简化条件有:单个粒子、搜索停滞、无随机性、粒子间相互独立等,这些简化条件能够在一定程度上认识粒子优化的某些方面,得到的结论有待于在实际工程应用中检验。
R. Poli等对粒子群优化研究进行了比较全面的综述,本文总结粒子群优化理论研究脉络大体可分为确定型粒子群优化和随机型粒子群优化两个阶段,其中确定型粒子群优化理论研究常见的假设条件见表1,随机型粒子群优化理论研究可参考文献[7]。
2 粒子群优化方法的模糊特征分析
2.1 粒子群优化本身的模糊特征
粒子群优化模仿昆虫、兽群、鸟群和鱼群等的群集行为,按照某种合作的方式寻找食物,群体中的每个成员通过学习自身的经验和其他成员的经验来不断改变其搜索模式。在它们实际移动过程中,每个成员赋予了“记忆功能”(种群中的全局最优解和个体历史最优解)、“学习功能”(向着最优位置靠拢)和“自我调整功能”(设置不同的加速度权重调整当前速度对下一时刻速度的影响),所以确定种群全局最优个体、自身历史最优个体及向二者移动力度具有一定的模糊特征。
注:“√”表示研究者采用了相应的假设条件。
2.2 粒子群优化设计的模糊特征
在粒子群优化方法设计中,模糊特征主要体现在以下几个方面:
(1) 通过一个模糊系统自适应调整粒子群优化方法的参数,该思想最早追朔到1999年,Yuhui Shi等在2001年提出了一种模糊自适应粒子群优化方法[8],对此进行了比较系统的阐述,即通过标准化的当前粒子群最佳性能评价和惯性权重作为输入,通过模糊控制系统输出惯性权重的变化量,从而实现对惯性权重的自适应调整,在该思想的指引下,Hongbo Liu等采用最小速度来避免粒子群优化早熟[9],利用模糊控制器来调整最小速度的阈值,Wenping Chang等利用适应值函数的均方偏差和进化速度模糊控制粒子群优化过程的权重因子[10]。
(2) Xuelei Meng等在粒子群优化速度更新方程中引入隶属度函数[11],通过定义隶属度函数的类型以达到效率和速度的均衡,并指出简单的隶属度函数可以得到更快的收敛速度,而精确平滑的隶属度函数得到更好的结果。
(3) 粒子群优化方法中速度和位置表示由实数向量转化为模糊矩阵,该思想首先是由W.Pang等在2004年提出[12],H.Liu等提出了新的方法并将其应用到车间调度问题[13]。
(4) 模糊理论也引入粒子群优化,黄信想采用模糊理论描述粒子与粒子群的关系并按隶属度进行变步长的混沌变异[14]。Bilal Alatas等较系统地研究了模糊和混沌理论与粒子群优化的关系并提出了12种嵌入混沌映射的粒子群优化方法[15]。
2.3 粒子群优化工程对象的模糊特征
(1) 人为主观因素不断加强。
随着粒子群优化应用领域的不断拓展,现实生活中的经济、工业和生态等领域的问题都可转化到优化的框架中研究,但是该优化框架具有统计的不确定性和数据本身的不精确性,需要考虑专家综合自身的感知。
(2) 粒子群优化工程对象属性越来越复杂,优化参数和变量逐渐增多。
一方面,粒子群优化工程对象状态无法明确的划分,序列具有模糊性;另一方面,研究对象的无后效性具有模糊性,即当前数据与历史数据的相关性是不确定的,因此在工程实际应用中需要体现研究对象的模糊属性。
2.4 模糊建模在仿生学研究中的应用
Valeri Rozin等指出模糊模型能够分析仿生技术[16],并应用模糊模型对蚂蚁觅食的行为进行建模(该模型在人工系统中实现,例如自治机器人)。他们还列举了通过模糊建模研究生物行为学的原因有:
(1) 很多动物或人的行为是模糊的,比如对轻度刺激的反应是一个有目的的动作,这暗示着这个动物或人要做什么。在有目的的动作和整个反应之间没有明显的界限,二者组成一个统一体;
(2) 在动物行为现象的描述和分析处理时经常需要语言描述和表达,而没有确定的数学模型;
(3) 近期出现了基于模仿生物现象而出现的人工产品和机制的仿生学研究,比如棘鱼的区域行为的研究、控制三肠虫对光线适应性的机制的建立、大苍蝇种群大小的自动调整等。
人工专家系统来源于生物行为,随着其不断的发展,仿生领域的研究越来越受到关注。模糊模型能够按照一个系统的方式对仿生学进行有效的研究。粒子群优化是一种典型的仿生群智能优化技术,模糊建模可按照一个系统的方式对该仿生优化方法进行有效的理论研究和应用研究。
3 结 语
在粒子群优化理论研究的背景下,文中从四个方面探讨了粒子群优化的模糊特征,得到如下结论:粒子群在优化过程中具有一定的模糊性;粒子群优化与模糊理论有效融合,相互促进;工程对象模糊属性、统计的不确定性和数据本身的不精确性比较明显;模糊建模可按照一个系统的方式对粒子群优化等仿生优化方法进行有效的研究。
摘要：粒子群优化是一种典型的群智能优化技术,在不同的工程领域得到了广泛应用。概述了粒子群优化理论研究进展,从粒子群优化方法本身、优化设计、工程对象属性和模糊建模优势等方面,探讨了粒子群优化的模糊特征。
随机粒子群优化 篇7
在现代电力系统中，随着电网规模的不断扩大，机组单机容量的增加，以及快速励磁系统的投入，低频振荡问题已经成为影响互联电力系统稳定的重要原因之一。同时，低频振荡也是一个向远距离输电线路上增加输电容量的严重瓶颈。低频振荡的发生是由于在电力系统中，发电机经输电线路并列运行时，在小扰动作用下，发电机转子之间会发生相对摇摆，这时电力系统如果缺少必要的阻尼就会失去动态稳定。由于电力系统的非线性特性，动态失稳表现为发电机转子之间的持续的振荡，同时输电线路上功率也会发生相应的振荡，影响了功率的正常输送。由于这种持续振荡的频率很低，一般在0.2～2.5 Hz之间，故称为低频振荡[1]。其振荡时产生的能量通过机电联系来传递，因此又称为机电振荡，表现为发电机电功率和功角的变化。低频振荡严重时会导致系统解列或失去稳定。
为了抑制低频振荡，提高电力系统的动态稳定性，可以采用附加控制信号，通过励磁系统提供附加的正阻尼，以补偿原来的负阻尼，使得系统总的阻尼为正值。通过在发电机励磁系统中加装电力系统稳定器PSS(Power System Stabilizer)为系统提供正阻尼是抑制低频振荡的有效措施，合理配置PSS的参数可以取得理想的系统动态性能，提高系统的稳定性。
目前，国内外学者在PSS参数优化协调方面做了一定的研究工作。多种优化算法如遗传算法、免疫算法、进化规则和粒子群算法已经对PSS的参数进行了优化[2,3,4,5,6]，并且起到了一定的优化效果，但是都存在可操作性差、收敛性差、容易陷入局部极值等缺点。
粒子群算法PSO(Particle Swarm Optimization)是美国Kennedy和Eberhart博士受鸟群觅食行为的启发，于1995年提出的一种生物进化算法[6]。PSO算法采用速度-位置搜索模型，每个粒子代表解空间的一个候选解，粒子在搜索空间以一定的速度飞行，飞行速度根据飞行经验进行动态调整。每个潜在解与粒子运行速度相联系，该速度不停地根据粒子经验以及与该粒子邻近的粒子经验来调整大小、方向，总是希望粒子能朝着更好的方向发展。因此，在搜索过程中全局搜索能力与局部搜索能力的平衡关系对于算法的成功起着至关重要的作用。
惯性权值自适应的粒子群算法PSO-ω(Particle Swarm Optimization)是在全局搜索与局部搜索平衡特性的基础上，得到的一种具有较好的全局搜索能力和寻优速度的群体智能优化算法。在标准PSO算法中,惯性权值ω是平衡算法的全局搜索能力和局部搜索能力的关键参数。PSO-ω算法中，惯性权值ω采用了自适应的方式，以达到更好的全局搜索能力。
本文在前述PSS优化研究工作的基础上，提出了一种PSO-ω算法的PSS设计，在这种方法中，不同于以往只寻找机电振荡模式下阻尼比最小的PSS优化方法[2,3,4,5,6]，根据最优控制原理综合考虑PSS与励磁系统的性能，优化的控制目标设为系统输出按最小误差跟踪给定值的能力，将PSS参数优化协调转化为带有不等式约束的优化问题。用PSO-ω算法对该问题求解，不易使问题的解收敛于局部最优解，并且可以提高寻优速度，从而能够对系统所装PSS的参数进行很好优化，同时证明了该算法的有效性和优越性。再通过Prony[7,8]特征值分析以及故障测试的仿真，验证了所设计PSS的有效性和鲁棒性。
1 PSS的设计
1.1 电力系统模型
电力系统的数学模型用非线性微分方程组表示如下：
式中：X为状态变量向量;U为控制变量向量。
加装PSS后，系统在小扰动情况下，根据李雅普诺夫线性化方法，把描述系统动态特性的微分-代数方程组在平衡点(稳定运行点)处线性化，得到电力系统的状态方程为：
式中：A、B为平衡点估计值;∆X为状态变量的偏差量;∆U为控制变量的偏差量。
1.2 PSS模型
本文PSS采用超前-滞后校正模型，以发电机的转速偏差∆ωp为输入信号，传递函数如下：
式中：U为发电机的PSS输出信号;Tw为隔直环节的时间常数;T1、T2、T3、T4为超前-滞后环节的时间常数;K为PSS增益。
1.3 PSS优化的目标函数和约束条件
目前，大多数PSS优化问题仅仅是寻找机电振荡模式下阻尼比最小的参数，无法综合考虑PSS与励磁系统的性能。而根据最优控制原理，对有约束最优化问题借助于Pontryagin极小值原理[11,12]，控制目标可描述为系统输出按最小误差跟踪给定值的能力，这样就考虑了综合性能指标，实现抑制系统中有功功率、频率等量的振荡，使其保持稳态值。
从动态角度考虑，ITAE准则在处理误差绝对值与时间乘积的积分时，兼顾了受扰动时系统在振荡过程中及趋于平稳时的输出误差[11,12]，故本文选择它作为PSS作用效果的目标函数，误差为各转子角速度与它们各自稳态值的相对误差绝对值之和。对于单目标最优化问题，选取目标函数如下：
式中：ω1(t)为发电机在t时刻的转子角速度;ωs1为发电机转子角速度的稳态值;1a为可调权重因子。
考虑到PSS中各参数的限制，PSS设计问题可以表述为如下带约束的优化问题：
式中：K、T1、T3为待优化的参数。参数K的典型取值范围是[0.1,1000]，T1的典型取值范围是[0.01,1.0]，T3的典型取值范围是[0.01,1.0]，Tw、T2、T4为给定值。
2 粒子群优化算法
2.1 PSO算法的基本原理
PSO算法是从生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成D维搜索空间上的一个点，我们称之为“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整，所有的粒子都有一个被目标函数决定的适应值，并且知道自己到目前为止发现的最好位置(记为Pbest)和当前的位置。这个可以看作是粒子自己的飞行经验，除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(记为Pbest)，这个可以看作是粒子的同伴的经验。每个粒子使用下列信息改变自己的当前位置：1)当前位置;2)当前速度;3)当前位置与自己最好位置之间的距离;4)当前位置与群体最好位置之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个种群中，以迭代的方式进行的。
假设在M维搜索空间(解空间)里，有s个粒子组成的粒子群，其中第i个粒子位置可以表示成M维向量，xi(n)=[xi1,xi2,…,xij,…,xiM]，j表示变量ix的第j维分量;粒子的飞行速度为iv(n)=[vi1,vi2,…,vij,…,viM];该粒子所经历的个体最佳位置可表示为ip(n)=[pi1,pi2,…,pij,…,piM];在整个粒子群中，所有粒子经历过的最佳位置为g i(n)=[gi1,gi2,…,gij,…,giM]，当第i个粒子从n-1代迭代到n代时,可采用下式进行其速度和位置的更新[6]：
式中：ω为惯性权值;Rand为在[0,1]范围内变化的随机数;n为迭代次数;粒子数i=1,2,…,s。
2.2 PSO-ω算法的基本原理
针对PSO算法搜索性能取决于对全局搜索和局部搜索能力的平衡这一特性，本文在其基础上进行改进，提出了一种具有较好的全局搜索能力和寻优速度的PSO-ω算法。
在PSO-ω中，惯性权重采用自适应的方式：
Maxit:最大迭代数;iter：迭代数;
其算法流程如下:
1)t←0;
2)初始化：在搜索空间均匀随机地产生s个初始位置，
3)评价：计算每个粒子个体的位置(解)的目标函数值;
4)比较粒子的适应值和自身最优粒子pbest的适应值，如果当前值比pbest更优，则以当前粒子替换pbest;
5)比较粒子适应值与种群最优值，如果当前值比gbest更优，则置gbest为当前粒子的矩阵下标和适应值;
6)位置更新：按式(8)和式(9)更新粒子的位移方向和步长,产生新种群X(t+1);
7)t←t+1;
8)若不满足进化结束条件,则转3),否则转8);
9)输出结果。
3 PSS参数优化与仿真结果
3.1 PSS参数优化结果
为了检验PSO-ω算法的性能以及PSS参数优化对系统暂态稳定的作用，本文使用Matlab7.0的电力系统仿真模块集Sim Power Systems Blockset(SPB)，对标准的单机无穷大系统进行PSS参数优化和系统性能仿真。
单机无穷大系统仿真模型如图1所示，图中参数均为标么值，其额定容量均为200 MVA，并且均配有自并励静止励磁系统。其中Tw=5,T2=0.05,T4=0.05[7]。通过采用种群大小为100、进化代数为100的PSO-ω算法对Kp、T1、T3三个参数进行优化，且与在相同条件下的全面学习粒子群算法(CLPSO)[6]参数优化结果进行了比较。表1为两种优化算法的参数优化结果。图2所示是在随机选取初始解的条件下，随着进化代数的增加，PSO-ω算法搜索到相对最优参数对应的ITAE变化曲线。
表2为单机系统特征值，单机系统在无PSS时阻尼比为0.062 3，系统是处于临界稳定的状态，安装PSS后系统稳定，但是机电振荡模式下的阻尼比比较小，为0.15。用PSO-ω算法优化后的PSS的阻尼比提高到0.409 0，较大程度地提高了系统的阻尼。
3.2 动态仿真结果分析
为了评价基于PSO-ω算法优化的PSS性能，对系统励磁系统参考电压加5%的扰动、系统发生三相短路、三相断路故障的情况下，对配置了采用CLPSO、PSO-ω算法优化的PSS系统进行动态仿真。
3.2.1 小扰动情况下PSS有效性分析
机端电压参考值加5%方波电压阶跃，对比不同算法得出的PSS对提高静态稳定性的作用。
图3是测试励磁系统参考电压在12 s时发生5%的扰动并持续0.5 s的结果。这种干扰情况会使发电机机端电压产生变化，从而影响系统的暂态稳定。从图中可以看到采用PSO-ω算法优化的PSS，转子角速度摆动幅度比较小，发电机的转子角速度在12.7 s时达到稳定。与其比较，CLPSO算法优化的PSS的发电机在14.5 s才达到稳定。
图4所示为机组的电磁功率动态响应曲线。图中可见采用PSO-ω算法优化的PSS，电磁功率摆动幅度较小，发电机的电磁功率在12.5 s时达到稳定。与其比较，CLPSO算法优化的PSS的电磁功率在14.6 s才达到稳定。
3.2.2 大扰动情况下PSS有效性分析
对于PSS的暂态性能，通过发电机出口t=12 s发生三相短路和t=1 s发生三相断路故障的情况下进行仿真。
图5、6为三相短路故障持续0.1 s后重合闸成功后转子角速度和电磁功率变化的结果。图7、8为三相断路故障持续0.1 s后转子角速度和电磁功率变化的结果。从图中可见采用PSO-ω算法优化的PSS，转子角速度和电磁功率摆动幅度较小，发电机转子角速度、电磁功率达到稳定的时间均比CLPSO算法优化的要快。所以PSS能够很快地平息低频振荡，提高了转子的暂态特性。
4 结论
本文在Matlab环境下，将PSO-ω算法用于单机无穷大系统PSS的参数优化问题。不同于以往只寻找机电振荡模式下阻尼比最小的PSS优化方法，本文根据最优控制原理综合考虑PSS与励磁系统的性能，优化的控制目标设为系统输出按最小误差跟踪给定值的能力，将PSS参数优化协调转化为带有不等式约束的优化问题。通过采用电力系统仿真模块集SPB，单机无穷大系统进行PSS参数优化和系统动态性能仿真。仿真结果表明，经PSO-ω算法优化的PSS在不同的干扰下都具有良好的性能，采用Prony分析法提出的特征值也验证了系统阻尼得到了提升，从而使系统的低频振荡现象得到了很好抑制。对PSO-ω算法采用惯性权值ω自适应的方式，达到了全局搜索与局部搜索平衡的特性，是一种具有较好的全局搜索能力和寻优速度的群体智能算法。
摘要：粒子群算法(PSO-ω)是一种应用于连续空间的、具有较好的全局搜索能力和寻优速度的群体智能优化算法。基于单机无穷大系统模型,通过采用PSO-ω算法对电力系统稳定器(PSS)进行参数优化,以抑制低频振荡。该方法是以最优控制原理为基础,综合考虑PSS与励磁系统的性能,将PSS参数优化协调转化为带有不等式约束的优化问题,控制目标为系统输出按照最小误差跟踪给定值的能力(ITAE准则)。用Matlab软件进行仿真,结果表明,利用该方法设计的PSS,它的稳定性有了较大的提高。
动态系统中粒子群优化算法综述 篇8
粒子群算法(Particle Swarm Optimization,PSO)是由生物学家Kennedy和Eberhart于1995年提出的进化计算技术,该算法通过对鸟类觅食行为的模拟,从而实现对实际问题的优化。
PSO算法在高维空间函数寻优方面具有解质量高、鲁棒性好、收敛速度快的优点,因而在神经网络训练、函数优化、模糊系统控制、模式分类领域得到广泛应用。同时,PSO算法具有程序简单、设置参数少、收敛速度快、实现容易等特点,目前已被广泛应用于静态问题优化中。然而,直接利用PSO算法跟踪动态系统,其效果不佳,因此动态系统中PSO算法的改进尤为必要。本文主要对PSO算法在动态系统中的改进方法进行总结。
1 基本粒子群算法
PSO算法中每一个潜在的解都被称为一个“粒子”,粒子在解空间内“飞行”,并且具有速度和位置两种属性,粒子的位置受自身运动经验的影响(个体最优位置)以及所有粒子运动经验的影响(全局最优位置),在飞行过程中其速度和位置按照下式进行更新:
式(1)、式(2)中,vid(t)、xid(t)分别代表第i个粒子目前的速度和位置,yid(t)是粒子自身的最优位置,y(t)是粒子的全局最优位置,ω是惯性权重,c1、c2是学习因子,r1、r2是在[0,1]之间均匀分布的随机值,式(1)的第一部分代表了粒子对速度的记忆,第二部分是自我认知部分,引导粒子群飞向自身经过的最好位置,第三部分是社会部分,代表了粒子间的信息共享和相互合作,具体算法流程如图1所示。
2 动态优化问题
现实生活中许多优化问题都是动态的,例如,城市交通状况由于不同交叉口红绿灯的转换,可以连续地动态改变,这就可以看成动态优化交通问题。动态系统可以分为以下几种:(1)最优值不变,取得最优值时对应的位置发生改变;(2)保持位置不变,最优值改变;(3)最优值以及取得最优值时对应的位置均发生改变;(4)在多维系统中,这些改变可以同时或独立地发生在同一维或多维上[6]。
与静态优化不同,动态优化不仅需要达到最优值,而且还需要能够跟踪最优值的轨迹变化。近年来,人们越来越关注进化算法在动态系统中的优化问题,动态优化问题可以被描述为如下形式:
式(3)中,目标函数f由向量和时间t决定。
已有许多研究者对进化过程和进化算法做了研究,大多是从基准函数(三维Parabolic函数)中创建动态环境,文献和文献则详细提供了创建动态环境的一系列方法,并给出了具体应用。三维Parabolic基准函数如式(4),在(0,0,0)处取得最小值0。
对式(4)中的x增加偏移量Offset,即在一定的更新频率(每隔多少代)下,对基准函数在每一维上进行线性、环形、随机处理,即能够产生3种类型的动态轨迹:线性、环形、随机轨迹,其具体函数表达式如式(5):
然而,现实生活中的许多问题更加复杂多维且变化多端,因此,一个可以涵盖各种各样变化类型的测试函数应运而生,文献提供了该测试函数的表达式,见式(6):
式(6)中,N代表该动态系统中有多少个峰,并且每个峰在位置(Xi,Yi)上独立,其高度为Hi,倾斜为Ri,这些峰用Max函数混合起来,每一次生成器f(X,Y)被调用时,基于式(7)、式(8)作改变,就会产生新的随机的形态学类型。
该测试函数具有以下优点:(1)易生成较为复杂的问题;(2)适应值可以方便设置为所希望的数据;(3)可以扩展到高维空间;(4)函数提供了3种可以生成动态环境的特征(高度、位置、倾斜度)。当需要生成较为复杂的动态环境时,只需改变以下参数:N(峰的数目)、Rbase(倾斜度可控变量的最小值)、Rrange(允许的变化)、Hbase(斜坡高度的最小值)、Hrange(允许的变化值),简单易行。同时,文献则对两种动态环境作对比,动态函数DF1更能代表一些复杂多维的环境。
3 动态系统PSO优化方法
许多优化问题是动态的、时变的,它们的最优解将会随着时间的改变而改变。对于这种时变优化问题,优化算法不仅要迅速检测到环境的改变,同时,还要对改变作出相应的应对策略。Eberhart首先将基本PSO算法应用到动态系统中,结果显示当环境改变,频率、步长较小时,基本PSO能够及时跟踪动态极值。然而,当动态系统变化较大时,基本PSO算法检测和跟踪效果不好。因此,为了更好地适应动态环境变化,提出了一些经典的优化PSO算法以实时检测环境变化,并及时针对改变调整寻优策略。
3.1 检测、响应动态系统的PSO算法
Hu and Eberhart通过检测“固定的”最优值以及“改变的”最优值来判断环境的改变,“固定的”最优值即找到最优值后经过一定的代数,再次检测最优值,看其是否发生明显改变;“改变的”最优值[13]即每一代最优值的位置将会被重新计算,如果最优值改变,则说明环境发生了动态改变。针对这两种改变,本文给出了多种响应方法,可根据不同的应用,选择不同的响应方法。
Carlisle[14]提出了一种“哨兵”粒子群优化器,在解空间内用一个固定的点来检测环境的改变,在每一次迭代前,“哨兵”将会重新计算适应值,并与之前进化的值作对比,由于“哨兵”所在的位置是固定的,如果适应值发生较大改变,则说明环境发生了改变,“哨兵”将会提醒种群更新最优位置记忆;文献[15]同样是利用了“哨兵”的思维,但是由于Carlisle[14]的固定粒子改为一个或多个随机选择的粒子,这样就可以检测到全局的环境变化;文献[16]则在文献优化器的基础上,作出以下优化:当环境发生改变时,不是盲目取代最优值的位置,而是利用目前最优值的位置重新计算环境改变后的适应值,如果此时的适应值优于之前的最优值,则保留此处信息,这样就大大提高了寻优准确性。
3.2 自适应PSO算法
文献不需要实时检测环境的改变,它是基于传统的PSO算法,提出了一种新的粒子群最优适应值更新机制,传统的最优值更新公式如式(9):
当t+1时,比较最优值与f(Xi(t+1))的大小,保留最大值,自适应PSO算法更新公式如式(10):
在式(10)中,引入衰减常量T,T∈[0,1],个体最优值以及全局最优值将会以一定的速率随着时间衰减,目前位置的适应值将会高于衰减的适应值,并取代之前的适应值。尽管所有的粒子具有相同的衰减常量,但每一个粒子的更新频率也是不同的,当f(X)越来越大,f(P)越来越小,粒子将会频繁更新最优值,直至达到循环迭代次数,寻优停止。
Shimin引入了“活跃因子(Activity Factor,AF)”来评价粒子群搜索全局最优值的能力,可以被用来检测粒子的搜索状态并评价整个种群的收敛情况。在搜索空间里,AF可以定义如式(11):
式(11)中,Ai(t)是第i个粒子在时间t时的活跃度,wd是聚合粒子AF的惯性权重,Aid(t)是第i个粒子在第d维时的活跃度,它可以由式(12)获得:
其中,vid(t)是第i个粒子在时间为t、维度为d时的速度,Rd是在d维上的搜索范围,c是调谐变量。
根据AF的定义可知,当粒子运动缓慢时,AF的值很小。同时可以认为,整个种群达到最优值时,粒子才会保持缓慢运动的状态,这里将AF作为粒子群运动状态的评价标准,同时,在复杂的动态环境中,需要随机选取一部分粒子群为“活跃粒子”。当粒子群运动缓慢时,活跃粒子将会检测移动状态并且重新初始化,然后通过粒子群更好地搜索全局最优值。
3.3 混合PSO算法
Dianmin引进混沌变化技术,当环境发生动态改变时,由粒子群多样性引导的混沌技术进行响应,提高响应效率。目前,对混沌没有严格的定义,一般而言,混沌状态可以通过式(13)的logistic映射得到。
式(13)中,μ是控制因子,当μ=4时,处于完全混沌状态。
此处响应政策可以被描述为以下方式:当环境发生改变时,选择要被处理的粒子i,它目前的位置为xij(t),范围为[aj,bj],基于文献、文献,将粒子i的每一维映射到[-1,1],映射方法是:
式(16)将i映射到搜索空间:
这使得个体粒子具有智能的混沌变化,每个粒子不仅能通过个体极值点和全局极值点调整自身的位置,还可以通过混沌变异,调整粒子群的多样性,促进了粒子群搜索整个解空间。
粒子的多样性可以由式(17)描述:
式(17)中,diversity(s(t))是粒子群在t代时多样性的值,s(t)代表粒子群种群,|s(t)|是粒子群的大小,|L|是搜索空间最长的半径,N是维数,pij(t)是粒子i在j维上的最优位置,是所有粒子在j维上的最优值位置的平均值。在搜索过程中,如果粒子的多样性较高,并且diversity(s(t))≥h×diversity(s(0)),则不需要处理粒子;如果粒子的多样性较低,diversity(s(t))≤h×diversity(s(0)),粒子分布集中,需要对粒子进行处理,即引入上述混沌变异技术,这里h是多样性的控制因子,不同的h会使算法效果不同。
4 结语
在现实生活中,许多系统状态的改变,如目标、优先性、资源等的改变会导致一些再优化问题。例如,自动集装箱制造商进行船对岸起重时,应该保证在5~10分钟内对于整个接口设施实施一个新的设备安排表;当给某地区提供药物时,如果该地区突然急需药物,则针对这一优先性的改变,一个新的安排表应该快速可得,改进的粒子群算法可以有效且快速解决这些优化问题。
粒子群算法求解物流路径优化问题 篇9
物流问题是当今最流行的运输优化问题, 描述为:有n个客户点, 最多使用m辆汽车, 要求安排车辆行驶路线使车辆行驶总距离最少.并满足条件:
1) 每个客户点的需求只能由一辆车来完成;
2) 每个客户点需求量总和必须小于等于汽车载重量;
3) 所有路径的长度总和必须小于等于单次配送行驶的最大距离。
2 粒子群算法
粒子群优化算法主要模拟鸟集群飞行觅食行为, 每个粒子利用自身历史最优位置和整个粒子群的全局最优解提供的信息, 在解空间内不断飞行, 实现寻找最优解的目的。在基本PSO算法中, 第i个粒子的飞翔速度是一个D维的向量, 第i个粒子迄今为止发现的最好位置 (个体极值) , 整个粒子群迄今为止发现的最好位置 (全局极值) , 整个粒子群是通过个体极和全局极值来更新自己的飞行速度和飞行位置, 在解空间中寻求最优解。c1和c2是学习因子, r1和r2是随机数。PSO算法每粒子采用如下公式来更改自己的速度和位置:
3 算法流程
步骤1:初始化种群规模、粒子的位置向量、速度向量, 计算粒子的适应度;
步骤2:根据初始化粒子的全局最优值和个体最优值;
步骤3:并将粒子的p Best设置为个体当前最优位置, g Best设置为初始群体中整个粒子群体最佳位置;
步骤4:若算法满足收敛条件或达到最大迭代次数, 则执行步骤7, 否则, 执行步骤6;
步骤5:根据公式 (1) 和公式 (2) 求出粒子移动后的新个体最优和全局位置最优值;
步骤6:将迭代次数加1, 并执行步骤3;
步骤7:输出g Best, 算法结束。
4 实验结果分析
某物流公司有一个配送中心, 各配送点位置坐标和需求量如表1所示。
所有试验均在操作系统为windows 7, 双核3.16GHz的Intel处理器和4GB内存, Matlab2010的平台上完成。连续计算50次, 路线仿真图如图1所示, 遗传算法和粒子群算法运行50次实验结果如表2所示。
从表2可以看出:PSO算法无论是从最优解、平均值、50次找到最优解次数还是平均计算时间均优于GA算法。实验数据说明PSO算法收敛速度快, 对物流配送路径优化问题具有一定的可行性和有效性。
5 结论
针对物流问题的特殊性, 提出了一种粒子群算法的物流车辆路径优化解决方案。仿真结果表明此算法, 有效防止算法陷入局部最优解, 加快了路径优化问题求解效率, 并求得了最优解。可以用于解决寻求最优路径这一类实际问题。
参考文献
[1]Kennedy J, Eberhart R.Particle swarm optimization[C]//IEEE Int Conf on Neural Networks.Piscataway:IEEE Press, 1995:1942-1948.
[2]Azzawi A A G, Al-Saedi M A H.Face recognition based on mixed between selected feature by multiwavelet and particle swarm optimization[C]//Developments in E-systems Engineering (DESE) .Piscataway:IEEE Press, 2010:199-204.
基于粒子群优化的公交调度研究 篇10
城市公交系统是绝大多数市民出行的主要交通工具,其运行好坏直接影响着整个城市交通运输系统的交通状况,需要对各线路进行合理的调度。调度问题涉及到多个约束因素,是一个多目标优化问题,应用传统的优化方法计算,计算时间长,效率较低。
粒子群优化算法(Particle Swarm Optimization, PSO)是一种全局优化算法,能够有效解决各种约束或不带约束的复杂优化问题。算法源于对鸟类捕食行为的模拟,其突出特点是结构简单,运行速度快,计算量小,程序实现非常简洁,需要调整的参数少。基本PSO算法在搜索的初期能以较快的速度收敛,但在后期容易陷入局部最优解。为此,本文提出了一种改进策略,能够有效跳出局部最优解,实现全局收敛。并针对公交调度的问题,以乘客和公交公司总效益最大化为调度目标,应用改进的粒子群优化算法求解,取得了较好的效果。
1 公交调度优化模型
公交调度与诸多因素有关,对于公交线路上的公交车调度,其难点在于协调乘客与公交公司两者的利益。调度方案即要照顾乘客的利益,即减少乘客的等待时间;又要考虑公交公司节省运行支出。只有使乘客与公交公司费用之和为最小才能获得最大的社会效益[1,2],所以以其作为目标函数来建立数学模型。
1.1 模型假设
调度优化模型的建立基于以下假设:
①所有车辆车型一致,并沿着规定线路运行。
②不准许越站和超车。
③假定每辆车经过各车站时不会留有乘客。
④在给定的时间段内,发车间隔是固定的。
⑤各时间段内乘客到站服从均匀分布。
⑥站间运行时间一定。
1.2 基本变量的定义
K表示时段总数,将一天划分为k个时段。
Mk表示第k时段的类型(高峰期时段、平峰期时段、低峰期时段),Mundefined为该时段内最小发车间隔,Mundefined为该时段内最大发车间隔。
Tk表示第k时段的时段长度。
tk表示第k时段内的发车间隔,根据Mk的值有不同的取值范围。
J表示该线路的车站总数,将线路划分为j个车站。
pkj表示第k时段第j站的乘客到站密度(服从均匀分布)。
C公交线路车辆平均每班次运行所需要的费用。
S社会平均每分钟的工资。
1.3 目标函数
一个工作日内公交线路运营总费用为:
undefined
一个工作日内乘客等待总费用为:
undefined
记符号Z表示总费用,则公交调度优化问题的目标为:
min Z=α·F(e)+β·f(e) (3)
约束条件:
Mundefined≤tk≤Mundefined
α+β=1(加权系数,反映了二者之间的制约关系)
2 基于改进粒子群优化的公交调度优化方法
2.1 粒子群优化(PSO)
PSO算法是基于群体与适应度,根据对环境的适应度将群体中的个体移动到好的区域。将每个个体看作D维搜索空间中的一个没有体积的粒子,在搜索空间中以一定的速度飞行。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。第i个粒子表示为Xi=(xi1,xi2,…,xiD),它经历过的最好位置称为pbest。在群体所有粒子经历过的最好位置的索引号用符号gbest表示。粒子i的速度用Vi=(vi1,vi2,…,viD)表示。对每一代,其第d维(1≤d≤D)根据如下方程变化:
vundefined=ωvundefined+c1·rand()·(pundefined-xundefined)+
c2·rand()·(pundefined-xundefined) (4)
xundefined=xundefined+vundefined (5)
其中,k为迭代次数;ω为惯性权重,它使粒子保持运动的惯性,使其有能力探索新的区域;c1和c2为加速常数,它们使每个粒子向pbest和gbest位置加速运动;rand为[-1,1]范围内变化的随机数。
2.2 改进的粒子群优化算法(MPSO)
在基本PSO算法的迭代初期,粒子在较大的空间内进行搜索,但随着迭代次数的增加,在搜索的后期,粒子会向局部极小或全局极小收敛。此时,pbest,gbest和Vi都会趋向于同一点,且每个粒子的运动速度趋向于0。这种情形下,粒子群所趋向的那个点即为粒子群优化算法的最终求解结果,此结果可能并不是全局最优。因此,需要为PSO算法提供一种机制,使得在陷入局部最优时能够跳出局部最优位置,进入空间的其它区域进行搜索,从而增强PSO算法的全局搜索能力[3]。通过采用“驱散”策略的方法来实现这一目标,方法原理如下:
首先,用一个参数p代表粒子群的聚集度。将第k代粒子群分布的当前搜索空间D划分成为Q个相等区域,分别统计每个区域中所包含的粒子数目,并记为p1,p2,p3,…,pQ,定义粒子数目最多的一个为pL,当pL(0
当运行一定代数之后,pL会逐渐稳定下来,且趋近于粒子群的粒子总数,此时可认为当前gbest为局部最优,为了逃出局部最优,对所有粒子的位置进行重新初始化,分布于Q个区域中,这样就将原本聚集在一起的粒子“驱散”开来,而每个粒子在随后的迭代过程中在新的位置基于粒子在上次搜索中的运动惯性向pbest,gbest的方向前进。随着迭代的继续,经过驱散的粒子群又将趋于同一点,当粒子群收敛到一定程度时又进行下一次驱散过程,如此反复,直到指定的最大进化代数或者最优解继续保持一定代数不变。
3 基于MPSO的公交调度优化方法
3.1 粒子编解码
从调度优化模型中可以看出,目标函数是公交线路上发车间隔的函数,是进行优化的对象。对于使用MPSO算法解决公交调度优化问题,关键在于怎样表达发车时序。鉴于所建立的模型是分时段等间隔的,我们采用整数形式的编码方式。结合实际情况,规定Mmink不得小于3min,Mmaxk不得大于18min,即区间长度为16,可以采用1位16进制代码表示,编码与区间的映射关系为:3→0,4→1,…,18→F。具体编码过程如下:
假设全天分为4个时段,发车间隔分别为12min,5min,8min,15min,则经过映射后粒子表示为
X=[9|2|5|C]
解码时依据映射关系进行反向映射即可得到发车时序。
根据上述编码机制,按照不同时段内发车间隔的取值范围,随机产生初始粒子群,粒子群规模为N,MPSO的搜索空间也设计成n维空间。
3.2 适应度评价
MPSO算法通过适应度来评价粒子当前位置的优劣。对应公交调度方案的总费用越低,则适应度越高。相应的适应度函数为:
undefined
3.3 算法描述
算法步骤描述如下:
步骤1:编码和初始化粒子群。
步骤2:按式(4)、(5)产生下一代种群,按式(6)计算所有粒子的适应度。
步骤3:评价新种群:找到新的pbest和gbest;更新种群的gbest和每个粒子的pbest。
步骤4:更新聚集度pL。
步骤5:判断pL的值。如果满足驱散条件,则进行驱散操作,跳转返回步骤2;否则继续执行步骤6。
步骤6:判断算法是否达到全局收敛或达到预先设定的迭代次数,如果满足,继续执行步骤7;否则跳转返回步骤2。
步骤7:输出全局极值gbest,算法运行结束。
4 实例研究
以武汉市一条典型的公交线路为例进行计算。该条公交线路运营长度为8.7公里,共设16站,运营时间为6∶00～20∶00,表1中给出该线路某一周内下行方向各站客流数量统计数据。算法主要参数设置:共划分14个时段;发车间隔变化区间高峰期为[3],平峰期为[6,12],低峰期为[12,18],且取值均为1的整数倍;公交车综合运营费用为3.2元/km;乘客等待成本为0.15元/min;加权系数α=β=0.5;粒子群规模为200;最大迭代次数为200。应用MPSO算法得优化发车间隔如表2所示。
5 结束语
以公交公司运营费用和乘客等待时间为衡量标准构造公交调度优化模型。针对公交调度的组合优化特性,运用改进的粒子群优化算法对调度方案进行优化。优化后的方案兼顾了公交公司和乘客两方面的利益,实现了资源的优化配置,使得社会总体效益达到最优,为公交优化调度提供了一种解决办法,具有一定的实际意义。
参考文献
[1]Yang Zhiwei,Zhao Shengchuan,Zhao Qian.Research on Bus SchedulingBased on Artificial Immune Algorithm[C].WiCOM’08.4th Interna-tional Conference,2008:1-4.
[2]陈芳.城市公交调度模型研究[J].中南公路工程,2005,30(2):20-23.
【随机粒子群优化】推荐阅读：
混沌粒子群优化09-06
自适应粒子群优化05-10
概率并行粒子群优化05-22
多目标粒子群优化06-10
粒子群优化算法研究10-23
离散粒子群优化算法10-27
自适应粒子群优化算法06-12
改进多粒子群优化算法06-23
粒子群优化的模糊特征08-04
双层多目标粒子群优化08-08