一种基于遗传算法改进的粒子群优化算法
第28卷第9期2011年9月计算机应用与软件
ComputerApplicationsandSoftwareVol.28No．9Sep．2011
一种基于遗传算法改进的粒子群优化算法
潘勇
1
2
1
郭晓东
2
（山东大学信息科学与工程学院（山东大学网络与信息中心
山东济南250100）山东济南250100）
在研究标准粒子群算法和遗传算法的基础上，介绍一种加入遗传选择，交叉算子以及变异算子的扩展算法，以提高粒子
群算法摆脱局部极值点的能力，并且算法具有较快的收敛能力。摘
要关键词中图分类号
遗传算法TP301．6
粒子群算法
交叉算子
A
变异算子
文献标识码
ANIMPROVEDPARTICLESWARMOPTIMISATIONALGORITHMBASED
ONGENETICALGORITHM
PanYong1
1
2
GuoXiaodong2
（SchoolofInformationScienceandEngineering，ShandongUniversity，Jinan250100，Shandong，China）
（NetworkandInformationCenter，ShandongUniversity，Jinan250100，Shandong，China）
AbstractBasedonstudyingstandardparticleswarmoptimisationandgeneticalgorithm，thispaperproposesanexpandedPSOby
introducinggeneticselection，crossoveroperatorandmutationoperatorfromgeneticalgorithm，whichmakesPSOsearchprocessgetridoflocalminimumandhasarapidconvergencerate．Keywords
Geneticalgorithm
Particleswarmoptimisation（PSO）
Crossoveroperator
Mutationoperator
0引言
在解空间中进行搜索，经过迭行经验来调整自己的速度和位置，
代找到最佳解。在每次迭代中，粒子通过跟踪两个极值来更新自己：即个体极值pbest（粒子自身目前所找到的最优解）和全局极值gbest（整个粒子群目前寻找到的最优解）。粒子更新本身速度与位置的公式为：
+1nnnnvn=vnxyxy+c1×r1×（pbestxy－uxy）+c2×r2×（gbesty－uxy）（1）
+1n+！
un=unxyxy+vxy
粒子群优化算法PSO（ParticleSwarmOptimization）是一种
进化计算技术，该算法源于对鸟群捕食的行为研究，通过模拟鸟群觅食过程中迁徙和协同合作行为而提出的一种智能随机优化
也是一种迭代优化算法即算法。其功能与遗传算法非常相似，
系统初始化为一组随机解，经由迭代来寻找最优解。与传统的
粒子群优化算法简单容易实现并且没有许遗传算法（GA）相比，
多参数需要调整，因此广泛运用于神经网络、模式分类以及函数
优化等领域。但是，粒子群算法在处理复杂问题时容易陷入局部最优解上而停止不动，即所谓的早熟收敛现象。本文在研究
提出了一种加入遗传选择、标准粒子群算法和遗传算法基础上，
交叉算子和变异算子的粒子群优化算法，改进了算法的全局搜
索能力、局部搜索能力和收敛速度。通过经典函数的优化计算，验证了改进算法的有效性。
（2）
x表示粒子的编号，y表示粒子位置或速度的维，n表示迭式中，
nn
uxy分别是第x个粒子在第n次迭代中第y维的代代数，即vxy，c1，c2∈［0，4］；r1，r2∈［0，1］，速度和位置；c1和c2是学习因子，
n
是一组随机数；pbestxy是第x个粒子在第y维的个体极值的坐
标；gbesty是群体在第y维的全局极值的坐标。
n
1．2粒子群优化算法的特点
粒子群优化算法与遗传算法相比较，两者功能相似，但前者具有以下一些特点：
（1）搜索过程是通过并行性从一组解迭代到另一组解；（2）采用实数进行编码，算法简单易实现；（3）粒子运行具有随机性，可以搜索不确定的复杂区域；（4）粒子具有学习功能，可以及时更新自己的位置和速度；（5）解的质量不依赖初始点的选取，保证收敛性；（6）具有全局/局部搜索能力。
收稿日期：2010－06－16。潘勇，硕士生，主研领域：智能信息处理，集成电路设计，嵌入式开发。
1
1．1
粒子群优化算法基本原理和特点
粒子群优化算法基本原理
标准粒子群优化算法是粒子群优化算法的一般形式。其寻
优过程就是个体根据自己到达过的最佳位置和其他个体到达过
的最佳位置来改变自己的速度及位置，从而趋向全局最优的过程。PSO算法初始化随机粒子后，粒子通过对个体和群体的飞
（3）对粒子进行遗传选择、交叉和变异运算；
基于以上特点，粒子群算法广泛应用于函数优化、图像分
割、神经网络、机器学习、数据挖掘、自适应控制、人工生命、生产调度和组合优化等众多领域。但粒子群优化算法也有一些缺点，例如：很容易陷入局部极值点，搜索精度不高等。因而，本文提出了一种基于遗传操作的粒子群优化算法。
（4）重新计算粒子的适应度值，并对适应度排序，更新粒子的速度和位置；
（5）对算法收敛次数进行计算，把当前粒子作为种群的个体最佳pbest，把粒子群中适应度最小的粒子作为全局最优gbest，并按式（6）和式（7）进行运算，达到最大循环得到最优值和最小值；
（6）反复执行步骤（3）到（5），直到满足收敛条件；（7）输出最优解。
2
2．1
基于遗传操作的改进的粒子群优化算法
改进的粒子群优化算法思想
遗传算法的基本思想是基于达尔文进化论和孟德尔的遗传
经过编码组成初始群体后，遗传操作的变异理论。在该算法中，
任务就是对群体的个体通过优化搜索的过程，一代又一代地优
化，从而逼近最优解。遗传操作包括三个基本遗传算子：选择、交叉和变异。
标准粒子群优化算法不具备选择、交叉和变异操作，因此，本文就是在粒子群算法中引进了遗传算法的三种遗传操作，通过改进种群的分割策略来提高粒子群算法摆脱局部最佳值的能力和提高搜索精度的能力。
交叉就是把两个父代个体的部分结构加以替换重组而生成
从而使遗传算法的搜索能力得以提高。本文算新个体的操作，
法采用的是实值编码，因而，遗传操作中交叉通过算术交叉算子
i
xjn（i≠j）进行算术交叉，那来实现。设在n时刻的两个个体xn，么交叉后在n+1时刻产生的两个新个体为：
xin+1=αxjn+（1－α）xin
（3）
3算法仿真与实验结果分析
为了验证改进的粒子群优化算法的寻优性能，本文选用的
实验函数如下：
（1）Sphere函数：
f1（x）=
D
∑x
i=1
2
i－100＜xi＜100
该函数是简单的单峰二次函数。
（2）Rastrgin函数：f2（x）=
D
∑（x
i=1
2i－10cos（2πxi）+10）－100＜xi＜100
该函数是具有大量局部极值点的多峰函数，非常难寻到全局最优值。
本文将粒子群规模设为N=40，粒子群的最大迭代次数为MaxDT=500，所有函数的搜索空间维数为D=20，学习因子c1=1．4962，c2=1．4962，惯性权重w=0．7298，收敛精度为eps=10－10。函数f1（x）和f2（x）的标准粒子群算法和改进的粒子群Sphere优化算法函数的运算20次平均优化结果图如表1所示，函数和Rastrgin函数优化曲线分别如图1和图2所示。
表1
两种算法平均优化结果
xjn+1=αxin+（1－α）xjn（4）
式中，α为一参数，当α为常数时，交叉运算成为均匀算术交叉；当α为变量时，此时进行的是非均匀算术交叉。
变异运算模拟了生物进化中的基因突变的过程，将基因序列上的某一基因变异为等位基因。主要作用有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子逼
通过变异算子的局部随机搜索能力可以加速近最优解邻域时，
以防止出向最优解收敛。二是使遗传算法可维持群体多样性，
i
用xn代替粒子群中的第i个粒子在现未成熟收敛现象。在此，
i
D维空间的位置即xid，用历史最优个体xmax代替粒子群算法中
函数算法
理论最优值0000
平均最优值
0．[**************]2．[**************]E-1233．[**************]8．[1**********]097
平均收敛迭代次数74．4100．6152．1208．9
Sphere标准粒子群优化算法函数改进的粒子群优化算法Rastrgin标准粒子群优化算法函数改进的粒子群优化算法
的个体最佳pbest，用历史最优种群xx
imax
nxyjmax代替全局最优gbest，用n
y
的累差Δximax代替vn+1xy，其中Δxi
max由式（5）求得：
iiii
（5）Δxmax，n=Δxmax，n－1+（Δxmax，n－Δxmax，n－1）/n
将上述公式代入式（1）和式（2），得出引进变异算子的速度
与位置更新表达式为：iiinjnΔxmax，n+1=Δxmax，n+c1×r1×（xmax－uxy）+c2×r2×（xmax－uxy）
+1i
un=unxyxy+Δxmax，n+1
（6）（7）
根据上述公式的改进，使粒子群具备了学习能力，同时也提
高了粒子群的局部和全局搜索能力。
2．2改进的粒子群优化算法步骤
改进的粒子群优化算法步骤如下：（1）初始化c1、c2、r1和r2等因子，粒子群规模、惯性权重、最
图1
Sphere函数的寻优曲线图
图2
Rastrgin函数的寻优曲线图
收敛精度和搜索空间维数等参数以及粒子的速度大迭代次数、和位置；
（2）计算各个粒子的适应度，并对适应度排序，把当前粒子作为种群的个体最佳pbest，把粒子群中适应度最小的粒子作为全局最优gbest，并按照式（6）和式（7）计算最佳解，如果达到最大迭代次数或收敛精度，执行步骤（7）；
由表1可知，对于Sphere和Rastrgin两个函数来说：改进的粒子群优化算法比标准粒子群优化算法具有更好的寻优能力，能通过数值比较也可以发现，改进的粒子找到更佳的平均最小值，
群优化算法收敛性能和搜索能力比标准粒子群优化算法有比较Sphere函数的迭代次数比达到了1．35，Rastrgin函数的大的提高，
迭代次数比达到了1．37，摆脱局部最优的效果比较明显。同时，
由图1和2的寻优曲线图可了解到：对于Sphere函数，从寻优曲线来看，改进的算法迭代的次数为100次左右，标准优化算法为52次左右，改进的算法能达到更小的适应度值，从而扩大了搜索改范围和提高了收敛精度；对于更加复杂的多维Rastrgin函数，进的算法寻优曲线远比标准算法寻优曲线平滑，说明了改进的算法稳定性更好，效果也更明显，从两个函数寻优曲线达到收敛迭代次数上来看改进的粒子群优化算法可以有效地摆脱局部最优，避免了早熟收敛，从而寻到最佳的全局最优。综上所述，表明本提高收敛速度、增强摆文所提出的新算法在克服早熟收敛问题、
脱陷入局部最优值、改善局部和全局搜索能力方面效果明显。
入第四部分：主观题。学生在规定的60分钟内答题，最后提交。至此，考试全部结束。
2．4．2
实验平台
同在线考试子系统一样，实验之前必须阅读实验规则，选择实验科目。本文中选择C语言实验。
实验题可查看图片，若图片存在，则显示图片，若不存在对应图片，则弹出错误提示。
2．5系统特点
从实际应用出发，对比其他考试特点，可以得出本系统的特
除了能再现考试之外，整合了上传下载、点：1）功能较为全面，
实验平台、在线留言等功能板块；2）操作界面美观，给使用者一种美感；3）多选题自动评分，主观题人工评分，实现了电脑评分与人工评分的结合；4）实现对考试信息的汇集存储，彻底实现了无纸化。
4结语
本文对遗传算法和标准粒子群优化算法进行了结合研究，从理论上分析了标准粒子群优化算法的缺点及其改进方法，提出了一种带有遗传操作的粒子群优化算法。标准PSO中在经过选择、交叉和变异操作后，增强了粒子群的更新能力和跳出局部最验证了这一改优的能力。通过用两个测试函数进行了性能测试，
进算法在解决局部寻优和早熟收敛的问题上有着良好的效果。
3讨论
［8－10］
参考了其他考试系统，吸收了部分设计理念，在收集
了大量试题，实验信息之后，将这些信息归类。以VisualStudi-o2005为开发环境，C#作为开发语言和ASP．NET2．0开发工具，经过数月时间开发，不断调试，完成了基于ASP．NET2．0的在线考试系统。本系统与在线考试考务管理系统的在线考试系统更胜一筹。
本系统可以更好地服务于大专院校，操作简便，支持进一步构建实验自动评分系统，实时聊天系统等等。系统拓展的关键在于对各种实验平台的掌握与考试需求信息的收集。在系统的加强考试子系统与实验平台对图片的处理后续开发与应用中，
能力，开发出更加完善的考试系统，以顺应不断变化发展的潮流。
［11］
［1］
参考文献
［1］WangLei，KangQi，XiaoHui，etal．AModifiedadaptiveparticleswarm
optimizationalgorithm．IEEE，Shanghai，2005：209-214．
［2］AhmedAAEsmin，GermanoLambert-Torres，AntonioC．Zambronide
Souza，Ahybridparticleswarmoptimizationappliedtolosspowermini-2005，mization［J］．IEEETRANSACTIONSONPOWERSYSTEMS，20（2）：859-866．
［3］DanielWBoeringer，DouglasHWerner．ParticleSwarmOptimizationVersus
GeneticalgorithmsforPhasedArraySynthesis［J］．IEEETRANSACTIONSONANTENNASANDPROPAGATION，2004，52（3）：771-779．［4］SangwookLee，SangmoonSoak，SanghounOh，etal，Modifiedbinary
J］．NaturalScience，2008：1161-1166．particleswarmoptimization［
［5］HollandJH．AdaptationinnaturalandartificialSystemsAnnArbor
［M］．Michigan：TheUniversityofMichiganPress，1975．
［6］ChatterjeeA，SiarryP．Nonlinearinertiaweightvariationfordynamic
adaptationinparticleSwarmoptimization［J］．ComputersandOpera-2006，33（3）：859-871．tionsResearch，
［7］胡旺，．软件学李志蜀．一种更简化而高效的粒子群优化算法［J］
2007，18（4）：861-868．报，
［8］黄友锐．智能优化算法及其应用［M］．北京：国防工业出版
2008．社，
，基于B/S结构
相比，无论在界面设计还是功能适用方面都
参考文献
［1］陈志权．基于ASP．NET的在线考试考务管理系统［D］．中山大
2009．学，
［2］徐龙．基于ASP．NET技术的电子留言板设计与实现［J］．电脑知
93（25）：74-76，93．识与技术2009，
［3］李伟红．SQLSERVER2000实用教程［M］．中国水利水电出版社，2005．［4］郭常圳，李云锦．ASP．NET网络应用开发例学与实践［M］．清华大
2006．学出版社，
［5］林少景．ASP．NET编程百例通［M］．清华大学出版社，2002．［6］林邦杰．深入浅出C#程序设计［M］．中国铁道出版社，2005．［7］陈钟，．清华大学出版刘强，张高．C#编程语言设计与开发［M］
2004．社，
［8］邵维．基于ASP．NET的中学在线考试系统的研究与实现［D］．天
2008．津师范大学，
［9］曾长军，张新令．基于．NET的课程资源与教学管理平台设计与
2010（04）：开发［J］．湖北经济学院学报：人文社会科学版，176-178．
［10］宋继红，曹悦．基于ASP．NETAJAX的网上考试系统的设计与实
2009（25）．现［J］．电脑知识与技术，
［11］郑瑞卿．基于B/S结构的在线考试系统的实现［D］．南昌大
2007．学，
（上接第165页）
目有所不同。因此在子系统中设置了考试科目，供学生选择。系统数据库中建立了有关考试科目与试题的数据表，考试科目的试题随机出现在考试中。考试正式开始之前，学生需阅读考然后选择考试科目。试规则，
考试正式开始，第一部分出现的是单选题，单选题部分考提交该部分答题，系统自动给出评分。进入第二部分：多选完，
题，学生需在二十分钟时间内答完5道多选题，每小题4分。答完多选题，提交，系统自动给出评分。接下来，进入第三部分：填空题，学生在10分钟内完成答题，否则系统自动提交。最后，进