第24卷第5期 计算机仿真 2007年5月 文章编号:1006—9348(2007)05—0158—04 基于群体适应度方差的粒子群优化算法 李海楠,张学良,温淑花 (太原科技大学机械电子工程学院,山西太原030024) 摘要:由于粒子群算法在进化后期存在搜索速度较慢,容易陷入局部最优点以及搜索到解的时间较长且精度不高的缺点,所 以对算法进行改进的研究就成为一个必要的课题。通过利用混沌的遍历性和随机性的特点,引入基于Tent映射的混沌理论 机制,使算法在进化后期一旦陷入局部最优点就可以跳出局部最优点的位置,并且通过群体适应度方差的计算来判断当前 群体的离散程度或聚集程度,进而判断是否需要以一定的概率选择微粒个体去进行混沌更新。几个测试函数的仿真实验结 果也表明了该算法在搜索时间上、解的精度上都要远远优于标准的粒子群算法,是一种可行的优化工具,有一定的应用前 景。 关键词:混沌优化算法;帐篷映射;粒子群优化算法;群体适应度方差 中图分类号:TP273 文献标识码:A A PSo Algorithm Based on Colony Fitness Variance LI Hai—nan,ZHANG Xue—liang,WEN Shu—hua (Mechatronics Engineering Institute of Taiyuan Science and Technology University,Taiyuan Shanxi 030024,China) ABSTRACT:For the defects of particle swarm optimization algorithm such as lower search velocity,being prone to getting into local best position in later evolution phase,longer search time and lower precision,it is essential to make some researches about improvement of PSO.By making use of the ergodicity and randomicity characteristics of chaos, a chaos theory mechanism based on Tent mapping is introduced that may be helpful to guide particles to break away out of the position if it has gotten into local best position.And by calculating the colony fitness variance,it is also easy to judge its dispersion or congregation degree,furthermore,to make decisions whether to have chaos operations according to certain individual probability.The simulated experimental results show that it is prior to standard PSO in the search time and solutions’precision.Also it proves that it is a reasonable optimized tool and is promising. KEYWORDS:Chaos optimization algorithm;Tem mapping;Particle swarln optimization;Colony fitness variance 1 引言 收敛的现象;对于有些问题PSO算法虽然可以搜索到最优 粒子群优化算法(Particle Swarm Optimization,简称 解,但是也存在搜索时间较长,得到的解精度不高的缺点。 PSO)是由Eberhart和Kennedy于1995年提出的一种新型的 对此不少学者也提出了利用混沌的不同的改进方法,但是大 基于群聚智能的全局优化算法” ,它源于对鸟群、鱼群捕食 多数仍然是基于Logistic映射产生混沌序列的。由于Logistic 行为的模拟。自从PSO提出以来,一直受到人工智能等领域 映射的分布并不均匀,而可能导致搜索时间较长。为此,本 的研究人员的广泛关注。作为一种重要的优化工具,由于其 文利用Tent映射对初值的不敏感性,引入了基于Tent映射 编程的容易实现性以及算法需要设置的参数较少等优点,目 的混沌理论和群体适应度方差机制,尝试对算法的性能进行 前它已经被成功地用于了农业工程优化设计 、数字电路演 改进,以缩短算法的搜索时间,提高算法解的精度,并且解决 化、函数的优化、时变系统辨识和神经网络训练 '4 等许多的 陷入局部最优位置的问题。同时在混沌操作的时候,以一定 领域。 的概率选择性的取部分粒子执行操作也大大缩短了搜索时 虽然,PSO算法本身收敛速度较快,但是在进化后期收 间而又增加了算法的有效、可行性。 敛的速度明显变慢,容易陷入局部最优点,出现所谓的早熟 2粒子群优化算法概述 基金项目:国家自然科学基金资助项目(50475050) 在基本的粒子群算法中,系统首先随机初始化一群微 山西省高校科技开发项目(20051245) 粒,然后在以后的迭代中可行域内微粒不断追随当前最优的 牧稿日期:2006—04—03修回日期:2006—04—24 粒子进行搜索。假设在一个n维的目标搜索空间中,有Ⅳ个粒 .-———158 .——— 维普资讯 http://www.cqvip.com
子组成一个群体,其中第i个粒子表示为一个n维的向量 =出结果,否则,按公式(1)和(2)对粒子进行更新。 ( .1' ,2,三, ) (i=1,2,三,N), ≤ J≤ ( =1,2, ,Step 5对更新后的粒子重新进行适应度的计算,并更新 个体最优微粒和全局最优微粒。 Step 6按式(3)和式(4)计算当前粒子群的群体适应度 …n)其“飞行”速度表示为 =( . , f-2,…, . ) ,记 pbest(t)是第i个微粒的历史最优值,gbest是粒子群迄今为止 搜索到的最优解, 粒子群优化算法采用下列公式对粒子操作: (t+1)=wE(t)+c1 rand1()[pbest(t)一Xi(t)]+ c2rand2()[gbest—X (t)] (t+1)=X (t)+ (t+1)。 方差,若计算值小于给定的适应度方差,则按式(5)和(6)对 粒子群的随机的部分粒子进行混沌搜索;否则,更新粒子,返 回重新执行Step 5。 (1) (2) 适应度方差的计算公式 : 其中,埘是权重,t是迭代数,学习因子c 和c 是非负常 数,rand ()和rand2()是区间[0,1]上的随机数。 砉( 取值如下 : ㈩ (4) 其中 是第i个粒子的适应度值 是当前群体的平均适 应度方差值 是归一化因子,主要是为了限制 的大小,其 3 基于Tent映射的混沌粒子群优化算法 3.1 混沌现象和混沌优化算法的基本思想 混沌现象是无固定周期的循环行为,即非周期的具有渐 ,:{.m {。 一川,ma)【{。 一川≥ L1,others 进的自相似有序性的现象。混沌现象具有其独特性质:①随 机性即混沌现象具有类似随机变量的杂乱表现;②遍历性, 即混沌现象能够不重复地历经一定状态空间中的所有状态; : Tent映射 J: 【J 0≤ ≤ 2(1一 J) 1/2≤ J≤1 ( :1,2,三,Ⅳ :1,2,三,n) 一’ ” 一’“ (5) ③规律性,即混沌现象是有确定性的迭代方程产生的 。鉴 于混沌的这种遍历性、随机性和有规律的随机性,利用混沌 粒子群混沌搜索的概率 j: 1 的优化算法也就应运而生了。 混沌优化算法的基本思想 是把混沌变量从混沌空间 映射到解空间,然后利用混沌变量具有遍历性、随机性和规 P=1一i— — ite =1,2,L,Clter(6 Step 7 输出结果。当达到最大迭代数或者已满足给定 的收敛精度时,结束迭代,输出结果,即为要求的最优值。 由上述计算流程可以看出,本文是在标准的粒子群优化 算法的基础上,通过计算当前粒子群的群体适应度方差,来 判断是否需要进行混沌搜索,并通过混沌搜索使粒子群在算 法的后期可以跳出局部最小值,以尽快达到全局最优。 律性的特点进行搜索。混沌优化算法具有不对初值敏感、易 跳出局部极小、搜索速度快、计算精度高、全局渐近收敛的特 点。本文提出的混沌粒子群优化算法正是利用混沌优化算法 的这一点,将其与粒子群算法结合起来,以使粒子在进化后 期跳出局部最优点,而不至于早熟收敛。在标准粒子群算法 的基础上,对已经得到的粒子最优解进行混沌优化赋值,然 后在粒子群优化算法执行的过程中,根据群体适应度方差的 信息,改变粒子个体位置的更新策略,引导粒子群进行混沌 更新。这种算法有利于跳出局部最小值点,尽快寻到最优。 3.2 基于Tent映射的混沌粒子群优化算法 迄今为止,许多文献中提到的优化算法中都使用了 Logistic混沌映射产生搜索序列,而Logistic混沌序列的分布 是不均匀的,所以往往使搜索时间加长;帐篷映射具有均匀 4 算法的测试性能仿真 为了验证本文算法的可行性,本文运用了以下几个测试 函数来进行算法性能的计算: 测试函数1: O48 ・ F1= ( )=100(x 一 2) +(1一 1) ,一2.048≤ ≤2. 测试函数2: = 的分布函数,产生的混沌序列的概率密度分布函数初值敏感 性并不强,产生的混沌序列也具有全局遍历性,所以本文采 用Tent帐篷映射产生混沌序列。 ( )=。・5+ — I_ ,一 。。≤ ≤ 。。 测试函数3: = 具体计算流程如下: Step 1给定群体适应度方差or ,群体的规模Ⅳ,粒子变 量的维数n,混沌迭代的最大步数Citer。 Step 2随机初始化一群微粒的位置和速度。 =( )=∑[ 一10cos(2 )+10], l≤5.12,D 10 三个测试函数的理论最优解分别为 (1,1)=0, (0, 0)=0.5, (0,0,L,0)=0o混沌搜索前后的结果对比如表 1所示。 Step 3将初始的粒子设为对应的每个粒子的当前最优, 并通过计算适应度值比较得到当前粒子群的全局最优值。 Step 4判断是否满足收敛准则,若满足收敛精度,则输 一159— 维普资讯 http://www.cqvip.com
表1测试函数进行混沌前后的对比结果 测试函数进行混沌搜索前后的结果对比曲线图分别如 图1一图6。 图1测试函数l初始的最优解迭代曲线 图2测试函数l混沌变化后的最优解迭代曲线 图3测试函数2初始的最优解迭代曲线 ---——160---—— 图4测试函数2混沌变化后的最优解迭代曲线 迭代1()o次后的曲线变化图 J 4・5 _ I藿鼍冀罄| 羹l鹱 蠹毒鼍 ÷罄巷 蠹誊甏赣蘩|擎 蘩 囊囊 4 鼙冀餐 i臻0 琴囊I鬻 落琵臻舞纂一 慧 逛3.5 ||鬟警 lli襄 0i§ i 薯≤0_ ■冀黧囊 警s ?I |_0ll l-l ll∥_ I_000_ 管| !嚣z霉=2.5 0 _ 1_0_ 0|_。。00000 露15 j 00 0_ 0 主 .1 lll l|\|0l 薅 ll_ ll|l 0Il i 0.5 0l- 0— —0 0—¨≯|。 誊鬈 爨 鼍l毽E l 零 ≥l 誊冀|§誊鬈萋《| 孽鬟| 》 鏊 1 5 9 13 l7 21 25 29 33.37 41 45 49 5.3 57 迭代数 图5测试函数3初始的最优解迭代曲线 由上述结果数据比较分析和曲线图可以看出,在同样 维普资讯 http://www.cqvip.com
的时间内,加入混沌搜索后的粒子群优化算法很好的避免了 早熟收敛现象,并且精度上更接近于理论值。 1995.1942—1948. 李智,郑晓.粒子群算法在农业工程优化设计中的应用[J 3. 农业工程学报,2004,20(3):l5一l8. 5结论 H F哈尔姆斯,张其善译.序率理论基础与应用[M].北京:人 民邮电出版社,1980. 本文针对标准粒子群优化算法在进化后期搜索时间较 长以及搜索到的解的精度不高的缺点,根据帐篷映射对初值 的不敏感性,运用帐篷映射来产生混沌序列,将混沌优化算 法与粒子群优化算法结合了起来。不同于其它的混沌粒子 群优化算法,本文的算法是在初始化得到初始的所谓的最优 王能超.Walsh函数的演化生成[J].中国图像图形学报, 1996,l(3):231. 冯春,谢进,李柏林,陈永.混沌优化算法的研究[J].机械设 计与研究,2004,20(1):304~306. 张琳,王建华,朱志宇.一种混沌遗传混合算法及其在机动多 解的时候进行方差判断,运用混沌理论的遍历性特点使粒子 目标数据关联中的应用[J].华东船舶工业学院学报(自然科 跳出当前最优解的位置,同时通过一定的粒子混沌更新选择 学版),2005,19(1):5O一53. 概率使算法的搜索速度加快。试验的对比结果也表明,它的 吕振肃,志荣.自适应变异的粒子群优化算法[J].电子学报, 寻优性能得到了很好的改善,搜索速度明显加快,搜索时间 2004,32(3):16—420. 也大大缩短,对于相同的问题得到的解的精度也得到了很大 单梁,强浩,李军,王执铨.于Tent映射的混沌优化算法[J]. 的提高。 制与决策,2005,20(2):79—182. 混沌粒子群优化算法虽已不是首次提出,但是其性能的 杨俊杰,周建中,喻普,吴玮.基于混沌搜索的粒子群优化算法 改善仍然存在很大的问题,比如,1J 11如何很好的将混沌思想加 1J 1j [J].计算机工程与应用,2005,16:69—71. 入到粒子群算法中、如何用更合适的映射产生混沌序列、如 何加快搜索速度,缩短搜索时间等等。同时基于目前粒子群 [作者简介] 算法在多目标问题中的应用研究较少,所以尝试将混沌思想 李海楠(1979.8一),女(汉族),山西朔州人,在读 加入到多目标优化算法中以改善问题的性能也是下一步研 硕士研究生,研究方向:人工智能; 张学良(1964.3一),男(汉族),山西新绛人,博士 究的方向。 生导师,教授,研究方向:人工智能,结合面,有限元 等; 参考文献: 温淑花(1792.6一),女(汉族),山西新绛人,教授,研究方向:人工 [1]J Kennedy,R C Eberhart.Particle 8walln optimization[C].Proc. 智能,数控机床,机制工艺等。 IEEE Int.Conf.Neural Netw0rks,Piscataway,NJ:IEEE Press, (上接第24页) [2]R M Hinterhoelzl,R A Schapery.FEM Implementation of a Three [9]B D Lubachevsky.Geometric Properties of Random Disk Pickings ..Dimensional Viscoelastic Constitutive model for Partic ̄ate Com.. [J].Journal of Statistical Physics vo1.60(6/5)1990.561— posites with Damage Growth[J].Mechanics Of Time—Dependent 583. Materials 8:65—94,2004.65—94. [10]B D Lubachevsky.Disks VS.Spheres:Contrasting Properties Of [3]S Ozupek.Constitutive Equations For Solid Propellants[D].PHD Random Packing[J].Journal of Statistical Physics vo1.64 1991. Dissertation The University Of Texas at Astin 1997. 501—524. [4] K Matous.Damage evolution in particulate composite materials [11]G M Knot,et a1.Random Packing of Heterogeneous Propelnats 【J].International Journal ofSolidsand Structures40 2003.1489 【J].AI从Journal,2001,39(4):678—686. —1503. [12]S V Kochevets.Random Sphere Packing Model of Heterogeneous [5]N AFava8.Constitutive Response and Damage in Solid Propellants Propelnats[D].Doctoral Thesis University of Illinois at Urbana [R].AIAA 2005—4348. —Champaign,2002. [6]F Xu,et.a1.Finite Element Modeling of Porous Sohd Propellants [R].AIAA 2005—4349. 【作者简介】 [7]K Matous,P H Geubelle.multiscale modeling of particle debond— 史佩(1971一),男(汉族),甘肃兰州人,讲师,硕 ing in reinf0rced elastomers subjectde to finite deformations[J]. 士,主要研究方向:复合固体推进剂损伤和断裂; International Journal for Numerical Methods in Engineering 2006. 李高春(1978一),男(汉族),浙江I临海人,博士生, 190—223. 主要研究方向固体推进剂多尺度模型; [8]S W Park.Fracture Toughness For Microcracking in a Viscoelsatic— 李昊(1978一),男(汉族),安徽安庆人,博士生, Particulate Composite[J].Journal of Engineering Mechanics 主要研究方向推进剂损伤。 1999.722—725. .--——161・--——
因篇幅问题不能全部显示,请点此查看更多更全内容