基于动态混沌扰动的粒子群优化及其应用

混沌粒子群优化算法¨计算机科学2004V01．31N-o．8高鹰h2谢胜利1(华南理工大学电子与信息学院广州510641)1(广州大学信息机电学院计算机科学与技术系广州510405)2摘要粒子群优化算法是一种新的随机全局优化进化算法。

本文把混沌手优思想引入到粒子群优化算法中，这种方法利用混沌运动的随机性、遍历性和规律性等特性首先对当前粒子群体中的最优粒子进行混池寻优，然后把混沌寻优的结果随机替换粒子群体中的一个粒子。

通过这种处理使得粒子群体的进化速度加快t从而改善了粒子群优化算法摆脱局部极值点的能力，提高了算法的收敛速度和精度。

仿真结果表明混沌粒子群优化算法的收敛性能明显优于粒子群优化算法。

关键词粒子群优化算法。

混沌手优，优化’ChaosParticle SwarmOptimizationAlgorithmGAOYin91”XIESheng—Lil(Collegeof Electronic＆InformationEngineeringtSouthChina University ofTechnology，Guangzhou510641)1(Dept．of ComputerScience andTechnology．GuangzhouUniversity·Guangzhou510405)2Abstract Particle swarmoptimizationis anewstochasticglobaloptimization evolutionaryalgorithm．Inthis paper，the chaotic searchis embeddedintooriginalparticleswarmoptimizers．Basedon theergodicity，stochastic propertyandregularityofchaos，fl newsuperiorindividualisreproducedbychaoticsearchingonthecurrentglobalbest individ—ual。

混沌粒子群优化算法理论及应用研究的开题报告一、选题背景粒子群优化算法（Particle Swarm Optimization, 简称PSO）是一种基于种群的随机搜索算法，由于其方法简单、易于实现、高效且具有全局优化能力等特点，已经成为了求解多维函数优化问题的重要工具之一。

PSO起源于1995年Eberhart和Kennedy提出的鸟群觅食行为的模拟，近年来随着PSO算法在优化问题中的成功应用，PSO算法也得到了越来越多的关注与研究。

混沌理论是一种新近发展起来的复杂科学，具有良好的非线性、随机性和强敏感性等特点，对于许多问题的理论解释和应用有着很好的作用。

混沌粒子群优化算法（Chaotic Particle Swarm Optimization, 简称CPSO）是将混沌模型应用于PSO算法的一种新型优化算法。

CPSO算法不仅能够充分利用混沌迭代过程中的随机性和全局搜索能力，还能避免PSO算法中易于陷入局部最优解的缺点，能够更好地求解复杂优化问题。

二、研究目的和意义PSO算法在解决优化问题中已经得到了广泛的应用和研究，但PSO算法中易于陷入局部最优解的问题一直是其应用的难点之一。

而CPSO算法则在这一方面具有更好的性能。

本文旨在深入研究CPSO算法的原理及其应用，通过对比实验来验证CPSO 算法的优劣性能，为优化问题的解决提供更好的技术手段。

三、研究内容和方法（一）研究内容1. PSO算法的基本原理及其不足之处。

2. CPSO算法的基本思想、数学模型和迭代过程。

3. CPSO算法的参数设置及其影响因素的分析。

4. CPSO算法在求解不同类型的优化问题中的应用及效果对比分析。

5. 实际问题的优化应用。

（二）研究方法1. 阅读相关文献，综述PSO和CPSO算法的研究现状。

2. 探讨CPSO算法的数学模型及其迭代过程，并对CPSO算法的参数进行分析。

3. 进行基于标准测试函数的对比实验，比较CPSO算法与其他优化算法的性能差异。

基于混沌思想的可多步搜索的新型粒子群优化算法¨作者：林博艺来源：《赤峰学院学报·自然科学版》 2012年第20期林博艺（泉州信息职业技术学院，福建泉州 362000）摘要：针对基本PSO算法在全局优化中收敛精度低和易陷入局部极值的不足，提出一种基于混沌思想的多步搜索的新型的粒子群优化算法(CMPSO).该算法先引入混沌思想对粒子种群进行位置初始化，然后再引入多步搜索，最后引入概率条件的选择性重新初始化.通过与其它三个改进算法比较，结果表明CMPSO算法的有效性.关键词：粒子群优化；多步搜索；混沌中图分类号：TP18 文献标识码：A 文章编号：1673-260X（2012）10-0015-051995年Kennedy博士和Eberhart教授提出粒子群优化（Particle Swarm optimization，PSO）算法[1,2]，它是一种基于群体智能(Swarm Intelligence，SI)仿生的优化方法，该算法基本思想是源于对鸟群捕食行为的模拟.由于其原理简洁，参数较少，易于实现等优点，成为继遗传算法后的研究热点之一.其已被广泛的应用于函数优化[3]，工程优化[4]，参数估计[5-9]，电力系统优化[10-14],控制器设计[15-7]，机器人路径规划[8]等.类似于GA，PSO算法也有收敛精度低，早熟等不足[18-20]，因此继Kennedy和Eberhart之后有许多改进型PSO算法提出.如：引入惯性权重，加入微分演化或是交叉操作，加入混沌初始化，与其它智能算法混合等，这些算法在增加算法得杂度的前提下，都不同程度的提高算法的性能.但这样做都有悖于算法的初衷：简洁实效.本人在分析基本PSO算法不足的基础上，引入混沌初始化，并将多步式位置更新引入其中，并通过实验来验证我们改进的有效性.1 PSO简介一个有N个粒子的种群，在D维空间中进行寻优过程的算法的基本递推公式：其中：i=1，2，…，N；d=1，2，…，D；Xid(k+1)，Xid(k)，Vid(k+1)，Vid(k)分别表示第i个粒子在k+1和k代的空间位置对应的第d维值及运动速度对应的第d维值；ω为惯性权重；c1，c2分别表示粒子个体和粒子群体的加速权重系数；r1，r2均为0到1之间的随机值，分别表示粒子个体和全体的加速权重；Pid与Pgd分别表示第i个粒子个体在搜索过程中自身的历史最佳位置和整个粒子群体目前找到的最佳位置.2 新的PSO算法2.1 PSO算法陷入局部收敛的原因基本PSO算法易陷入局部极值的原因在文献[3]做了详细的分析，并通过数学推导得到式(3)：由式(3)可知，每个粒子不仅受它自己找到的当前最优解的吸引，而且还受全局最优解的吸引.如果这两个最优解都是局部最优值，粒子将被这两个值吸引而很快重复相同的搜索轨迹.由于式(1)没有使算法跳出局部最优的机制，随着进化迭代的进行，粒子最终将聚集到由个体极值位置P0和全局极值位置Pg共同决定的位置P*上，如果P*是某个局部最优位置，且所有粒子在向位置P*靠拢的过程中若没有找到优于Pg的位置，则基本PSO的进化过程将很难跳出该局部最优，粒子将逐步收敛到P*.另外，结合式(1)还可看出，惯性权重仅能改变粒子的搜索步长，不能改变其运行方向，从而不能克服早熟问题.可见，加强搜索多样性、使算法跳出局部最优，是提高算法收敛速度和寻优精度的重要措施.本文从以下三个方面入手，提出一种基于混沌思想和多步搜索的PSO算法.2.2 初始化粒子群初始位置混沌序列的运动特点：随机性和遍历性及规律性.本文采用混沌序列的这一特点对粒子进行初始化分布，这样可以更好的体现初始种群的多样性，为在寻优空间中找到最优解和加快收敛速度奠定较为坚实的基础.Logistic映射是一个典型的混沌系统，首先利用Logistic映射产生混沌序列，如式(4)：式(4)中u为一个常数，u∈[3.56，4.0]，称为控制参量，主要用来控制系统的混沌程度，L(d)∈(0，1)，d=1，2，3，…，D.第二步对处于D维中间中的N个粒子，首先产生N个初始值：L1(1)，L2(1)，…，Li(1)，…，LN(1)，把这N个初始值代入式(4)中进行D次迭代运算，将产生的结果代入式(5)中运算：式(5)中：Xi,d表示第i个粒子第d维坐标，而Li(d)是第i个粒子用Li(1)经过d次迭代运算产生的值，Maxd，Mind分别是第d维的上下限.2.3 引入多步搜索由公式(1)知，粒子的运动失量由惯性项Vid(k)，自身认知成分项c1*r1*(Pid-Xid(k))，社会认知成分项c2*r2*(Pgd-Xid(k))三项决定的，受人类活动行为的启发可知：人类在做事时，有时会惯性式的执行，有时会加以总结靠自身的经验，有时却也会对所有信息加以汇总考虑然后再去做事（基本PSO算法则是这种方式）[19].本文在尽量不增加PSO算法的基础上，对运算过程中的三项结果直接加以分析迭代：由式(8)可知，粒子在搜索过程中，先利用自身惯性做第一步位移Xid(k+1)2，如果此步位移得到搜索位置最好，则取之；否则进一步利用自身认知经验项得到位移点Xid(k+1)３，同进也可再利用社会认识经验得到Xid(k+1).最后比较Xid(k+1)，Xid(k+1)2，Xid(k+1)3，取其最优者做为下一步的运动位置更新点.综上所述，改进的PSO算法具有PSO算法的基本特点，简单，易实现，运算量较小等优点，同时兼顾了搜索效率和收敛精度，此外，新算法并未引入新的参数，这样就易于通用，因为新算法将搜索的中间值加以利用和分析，省去了参数调节的烦琐计算，因此新算法较简单通用.2.4 重新初始化在粒子群的进化过程中，当得到的最优解在连续的M次迭代中都无变化时，用一个计数器记录到目前为止停滞的代数T，可以这样设定：如果连续两次得到的最优解相同则将T增1，否则将其清0；当T≥M时，则说明算法可能停滞，在M次的迭代中，粒子没有能力跳出局部最优.此时，为加强粒子的对空间的搜索可以对某些粒子在概率性选择下进行随机重新初始化.搜索空间区域为：[XMind,XMaxd]，在其内部重新初始化即为：if(T>M and rand()>?茁Xi,d(k+1)=XMind+(XMaxd-XMind)*rand() (9)其中：β为事先设定的一个阈值，可取[0.8,１].在迭代过程中，当粒子有可能陷入局部极值时，为避免过大的破坏粒子原有的运行状态，仅选择少部分粒子进行重新初始化.3 实验及结果分析3.1 实验设计选用4个典型基准测试函数，与基本PSO及sPSO[18]，tPSO[18]，HPSO-TVAC[15]等算法比较，验证CMPSO的可行性.这4个常用的基准函数、函数形式、搜索范围及维数、理论极值(极小值)和优化目标精度等见表1；其中：HPSO-TVAC，sPSO和tPSO 参数设置与文献[18]与文献[15]一致，CMPSO参数设置为：?棕0=1.2,c1=c2=2,?棕=?棕0*exp(-0.5*k*k),?滋=3.99,Max=10，β=0.8.对算法性能评估采用如下方法[18]：(1)固定迭代次数下的实验效果对比；(2)固定收敛精度的实验效果对比.3.2 实验结果分析3.2.1 固定迭代次数下的实验效果对比固定代数下的的实验结果对比如图1所示，实验结果是采用独立运行50次后的平均值给出.其中：粒子数目为50，进化代数为1000；图1(a)~图1(h)是五种算法分别在测试函数f1~f8的适应度值的对数曲线(为方便显示统一加10-10做为适应度的截止值).从图1-1(a)到图1-1(h)可以看出，PSO算法在1000代内都难以收敛到目标精度，其他改进算法表现在总体上均优于PSO算法.下面依次详细分析.从图1-1中可以看出，CMPSO算法较其它四中算法均得到较大改进，对8个函数的优化来看基本上在100代以内都能收敛到目标精度，有的函数甚至在20代以内都能收敛到目标精度，可以说CMPSO算法表现是较其它算法是最佳的.其它算法中sPSO，再次是tPSO算法收敛情况较好.在对Rosenbrock函数f6（一个经典的复杂优化问题，取值区间内平坦，为算法提供了少量的信息，要收敛到全局最优位置的机会非常小，所以它一般用来测试算法的执行效率[19]）及Schaffer’s函数f8这两个函数上，CMPSO将其改进后的开求精能力和开挖能力充分表现出来：如Rosenbrock函数f6，其在４00代后又进一步向高精度深度求精；在Schaffer’s函数f8表现更为明显，在1000代以内不断向更高精度逼进，充分体现了其对空间的开挖能力和求精能力.因此，CMPSO算法改善了PSO算法对空间的全局搜索效果，提高了算法的收敛速度和精度，较为有效的避免了早熟问题，与其它改进算法相比也是有较大的改进，如：较tPSO算法参数少，更具有通用性；较sPSO收敛速度和精度也有较大的提高.因此，在固定迭代次数的前题下，CMPSO算法改进有效性得到有力证实.3.2.2 固定收敛精度的实验效果对比作如下规定：同样是种群规模为50，在表1指定的收敛精度下，对达到收敛精度所需的迭代次数进行比较.由达到目标精度的最小值，均值，最大值，方差等方面加以考察.表2是由表１指定精度下独立50次所得(如果算法在10000代内还没有收敛到目标精度于以终止).由表2可见：在收敛速度上PSO算法最差，其次是HPSO-TVAC，这两个算法在大部分情况下不能收敛到目标精度，而其它三种算法基本上均能收敛到目标精度.CMPSO在固定收敛精度下，其收敛速度均优于其它算法，而sPSO在收敛速度上优于tPSO，三者中CMPSO表现最佳，说明了改进有效性.4 总结本文在分析基本PSO算法收敛精度低，早熟等不足的基础上，受自然现象的启发，提出了一种改进型的PSO算法.用经典的测试函数来测试算法，经验证，充分表明了改进算法的有效性.参考文献：〔1〕Kennedy J, Eberhart R C. Particle swarm optimization [C]. In: Proc. of the IEEE Internationa1 Conference on Neura1 Networks, Perth, Australia. 1995,1942-1948.〔2〕Shi Y, Eberhart R C. A modified particle swarm optimizer [C]. In: Proc. of the IEEE International Conference on Evolutionary Computation. 1998,69-73.〔3〕Clerc M, Kennedy J. The particle swarm: Explosion stability and convergence in a multi-dimensional complex space [J]. IEEE Trans. on Evolutionary Computation. 2002,6(1):58-73.〔4〕武忠勇，缑锦，赵志强.具有自适应邻域探测机制的改进型PSO算法[J].小型微型计算机系统，2010，31(9)：1938-1945.〔5〕郑宣耀，李欢，滕少华.自适应变邻域混沌搜索微粒群算法[J].计算机工程与应用，2007，43(31)：90-93.〔6〕赵娜，张伏生，魏平，等.基于改进多粒子群算法的电力系统无功优化[J].西安交通大学学报，2006，34(4)：463-467.〔7〕张勇，巩敦卫，张婉秋.一种基于单纯形法的改进微粒群优化算法及其收敛性分析[J].自动化学报，2009，35(3)：289-298.〔8〕Parsopoulos K E, Vrahatis M N. UPSO: A unified particle swarm optimization scheme[C]. In: Proc. of the ICCM SE 2004. Attica. 2004:868-873.〔9〕Mendes R, Kennedy J, Neves J. The fully informed particle swarm: Simpler, maybe better [J]. IEEE Trans. on Evolutionary Computation. 2004,8(3):204-210．〔10〕赫然，王永吉，王青，等.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报，2005，16(12)：2036-2044.〔11〕Peram T, Veeramachaneni K. Fitness-Distance-Ratio based particle swarm optimization [C]. In: Proc. of the IEEE Swarm Intelligence Symp. Indianapolis. 2003,174-181.〔12〕〔13〕Trelea IC. The particle swarm optimization algorithm: Convergence analysis and parameter selection[J]. Information Processing Letters.2003,85(6):317-325.〔14〕潘峰，陈杰，甘明刚，等.粒子群优化算法模型分析[J].自动化学报，2006，32(3)：368-377.〔15〕Ratanaweera A, Halgamuge S K, Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE Trans. on Evolutionary Computation, 2004, 8(3):240-255.〔16〕Liang J J, Qin A K. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [J]. IEEE Trans. on Evolutionary Computation, 2006,10(3):281-295.〔17〕吕艳萍，李绍滋，陈水利，等.自适应扩散混合变异机制微粒群算法[J].软件学报，2007，18(11)：2740-2751.〔18〕胡旺，李志蜀.一种简化而高效的粒子群优化算法[J].软件学报，2007，18(4)：861-868.〔19〕高芳，崔刚，吴智博，等.一种新型多步式位置可选择更新粒子群优化算法[J].电子学报，2009，37(3)：529-534.〔20〕纪震，周家锐，廖惠连，等.智能单粒子优化算法[J].计算机学报，2010，33(2)：556-561.。

云计算资源的动态随机扰动的粒子群优化策略喻德旷;杨谊;钱俊【期刊名称】《计算机应用》【年(卷),期】2018(038)012【摘要】云计算环境中的资源具有动态性和异构性,大规模任务资源分配的目标是最小化完成时间和资源占用,同时具有尽可能好的负载均衡,这是一个非确定性多项式(NP)问题.借鉴智能群体算法的优点,提出基于改进的粒子群优化(PSO)算法构建混合式群体智能调度策略——动态随机扰动的PSO策略(DRDPSO).首先,将PSO 的惯性权重常数修改为变量,实现对求解过程收敛速度的合理控制;其次,缩小每次迭代的搜索范围,在保留候选最优集合的前提下减少无效搜索;然后,引入选择操作,筛选出优质个体并传递到下一代;最后,设计随机扰动,提高候选解的多样性,在一定程度上避免了局部最优陷阱.在CloudSim平台上进行了两类仿真测试,结果表明,处理同构任务时,在大部分情况下DRDPSO的指标都优于模拟退火遗传算法(SAGA)和遗传算法(GA) +PSO算法,总执行时间比SAGA减少13.7％～37.0％,比GA+ PSO减少13.6％～31.6％;其资源耗费比SAGA减少9.8％～17.1％,比GA+ PSO减少0.6％～31.1％;其迭代次数比SAGA减少15.7％～ 60.2％,比GA+ PSO减少1.4％～ 54.7％;其负载均衡度比SAGA减小8.1％～18.5％,比GA+ PSO减少2.7％～ 15.3％,且波动幅度最小.处理异构任务时,三种算法表现出相似的规律:CPU 型任务的总执行时间最多,混合型任务次之,IO型任务最少,DRDPSO的综合指标最好,较为适合处理多种类型的异构任务,而GA+ PSO算法适合快速求解混合型任务,SAGA则适合快速求解IO型任务.所提DRDPSO在处理较大规模的同构和异构任务时,能够较为明显地缩短总的任务执行时间,不同程度地提高资源利用率,并适当兼顾计算节点的负载均衡.【总页数】6页(P3490-3495)【作者】喻德旷;杨谊;钱俊【作者单位】南方医科大学生物医学工程学院,广州510515;南方医科大学生物医学工程学院,广州510515;南方医科大学生物医学工程学院,广州510515【正文语种】中文【中图分类】TP391【相关文献】1.粒子群算法在嵌入式云计算资源调度中的运用 [J], 韦湘夫;汪一百2.自适应动态调整粒子群的云计算任务调度 [J], 侯欢欢3.以云计算资源为基础实现粒子群算法的优化 [J], 张乐4.基于竞争粒子群算法的云计算资源调度策略 [J], 王镇道;张一鸣;石雪倩5.基于改进粒子群算法的云计算虚拟机资源配置优化研究 [J], 屈慧姣;郭银章因版权原因，仅展示原文概要，查看原文内容请购买。

一种混沌编码的粒子群优化算法及其应用
任金霞;阳帅
【期刊名称】《计算机仿真》
【年(卷),期】2013(30)3
【摘要】研究粒子群优化算法.传统的粒子群算法采用实数编码,收敛速度慢.为了提高收敛速度,提出了一种混沌编码的粒子群优化算法.混沌编码作为一种全新的数学编码方式,更能准确地表达编码对象的多样性,将混沌编码应用到粒子群优化算法中,使算法在初期的搜索区域更大,更快找到全局最优解.把混沌编码的粒子群算法与BP算法相结合用来优化神经网络.利用混沌编码的粒子群算法快速找到全局最优位置的邻域,然后再用BP算法进行局部寻优,收敛到全局最优位置.仿真结果证明混沌编码的粒子群神经网络比实数编码的粒子群神经网络分类收敛速度更快,验证了算法的有效性.
【总页数】4页(P299-302)
【作者】任金霞;阳帅
【作者单位】江西理工大学电气工程与自动化学院,江西赣州341000;江西理工大学电气工程与自动化学院,江西赣州341000
【正文语种】中文
【中图分类】TP202+.7
【相关文献】
1.一种应用混沌编码技术的盲信道估计研究 [J], 陈昶;魏学业
2.动态混沌在通信系统和计算机网中的应用--混沌编码器和信道编码器的分离 [J], 王永林
3.一种基于空间混沌序列的量子粒子群优化算法及其应用 [J], 靳雁霞;师志斌
4.一种基于混沌动态权重粒子群优化算法 [J], 王进成;马梅琴
5.一种改进惯性权重的混沌粒子群优化算法 [J], 谷晓琳; 黄明; 梁旭; 焦璇
因版权原因，仅展示原文概要，查看原文内容请购买。

基于混沌和多群体的粒子群优化算法宫玉琳;文大化【摘要】Because the basic particle swarm optimization algorithm has the problem that the initialization of the algo-rithm is easy to fall into local optimum,the global search is easy to fall into local optimization. The particle swarm op-timization algorithm based on chaos and multi population is proposed. The algorithm can be used to improve the speed and accuracy of different populations.%由于基本粒子群优化算法存在初始化随机性和遍历性不强,全局搜索容易陷入局部最优的问题,提出了基于混沌和多群体的粒子群优化算法,利用混沌特性初始化粒子,增强其随机性和遍历性,并根据适应度值将粒子群划分为多个群体,对不同群体中粒子的速度和位置采取不同的计算方法,进一步提高算法的收敛速度和精度.【期刊名称】《长春理工大学学报（自然科学版）》【年(卷),期】2015(038)005【总页数】4页(P88-91)【关键词】混沌;多群体;粒子群优化【作者】宫玉琳;文大化【作者单位】长春理工大学电子信息工程学院,长春 130022;中国科学院长春光学精密机械与物理研究所,长春 130033【正文语种】中文【中图分类】TP301粒子群优化（Particle Swarm Optimization，PSO）算法［1］，通过追随当前搜索到的最优值来寻找全局最优，在求解优化问题等方面已经得到了越来越广泛的应用。