免疫粒子群算法(精选11篇)
免疫粒子群算法 篇1
1 引 言
模糊控制策略是解决非线性和复杂控制问题的一种有效的智能控制方法[1]。模糊控制器的设计通常需要专家经验并要对众多的参数进行整定以达到满意的控制效果。这样一个依赖于专家经验的人工寻优过程会给工程应用带来不便。目前, 很多学者致力于用进化算法来优化模糊控制器的参数[2,3,4], 但是很少有文献提出对控制决策表进行优化。控制决策表是模糊控制器的重要组成部分, 在实时控制中是影响控制效果的关键因素。另外, 用于参数优化的进化算法往往需要调整很多参数, 给优化的实现带来了难度。
基于传统粒子群算法 (Particle Swarm Optimization, PSO) 提出的量子粒子群算法 (Quantum-behaved PSO, QPSO) 具有计算机实现简单、鲁棒性强、可调参数少的优点。本文给出一种免疫量子粒子群算法 (QPSO-immune Algorithm, QPSO-IM) , 它根据系统所要达到的性能指标来优化模糊控制器中的控制决策表, 使模糊控制规则更加完善。该算法将免疫算子引入QPSO算法中, 在保留原算法优点的基础上提高了算法的全局搜索能力。模糊控制器和控制决策表的优化设计在SCON-2000模糊控制平台进行了工程化实现, 在对水箱液位模糊控制中取得了令人满意的控制效果。
2 模糊控制系统简介
常规模糊控制系统如图1所示, 其控制可分为模糊化、模糊推理和解模糊三步。
模糊化就是将基本论域上的精确量:误差e和误差变化率ec, 变换为量化论域上的模糊集的过程。模糊推理过程就是对模糊输入量根据制定的模糊规则和模糊推理方法进行模糊推理, 求出模糊输出量, 继而通过解模糊求得确定的控制量。为提高系统的实时性, 通常是根据上述过程离线计算出控制决策表用于控制。水箱液位模糊控制的控制决策表如表1所示。控制过程中, 根据输入信号e和ec查询控制决策表, 所得增量按比例转换后再施加于被控对象。
在系统投运时, 仅基于专家经验构成的控制决策表往往是不完善的, 还要对控制决策表进行参数整定以取得满意的控制效果。由表1可以看出, 控制决策表是一个13×15的实数矩阵, 其参数的人工整定不仅需要丰富的专家经验, 还要耗费大量时间。因此, 控制决策表的自动调整优化是一项具有实际意义的工作。
3 基于QPSO-IM算法的控制决策表优化
3.1 QPSO算法简介
传统粒子群算法将算法中的可行解看作没有重量和体积的粒子, 粒子在n维搜索空间中追随本身目前所找到的最优位置和整个粒子群所找到的最优位置进行迭代飞行[5]。
Sun等人从量子力学的角度提出了一种新的PSO算法模型——量子粒子群优化算法 (QPSO) 。研究结果证明, 在保证种群规模的情况下, QPSO算法的搜索能力优于PSO算法, 而且QPSO算法的参数少, 更容易实现控制[6]。设粒子i的当前位置为xi= (xi1, xi2, …, xin) ;粒子i所经历的最好位置为pi= (pi1, pi2, …, pin) ;整个粒子群所经历的最好位置为pg= (pg1, pg2, …, pgn) , 即搜索到的最优解。粒子根据式 (1) ~ (3) 进行迭代飞行, 达到迭代次数后飞行结束。
xij (t+1) =p′ij±β|mbestj-xij (t) |ln (1/u) (1)
其中,
mbest是各粒子本身所经历的最优位置的平均位置;φ和u是在[0, 1]上产生的相互独立的随机数;β为伸缩因子, 是QPSO算法中唯一的可调参数。式 (1) 中的正负号以相同概率随机产生。
3.2 人工免疫算子的引入
把QPSO算法中的粒子看作人工免疫系统中的抗体, 将免疫的思想引入QPSO算法可以提高算法的性能[7]。基于人工免疫原理, 浓度选择机制保证了粒子 (抗体) 的多样性从而提高了算法的全局搜索能力。设有N+M个粒子, 每个粒子的适应度值为f (·) , 则第i个粒子的浓度为:
从N+M个粒子中选择N个粒子以避免粒子过度集中, 第i个粒子的选择概率为:
另外, 接种机制用在QPSO中, 以保留最优粒子的形式提高算法的收敛速率[8]。
改进后的QPSO算法称为免疫量子粒子群算法 (QPSO-IM) 。
3.3 基于QPSO-IM算法的控制决策表优化
QPSO-IM算法流程如图2所示, 其实现步骤如下。
(1) 编码。
本文要优化的控制决策表是一个13×15的实数矩阵, 如表1所示。采用实数编码方式, 将该矩阵元素以行序组成一维向量, 作为一个粒子。若矩阵的第i行元素表示为aij, 则粒子编码为:
a1j, a2j, …, a13j (j=1, 2, …, 15)
可见, 每个矩阵的编码是一个195维的行向量, 所以控制决策表的优化是一个高维优化问题。
(2) 初始种群的生成。
本文对已经存在但控制效果欠佳的控制决策表1进行优化调整, 以达到满意的控制效果。因此, 没有必要在实数域内随机产生初始种群。而且, 随机产生的控制决策表几乎都无法达到控制目的, 进化中对它们的评价也就没有意义。因此, 初始种群可在表1的基础上产生。本文的方法是按表1编码的各位加上[-c, c]之间的随机实数, 由此产生初始种群, 在可行解空间范围内搜索最优解。正实数c的选取将影响算法的寻优能力。较大的c有助于提高算法的全局搜索能力;较小的c则有助于提高算法的局部搜索能力。在工程应用中, c的选取受制于控制量的约束范围。在执行机构允许范围内, c的选取可参考表1中的最大元素 (aij) max, 即:
c< (aij) max (i=1, 2, …, 13;j=1, 2, …, 15)
(3) 记忆库。
用于保存进化过程中的最优粒子, 记忆库在迭代过程中不断更新。
(4) 适应度值的确定。
本文采用时间与误差绝对值的乘积的积分 (ITAE) 来评价个体性能, 它综合反映了系统的超调量、上升时间以及过渡过程等性能指标[9], 如式 (6) 所示。
ITAE=∫
其中, 积分上限T的设定关系到能否对个体优劣进行有效区分。过小的T无法有效区分个体优劣程度;过大的T不仅过度放大了较差个体的劣势, 而且会增加计算机的计算量, 从而给算法实现带来困难。通常T可取调整ts的2~4倍。据式 (6) 可知, ITAE值较小的粒子具有较好的控制效果。为了使控制效果更好的粒子具有更大的适应度值, 我们将计算出的ITAE值进行转换, 然后用于浓度的计算。这里采用一种线性转换的方式来计算粒子的适应度, 如图3所示。
在进化过程中, 每一代粒子的适应度值由该粒子的ITAE值以及这一代粒子的最大ITAE值和最小ITAE值确定, 则ITAE值为x的个体的适应度值为:
这种变换令某一代的最差个体和最优个体的适应度值分别为0和1, 能够有效区分个体之间差异。需要指出的是, 该变换得出的适应度值仅在该代中有效, 不同代个体不能利用这种变换得出的值进行比较计算。不同代个体只需直接用ITAE值进行比较即可。
(5) 粒子更新的两种方式。
a.迭代更新。由式 (1) ~ (3) 产生N个新粒子;
b.重新生成M个新粒子。生成方式和初始种群的生成方式相同。
(6) 基于浓度的粒子选择。
用式 (4) 计算N+M个新粒子的浓度, 然后依概率公式 (5) 选择N个粒子组成新的群体。
(7) 接种疫苗。
用记忆库中的免疫记忆粒子替换粒子群中适应度较差的粒子。
(8) 结束条件。
达到预先设定的最大进化代数时寻优结束。
4 应用实例与结果分析
LTT三容液位控制实验装置是高等院校的教学实验设备, 主体由三个圆柱形容器罐、若干手动排水阀和一个蓄水池组成。用液位传感器检测容器水位, 用变频器调节泵的转速, 继而改变泵的供水量。本文在自行研制的SCON-2000先进控制系统的模糊控制平台上进行单容水箱液位模糊控制, 考察跟踪参考输入响应和负荷变化时的响应, 并将优化前后控制决策表的控制效果进行了对比。
初始种群规模N=50, 产生的方式是按表1的编码的各位加上[-2, 2]之间的随机数;每次迭代, 产生新粒子数M=10;伸缩因子β在迭代过程中从1.0到0.5线性下降;粒子的每位限定在[-7.5, 7.5]之间;取式 (6) 的积分时间T=4ts;每次迭代时, 选择种群中3个最差粒子替换为免疫记忆粒子;最大进化代数为200。本文同时利用SCON-2000先进控制系统的建模平台对水箱进行建模, 得到的水箱模型为:
优化后的控制决策表如表2所示。
在SCON-2000先进控制平台上对水箱液位进行实时控制, 设定液位为200 mm, 误差量化因子Ke=2.53, 误差变化率量化因子Kec=125, 控制量比例因子Ku=1, 模糊控制器采用增量形式。优化前后的响应曲线以及控制量曲线如图4、图5所示, 可见优化后的控制决策表性能比优化前有了很大的改善。
(1) 优化前, 系统响应的超调量为30%, 调节时间为3.5min;优化后, 系统响应的超调量为5%, 调节时间为2 min。
(2) 优化前, 系统响应的稳态波动在±25mm内;优化后, 系统响应的稳态波动在±10 mm以内。这表明优化后的控制决策表的精度更高。
(3) 在系统稳态时加入负荷扰动, 优化前的系统需要5.5min恢复稳态, 并有超调;优化后的系统仅用2 min就重新到达稳态, 且没有超调。这表明优化后系统响应具有更好的快速性和平稳性。
5 结束语
本文提出用QPSO-IM算法来优化模糊控制器中的控制决策表。算法实现简单, 可调参数少, 使模糊控制决策表的参数整定易于工程应用。实验结果表明:用QPSO-IM算法优化过的控制决策表明显改进了模糊控制器的性能, 从而达到了优化模糊控制器的目的。
参考文献
[1]孙绪刚, 王丽荣.模糊控制在聚合装置的应用[J].化工自动化及仪表, 2001, 28 (4) :29-32.
[2]LINKENS D A, NYONGESA HO.Genetic Algorithm for FuzzyControl, Part 1:Offline System Development and Application[C]//IEE Proceedings-Control Theory and Applications.U-nited Kingdom:IET, 2004:161-176.
[3]ESMIN A A A, AOKI A R, LAMBERT-TORRES G.ParticleSwarm Optimization for Fuzzy Membership Functions Optimiza-tion[C]//IEEE International Conference on Systems, Man andCybernetics.Tunisia:IEEE, 2002, 3:5.
[4]HOMAIFAR A, MCCORMICK E.Simultaneous Design of Mem-bership Functions and Rule Sets for Fuzzy Controllers Using Ge-netic Algorithms[J].IEEE Transactions on Fuzzy System, 1995, 3 (2) :129-139.
[5]KENNEDY J, EBERHART R.Particle Swarm Optimization[C]//Proceedings of the IEEE International Conference onNeural Networks.Australia:IEEE, 1995:1942-1948.
[6]SUN J, FENG B, XU W B.Particle Swarm Optimization withParticles Having Quantum Behavior[C]//Proceeding of 2004Congress on Evolution Computation.Portland:CEC, 2004:325-331.
[7]LIUJ, SUNJ, XUW B, et al.Quantum-behaved Particle SwarmOptimization Based on Immune Memory and Vaccination[C]//Proceedings of the IEEE International Conference onGranular Computing.USA:IEEE, 2006:453-456.
[8]DASGUPTA D.Artificial Immune Systems and Their Applica-tions[M].New York:Springer-Verlag, 1999.
[9]DORF R, BISHOP R H.Modern Control Systems[M].Califor-nia:Addison Wesley, 1998.
免疫粒子群算法 篇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提出的一种全局优化算法[1],现已广泛应用于科学与工程领域。然而,粒子群算法随着问题规模的增大,在进化后期算法收敛速度变慢且易陷入早熟收敛。近年来,相关学者提出了许多改进算法以改善粒子群算法的性能。如Chia-Feng Juang将遗传算法的交叉与变异机制引入粒子群算法,提出了一种混合粒子群优化算法(HGAPSO)[2]。文献[3]提出了一种自适应粒子群算法(APSO),比较PSO该算法改善了收敛速度、增加了收敛精度和可靠性。文献[4]提出了一种自适应综合学习粒子群算法(A-CLPSO),该算法减少了陷入局部最优的可能。然而,这些改进都只在一定程度上改善了PSO的性能,早熟收敛仍是粒子群算法的一大难题,尤其是对于复杂高维及多模态优化问题更是如此。
通过分析粒子群算法的特性,寻找其早熟收敛的原因因,,本本文文提提出了一种新的免疫网络粒子群算法(Immune Network PPaarrttiiccllee Swarm Optimization,INPSO)。经过经典测试函数的测试试表表明明,,INPSO算法明显提高了粒子群体的多样性和算法的求解精精度度,,有有效效避免了粒子群算法易出现早熟收敛和进化后期收敛速度慢慢的的缺缺点点。。
2 算法改进基础
2.1 标准粒子群算法
其中,惯性权重。随着进化代数的增长,从0.9线性减少至0.4。粒子的位置更新公式如下:
2.2 改进的克隆选择算法
克隆选择算法是由L.N.De Castro提出[5],算法中变异算子主要是高斯变异与柯西变异,变异空间比较固定,不利于免疫克隆选择算法的动态寻优。而小波变异的变异空间可变,且具有微调能力,有利于提高算法的动态优化性能。基于小波变异的克隆操作步骤如下:
Step 1各个粒子的个体极值生成一个临时克隆种群。将临时克隆种群中的每个粒子视为抗体,克隆规模与亲和度成正比,克隆倍数Nc如下:
其中,N为种群规模,。另外,为了保证每个抗体都有一定的克隆数量,因此加上了b1的整数常量。经过克隆扩增后,生成新群体Sub。
Step 2对群体Sub中的每个个体实施高频变异,其方法为自适应Morlet小波变异。受自然生物进化思想启发,算法在进化初期以一定的变异概率采用较大的小波变异幅值以保持粒子群体的多样性,而到进化后期小波变异幅值逐渐缩小以提高算法的局部微调能力。其变异算子如下:
Step 3免疫选择操作,从克隆变异后的个体中选择亲和度最高的个体进入下一代。通过局部择优实现了种群的压缩,同时保证了抗体群中的最优解不会变差。
2.3 免疫网络
受独特型免疫调节网络的启发,De Castro构造了一种aiNet算法,来模拟免疫网络对抗原刺激的应答过程[6],有效地维持了抗原-抗体、抗体-抗体之间的动态稳定平衡,保持了抗体的多样性。aiNet新生成的网络细胞群C*如下。
其中C是网络细胞群,X是抗原细胞,是学习率或者成熟率。的取值根据网络单元与抗原的亲和度而定,亲和度高则的取值小,使抗体将朝着识别抗原的方向进化。
利用免疫网络及柯西变异扰动可有效克服粒子群算法早熟收敛,增强粒子种群的多样性,提高算法的收敛速度及全局搜索能力。因此,文中采用了柯西免疫网络来生成下一代群体,其新种群个体的生成公式如下。
其中,,r1,r2为区间之间的随机数,cauchy密度函数的表达式如下。
3 免疫网络粒子群算法及流程
本文将克隆选择、免疫网络与粒子群算法进行了有机结合,提出了一种新的免疫网络粒子群算法(INPSO)。算法的基本流程如图1所示。
免疫网络粒子群算法的基本流程如下:
(1)随机初始化m个粒子的位置与速度,并初始化相关参数。
(2)评价各粒子的初始适应度值,并保存相应粒子初始最优位置以及初始最优适应度值。While(不满足退出条件)do//退出条件为找到相应的全局最优解或达到设定的截止代数。
(3)根据式(2-1)(2-2)对粒子的速度和位置进行更新,并计算各粒子的适应度值,如果各粒子适应度值优于相应粒子历史最优适应度值,则粒子的pBest更新。
(4)将所有粒子按适应度排序,对中间M个粒子根据式(2-6)进行柯西免疫网络操作,并重新初始化最后X个粒子,如果各粒子适应度值优于相应粒子历史最优适应度值,则粒子的pBest更新。
(5)对前面N个粒子的p Best进行克隆选择操作,如果所有粒子中最优粒子适应度值优于历史全局最优粒子适应度值,则gBest更新。
End While
(6)输出结果,算法运行结束。
4 算法性能分析
为了验证本文提出的免疫网络粒子群算法(Immune Network Particle Swarm Optimization,INPSO)的收敛速度以及全局优化能力,用本算法对表1所示函数进行测试,其中f1~f4为单模态函数,f5~f8为多模态函数。并将INPSO与其它混合粒子群算法进行比较,充分考察免疫网络粒子群算法对不同类型问题的优化性能。
实验仿真环境为Windows 7系统,AMD Athlon(tm)II X2255处理器,2.0GB内存,仿真软件为Microsoft Visual C++6.0,绘图软件为MATLAB 7.0。
实验参数设置:对于所有函数,I N P S O的加速因子,惯性权重在区间[0.9,0.4]内线性递减,且克隆变异概率为0.8。对于所有算法,设置粒子个数为40,问题维数为30,算法迭代次数为1000,运行次数为30。
4.1 算法精度比较
本节将免疫网络粒子群算法(INPSO)分别与混合遗传粒子群算法(HGAPSO)[7]、自适应粒子群算法(APSO)[8]以及自适应综合学习粒子群算法(A-CLPSO)[9]进行比较,对于表1中所列的8个经典测试函数,各算法30次独立运行结束后的均值(Mean)和均方差(Std.Dev)如表2所示,而图2则分别比较了各算法在进化过程中的收敛性能。
从表2和图2中可以看出,无论是对于单模态函数还是对于多模态函数,INPSO算法的收敛速度以及收敛精度都明显优于其它3种改进粒子群算法,而且具有更强大的搜索能力。
4.2 高维函数实验
从表1中选取两个单模态函数(f1、f3)和两个多模态函数(f5、f7),将函数维数分别取100维、500维、1000维与5000维来对算法进行测试,函数维数对算法性能的影响及函数维数与适应度值关系分别如表3、图3所示。
从表3与图3中可以看出,在其它参数不变的情况下,免疫网络粒子群算法(Immune Network Particle Swarm Optimization,INPSO)的优化能力并没有随着函数维数的增大而减弱,算法所需时间正常增长,这说明INPSO在高维函数优化方面有明显优势。由于INPSO很好地保持了群体的多样性,对超高维函数也几乎能够在相同的代数下找到理想的全局最优值。
5 结语
本文提出了一种免疫网络粒子群算法。在标准粒子群算法的基础上,引入了克隆选择机制与免疫网络思想,并将克隆变异算子加以改进,提高了算法的动态寻优能力。实验结果表明,改进后的算法明显提高了算法的求解精度,有效克服了粒子群算法易出现早熟收敛与进化后期收敛速度慢等缺点。同时表明INPSO算法在求解多模态问题及高维优化问题上优势明显,可以预见INPSO算法在复杂系统控制器优化与设计领域有着较好的应用前景。
参考文献
[1]Eberhart R,Kennedy J A.New optimizer using particle swarmtheory[C]//Proceedings of the Sixth International Symposium on MicroMachine andHuman Science.Piscataway,NJ,USA:IEEE,1995:39-43.
[2]Chia F J.A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design.IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS—PART B:CYBERNETICS,2004,34(2):997-1006.
[3]Zhi H Z,Jun Z,Yun L H,Shu H C.Adaptive Particle Swarm Optimization.IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS—PART B:CYBERNETICS,2009,39(6):1362-1381.
[4]Ho S Y,Lin H S,Liauh W H,et al.OPSO:Orthogonal particle swarm optimization and its application to task assignment problems[J].IEEE Transactions on Systems,Man,and Cybernetics,Part A:System and Humans,2008,38(2):288-298.
[5]De L N,Castro F,Zuben J V.Learning and optimization using the clonal selection principle.IEEE Trans.Evol.Computer,2002,6(3):239-251.
[6]De L N,Castro F Zuben J V.An evolutionary immune network for data clustering.Proceedings Sixth Brazilian Symposium on Neural Networks,2000,84-89.
[7]Chia F J.A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design.IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS—PART B:CYBERNETICS,2004,34(2):997-1006.
[8]Zhi H Z,Jun Z,Yun L H,Shu H C.Adaptive Particle Swarm Optimization.IEEE TRANSACTIONS ON SYSTEMS,MAN,AND CYBERNETICS—PART B:CYBERNETICS,2009,39(6):1362-1381.
免疫粒子群算法 篇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
由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。
一、蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。
蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。
初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。
其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:
其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:
其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。
算法流程如图1所示:
二、粒子群算法
Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。
假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:
其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。
算法流程如图2所示:
三、两种算法的比较分析
1算法各自优缺点
(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:
①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。
②扩展性:信息交流方式是非直接的,通信开销少。
③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。
④优化过程无需依赖具体问题的数学特性,例如可微、线性等。
⑤算法简单容易实现:系统中个体能力简单,执行时间短。
另外,PSO还具有如下优点:
①群体搜索,并具有记忆功能,保留个体和全局的最优信息;
②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。
(2)ACO和PSO也存在着局限性:
①优化性能在很大程度上依赖于参数设定,受初始值影响较大。
②容易产生早熟收敛。
另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。
PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。
2应用领域
●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。
●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。
3与其它算法混合
由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。
①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。
③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。
④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。
⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。
四、展望
群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。
参考文献
[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.
[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.
[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.
粒子群算法的改进算法研究 篇8
基本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.
粒子群优化算法综述 篇9
PSO在解决许多GO问题上被证明是一种有效的方法;在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。
1 PSO算法原理
在PSO算法中, 首先随机产生一群粒子, 每一个粒子都是搜索空间的潜在解。然后通过迭代寻找最优解。每一个的粒子都有一个适应于种群的适应值 (fitness) , 及决定粒子飞翔的位移和速度。每次迭代后, 粒子下一时刻的速度和位移通过两个“极值”来更新:第一个极值是迭代后粒子本身的最优解, 称为局部最优解;第二个极值是整个种群的最优解, 称为全局最优解。
假设在一个D维的目标搜索空间中, 有m个粒子组成一个群落, 其中第i个粒子的位置表示为, xi= (xi1, xi2, …, xi D) , i=1, 2, …, m;速度表示为vi= (vi1, vi2, …, vi D) 。第i个粒子目前为止搜索到的最优位置为pi= (pi1, pi2, …, pi D) , 整个粒子群的最优位置为pg= (pg1, pg2, …, pg D) 。
PSO算法采用下列公式对粒子操作:
其中i=1, 2, …, m, d=1, 2, …, D;加速因子c1和c2是非负常数, 分别调节个体最好粒子和全局最好粒子飞行的最大步长。若太小, 则粒子可能远离目标区域, 太大则会导致粒子突然向目标区域飞去, 或飞过目标区域。合适的c1和c2可以加快收敛且不易陷入局部最优, 通常令c1=c2=2;r1和r2是介于[0, 1]之间的随机数。粒子在每一维飞行的速度不超过算法设定的最大速度vmax。
公式 (1) 的第一部分表示粒子当前速度对粒子飞行的影响, 这部分提供粒子在搜索空间飞行的动力;第二部分为“个体认知”部分, 表示粒子根据自己的经验飞行;第三部分为“社会认知”部分, 表示粒子通过交流和合作根据社会成员的经验飞行。文献[3]对公式 (1) 作了如下改动:
其中, w是非负数, 称为惯性因子。公式 (2) 和公式 (3) 也叫基本PSO算法。基本PSO算法需要用户确定的参数并不多, 而且操作简单。但是它的缺点是易陷入局部极小点, 搜索精度不高, 因此研究者们对其进行了各种各样的改进。
2 PSO改进算法
2.1 收敛PSO
文献[4]通过对算法的研究, 证明采用收敛因子能够确保算法的收敛。在收敛因子模型中速度的更新公式为:
其中, φ=c1+c2, φ>4, 通常取φ=4.1, 由此计算得χ=0.729。改进后的公式 (2) 和公式 (4) 被称为标准PSO。
文献[5]在对基本PSO算法分析的基础上, 提出了一种能够保证以概率1收敛于全局最优解的PSO算法———随机PSO算法 (Stochastic PSO, SP-SO) , 并利用Solis和Wets的研究结果对其全局收敛进行了理论分析。文献指出当ω=0时, 公式 (2) 、 (3) 描述的进化方程变为:
其中, 粒子的飞行速度只取决于粒子的当前位置xi、历史最好位置pi和粒子群的历史最好位置pg, 速度本身无记忆性。这样, 对于位于全局最好位置的微粒将保持静止。为了改善公式 (5) 的全局搜索能力, 可保留pg作为微粒群的历史最好位置, 而在搜索空间s重新随机产生微粒i的位置xi。
文献[5]通过将式 (5) 改成一个差分方程, 在理论上分析了当c1+c2<2时, SPSO算法的进化方程线性渐进收敛。
2.2 基于拓扑结构的PSO
最早的粒子群优化版本是全局PSO, 它使用全局 (gbest) 拓扑结构, 社会只能通过种群中最优的那个粒子对每个粒子施加影响。实验证明利用全局PSO训练前向神经网络的权矩阵是有效的。但是在全局PSO中, 粒子间的交流不够充分。文献[6]提出了一种局部 (lbest) 拓扑结构。在这种模型中, 每个粒子都和它的邻居进行交流。例如种群中的第5个粒子和第6个以及第7个粒子进行交流。图1是粒子群的全局和局部拓扑结构。
在局部拓扑结构中, 粒子之间的交流相对比较缓慢。如果第i个粒子找到一个比较好的解, 它可以传递给它的邻居j。若粒子k和j连接但是和i没有连接, 只有当j更新后才可能传给k。因为传递的比较慢, 粒子更容易搜索问题空间中的不同地区。
文献[7]根据对人类社会的模拟进而提出了FIPS (Fully-Informed Particle Swarm) , 认为粒子应受所有邻居的影响。对粒子速度用公式 (6) 进行操作:
其中, N是第i个粒子的所有邻居组成的集合, k是粒子i的第k个邻居, pk是粒子k目前找到的最优值。如果N定义为只包含粒子i它自己和它的最优邻居, 公式 (6) 就是标准PSO。在FIPS中, 粒子的速度是根据粒子当前位置和它的邻居目前找到的最优位置之间的加权平均差来更新。
文献[8]在研究了领域拓扑结构对粒子群算法性能的影响后, 设计了两种动态邻域生成策略, 验证不同的邻域拓扑结构和不同的算法模型能够影响粒子群算法的性能。文献[9]提出了一种该改进的PSO算法PSO-DSF。引进有向类无标度网作为粒子群寻优的拓扑结构, 提出作为粒子邻域拓扑的有向网络动态变化机制, 从而提高算法的多样性, 避免过早陷入局部最优的情况。文献[10]提出基于KRTG的动态拓扑结构的粒子群算法研究。从粒子间的拓扑结构出发, 动态地调整种群的拓扑结构, 增加种群的多样性, 使算法收敛于全局最优解。文献[11]提出了一种动态拓扑结构改进PSO算法。在这种结构中, 用了两种方法改进邻居的拓扑结构:随机边缘移植 (Random Edge Migration, REM) 、邻居重组 (Neighborhood Restructuring, NR) 。随机边缘移植是指随机选取一个邻居数目大于1的粒子节点, 移去一个邻居节点, 并把这个邻居节点和另一个随机选取的未满的粒子节点相连接。邻居重组保持粒子的邻居结构在一段时间内固定, 然后重新构造粒子邻居的结构。通过对六个基准函数的实验表明这种方法是一种好的策略, 对每一个函数的测试都取得了令人满意的结果。研究基于拓扑结构的PSO算法一直在持续, 是一个值得研究的方向。
2.3 混合PSO
文献[12]针对带障碍约束的空间聚类, 提出了一种改进的蚁群算法 (IACO) 和混合粒子群算法 (HPSO) 。首先, 使用蚁群算法获得最短的障碍距离, 然后设计了一个带障碍约束的遗传K中心空间聚类分析算法。
文献[13]中, 使用交叉算子和变异算子, 并结合混合粒子群优化算法以及遗传算法解决柔性作业调度问题, 并提出混合整数编程模型。
文献[14, 15]介绍了一种和差分进化 (Differential Evolution, DE) 算法结合的混合PSO算法。在DEPSO中, 传统的PSO操作和DE操作交替的进行, 当迭代次数为奇数时执行PSO算法, 而当为偶数时执行公式 (8) :
其中, r∈[0, 1]是随机数, k∈[1, D]是整数, 用来保证至少在其中一维产生变异, CR是一个交叉常数, δ2是N=2时的一般差分向量δN, 定义如下:
其中, 是一个差分向量用来表示从一个由粒子组成的集合中选取的两个元素的差, 这个集合包括当前所有的个体最优值 (pbest) 。N是包含的元素个数, 在第d维有:
其中, 和从pbest集中随机选取。在一组基准函数上的测试表明DEPSO优于PSO算法和DE算法。在DEPSO中, 如果知道参数之间的关系, 就能确定一个合适的CR, 但这通常需要人们对问题有很深的了解。
2.4 统一PSO
PSO算法的性能依赖于全局搜索和局部搜索之间 (Exploration and Exploitation) 的平衡能力, 即搜索空间的全局搜索能力和快速收敛于有希望的区域的能力, 分别对应全局变量和局部变量。根据这一思想, 文献[16]提出了一种新的PSO结构UPSO (Unified Particle Swarm Optimization) 。为达到全局搜索和局部搜索的平衡, UPSO将全局变量和局部变量合在一个公式里, 从而更新粒子的位置:
其中, u是统一因子, 在[0, 1]之间取值, 用来平衡全局和局部搜索。u=0和1分别对应着局部PSO和全局PSO。Gnid+1表示在全局PSO变量中粒子xi的速度更新, Lnid+1表示在局部PSO变量中粒子的速度更新, 它们分别用下式计算:
其中, k是迭代次数, g (全局变量) 是整个粒子群目前找到的粒子最优位置的下标, gi (局部变量) 是xi的邻居目前找到的粒子最优位置的下标。
2.5 感知PSO (PPSO)
感知PSO (Perceptive Particle Swarm Optimization, PPSO) [17]与传统PSO的搜索过程相似, 不同的是PPSO在n+1维空间搜索, 附加的维是粒子的适应值。一个n维的目标函数在PPSO中被看成n+1维的自然地形 (Physical Landscape) 。在PPSO中引入了三个参数:感知半径、要观察方向的数量和沿着每个观察方向要观察的点的个数。PPSO允许每个粒子有一个有限的感知范围去观测搜索空间, 并且感知在这个范围内的其他粒子的近似位置, 而不是在临近粒子之间直接交换信息。在PPSO中粒子通过采集固定数量要观察的方向和沿着这些方向的有限数量的点观测搜索空间。例如对一个三维的观察空间, 粒子沿着+x, -x, +y, -y, +z, -z六个不同的方向观测搜索空间。
研究表明:较大的感知半径易于群间个体的交流和扩大粒子的搜索空间。因为当在它的感知范围内没有邻居时, 粒子会飞到自己的最好位置。而要观察方向的数量越多, 得到一个好解的机会越大。观察的点的个数越多, 得到的解越精确。但是观测搜索空间需要的时间也越多。为了获得一个满意的解, 这是值得的。
2.6 主要素PSO (PCPSO)
主要素PSO (Principal Component Particle Swarm Optimization, PCPSO) [18,19]中的粒子在两个分开的空间飞行:传统的n维x空间和经过旋转后的m维z空间。PCPSO在x空间使用下面的公式进行迭代:
其中, 表示和z空间相关, 用下式进行计算:
在z空间用下面的公式迭代:
z空间和c空间之间通过标准正交基U~联系:
其中, U满足U'SU=L, L是一个对角矩阵, S是加权协方差矩阵, 是通过主元素分析 (Principal Component Analysis, PCA) 得到的。
和标准PSO相比, PCPSO的优点是时间复杂度比较低, 它一定能在少得多的迭代次数内找到最优解。实验证明PCPSO是一个很有前途的算法, 能降低求解高维函数最优解的时间复杂度。缺点是因涉及数学计算, 对数学基础要求比较高, 不易掌握。
2.7 带时间加速因子的自组织分层的PSO
文献[20]提出了一个新的参变量:随时间变化的加速因子 (Time-Varying Acceleration Coefficients, TVAC) , 目的是在算法前期提高全局搜索能力, 在算法后期促使粒子收敛到全局最优。方法是通过随时间改变加速因子c1和c2来减少个体认知因素而增加社会因素。研究表明在算法初期, 较大的个体认知因素和较小的社会因素使粒子能有更好的全局搜索能力。相反在粒子的后期, 较小的个体认知因素和较大的社会因素, 则能使粒子更好的收敛于全局最优。c1和c2分别用下式计算:
其中, c1i, c1f, c2i和c2f是常量, iter是当前迭代次数, MAXITER是最大允许迭代次数。
另外, 文献对PSO的另一个改进是去掉了公式 (1) 中粒子上一时刻的速度, 研究表明去掉此速度粒子会很快因为缺乏动力而收敛于局部最优, 并停滞不前。为了解决这个问题, 文献中提出了自组织分层的PSO, 提供粒子寻找全局最优的动力。方法是当粒子停滞不前时 (vid=0) , 重新初始化速度向量的系数。实验表明, 和传统PSO算法相比, HPSO-TVAV在单峰和低维函数上表现不时很好, 但是在多维和多峰函数上表现优异。
3 PSO应用
由于简洁易操作的特点, PSO算法一提出就引起了各方面的关注, 关于PSO算法的应用不断出现, 现已广泛应用于函数优化、神经网络训练、工业系统控制、模式识别及其他遗传算法的应用领域。
PSO最早应用时将其应用于神经网络训练。文献[21]将PSO算法用于神经网络集成, 加强了神经网络的泛化能力。文献[22]将PSO算法用于解决优化网页内容描述的问题中。文献[23]将离散PSO算法用于求解TSP问题;文献[24]提出一种将PSO算法用于文本知识发现的方法;文献[25]将PSO算法用于多目标问题的求解;文献[26]将PSO算法用于人脸识别中。文献[27]则将PSO算法用于软件结构测试数据自动生成也取得了良好的效果。文献[28]将BPSO算法应用于特征选择中, 提出了一种不基于分类器的特征选择方法。
总之, 在解决复杂问题时, PSO算法被证明是一种有效的方法, 已被应用于各个研究领域。
4 PSO展望
PSO是一种新兴的有潜力的基于群智能的演化计算技术。自从2002年PSO算法被引进国内[27], 已经有很多学者对PSO进行了研究。虽然已经取得了一些研究成果, 但是仍然有许多问题值得关注。
4.1 算法的理论基础
PSO算法在实际应用中已被证明是一种有效的优化工具, 已广泛的应用于科学研究和工程实践, 但是其内部机理仍不明确, PSO算法缺乏数学理论支持。PSO的改进算法及其应用也都停留在实验阶段。文献[4, 5]对算法的收敛做了一定的分析, 但是对于这样一个年轻有潜力的算法, 还远远不够。所以开展一些理论研究, 不仅可以加深对PSO算法内部机理的认识, 而且对于扩展PSO的应用领域也有深远意义。
4.2 拓扑结构
文献[7-11]对拓扑结构的研究表明一种好的拓扑结构能有效地改善算法的性能, 并且能在许多优化问题上取得非常不错的结果。寻求一种好的拓扑结构, 加强PSO算法的泛化能力, 使其能在多数优化问题上取得满意的结果, 并不是不可能。
4.3 参数调整模型
尽管目前已经有许多PSO算法的改进版本, 但是都各有优缺点。如何针对问题的不同特点, 构造一个参数调整模型, 达到平衡粒子的全局搜索能力与局部搜索能力, 避免粒子早熟收敛, 对工程应用有十分重要的意义。
4.4 与其他方法结合
PSO算法虽然是一种有效的优化工具, 但同样有其不足, 如迭代后期搜索能力不够, 早熟收敛等。所以, 如何将其他算法引进PSO算法, 以弥补其不足是一个重要方向。
4.5 算法应用
科学与工程实践中的许多问题都可以归结为优化问题。所以如何将PSO算法与实际问题结合, 将会有力的推动PSO算法的发展。
摘要:粒子群优化 (PSO) 算法是一种基于群智能方法的演化计算技术, 通过粒子间的相互作用发现复杂搜索空间中的最优区域, 优势在于简单容易实现而且功能强大。由于它简单易操作的特点, PSO一提出, 立刻引起演化计算等领域学者们的广泛关注, 并在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。介绍了基本的PSO算法、若干类改进的PSO算法及其应用。
基于粒子群算法的改进遗传算法 篇10
遗传算法是根据自然界的“物竞天择,适者生存”现象二提出的一种随机搜索算法。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.
免疫粒子群算法 篇11
生物免疫特性能较好实现粒子群在进化过程中收敛性和个体多样性的平衡,解决算法在后期因粒子逐步趋同导致收敛速度慢、易陷入局部最优的问题,提高算法的全局搜索能力。利用免疫粒子群算法训练BP神经网络的结构、初始权值和阈值,克服BP神经网络收敛速度慢、容易陷入局部最优等固有缺陷。仿真实验结果表明:在相同的精度和误差要求下,与普通粒子群算法相比,免疫粒子群算法训练后的BP神经网络具有更快的收敛速度。
1 BP神经网络模型
作为多层前馈型神经网络,BP神经网络的神经元具有n个输入,每个输入通过一个适当的权值w与下一层互连,人工神经网络的神经元模型如图1所示,网络输出可表示成
BP神经网络通常有一个或多个隐层,层中神经元的传递函数f(·)通常采用Sigmoid型变换函数(如正切型函数tansig或对数型函数logsig)将输入量映射为-1~1之间的连续输出量,实现从输入到输出的任意非线性映射。在输出层的神经元传递函数f(·)一般采用纯线性purelin变换函数。隐层的BP神经网络结构,如图2所示。其中n是输入向量的个数;S1、S2分别表示第1层(隐层)和第2层(输出层)的神经元数。
确定BP神经网络的结构后,利用输入输出样本集对网络进行训练,并采用误差反向传播的学习算法对网络中的权值wi和阈值θi进行学习调整,实现给定的输入输出映射关系。BP神经网络算法流程图如图3所示。
2 粒子群算法
2.1 粒子群基本算法
粒子群算法采用“速度-位移”模型解决优化问题。设一个维度为m的粒子群中,粒子i在d维空间的位置表示为:Xi=(xi1,xi2,…,xid),其速度表示为:Vi=(vi1,vi2,…,vid),其中i=1,2,…,m。此外,用Pi=(pi1,pi2,…,pid)和Pg=(pg1,pg2,…,pgd)分别表示粒子i以及整个种群当前搜索到的最优位置。
根据目标函数评估第k代粒子i的位置信息,计算该粒子的最优位置Pi和种群的最优位置Pg,并根据式(2)、式(3)生成下一代粒子的速度和位置信息
式中:w为惯性权重,它可按照式(4)根据进化代数Iter进行更新。c1,c2是加速系数,用于调节向个体最好位置与全局最好位置方向飞行的最大步长。η1,η2为均匀分布在0[,1]区间的随机数。
各粒子在解空间内搜索并跟踪个体极值点和全局极值点,直到达到规定的最大迭代次数或最小误差精度。
2.2 基于免疫记忆和免疫调节的粒子群算法
根据生物免疫系统的特性,在免疫算法中,将抗原看成问题的最优解,免疫产生的抗体看成问题的候选解,抗体不断排除抗原的过程即是候选解不断向最优解逼近的过程。抗体与抗原或抗体之间的相似程度用适应度函数表示,以建立抗体和抗原之间的评价机制。
免疫算法采用基于浓度选择机制的多样性保持策略,使粒子群中处于各适应值层次的粒子均保持一定浓度,以防止算法陷入局部最优。粒子xi的浓度定义如下
基于粒子浓度的选择概率公式
式中:f(xi)表示粒子xi的适应度函数值。
由式(6)可知,粒子i被选择的概率与其浓度成反比,使低适应值的粒子也能获得进化的机会,以克服粒子群算法在后期因粒子的“趋同性”导致在局部解空间上搜索效率差的缺点,提高群体的全局搜索能力。算法的流程如下:
Step1:初始化粒子群。根据基本粒子群算法随机产生种群大小为n的初始粒子群Pop0,并设置粒子的初始位置Xi0及速度Vi0,i=1…n。
Step2:计算粒子的个体适应值,确定当前粒子的个体极值Pi和全局极值Pg,并将Pg也设置为免疫记忆粒子,存入记忆库。
Step3:生成新粒子。先根据式(2)、式(3)更新上一代n个粒子的位置和速度,并再在群体中随机产生m个新粒子。
Step4:基于浓度的粒子选择。根据式(5)、式(6)计算新生成的n+m个粒子的选择概率,选择概率较大的n个粒子组成第k代粒子群Popk。
Step5:粒子群更新。将记忆库中的免疫记忆粒子Pg替换粒子群Popk中适应值较差的粒子,形成新一代粒子群体Popk+1。
Step6:当达到预设的最大迭代次数或最小误差精度要求,停止迭代并输出最优解Pg,否则转到Step2。
3 基于免疫粒子群BP神经网络的交通流量预测模型
3.1 交通流量数据的确定
在城市交通网络中,路段上某一时段的交通状况与临近时段中该路段以及上下游路段的交通状况关系密切。因此,预测时需参考与预测时段相关性强的前几个时段中上游路段的交通流量。此外,以周为周期的出行需求也能反映交通需求的规律性,如图4所示。t时刻路段a(即路口AB间)西进口的交通流入量Ia(t)受路口A北往东左转流量Oa-1(t)、由西往东直行流量Oa-2(t)、由南往东右转流量Oa-3(t)的影响。模型设定测量和预测周期Δt=3min,以Ia(t)、Ia(t-Δt)、Ia(t-2·Δt)、Oa-1(t)、Oa-1(t-Δt)、Oa-2(t)、Oa-2(t-Δt)、Oa-3(t)、Oa-3(t-Δt)以及路段a前一天的交通流入量Ia(t-24h)和路段a前一周的交通流入量Ia(t-7×24h)等11个观测数据作为预测t+Δt时刻路段a交通流入量Ia(t+Δt)的历史数据。
3.2 交通流量数据的预处理
依据输入层、隐层、输出层之间的传递函数,对输入向量进行初始化映射预处理,使其转换为对应区间内的连续输出量,实现从输入到输出的任意非线性映射。
模型选用只有一个隐层的三层BP神经网络,输入层、隐层和输出层之间的传递函数f(·)分别选用正切函数tansig和线性函数purelin,整个神经网络的输出范围为[-1,1]。依据式(7)将每个输入向量转换为[-1,1]之间的数值,使输入向量能较对称地分布在tansig函数的非饱和区内,以提高BP神经网络输入输出映射关系的逼近程度。
式中:x为原始输入向量,x′为预处理后的输入向量,xmax和xmin表示x的最大值和最小值。
3.3 确定神经网络的参数范围
3.3.1 确定隐层节点数、初始权值、阈值的初始化范围
模型中的三层BP神经网络的输入向量个数Input_num=11,输出向量个数Output_num=1。根据式(8)确定隐层节点数Mid_num的范围为[5,14]。
式中:α为1~10。因预处理后输入向量的范围为[-1,1],各节点初始权值的和的绝对值应小于1,以保证各神经元能在它们激活函数变化最大的位置进行初始操作,因此,初始权值和阈值的范围区间均为[-1,1]。
3.3.2 设置粒子适应度函数和粒子浓度函数
为寻找使神经网络误差最小的粒子,模型根据式(9)设置粒子的个体适应度函数Fitness(·)
式中:Ti是粒子i的理想输出,Oi是粒子i的实际输出。免疫粒子的浓度函数D(·)和浓度选择概率P(·)按照式(5)、式(6)定义。
3.4 免疫粒子群算法训练神经网络,确定网络的初始结构
根据3.3中确定神经网络结构的参数范围并输入训练样本,用免疫粒子群算法逐一对含有不同隐层节点数的神经网络进行训练,直至达到最大进化代数或最小误差精度要求。比较确定最优的神经网络结构,获得其最优隐层节点数、初始权值和阈值。
3.5 采用BP算法训练神经网络
利用误差反传思想对最优神经网络模型进行训练,迭代计算直至达到指定精度,最终输出该BP神经网络的初始权值、阈值、实际训练次数和误差。Matlab算法命令:NET=train(net,P,T)。其中net是免疫粒子群算法训练后所建立的神经网络,NET是用BP算法训练后的神经网络。P,T分别表示训练样本的输入向量和输出向量。
3.6 仿真输出与数据还原
用BP神经网络对交通流量进行仿真输出,Matlab算法命令为:Y=sim(NET,P1)。其中P1为输入向量,Y为输入向量P1的仿真输出。最后将仿真输出结果Y参照式(7)还原,得到预测后的交通流量。
4 交通流量预测实验及结果分析
实验用福州市杨桥中路(二环路往白马路方向)作为流量预测路段,并统计二环杨桥路路口连续两周9:30—10:30的交通流量,随机从记录集中抽取9:30—10:15中时间间隔为3 min的50组流量数据作为训练样本对神经网络进行训练。实验设置粒子种群大小为30,最大训练进化代数为1 000代,最小误差设置为0.000 001。
4.1 神经网络训练结果比较
免疫粒子群算法训练的BP神经网络,当训练到第166代时,网络误差精度达到0.000 001,如图5所示。基本粒子群算法训练BP神经网络的误差精度与训练步数的关系,如图6所示。快速BP算法训练神经网络的误差精度与训练步数的关系,如图7所示。比较可以看出,免疫粒子群算法训练BP神经网络的收敛速度最快。
4.2 仿真输出结果比较
抽取2015年11月11日10:15-10:30的5组交通流量数据,并分别用免疫粒子群IMPSO、基本粒子群PSO和快速BP算法训练神经网络进行仿真输出,得到以下结果:
实际测量的交通流量数据如下:
将仿真输出结果根据式(7)进行还原,其中xmax=51,xmin=26。交通流量预测值如表1所示。
从仿真输出结果与实际流量的对比可看出,相对于基本粒子群算法和快速BP算法训练的神经网络,免疫粒子群算法训练BP神经网络得到的仿真流量与实际流量的拟合程度较好,如图8所示。
辆
5 结束语
免疫粒子群算法能根据群体粒子间的信息沟通形成的群体智能进行全局搜索,避免了粒子群算法在群体收敛性和个体多样性平衡问题上的不足,利用免疫粒子群算法训练神经网络的结构,能克服神经网络收敛速度慢、容易陷入局部最优等固有缺陷。比较实验结果,免疫粒子群算法训练的BP神经网络能有效提高交通流量的预测精度,减小预测误差。
摘要:免疫理论中的基于浓度选择机制能避免粒子群算法在群体收敛性和个体多样性平衡问题上的不足,使改进后的粒子群算法优化BP神经网络参数的配置,提高短时交通流量预测的准确性。仿真实验表明:免疫粒子群优化后的BP神经网络可有效提高短时交通流量的预测精度,减小预测误差。