简化粒子群算法（共11篇）
简化粒子群算法 篇1
0引言
粒子群优化 (Particle Swarm Optimization, 简称PSO) 作为一种新的智能优化算法, 是Kennedy James和Eberhart Russell在1995年率先提出的[1]。PSO算法自提出以来, 算法的优势在很多领域得到了体现, 但仍存在收敛速度慢等缺陷。针对实际问题的多样性和复杂性, 目前出现了多种基于PSO的改进算法。Y Shi和R C Eberhart在1998年的IEEE国际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimizer”的论文, 首次在进化方程中引入惯性权值w[2], 大大改善了基本PSO算法的性能。本文给出一种新的混沌惯性权值的调整策略及其相应的简化粒子群优化算法, 并把此算法应用于机械优化设计问题, 取得了良好的效果。
1混沌惯性权重的SPSO算法与实验结果分析
PSO算法进化公式为:
vi (t+1) =c1r1 (Pi-xi (t) ) +c2r2 (Pg-xi (t) ) 。 (1)
xi (t+1) =wxi (t) +vi (t+1) 。 (2)
其中:t为进化代数;c1、c2为正的加速度常数;r1、r2为 (0, 1) 之间的随机数;Pi为个体最优值;Pg为全局最优值;xi (t) 和vi (t) 分别为粒子的位置和速度。
从位置更新模型可以看出, 式 (2) 等号右端由两项和组成。第一项wxi (t) 表示粒子上一代的位置对下一代的影响。此项提供了粒子在搜索空间飞行的动力, 是算法拓展搜索空间以摆脱局部最优解的关键部分, 它越大, 全局搜索能力愈强。wxi (t) 的大小由w决定。最初w为固定的常数, 如w=1。后来w设定为随代数增大而线性递减, 但在实际的问题解决中, 对于不同的问题, 其每一代所需的比例关系并不相同, 所以, w简单的线性递减只是对某些问题很有效。考虑到PSO算法是一种随机性算法, 将w设定为服从某种随机分布的随机数, 这样能使算法更具随机性, 更好地克服w的线性递减所带来的不足。
混沌是普遍存在于非线性系统中的一种现象, 其表现为遍历性、随机性和规则性[3]。混沌搜索的主要思想是:通过某种迭代方式产生混沌序列, 一般采用Logistic方程:
xk+1=μxk (1-xk) 。 (3)
Logistic映射在分叉参数3.569…5<μ<4时处于完全混沌状态, 在此区间内方程运动轨迹呈现混沌特征。本文利用混沌序列的内在随机性、遍历性和规则性产生w。如果算法在进化初期接近最好点, 混沌w可能产生相对小的w值, 加快算法的收敛速度;否则, 如果初期找不到最好点, w的混沌生成可以使得算法继续拓展搜索空间, 增大找到最好点的机率。
混沌WPSO算法采用舍弃速度项的简化粒子群算法 (SPSO) [4], 形式更加简洁, 运算简单, 位置更新公式为:
xi (t+1) =wxi (t) +c1r1 (Pi-xi (t) ) +c2r2 (Pg-xi (t) ) 。 (4)
下面通过4个典型测试函数的仿真实验, 来测试上述选择策略的性能。4个测试函数的最优值均为0。
(1) Spere函数:
(2) Schaffer函数:
(3) Rastrigin函数:
(4) Griewank函数:
实验中w按照式 (3) 混沌进化, 混沌初值不取0.25, 0.5, 0.75, μ=4, 随初值不同w混沌进化值有所不同。微粒进化公式采用式 (4) , 其中:c1=2.0, c2=2.0;群体规模均为30;最大进化代数为300代;4个测试函数误差都取0.000 1。使用基准函数对混沌产生的简化粒子群算法 (CWSPSO) 连续运行50次, 结果取平均值。表1为4个测试函数的运行结果。
从实验结果可以看出, 4个常用函数混沌w比线性递减w和随机w的算法性能有显著改进, 且混沌w的算法具有更快的收敛速度和更好的稳定性, 这源于混沌w的内在随机性、规则性, 并且初值敏感性没有影响算法的性能。Rastrigin函数一直都是很难优化的复杂函数, 当w采用混沌进化策略时, 不论混沌初值取多少, 用于Rastrigin函数均能得到很显著的效果。
2算例
本文以旋转式滑片压缩机为例, 对新算法进行验证。为使压缩机气缸面积得到最大程度的有效利用, 以面积利用系数c=f (z, ε, σ) 最大为目标函数。其中, z为滑片数;ε为滑片相对厚度;σ为转子与定子的相对偏心距。其数学模型如下[5]:
实验参数取法与测试函数相同, 实验结果见表2。
从表2数据可以看出, 迭代过程逐渐收敛于最优解, 所得最优数据与理论分析结果相吻合, 证明了所用方法的可靠性。
3结束语
本文提出了一种混沌惯性权值调整策略及相应的简化粒子群算法, 新算法对每个测试函数都能搜索到最优解, 容易控制, 算法更稳定。将该算法应用于机械优化设计问题, 验证了算法的有效性。
摘要：利用混沌序列的内在随机性、遍历性和规则性, 提出了一种混沌惯性权重的简化粒子群优化算法。将该算法应用于机械设计, 结果表明新算法具有更快的收敛速度和更强的全局寻优能力。
关键词：机械设计,混沌,简化粒子群算法
参考文献
[1]Kennedy J, Eberhart R C.Particle swarm optimization[G]//Proc of 1995 IEEE Internation Conference onNeural Network.Perth Australia:IEEE, 1995:1942-1948.
[2]Shi Y, Eberhart R C.A modified particle warmoptimization[G]//Proceedings of the 1999 Congress onEvolutionary Computation.Piscataway:IEEE Press, 1998:69-73.
[3]张春慨, 李霄峰.基于线性搜索的混沌优化及其在非线性约束优化问题中的应用[J].控制与决策, 2001, 16 (1) :120-124.
[4]马强, 孙秀霞, 彭建亮.简化的位置随机扰动的粒子群算法[J].微计算机信息, 2009, 25 (6-3) :217-219.
[5]邓定国, 束鹏程.回转压缩机[M].北京:机械工业出版社, 1989.
简化粒子群算法 篇2
粒子群优化算法PSO(Particle Swarm Optimization)是一类性能优越的寻优算法.但由于早熟问题,影响了算法性能的发挥.针对这一问题,引入粒子距离的概念,提出一种新的PSO改进方法(称为NA-PSO).通过求解组网雷达的系统偏差,表明了NA-PSO算法的`可行性,与对比方法相比较,能有效配准,且具有更好的收敛精度和更快的进化速度.
作 者：王波 李瑞涛 王灿林 朱丹 WANG Bo LI Rui-tao WANG Can-lin ZHU Dan 作者单位：王波,李瑞涛,王灿林,WANG Bo,LI Rui-tao,WANG Can-lin(海军航空工程学院,山东,烟台,624001)
朱丹,ZHU Dan(91550部队,辽宁,大连,116023)
简化粒子群算法 篇3
关键词：粒子群算法；单目标；多目标；传递率；传递函数矩阵；无穷范数；状态反馈控制；控制力传递率
中图分类号：TU112.41文献标识码：A
单自由度、双自由度体系是研究设备振动隔离的主要模型方法，且隔振体系性能与隔振参数关系密切，选择合适的参数，能提高系统的隔振性能，如果参数选择不当，就会适得其反，所以隔振参数的优化研究显得非常必要.文献1将遗传算法与最大熵法结合，给出了两级隔振系统参数优化设计的一种混合方法；宋鹏金等2采用傅里叶变化法和直接积分法分别对时域函数和频域函数进行参数优化，提出了一种锻锤隔振参数优化的新方法；文献3根据超精密隔振器的内部结构和隔振系统的布置形式，建立了超精密隔振系统的动力学模型，并在此基础上推导出理论频响函数、进行了系统参数的辨识研究；LIU等4基于整星隔振体系进行了参数优化；ESMAILZADEH5采用梯度优化方法对汽车悬挂体系进行了隔振参数的优化研究；文献6提出了一种隔振参数线性变化的方法，主要通过刚度迟滞模型实现；刘春嵘等7基于反共振原理在小振幅假设下建立了两级浮筏系统的数学模型，并分析了隔振机理，推导出了力传递率的表达式.
作为新型的群智能算法——粒子群优化算法PSO自1995年提出以来，就因其简单、易实现、收敛快，可调参数少等优点得到了广泛应用8.由于传统粒子群算法的局限性，许多学者对其做出了改进.Shi9等提出了关于权重的线性调整策略，获得了满意的优化效果；李军等10在Shi的基础上提出了自适应权重变化策略，克服了传统粒子群算法寻优过程的早熟情况，能使粒子群算法达到局部最优及全局最优的平衡.Coello等首次提出了多目标粒子群优化算法MOPSO，掀开了多目标优化问题的新篇章，主要思想是通过Pareto最优解集决定粒子飞行方向以及在全局知识库中得到之前发现的非支配向量，以指导其它粒子飞行11.
状态反馈控制是振动控制领域的常用方法，通常包括线性二次型最优控制、极点配置控制、基于观测器的控制器等，由于实际问题的不确定性，鲁棒H2H
SymboleB@ 控制被提出并广泛应用 12.上述方法在机械、结构等振动控制领域中发挥了巨大作用，其实质是通过控制器产生基于输出的反馈控制力，以优化控制系统响应.
1粒子群算法
1.1标准粒子群算法
粒子群优化算法模型中，每一个粒子的自身状态都由一组位置和速度向量描述，分别表示问题的可行解和它在搜索空间中的运动方向.粒子通过不断学习它所发现的群体最优解和它在搜索空间中的运动方向，并不断更新它所发现的群体最优解和邻居最优解，从而实现全局最优解.粒子的速度和位置更新方程是PSO的核心，由式1表示：
1.3多目标粒子群算法
多目标粒子群算法的主要计算步骤如下所述：
Step1：初始化粒子群，计算各对应粒子的目标函数向量，将其中的非劣解加入到外部档案之中；
Setp2：初始化粒子的局部最优值pbest和全局最优值gbest；
Setp3：在搜索空间内，通过式1，2调整粒子的飞行速度和位置，形成新的pbest；
Step4：根据新的非劣解维护外部档案，并为每个粒子选取gbest档案的内容决定全局最优值的选取；
Step5：是否达到最大迭代次数，若否则继续计算，若是则停止计算，输出pareto最优解集及全局最优解.
多目标粒子群优化算法与单目标粒子群优化算法的主要区别就是全局最优解的选取方式及外部档案的设定和更新.需要着重指出的是，关于全局最优解的选取问题；对于多目标优化，直接计算会存在一组等价的最优解集，很难从每一次迭代中确定一个全局最优解.解决该问题最直接的方法即是利用Pareto支配的概念，考虑档案中的所有非劣解，并从中确定一个“主导者”，通常采用密度测量的方法来确定全局最优解.本文将采用基于粒子最近邻拥挤程度评判的最近邻密度估计方法
6结语
基于粒子群优化算法，以控制输出的传递率为目标函数，在单自由度、双自由度隔振体系传递率分析的基础上，分别进行了隔振参数的单目标和多目标优化设计研究.
传统的振动控制设计，往往是在已知隔振参数的情况下创新控制方法或者优化控制器，却忽略了隔振参数对控制系统的重要性，盲目地从控制角度优化体系，不仅容易造成控制能源浪费，还可能会引起系统响应发散.
我国《隔振设计规范》15仅对单自由度隔振体系的传递率等相关参数做了规定，事实上，本文研究表明，双自由度隔振体系更适用于常见的工程振动控制.本文亦为最优隔振体系设计及最优振动控制设计提供了新思路，对《隔振设计规范》接下来的修订工作具有指导意义.
参考文献
1 魏燕定，赖小波，陈定中，等. 两级振动隔振系统参数优化设计J.浙江大学学报，2006，405：893-896.
WEI Yanding， LAI Xiaobo， CHEN Dingzhong， et al. Optimal parameters design of twostage vibration isolation systemJ.Journal of Zhejiang University， 2006， 405：893-896.In Chinese
2宋鹏金，陈龙珠，严细水.锻锤隔振基础参数优化的新方法J.振动与冲击，2004，233：96-98.
SONG Pengjin， CHEN Longzhu. YAN Xishui. The new parameters optimization method of vibration isolation base of hammer J. Journal of Vibration and Shock， 2004， 233：96-98. In Chinese
3董卡卡，蒲华燕，徐振高，等. 超精密隔振系统的建模与参数辨识J.武汉理工大学学报，2013，31：126-128.
DONG Kaka， PU Huayan， XU Zhengao， et al. Modeling and parameter identification of the ultraprecision vibration isolation system J. Journal of Wuhan University of Technology， 2013， 31：126-128. In Chinese
4LIU L K， ZHENG G T. Parameter analysis of PAF for wholespacecraft vibration isolation J. Aerospace Science and Technology， 2007， 116： 464-472.
5ESMAILZADEH E. Design synthesis of a vehicle suspension system using multiparameter optimization J. Vehicle System Dynamics， 1978， 72： 83-96.
6ZHANG F， GRIGORIADIS K M， FIALHO I J. Linear parametervarying control for active vibration isolation systems with stiffness hysteresis J. Journal of Vibration and Control， 2009， 154： 527-547.
7刘春嵘，肖卫明，徐道临. 双层流体浮筏的隔振特性研究J.湖南大学学报：自然科学版，2013，401：43-48.
LIU Chunrong， XIAO Weiming， XU Daolin. Study of the vibration isolation of twodegreeoffreedom fluidtype floating raft J. Journal of Hunan University：Natural Sciences， 2013，401：43-48. In Chinese
8KENNEDY J， EBERHART R C. A new optimizer using particle swarm TheoryCProceedings of the Sixth International Symposium on IEEE.Micro Machine and Human Science， 1995： 39-43.
9SHI Y， EBERHART R C. A modified particle swarm optimizer CIEEE World Congress on Computational Intelligence.NewYork： IEEE，1998：69- 73.
10李军，许丽佳.一种带压缩因子的自适应权重粒子群算法 J.西南大学学报，2011，337： 118-120.
LI Jun， XU Lijia. Adaptive weight particle swarm optimization algorithm with construction coefficient J.Journal of Southwest University， 2011， 337： 118-120. In Chinese
11COELLO A C， LECHUGA， MOPSO M S： A proposal for multiple objective particle swarm optimizationC Proceedings of the 2002 Congress on IEEE.Evolutionary Computation， 2002， 2： 1051-1056.
12欧进萍.结构振动控制——主动、半主动和智能控制M. 北京：科学出版社，2003：61-68.
OU Jinping. Structure vibration controlactive， semiactive and smart controlM.Beijing： Science Press， 2003：61-68. In Chinese
13DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGAII J. IEEE Transactions on Evolutionary Computation， 2002， 62： 182-197.
14GOLDBERG D E， RICHARDSON J. Genetic algorithms with sharing for multimodal function optimizationC Proceedings of the Second International Conference on Genetic Algorithms and Their Applications.Hillsdale， NJ： Lawrence Erlbaum， 1987： 41-49.
15GB 50463-2008 隔振设计规范S.北京：中国计划出版社，2008： 36-40.
简化粒子群算法 篇4
粒子群优化 (particle swarm optimization, PSO) 算法是Kennedy和Eberhart受人工生命研究结果的启发并通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法[7]。作为一个有效的优化算法, PSO算法被广泛应用于函数优化、模式分类、模糊系统控制、神经网络训练以及其他工程领域中[8]。由于PSO算法程序实现简单, 需要调整的参数很少, 因此近年来出现了研究热潮, 并提出了很多改进的算法[9—12]。
标准PSO算法在进化后期由于粒子多样性的缺失而易于陷入局部最优, 发生早熟收敛问题。在文献[12]提出的简化粒子群算法 (simplified PSO, SPSO) 基础上, 融入蛙跳算法 (shuffled frog leaping algorithm, SFLA) 的分组思想, 可以有效避免算法早熟收敛现象的发生, 提高算法PSO的收敛速度和收敛精度。论文最后将这种改进的PSO算法用于集装箱装箱问题, 与现有文献相比, 可以得到更高的装箱率。
1 问题描述
集装箱装载问题是指将一批小的物体按照一定的顺序和方式装入集装箱中, 目标是使集装箱的空间利用率和 (或) 载重利用率最高。集装箱装载问题可从集装箱和货物两方面考虑, 即单集装箱贯序装配和多集装箱并行装配、同种货物装配和不同货物装配, 这两种方法相互组合, 对应单集装箱贯序装配、多集装箱并行装配、同种货物装配、不同货物装配四种装配情形。对于集装箱装载问题, 国内外已经开展了相应的研究, 现选取三空间分割法结合PSO算法实现装箱。这种方法规则简单, 且能够保证货物有足够的稳定性, 对于实际装箱具有现实性的指导意义。下面是对三空间分割法进行简单介绍。
假设待装载的货物均为长方体, 货物在装入集装箱时要求各边分别与集装箱各边平行, 不能斜放。集装箱的后左下处于空间坐标系的零点位置, L、W、H分别表示集装箱的长、宽、高尺寸, 如图1所示。装载开始前, 先按一定的规则整理好待装入的货物, 包括货物装载顺序、是否有旋转、如何旋转等。装载开始时, 首先将整个集装箱作为当前的装载空间, 第一个货物放在集装箱的后左下角的位置上。这样集装箱就被分割成三个空间:前空间 (front space) 、右空间 (right space) 和上空间 (top space) 。空间的分割方式如图1所示, 之所以这样分割, 一方面是为了使剩余的空间尽可能的大块存在, 有利于提高装箱利用率, 另一方面是为了保证小的货物在大的货物上面, 提高货物的稳定性。在第二个货物放入时就依次以这三个空间为当前装载空间, 被放入的那个空间又被分割成前、右、上三个空间。随着货物的依次装入, 不断重复上述分解过程, 直到货物全部装完或集装箱没有可以利用的空间为止。在集装箱中装载货物遵循以下规则: (1) 对当前空间按照体积由小到大的顺序进行排序, 每个货物选择能放下且体积最小的空间, 放在该空间的后左下角; (2) 每放入一个货物后, 删除体积为零的空间和不能放下剩下任一货物的空间。
2 算法描述
PSO算法是一种基于种群的智能优化算法。假设在D维的搜索空间中, 粒子群的规模是N, xi= (xi1, xi2, …, xi D) 是第i个粒子的位置, vi= (vi1, vi2, …, vi D) 是其对应的飞行速度, 则PSO算法的迭代公式如下:
式中, c1和c2被称为学习因子, pbest和gbest表示粒子自身历史最优位置和粒子群最优位置, r1和r2为介于 (0, 1) 之间的随机数。
胡旺等人仔细分析了PSO算法的式 (1) 和式 (2) , 发现速度项并不是必须的, 它的存在有可能使得粒子偏离正确的进化方向, 为此给出简化粒子群算法:
式 (3) 中, ω表示收缩因子。文献[12]从理论和实验上证明了这种简化粒子群算法的高效性。
蛙跳算法是模拟一群青蛙在一片湿地中跳动觅食行为而提出的一种优化计算方法[13]。假设一群青蛙生活在一片湿地里, 每个青蛙代表问题的一个解, 青蛙通过在不同的石头间跳跃寻找食物。这群青蛙又被分为可以进行充分交流的若干个子群, 即算法进化到一段时间后, 各子群间进行信息交流。这样, 每个青蛙同时利用子群和种群的信息来寻找食物。
由于SPSO算法只用到位置信息, 而SFLA算法也只需要位置项, 这样可以将SFLA算法的分组思想引入到SPSO中, 可以确保各个小组内粒子间的差异性, 有利于粒子位置的更新。混合蛙跳粒子群 (hybrid frog leaping particle swarm optimization, HFLPSO) 算法更新公式如下
式 (4) 中, 右边的第1项为“历史”部分, 第2项为“认知”部分, 第3项为“社会”部分, 第4项为“超社会”部分。“历史”部分表示过去对现在的影响, “认知”部分表示粒子对自身的思考, “社会”部分表示粒子与组内最优粒子的比较和模仿, “超社会”部分表示粒子与总的粒子群体最优值的比较和模仿。这样, 粒子可以获得更丰富的信息, 且局部信息和全局信息能够得到更加充分的利用, 粒子间的信息共享和合作也变得更加充分, 借此来更新粒子自身的位置。
3 数值试验
对于集装箱装箱问题, 物体和集装箱的形状会有多样, 本节数值试验研究的是三维空间中长方体的物体装入到长方体的集装箱中的情形, 即在三维欧氏空间中, 给定一个长方体容器和有限个待放长方体, 要求将这些长方体尽可能多地装入容器中, 使得容器剩余的空闲空间最小, 即容器的空间利用率最大。长方体在放入时要求满足以下三个条件:①完全在容器内, 不与容器的壁相嵌;②不与任一已放入的长方体相嵌;③长方体的棱与容器的某条棱平行, 即垂直放入长方体。
采用HFLPSO算法解决集装箱装载问题, 步骤如下:
Step 1随机生成m×n个箱子种类装箱序列;
Step 2利用三空间分割法计算每个种类装箱序列对应的集装箱空间利用率, 然后按照空间利用率由大到小的顺序进行排序, 选出种群内最优种类装箱序列g'best;
Step 3按照混合蛙跳算法的分组方式将种类装箱序列分为m组, 每组n个种类装箱序列。则第i组种类装箱序列为{xi, xm+i, x2m+i, …, x (j-1) m+i}, i∈[1, m], j∈[1, n];
Step 4将每个种类装箱序列对应的利用率与其自身历史最优种类装箱序列对应的空间利用率作比较, 如更高, 则更新自身历史最优种类装箱序列pbest, 否则, 保持pbest不变;
Step 5选出组内最优种类装箱序列gbest, 第i组种类装箱序列中的最优种类装箱序列为xi;
Step 6更新每个种类装箱序列, 在各小组内按照空间利用率由大到小的顺序对种类装箱序列进行排序, 然后进入下一次迭代, 转到Step 5;
Step 7达到组内迭代次数后, 得到了一组新的种类装箱序列, 再重新分组, 转到Step 2;
Step 8达到分组次数后, 存盘退出。
文献[14]给出15个LN算例, 本节应用HFLP-SO算法计算了其中6个, 这6个LN算例具体数据见文献[15], 计算结果见表1和图2。试验过程中取ω=1, c1=c3=2, c2=0.8;粒子群分为5组, 每组10个粒子;为了计算快速, 组内迭代次数取1, 分组次数为30;程序独立运行20次, 取最高利用率对应的解得到图2。
对于给定的集装箱R和箱子C={c1, c2, …, cn}, 集装箱R的长、宽、高分别为L、W、H, 第ci种箱子对应的长、宽、高、数量分别为li、wi、hi、ni, 则每个ci种箱子的体积为vi=li×wi×hi。由于箱子体积之和与集装箱的体积大小关系会随着问题的变化而变化, 集装箱不一定装入所有箱子, 同种箱子也不一定能全部装入集装箱中, 因此引入参数Lmax和ni_max。Lmax表示装箱结束后, 箱子在集装箱长度方向 (X方向) 占用的最远距离, 此时占用集装箱的体积为Vo=Lmax×W×H。如不作此处理, 当所有的箱子都能装入集装箱时, 集装箱的利用率将不会随着装载顺序的不同而发生改变, 永远保持固定值不变, 算法无法寻优。ni_max表示装入集装箱中第ci种箱子的最大个数, 显然有ni_max∈ (0, ni) 。有了上述定义后, 集装箱装载问题的适应度函数表示为
式 (5) 中, 或xi=0。在求解Vs时, 集装箱R要装下所有xi=1的箱子ci。
由表1可知, 本文算法在六组测试数据中均达到了86%以上的容积利用率, 其中组别LN01、LN02、LN06、LN07相对于文献[15]来说容积利用率均得到了提高, 尤其是LN06提高了5.05%, LN08和LN09原文献没有给出相应的容积利用率, 相应的装箱图见图2所示。从图2可以得到, 小箱子都是放在大箱子的上面, 满足了稳定性的要求;箱子按照由下到上、由左到右、由后到前的规则进行装载, 这样就保证了箱子摆放比较紧凑, 剩余空间比较集中, 有利于后续箱子的装入。
由于在实际的装箱过程中, 既要给出装入集装箱中货物的种类、数量, 更重要的是要给出一个清晰的三维装箱图, 才能给人工装箱时一个直接的参考。为此, 作者在Windows XP环境下利用matlab7.10.0 (R2010a) 中的用户图形界面 (GUI) 设计了一个集装箱装载软件。该软件可实现原始数据的输入, 在计算前可对算法参数进行调整。通过计算后能得到装箱图和装载结果表, 装箱图可三维观察, 装载结果表中给出了每个货物的具体位置。该软件用于解决大量货物在单一集装箱中的装载问题, 软件的输入界面和输出界面如图3所示。
4 结论
简化粒子群算法 篇5
摘 要：针对目前配电网中存在的分布式电源规划问题，在最大化电压静态稳定性、最小化配电网损耗以及最小化全年综合费用三个方面建立了分布式电源规划的优化模型。在规划模型的基础上，采用拥挤距离排序的多目标量子粒子群优化算法（MOQPSO-CD）以及基于量子行为特性的粒子群优化算法（QPSO），来更新和维护外部存储器中的最优解，通过对全局最优最小粒子的选择引导粒子群能够对分布式电源的配置容量与接入点位置的真实Pareto最优解集进行查找，获得对多个目标参数进行合理优化。最后采用IEEE33节点的配电系统，在模拟仿真实验过程中获得了分布式电源容量配置以及介入位置的合理方案，验证了优化算法的可行性。
【关键词】分布式电源规划 Pareto最优解 配电网
分布式电源（Distributed Generation，DG）由于其在减少环境污染、节约成本、发电方式灵活、减少发电输送中的线路损耗、改善电网中的能源质量以及提高电网供电稳定性等方面具有优点，在配电网中发展迅速。然而，在配电网中加入分布式电源会使电网中原有的结构发生改变，从而导致节点电压、线路损耗与网络损耗产生了不同程度的变化。如果分布式电源注入容量与接入点位置的配置出现问题，会加大电网中线路与网络等损耗，并且会对电网供电的可靠性产生严重影响，因此，针对这一现象，对DG的容量与配置参数进行合理的优化具有重要意义。
国内外许多学者曾对DG的参数配置优化问题进行了较为深入的研究并取得了一定进展。文献[1]针对分布式电源中的地址定容问题采取了单一目标的优化方法，但是该方法在实际电网中的可行性存在问题。文献[2]采用传统的模糊理论提出将电网中具有多目标优化方案转变为只有单一目标的优化方法，并且采用遗传算法，优化了分布式电源中的容量与位置。文献[3]对于配电网中DG的容量与选址通过改进遗传算法进行优化，但是该方法存在计算时间长、算法过于复杂有时会计算得出局部的最有求解等缺点。文献[4]通过改进的自适应遗传算法，搭建了基于DG环境效益与政府关于可再生能源补贴的最小化经济模型。
在实际应用中，对于配电网中分布式电源的优化需要考虑许多变量，一般都具有比较复杂的目标函数，对其进行优化时将多个目标函数转化为单一函数非常困难，因此必须采取有效措施节约分布式电源多目标模型建立中的相关问题。本文以分布式电源的配置容量及其在配电网中的接入位置为两个切入点进行研究，建立配电网在单位年中的费用最小、电网网络以及线路损耗最低、静态电压在最优系统中的稳定性3个目标函数的分布式电源优化模型。在粒子群优化（QPSO）算法中量子行为特性的理论上加入拥挤距离排序技术，维护与更新外部存储器中的最优解，将生成分布式电源的最优配置方案问题转化为求解全局最优的领导粒子问题。最后，运用Matlab仿真软件对本文所提出的方案进行验证。配电网中DG的多目标规划模型
1.1 目标函数
1.1.1 网络损耗最小目标函数为
那么，求解出配电网中电压稳定指标的最小值minL即可知最大化静态电压的稳定裕度。
1.2 约束条件
1.2.1 等式约束
约束方程可以用潮流方程表示为：
式中，Pdi、Qdi为配电网中第 台发电机的有功、无功输出，PDGmax为分布式电源有功输出上限，PDGmin为分布式电源有功输出下限，QDGmax为分布式电源无功输出上限，QDGmin为分布式电源无功输出下限，Uimax为节点i电压上限Uimin为节点i电压下限，SDGi为配电网中拟接入的第i个DG的容量大小，SDGmax为配电网中可以接入的DG最大装机容量，Pl为线路l的传输功率。基于拥挤距离排序的粒子群优化算法
2.1 量子行为特性的粒子群优化算法
传统的粒子群优化（PSO）算法在求解方面具有不同程度的缺点，如容易陷入局部求解最优，收敛精度低等。为了防止粒子群算法进入早熟，并且尽可能加快算法的收敛减少计算时间，文献[10-11]给出了改进粒子群算法，使得具有量子行为特性的粒子群算法的实用性大大提高，在局部精度方面得到明显的提高，并且与PSO相比较仅具有一个位移更新公式。在本文中基本粒子群的集合设定为不同负荷节点处DG的输入功率，因此得到的集合为：
其中，i（i=1，2，???，P）为粒子群中的第i个粒子，j（j=1，2，???，N）为粒子在粒子群中的第j维，N为搜索空间的维数；ui，j（t）和φi，j（t）均为在区间[0，1]上随机均匀分布的数值，t为进化代数，xi（t）为在t代进化时粒子i的当前位置，pi（t）为在t代进化时粒子i的个体吸引子位置，yi（t）为在t代进化时粒子i的个体最好粒子位置，为群体在t代进化时的最好位置，C（t）为粒子在第t代进化时的平均最好位置，定义为全部粒子个体位置最好时的平均位置；α为扩张-收缩因子，是在迭代次数与除群体规模以外的唯一参数。
2.2 MOQPSO-CD算法
由于粒子群算法具有记忆特性，利用这一特性可以解耦特性粒子的解空间，求出解空间后可以适时调整控制策略，并能够通过记忆功能对当前动态进行搜索，同时具有优良的鲁棒特性和在全局范围内的搜索能力。然而，QPSO收敛的速度过快，导致了算法收敛过快，因此Pareto的解不具有多样性特点。为了寻找该问题的解决方案，本文通过利用外部存储器储存Pareto在求解过程中所产生的非劣解，从而可以较快地达到Pareto前沿。这样可以达到减少计算时间，更快获得领导粒子的目的。由于领导粒子是在所有粒子中表现最好的个体中得到的，它可以体现出整体粒子群体的认知能力，对于群体在搜索中的方向起着引导作用。为了即时更新外存储器中的非劣解，本文所采用的拥挤距离排序算法属于第2代非支配排序遗传算法（NSGA-II），通过对其进行操作，可以尽快地通过领导粒子找到Pareto的最优解。与此同时，为了使多样性在粒子种群中得到丰富，基于此算法的基础上加入高斯变革算子对粒子种群寻优过程中解的多样性进行扩充。
2.2.1 领导粒子的选择
在领导粒子选择的过程中即时对新外部存储器中粒子集进行维护更新是很有必要的。其目的在于保证粒子群的多样性，并能确保Pareto最优解集的合理分布。在此算法条件下，外部存储器中的粒子集必然会存在当前代数最优的粒子，然后通过拥挤距离值算法计算器内部粒子集中每个个体距离值，通过计算拥挤距离值的方法，将粒子集合内的个体进行量化，当出现拥挤距离值最大的粒子时，表明在目标空间中该粒子成为领导粒子可能性增加。当有两个或多个领导粒子的拥挤距离值相等时，领导粒子将会在之对应的最优粒子中随机选取。
2.2.2 拥挤距离值的计算
拥挤距离排序方法描述了在一个最优解周围分布其他最优解的密度情况。以下简单阐述了本文所用到的拥挤距离计算方法，具体实现可参考文献[13]。Gj（i）（j=1，2，3）依次表示网络损耗、年综合费用和静态电压稳定指标3个目标函数值；P为粒子群集合的大小，亦可描述可行解的数量。首先，对于存储在外外部存储器的全部最优粒子，在所有需要优化目标上的函数取值进行升序排列，然后可以得到在所有优化空间上与最优粒子相接近的其它最优粒子，然后可以计算得出在统一空间内两个优化粒子的距离；最后最优粒子的拥挤距离可以通过所有最优粒子距离的求和方式得出。以本文为例详细说明拥挤距离值的特征，逐一计算并遍历相邻最优粒子的空间距离，粒子i和相邻粒子i+1在优化目标空间的距离：
2.2.3 外部存储器更替算法
在本文中人为设定两条存储器更新规则，以便满足外部存储器中存在最优粒子的目的，规则如下：
（1）位于存储器中的粒子被新生成的粒子支配时；
（2）如若外部存储器已满，则需运用拥挤距离排序算法对其内部所有进行重新排序，根据公式（16）计算所有粒子的拥挤距离值，并且按照计算出数值的大小进行排列。
2.2.4 算法实施步骤
本文选用借鉴第2代非支配排序遗传算法的基于量子行为特性的粒子搜索解空间算法对配电网中的分布式电源进行优化配置，图1所示为算法具体流程，计算过程为：
（1）初始化起始数据，数据内容为事先已规划内容，初始化算法基本参数（粒子群的规模、粒子群的初始位置、并设定最大迭代次数），系统对分布式电源位置，以及初始粒子群数据集进行随机采样。
（2）依照步骤（1）中设置的规则，对外部存储器中的粒子进行初始化设置。
（3）需要对粒子进行排位，排位的算法由公式（1）～（4）给出，可以计算出目标函数值，同时，根据公式（16）可以计算出拥挤距离值，根据以上两个参数进行排位。“2.2.1节”的方法选出粒子群中的领导粒子，最后利用QPSO位移更新方程对每个粒子进行重置。以上计算过程将会计算采样粒子集合内任意粒子的拥挤距离值。评价其是否达到Gauss变异算法条件，若达到该算法条件，则进行Gauss变异操作（Gauss mutation operator），否则转到步骤④。
（4）对③中运用QPSO位移更新算法计算出的所有粒子进行评价，并算出所有粒子的潮流数值，将其接入位置以及配置容量用数值量化，并对比量化后的函数值，按照柏拉图最优解定律计算出个体最优粒子及外部存储器最优粒子集。与计算出的上一个最优粒子相比较，新产生的粒子群中某粒子更优，则将新出现粒子作为最优粒子；若二者不能相互支配，那么二者中任意一个将被选为最优粒子，并将其放入外部存储器，然后转步骤⑤；否则舍弃更新后的粒子并转⑥。
（5）对已进入外部存储器中的粒子，按照公式（16）对其进行计算，已达到随时更新存储器中粒子的目的。通过步骤（5）可以达到将最优粒子存入外部存储器的目的。
（6）计算进化代数，若满足终止代数，则将存储器中现有的粒子作为输出，此时输出的粒子集就是所寻找的柏拉图最优输出集；否则转步骤③。算例分析
利用本文建立的模型，对IEEE 33节点配电系统进行模拟仿真，配电网系统如图2所示，对分布式电源的位置以及其容量进行重新配置。该配电系统中，额定电压为12.66kV，有功负荷的取值为3715kW，总无功负荷的取值2300kVar，总节点数为33个，总支路数为32条（其中5条为联络开关）。配电系统基准容量设为10MVA，其中平衡节点选在0号节点，分布式电源接入比例小于30%，安装节点集合为?x1，2，???，31?y（图2中的32节点将不会接入分布式电源中，因为该节点是尾端节点，并且同变压器支路侧相连，因此不需接入）。根据文献[3]可知，在计算分布式电源时，可以将其近似看成负的PQ节点，根据经验公式，选取功率因数值为0.9。初始采样粒子群集合规模为90，进行100次迭代。
按照本文所搭建的数学模型及算法计算出分布式电源配置的柏拉图最优解，及其目标函数的空间分布，如图3所示。根据图3可知，计算出的所有解相互独立分布，每个不同解均可表示出当前条件下的配置效果。以图中所列出的解
1、解2及解3为例，说明不同情况下的DG配置结果。解1情况下电压稳定指标大于0.02，相比其他两种情况最不稳定，网络损耗为80kW，损耗过大，但是年综合用最小；解3和解2相比较而言，解3在网络损耗和电压稳定性方面要优于解2，然而解3在年综合费方面是三种情况中最大的；对于解2来说，无论是年综合费用或者网络损耗以及电压稳定性指标这三个参数指标适均介于解1和解3之间，因此，考虑综合因素以解2最好。表1所示为解
1、解2和解3的DG配置方案，3个解分别与3个方案对应。
通过对比表1中的方案配置可以看出，不同DG配置方案会对年综合费用、网损和电压稳定性产生影响。在对电源在辐射线路中放置位置的分析后发现，放置位置越靠前，线路潮流受到的影响就越小。根据表1配置DG方案接入配电网，配电网络损耗将会有一定幅度下降，同时电压稳定性指标也会达到满意的效果，按照该配置方案规划，最为突出的优点是电网网络损耗方面，按照方案3配置后，电网网络损耗下降了80%。
结语
以减少电网网络损耗及年综合费用为优化目标，同时兼顾静态电压稳定性为原则，建立了DG规划的模型，在计算方面选取具有量子行为特性的粒子群优化算法（QPSO），以及基于拥挤距离排序的多目标量子粒子群优化算法（MOQPSO-CD），同时采用模拟仿真对33节点配电系统进行优化，得出了基于DG配置的Pareto最优解集，由此实现了对DG优化规划的目的。并得出以下结论：为了尽可能的降低电网损耗，同时提高电压稳定性，需要将DG配置在主变电站远端位置，即馈线末端，此时DG配置收益最高。
参考文献
[1]QIAN Ke-jun，ZHOU CHENG-KE，ALLAN MALCOLM，et al.Effect of load models on assessment of energy losses in distributed generation planning[J].Electrical Power and Energy Systems，2011，33：1243-1250.[2]陈海焱，陈金富，杨雄平，等.配电网中计及短路电流约束的分布式发电规划[J].电力系统自动化，2006，30（21）：16-21.[3]邱晓燕，夏莉丽，李兴源.智能电网中分布式电源的规划[J].电网技术，2010，34（4）：7-10.[4]李德泉，徐建政，罗永.含分布式电源的配电网扩展规划[J].电力系统及其自动化学报，2012，（5）.[5]孙俊.量子行为粒子群优化算法研究[D].无锡：江南大学信息工程学院，2009.[6]武晓朦，刘建，毕棚翔.配电网电压稳定性研究[J].电网技术，2006，30（24）：31-35.[7]KENNEDY J，EBERHART R C.Particle swarm optimization[C].IEEE IntConf of Neural Networks.Perth，1995：1942-1948.[8]ABGELINE P J.Using selection to improve particleswarm optimization[C]/Proc IEEE CongrEvolComput.Anchorage.AK.USA"IEEE Service Center，1998：84-89.[9]MIRANDA V，FONSECA N New evolutionary particle swarm algorithm applied to voltage control[C].Proc 14th Power SystComputConf.Spain：IEEE Service Center，2002：1865-1873.[10]LIjun-jun，WANGxi-huai.Amodified particle swarm optimization algorithm[J].Intelligent Control and Automation，2004，1：354-356.[11]候云鹤，鲁丽娟，熊信艮，等.改进粒子群算法及其在电力系统经济负荷分配中的应用[J].中国电机工程学报，2004，24（7）：95-100.[12]DEB K，PRATAP A，AGRAWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.[13]张君则，艾欣.基于粒子群算法的多类型分布式电源并网位置与运行出力综合优化算法[J].电网技术，2014，38（12）：3372-3377.[14]刘幸.基于量子粒子群算法的分布式电源多目标优化[D].北京：华北电力大学，2012.[15]ROUHANI A，HOSSEINI S H，RAOOFAT M.Composite generation and transmission expansion planning considering distributed generation[J].International Journal of Electrical Power & Energy Systems，2014，62（11）：792-805.[16]叶德意，何正友，臧天磊.基于自适应变异粒子群算法的分布式电源选址与容量确定[J].电网技术，2011，（06）：155-160.[17]BJELIC I B，CIRIC R M.Optimal distributed generation planning at a local level-A review of Serbian renewable energy development[J].Renewable & Sustainable Energy Reviews，2014，39（6）：79-86.[18]朱艳伟，石新春，但扬清，等.粒子群优化算法在光伏阵列多峰最大功率点跟踪中的应用[J].中国电机工程学报，2012，32（4）.[19]黄平.粒子群算法改进及其在电力系统的应用[D].广州：华南理工大学，2012.[20]施展，陈庆伟.基于QPSO和拥挤距离排序的多目标量子粒子群优化算法[J].控制与决策，2011，26（4）：540-547.[21]ZHANG L G，ZUO H.Pareto optimal solution analysis of convex multi-objective programming problem[J].Journal of Networks，2013（02）.[22]李中凯，李艾民，朱真才.拥挤距离排序的多目标文化粒子群优化算法[J].控制与决策，2012，27（09）：1406-1410.[23]慕彩红.协同进化数值优化算法及其应用研究[D].西安：西安电子科技大学，2010.作者单位
简化粒子群算法 篇6
关键词：计算机神经网络；粒子群优化算法；应用
中图分类号：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-），男，河南人，讲师，研究方向：云计算，数据挖掘，通信技术。
粒子群算法的改进算法研究 篇7
基本PSO算法虽然比较简单,实现相对容易,不需要调整太多的参数,同时算法的早期收敛速度也比较快；但算法后期会受到随机振荡现象的影响,导致算法搜索到全局最优解的时间比较长,减慢了收敛速度;并且在一定程度上使其局部搜索能力表现较差,极易陷入局部最小值,精度降低,易发散[2]。针对基本粒子群算法的收敛精度问题,该文提出了一种新的改进粒子群优化算法—LPSO。
1 改进PSO算法研究
1.1 基本PSO算法
随机初始一群粒子,每个粒子均不包括体积和质量信息,将每个粒子都看作为优化过程中的一个可行解,粒子的好坏通过一个事先设定好的适应度函数来进行确定。优化过程中,每个粒子都将在可行解空间中进行运动,由一个速度变量决定其方向和距离。通常情况下粒子将追随当前的最优粒子,并经过不断的迭代搜索最后得到全局最优解。在每一次迭代过程中,粒子都将会跟踪两个最优值:一个是粒子本身迄今为止找到的最优解,即局部最优解;另一个是整个粒子群体到目前为止找到的最优解,即全局最优解[3]。
假设一个由n个粒子组成的粒子种群在d维的搜索空间中按照一定的速度进行飞行。粒子i在t时刻的状态属性设置如下:
位置:
Xi(t)=(xi1(t),xi2(t),…,xid(t)
xid (t)∈[Ld,Ud]
其中Ld为搜索空间的下限,Ud为搜索空间的上限;
速度:
其中:vmin为最小速度,vmax为最大速度;
个体最优值位置:
Pi(t)=(pit(t),pi2(t),…,piD(t))
全局最优值位置:
pg(t)=(Pgt(t)pg2(t)…,pgD(t))其中:1≤d,1≤i≤M。
那么粒子在t+1时刻的位置可以通过下式来得到:
式中,r1、r2都为均匀分布在(0,1)区间的随机数;c1、c2是学习因子,一般取2。
基本的PSO算法尽管比较简单,实现也相对容易,并且不需要调整太多的参数,早期收敛速度快;但同时也存在其局限性,由于粒子在移动时没有选择性,即使下一个粒子位置的评价函数值较差,粒子还是利用逐个位置来代替当前位置,这样就使得粒子很容易跳出最优解附近的某一邻域,因此在一定程度上表现出较差的局部搜索能力,比较容易陷入局部最小值,降低了精度,也易发散[4]。鉴于基本粒子群算法还存在一些不足之处,该文提出了一种新的改进的粒子群算法,下面将对其做具体介绍。
1.2 粒子群算法的改进算法研究
该文所提出的改进的粒子群算法主要是在基本粒子群算法基础上,对以下几个方面做了改进:
(1)惯性权重模型。
由于惯性权重w较大时,算法具有较强的全局搜索能力;w较小时,则算法局部搜索能力较强。所以本文中采用线性模型,随着迭代次数的增加,将w由初始的0.9线性递减至0.4,以达到期望的优化目的。权重函数w由下式确定:
式中Wmax为最大惯性权重,一般取0.9,wmin为最小惯性权重,一般取0.4。
(2)学习因子模型。
学习因子c1、c2表示粒子向个体最优值和全局最优值进化的随机加速权值。当c1、c2都等于0时,粒子会按照当前速度进行飞行,直到运动至边界处。当学习因子较小时,粒子将会在远离最优值区域内发生振荡现象;较大的学习因子则可以促使粒子快速向最优解区域内移动。所以该文中采用自适应模型,如下式所示:
式中cmax为最大学习因子,Cmin为最小学习因子,MaxDT为最大迭代次数,t为当前迭代次数。
(3)粒子位置更新方程的改进。
基本PSO算法前期,精度较低,易发散。如果参数较大的话,在后期收敛速度会变慢,从而无法继续进行优化。在进化规划中,算法中若带有高斯变异和柯西变异算子时,算法都会取得较好的收敛效果,因此,该文中对个体最优解加入了高斯算子,每次找到一个个体最优值时,将在其周围利用高斯算子进行局部搜索。这样不仅可以提高算法前期的收敛精度,还可以改进算法后期的收敛速度,可以有效避免后期在最优解附近发生振荡。所以该文中的粒子位置通过下式来进行更新:
是均值为0,方差为1的高斯变量,fmin是n个粒子中的最小适应函数值,即当前最优值,β是尺度因子,通常取0.6。
(4)早熟收敛的改进策略。
PSO运行过程中,如果其中一个粒子发现一个当前最优位置,此时其他的粒子会快速向其聚集。如果该最优位置是个局部极值点,或者两个粒子均处于局部极值点,此时整个粒子种群将不可能在解空间内重新进行寻优,导致算法失去了搜索能力,陷入局部最优,这一现象就称为早熟收敛。该文对会与当前最优解重叠的粒子加入交叉操作过程,这样可以使该粒子状态重新更新,寻找新的搜索区域,从而跳出函数的局部极值点。首先给定一个阈值,如果其中一个粒子与当前最优粒子的位置距离小于之前设定的阈值,则对其进行交叉操作。具体的交叉公式如下:
式中x是粒子位置,x为粒子速度,pi是介于[0,1]之间的一个随机数,x'ibest为局部最优解。
2 仿真实验
(1)粒子群算法性能比较仿真。
为了验证改进粒子群算法的有效性,该文中选取标准的测试函数,分别利用基本粒子群算法和改进后的粒子群算法对函数进行优化,寻找适应度函数的最优解。
测试函数:Griewank函数
式(6)中的X表示一个粒子,xi为粒子的每个分量,d为每个粒子的维数[3]。
首先在[-10,10]的区间内均匀生成两组数,作为初始的粒子种群,数的个数为生成粒子的个数,每个粒子都是二维的,则该函数的三维图形如图1所示。由图可以看出:该函数存在多个局部极值点,但只存在唯一的全局最优点在(0,0)处。
该文在进行仿真实验过程中的相关参数设置如下:学习因子cimin=2,cimax=5,粒子个数n=100,粒子维数D=10,粒子位置范围xi∈[-100,100],最大迭代次数选取为100次,交叉操作过程中的阈值g取0.5,尺度因子β取0.6。仿真结果如下,图2中描述的是函数的最优适应值与迭代次数之间的关系。
由上述仿真结果可以看出,改进的粒子群算法(LPSO)较基本粒子群算法,不管是收敛精度还是循环迭代次数,都有所提高,验证了改进算法的有效性。
3 结语
该文在基本PSO的基础上,对参数的选择进行了调整,同时引入高斯算子及交叉操作过程。仿真结果证明,改进后的算法收敛效果较好。
参考文献
[1]张必兰.改进的粒子群优化算法及应用研究[D].重庆:重庆大学,2007.
[2]李丽,牛奔.粒子群优化算法[M].北京:冶金工业出版社,2009.
[3]吴进华,吴华丽,周仕.基于模拟退火的粒子群算法[J].仪器仪表学报,2008.
[4]Yumao Li.Particle swarm optimization algorithm research and improvement[D].Northwestern university master degree thesis,2009.
[5]任小波,杨忠秀.一种动态扩散粒子群算法[D].银川:宁夏工程学院,2010.
多种群粒子群分层进化优化算法 篇8
粒子群优化算法 (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
基于粒子群算法的改进遗传算法 篇9
遗传算法是根据自然界的“物竞天择,适者生存”现象二提出的一种随机搜索算法。1975年,Holland教授在他的专著《Adaptation in Natural and Artificial Systems》[2]中,首次系统地提出了遗传算法(GA or Genetic Algorithm)的基本原理,标志着遗传算法的诞生。该算法将优化问题看作是自然界中生物进化过程,通过模拟大自然中生物进化过程中的遗传规律,来达到寻优的目的。
进入90年代,遗传算法作为一种新的全局优化搜索方法,适用于处理传统搜索方法难以解决的复杂的和非线性的问题、组合优化、机器学习、自适应控制和人工生命等方面,都得到了极为广泛的应用[3,4,5,6,7,8],是21世纪有关智能计算的关键技术之一。
1995年Eberhart博士和Kennedy博士提出了粒子群优化算法。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的响应,并且在解决某些实际问题时,展示了其优越性。粒子群优化算法是一种新的进化算法,与遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的优劣。但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”和“变异”操作,它通过追随当前搜索到的最优值来寻找全局最优。
根据坐标的可平移性,从整体上看,我们可以假设优化问题的最优解在整个解空间服从均匀分布。按照最大熵原则,最优解应该更加趋向于较优解。为了能够更快地搜索到最优解,本文将粒子群算法和遗传算法相结合。得到了一个应用更加广泛的改进遗传算法。
1 初始化染色体
在遗传算法中,初始染色体是随机产生的,最优化问题的解转换成染色体一般有两种表示方法:二进制向量或浮点向量。使用二进制向量作为一个染色体来表示决策变量的真实值,向量的长度依赖于要求的精度,但使用二进制代码的必要性已经受到了一些批评。在求解复杂优化问题时,二进制向量表示结构有时不太方便。
另一种表示方法是用浮点向量,每一个染色体有一个浮点向量表示,其长度与解向量相同。用向量x=(x1,x2,⋅⋅⋅,xn)表示最优解问题的解,其中是维数。则相应的染色体是V=(x 1,x2,⋅⋅⋅,xn)。
对于每一个染色体V,我们选取已知的可行解做随机的扰动,这样便得到一个染色体V=(x 1,x2,⋅⋅⋅,xM)。如果如此得到的染色体可行,即说明满足约束条件。对于每一个染色体V在约束条件中,我们可以得出可行集中的一个内点,记为0V。我们定义一个足够大的数M,以保证遗传操作遍及整个可行集。当然M的选取依赖于不同的决策问题。在RM中,首先随机选择一个方向d,如果V0+M⋅d满足不等式约束,则将V=V0+M⋅d作为一个染色体,否则,置M为0到M之间的随机数,直到V0+M⋅d可行为止。由于V0是内点,所以在有限步内,总是可以找到满足不等式约束的可行解。重复以上过程popsize次,从而产生popsize个初始染色体V1,V 2,⋅⋅⋅,Vpopsize,其中popsize为种群规模。
2 适应函数
比较常用的评价函数是基于序的评价函数,我们将一代种群的染色体按照从好到差的顺序排列成{V 1,V 2,⋅⋅⋅,Vpopsize}。在极大化问题中,这个顺序就是指对应目标函数值由大到小排列染色体,在极小化问题中则正好相反。为了得到每个染色体的适应度,我们根据这个顺序给出如下的评价函数,
其中a∈(0,1)是一个事先给定的数。可以看到,机会越大的解适应值也越大。
3 选择过程
选择过程是以popsize个扇区的旋转赌轮为基础的。赌轮上的刻度是按各染色体的适应值来划分的,染色体的适应值越大,则其在赌轮上所占的面积就越大,该染色体被选中的概率也就越大,每旋转一次都会为新的种群选择一个染色体。但是为了避免早熟现象,在这里,我们结合粒子群算法的优越性,首先选出最佳染色体0V。然后,令0q=0,对于各染色体Vi,令其累次概率为
我们在区间中随机产生一个实数。如果满足,则选择。重复上述过程,直至生成个新的染色体终止,于是我们得到一个新的种群。
4 交叉算子
首先给定交叉概率,则每次种群中平均有cp*popsize个染色体进行交叉操作。对各染色体我们随机产生[0,1]上的一个随机数p,若p
其中随机数c∈[0,1]。经过上述交叉操作,我们可以得到一个子代染色体。最后,我们可以用约束条件对它进行可行性检验。若该子代染色体满足约束条件,则用子代染色体替代原染色体,否则,
重新检验该子代染色体的可行性,若还是不满足越深条件,则重新产生新的随机数,再次进行交叉操作,直到新的可行染色体出现或者达到最大交叉上限,则停止。这样,我们几可以得到popsize个新的染色体Vi,i=1,2,⋅⋅⋅,popsize。
5 变异算子
变异操作是产生新染色体的辅助方法,但它决定了遗传算法的全局搜索能力,可以保证群体的多样性,防止早熟现象。同样给定一个变异概率Pm,并从区间上随机产生p∈(0,1),若p
6 遗传算法步骤
步骤1:根据约束条件随机产生popsize个染色体,即种群。
步骤2:按照转盘赌原则,随机选取一个最佳父代染色体和其它popsize个父代染色体作为交叉种群(交叉种群不能包含最佳父代染色体)。
步骤3:对于每个父代染色体都以概率cp与最佳染色体进行交叉运算,即随机生成r∈(0,1),若r
步骤4:将所新得到的各子代染色体以概率mP进行变异操作,即随机生成r∈(0,1),若r
步骤5:更新父代染色体,即在子代染色体中,择优选取较好的染色体代替原来的父代染色体,作为下次交叉变异的父代染色体,并计算各自相应的适应值。
步骤6:重复步骤2—步骤5知道达到精度要求,或者达到约定的最大循环次数。
7 数值实验
7.1 实验模型
例1现运用遗传算法求解以下最大值问题,
对于这个问题,我们可以直接将解(x1,x2,x3)是为遗传迭代的染色体。显然染色体属于集合内
7.2 Matlab实验结果
运用Matlab软件来实现遗传算法,并设定相应的各参数如下:
最大交叉、最大变异次数、最大变异半径以及最大遗传迭代次数均设为1 000。利用Matlab7.6得到结果如下:
遗传迭代次数:i=135
最佳染色体:(x1,x2,x3)=(0.6332,0.3990,0.3058)
最优值:1.9805
显然这一结果要优于Liu[9]给出的遗传迭代400次的结果:
最佳染色体:(x1,x2,x3)=(0.636,0.395,0.307)
最优值:1.980
结果误差曲线图:2.3
其中横坐标为遗传迭代次数,纵坐标为每次迭代的误差取值。
8 结论3
本文按照最大熵原理,用粒子群算法代替了遗传算法的交叉算子,得到了一个应用更加广泛的改进遗传算法。最后的数值实验结果也表明,改进后的算法不管是在收敛速度还是精度上都明显优于原有的算法,说明该算法确实是有效可行的。实际上本文给出了一种判断算法优越性的新思路。
摘要：本文假设优化问题的最优解在整个解空间中服从均匀分布,并在此基础上,按照最大熵原则,最优解应该更加趋向于较优解。为了能够更快地搜索到最优解,用粒子群算法[1]代替了遗传算法的交叉算子。得到了一个应用更加广泛的改进遗传算法。最后的数值实验结果表明,改进后的算法不管是在收敛速度还是精度上都明显优于原有的算法,说明改进后的算法确实是有效可行的。
关键词：遗传算法,交叉算子,变异算子
参考文献
[1]胡辉.粒子群优化算法的VisualC++实现研究[J].科技广场,2008(5).
[2]Goldberg D E.Genetic Algorithms in Search,OptimizationandMachineLearning[M].MA:Addison-Wesley,1989.
[3]KozaJR.GeneticProgramming[M].Cambridge,MA:MIT Press,1992.
[4]KozaJR.GeneticProgrammingII[M].Cambridge,MA:MITPress,1994.
[5]Michalewicz Z.Genetic Algorithms+Data Structures=Evolution Programs[M].New York:Springer-Verlag,1996.
[6]YoshitomiY,IkemoueH,TakabaT.Geneticalgorithm in uncertain environments for solving stochastic programmingproblem[J].JournaloftheOperationsResearch SocietyofJapan,2000,43(2):266-290.
[7]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999.
[8]ZadehLA.Fuzzysetsasabasisforatheoryof possibility[J].FuzzySetsandSystems,1978,1:3-28.
粒子群算法改进策略研究 篇10
1基本粒子群算法
PSO中, 每个优化问题的潜在解都是搜索空间中的一只鸟, 称之为粒子。所有的粒子都有一个由被优化的函数决定的适值 (fitness value) , 每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索[1]。
PSO初始化为一群随机粒子 (随机解) , 然后通过迭代找到最优解。在每一次迭代中, 粒子通过跟踪两个极值来更新自己;第一个就是粒子本身所找到的最优解, 这个解称为个体极值;另一个极值是整个种群目前找到的最优解, 这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居, 那么在所有邻居中的极值就是局部极值。
假设在一个D维的目标搜索空间中, 有N个粒子组成一个群落, 其中第i个粒子表示为一个D维的向量:
Xi= (xi1, xi2, …, xiD) , i=1, 2, …, N。
第i个粒子的“飞行 ”速度也是一个维的向量, 记为:
Vi= (vi1, vi2, …, viD) , i=1, 2, …, N。
第i个粒子迄今为止搜索到的最优位置称为个体极值, 记为:
Pbest= (pi1, pi2, …, piD) , i=1, 2, …, N。
整个粒子群迄今为止搜索到的最优位置为全局极值, 记为:
gbest= (pg1, pg2, …, pgD)
在找到这两个最优值时, 粒子根据如下的公式 (1) 和 (2) 来更新自己的速度和位置:
vid=w×vid+c1r1 (pid-xid) +c2r2 (pgd-xid) (1)
xid=xid+vid (2)
其中:c1和c2为学习因子, 也称加速常数 (acceleration constant) , r1和r2为[0, 1]范围内的均匀随机数。式 (1) 右边由三部分组成, 第一部分为“惯性 (inertia) ”或“动量 (momentum) ”部分, 反映了粒子的运动“习惯 (habit) ”, 代表粒子有维持自己先前速度的趋势;第二部分为“认知 (cognition) ”部分, 反映了粒子对自身历史经验的记忆 (memory) 或回忆 (remembrance) , 代表粒子有向自身历史最佳位置逼近的趋势;第三部分为“社会 (social) ”部分, 反映了粒子间协同合作与知识共享的群体历史经验, 代表粒子有向群体或邻域历史最佳位置逼近的趋势, 根据经验, 通常c1=c2=2。i=1, 2, …, D。vid是粒子的速度, vid∈[-vmax, vmax], vmax是常数, 由用户设定用来限制粒子的速度。r1和r2是介于之间的随机数[2,5]。
算法的流程如图1所示。
1) 初始化粒子群, 包括群体规模N, 每个粒子的位置xi和速度Vi;
2) 计算每个粒子的适应度值Fit[i];
3) 对每个粒子, 用它的适应度值Fit[i]和个体极值pbest (i) 比较, 如果Fit[i]>pbest (i) , 则用Fit[i]替换掉pbest (i) ;
4) 对每个粒子, 用它的适应度值Fit[i]和全局极值gbest比较, 如果Fit[i]>pbest (i) , 则用Fit[i]替gbest;
5) 根据公式 (1) , (2) 更新粒子的速度vi和位置xi;
6) 如果满足结束条件 (误差足够好或到达最大循环次数) 退出, 否则返回2) 。
2粒子群算法的改进分析
对粒子群优化算法改进之前必须要知道有哪些改进方向, 从基本的算法流程来看, 初始化过程可以进行处理, 研究也表明, 初始化过程的确会对性能产生一定的影响[2]。接着是适应值的计算这一过程, 适应值是适应函数决定的, 而这是根据实际情况而定的, 没法做改进。接下来的最优值的处理过程, 可以打破基本粒子群原有的方式, 比如运用遗传算法里面的选择方法、变异或是杂交方法改进粒子群优化算法, 这种改进方式, 我们称之为混合策略。Angeline引入了具有明显选择机制的改进粒子群算法[3]。粒子群优化算法的核心也就是更新公式, 对于数学公式的改进是大多数研究者所热衷的, Clerc提出了收缩因子的概念[4], 这种方法描述了一种选择w, c1, c2的方法, 以确保算法收敛, 属于带有惯性权重的改进。Kennedy指出, gbest模型虽然具有较快的收敛速度, 但更容易陷入局部极值。为了克服gbest全局模型的缺点, 研究人员采用每个粒子仅在一定的邻域内进行信息交换, 提出各种gbest局部模型[5]。由此可见, 在基本的粒子群优化算法的基础上进行改进, 可研究的方向有, 带有惯性权重方面的改进, 初始化方面的改进, 邻域拓扑方面的改进, 以及混合策略方面的改进。
3带惯性权重的改进
公式 (1) 中, 建议w的取值范围为[0, 1.4], 但实验结果表明当w取[0.8, 1.2]时, 算法收敛速度更快, 而当w>1.2时, 算法则较多地陷入局部极值。较大的w有较好的全局收敛能力, 较小的w则有较强的局部收敛能力。因此, 随着迭代次数的增加, 惯性权重w应不断减少, 从而使得粒子群算法在初期具有较强的全局收敛能力, 而晚期具有较强的局部收敛能力。此时粒子群算法称为惯性权重线性递减粒子群一般情况下, 将w的初始值设置为0.9, 然后按照迭代次数线性递减至0.4[6], 在粒子群算法领域, 这种改进是很常见的, 其处理方式如下:
undefined
(t为当前迭代次数, MaxNumber为最大代数) (3)
公式 (3) 是线性调整的, 当然也有非线性调整的, 像基于模糊系统的惯性权重动态调整, 该模糊系统需要两个输入参数:当前惯性权重w和当前最好性能评价值 (CBPE) ;输出为惯性权重w的改变量。由于不同的问题有不同范围的性能评价值, 因此需要对CBPE 进行如下的规范化, 处理方式如下:
undefined
NCBPE是规范化后的评价值, CBPEmin, CBPEmax依问题而定, 且需实现得知或可估计。
Clerc在式 (1) 更新公式的基础上提出了收缩因子的概念, 该方法描述了一种选择w, c1和c2的值的方法, 以确保算法收敛。通过正确选择这些参数, 就没有必要将vid的值限制在[-vmax, vmax]之中, 改进了的速度公式为:
Vundefined=χ·[Vundefined+c1·r1· (Pundefined-Xundefined) +c2·r2· (Pundefined-Xundefined) ] (5)
在式 (5) 中undefined
式 (6) 描述的是收敛因子, φ=c1+c2>4, 通常φ的值为4.1, 则χ=0.729, 实验结果表明, 与使用惯性权重的粒子群优化算法相比, 使用收敛因子的粒子群优化算法有更快的收敛速度。
4改进学习因子
粒子群算法中的粒子在搜索过程中, 希望搜索的前阶段速度大, 达到对整个空间的搜索不至于陷于局部。对学习因子进行改进在搜索的前期c1的取值较大, c2取值较小, 目的是让粒子多向自己的最优pbest学习, 少向社会最优gbest学习, 使粒子的全局搜索能力增强。而在后阶段则相反, c1取较小值, c2取较大值, 使粒子向社会最优位置gbest的局部靠拢, 使得局部搜索增强[7]。基于这种思想, 对c1和c2做如下处理:
undefined
5粒子群初始化
研究表明, 粒子群初始化对算法性能产生一定影响[7]。为了初始种群尽可能均匀覆盖整个搜索空间, 提高全局搜索能力, Richard 和Ventura[8]提出了基于centroidal voronoi tessellations (CVTs) 的种群初始化方法;薛明志等[9]采用正交设计方法对种群进行初始化;Campana等[10]将标准PSO迭代公式改写成线性动态系统, 并基于此研究粒子群的初始位置, 使它们具有正交的运动轨迹;文献[2]认为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差, 并另外比较了3种初始化分布方法。
6邻域拓扑
在标准粒子群优化算法中, 粒子群跟踪两个极值, 自身极值pbest和群体极值gbest, 称为全局版本, 基本粒子群算法属于全局版本。另一种为局部版本, 指粒子除了追随自身极值pbest, 不追踪全局极值gbest, 而是追随拓扑紧邻粒子当中的极值lbest。在局部版本中, 每个粒子需记录自己和它邻居的最优值, 而不需要记录整个群体的最优值。Kennedy指出, 全局模型虽然具有较快的收敛速度, 但更容易陷入局部极值。为了克服全局模型的缺点, 研究人员采用每个粒子仅在一定的邻域内进行信息交换, 提出各种局部模型[11]。根据现有的研究成果, 本文将邻域分为空间邻域 (spatial neighborhood) 、性能空间 (performance space) 邻域和社会关系邻域 (sociometric neighborhood) 。空间邻域直接在搜索空间按粒子间的距离 (如欧式距离) 进行划分, 如Suganthan[12]引入一个时变的欧式空间邻域算子:在搜索初始阶段, 将邻域定义为每个粒子自身;随着迭代次数的增加, 将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标 (如适应度、目标函数值) 划分的邻域。
7混合策略
混合粒子群算法就是将其他算法或传统优化算法或是其他技术应用到粒子群算法中, 用于提高粒子多样性、增强粒子的全局搜索能力, 或者提高粒子局部开发能力、增强收敛速度与精度。这种结合的途径通常有两种:一是利用其他优化技术自适应调整搜索因子、惯性权值、加速常数等;二是将粒子群算法与其他进化算法操作算子或是其他技术结合。
目前有很多研究混合策略的粒子群算法, 将蚂蚁算法与粒子群结合用于求解离散优化问题;Robinson等和Juang将GA与粒子群结合分别用于天线优化设计和递归神经网络设计;将种群动态划分成多个子种群, 再对不同的子种群利用粒子群或GA或爬山法进行独立进化;Naka等将GA中的选择操作引入到粒子群中, 按一定选择率复制较优个体;Angeline则将锦标赛选择引入粒子群 算法, 根据个体当前位置的适应度, 将每一个个体与其他若干个个体相比较, 然后依据比较结果对整个群体进行排序, 用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度, 同时保留每个个体所记忆的个体最好位置;El-Dib等对粒子位置和速度进行交叉操作;Higashi将高斯变异引入到粒子群中;Miranda等则使用了变异、选择和繁殖多种操作同时自适应确定速度更新公式中的邻域最佳位置以及惯性权值和加速常数;Zhang等利用差分进化 (DE) 操作选择速度更新公式中的粒子最佳位置;而Kannan等则利用DE来优化粒子群的惯性权值和加速常数。
8结束语
目前, 大多数研究者在粒子群算法方面做了这样或那样的改进, 但是对于粒子群算法的改进的总体方向没有一个全面的分析, 对粒子群的各方面的可改进的方向做了整体的分析和总结。会对粒子群算法的改进有明确的认识, 更加明确如何改进粒子群算法。
参考文献
[1]dos Santos Coelho L, Herrera B M.Fuzzy identification based on a chaotic particle swarm optimization approach applied to a nonlinear yo-yo motion system[J].IEEE Trans.Ind.Electron, 2007, 54 (6) :3234-3245.
[2]Clerc M.Initialisations for particle swarm optimization.Online at http://clerc.maurice.free.fr/pso/, 2008.
[3]Kennedy J.The particle swarm:Social adaptation of knowledge[A].in:Proc.IEEE Int.Conf.Evol.Comput[C].1997:303-308.
[4]Clerc M.Stagnation analysis in particle swarm optimiza-tion or what happens when nothing happens.Online at ht-tp://clerc.maurice.free.fr/pso/.
[5]Kennedy J.Small worlds and mega-minds:Effects of neighborhood topology on particle swarm performance[A].in:Proc.IEEE Congr.Evol.Comput[C].1999 (3) :1931-1938.
[6]王维博, 林川, 郑永康.粒子群算法中的参数的实验分析[J].西华大学学报, 2008, 27 (1) :77-80.
[7]徐生兵, 夏文杰, 代安定.一种改进学习因子的粒子群算法[J].信息安全与技术, 2007, 19 (7) :17-19.
[8]Richards M, Ventura D.Choosing a starting configuration for particle swarm optimization[A].in:Proc.IEEE Int.Joint.Conf.Neural Network.[C], 2004 (3) :2309-2312.
[9]薛明志, 左秀会, 钟伟才, 等.正交微粒群算法[J].系统仿真学报, 2005, 17 (12) :2908-2911.
[10]Campana E F, Fasano G, Pinto A.Dynamic system analy-sis and initial particles position in particle swarm optimi-zation[A].in:Proc.IEEE Swarm Intell.Symp[C].2006:202209.
[11]Kennedy J.Small worlds and mega-minds:Effects of neighborhood topology on particle swarm performance[A].in:Proc.IEEE Congr.Evol.Comput[C].1999 (3) :1931-1938.
改进粒子群算法的应用研究 篇11
Kennedy和Eberhart于1995年提出了粒子群优化算法 (Particle Swarm Optimization, PSO) [1]。由于该算法描述简单、需要较少的调整参数, 具有较快的收敛速度等优点, 目前己在自适应控制、组合优化、模式识别、管理决策等领域得到了大范围的应用, 被证明是解决全局优化问题的有效方法之一。
随着研究的不断深入, 学者们也发现了粒子群算法在优化过程中存在的一些弊病。粒子群算法参数的选择对优化的结果会产生很大的影响, 参数选择的合适与否会导致收敛速度和精度不同。针对上面提出的问题, 学者们也作出了很多改进的措施, 通过实验表明, 改进后的算法大多取得了理想的效果, 随着对理论的深入研究以及工程领域的不断实践, 显示出了自身无比广阔的应用前景和研究价值[2]。
2 粒子群算法基本原理
标准粒子群优化算法的理论产生于对动物群体智能觅食行为的模拟。对于鸟群的捕食行为, 我们可以设置如下场面:一个鸟群在一个森林里随机地寻找食物, 但是这个森林里只有一个地方有食物。没有一个鸟知道这个有食物的地方的具体位置, 但是它们知道他们的位置与有食物地点之间的距离。怎么能找到这个地方?最简单的办法就是找到哪只鸟离这个有食物地点的距离最小。粒子群优化算法就是从这种问题中得到启发并且应用到优化问题中。
在粒子群优化算法中, 每一个需要优化的问题的可能解都是解空间中的一个“粒子”。每个粒子都会对应一个适应值, 这个适应值由适应函数计算得到, 适应值的优劣决定了粒子位置的好坏。寻优过程中每个粒子都有两个描述粒子状态的量, 即寻优的速度和当前的位置。每个粒子都会不断的去追踪当前位置最优的粒子, 从而不断地向最优位置移动。
在解空间中初始化一个具有M个粒子的粒子群体。在优化的过程中, 群中每个粒子的状态都通过两个N维向量表示出来, 即当前的位置和移动的速度, 记作:X= (X11, X12, …, X1M) 和V1= (V11, V12, …, V1M) 。前者为粒子自身到目前为止经过的最好位置, 表示粒子自身的搜索经验, 即个体极值Pk1, 记为P1= (P11, P12, …P1M) ;后者为当前所有粒子经过的最好位置, 表示其他粒子的搜索经验, 即全局极值PK, 记为P1= (P1, P2, …PM) 。每个粒子都要追踪这两个极值来更新搜索的速度, 从而更新自身的位置, 直至搜索到全局最优解。
3 改进粒子群算法
禁忌搜索算法的收敛效果较好, 但计算的结果很大程度上依赖于设定的初始解, 一个合适的初始解很有可能会帮助禁忌搜索算法快速地收敛, 并找到全局最优解, 而一个不恰当的初始值会很大程度地使算法的收敛速度降低, 收敛效果变差。介于此, 我们考虑运用其他智能优化算法进行前期的计算来求得一个较好的初始解, 从而来完善禁忌搜索算法的优化效果。粒子群优化算法计算到后期时收敛速度变得缓慢, 局部搜索能力差, 但是粒子群优化算法的操作简单、易于实现、全局搜索能力强。分析了两种算法的各自特点后, 本文在粒子群优化算法的后期加入局部寻优能力较强的禁忌搜索算法, 把两种算法融合在一起, 这样以来就解决了粒子群算法后期收敛难的问题。
4 仿真分析
本文利用Matlab编程, 采用下图所示的含DG的IEEE-33节点配电网系统进行仿真。其电网额定电压为12.66kV, 网络总负荷为3715.0kW+j2300.0kVar。在系统的7、17、19、29节点处接有DG。进行重构前, 支路7-20、8-14、11-21、17-32、24-28打开。
在分布式电源接入配电网时, 由于DG和节点上的负荷支路距离非常近, 所以支路7-33、17-36、19-34、29-35上的电阻与电抗忽略不计, 视为零计算;DG的注入功率按照负荷进行计算, 并标记符号为负。
经过重构后, 得到最优结果为打开开关6-7、8-9、13-1424-28、31-32。系统不接DG前的初始网损为203.55kW, 接入DG后系统网损降低到90.99kW, 与之前相比减少了55%, 可见DG的接入降低了网络损耗。
实验结果表明本文提出的改进方法较之基本粒子群算法对降低网络损耗和提高节点电压具有明显的效果。
摘要：粒子群优化算法是由Kennedy和Eberhart于1995年提出的一种基于智能的进化算法。目前, 在自适应控制、组合优化、人工生命、管理决策等领域得到了广泛的应用。本文在粒子群算法后期加入了禁忌表思想, 形成了改进粒子群算法, 并将改进后的粒子群算法应用于配电网重构问题。通过对含分布式电源的IEEE-33节点系统进行仿真, 结果表明分布式电源的接入能够提高节点电压, 降低网络损耗, 证明本文算法对含分布式电源的配电网重构问题具有良好效果。
关键词：粒子群算法,配电网重构,分布式电源
参考文献
[1]曾建潮.微粒群算法[M].北京:科学出版社, 2004.