（电路与系统专业论文）粒子群算法的改进及应用[电路与系统专业优秀论文].pdf

太原理工大学硕士研究生学位论文 粒子群优化算法的改进及应用 摘要 粒子群优化算法是在对鸟群捕食行为模拟的基础上提出的一种群 集智能算法，是进化计算领域中一个新的分支。它的主要特点是原理简 单、参数少、收敛速度较快、易于实现。因此，该算法一提出就吸引了 的广泛关注，逐渐成为一个新的研究热点。目前，粒子群优化算法应用 于神经网络的训练、函数优化、多目标优化等领域并取得了较好的效果， 有着广阔的应用前景。 论文的主要工作有： ( 1 ) 对粒子群优化算法的理论基础和研究现状作了简要的介绍，分 析了粒子群优化算法的原理及算法流程，对算法参数的选择做了详细的 研究，并进行了相应的仿真实验。 ( 2 ) 分析了粒子群优化算法存在的问题，主要包括：参数设置问 题、算法“早熟”问题和算法稳定性问题。在粒子群优化算法中，参数 的设置会影响算法优化的结果，因此，如何选择合适的参数达到最好的 优化结果是算法需要解决的问题。“早熟”问题是优化算法普遍存在的 问题。如果粒子在搜索最优值时过早收敛，就会使算法的寻优停滞在局 部最小值，无法找到全局最优解。由于算法中粒子的初始位置、速度和 太原理工大学硕士研究生学位论文 一些参数是被随机初始化的，因此每一次算法运行的结果并不相同，有 时结果的差别很大，这样就导致了算法优化结果不稳定。 ( 3 ) 针对粒子群优化算法存在的问题，论文提出了一种新的改进 算法一基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子 群优化方法，从“粒子进化 和“多种群”两个方面对标准粒子群算法 进行改进。多个粒子群彼此独立地搜索解空间，保持了粒子种群的多样 性，从而增强了全局搜索能力；而适当的“粒子进化 可以使陷入局部 最优的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的稳定 性。通过对测试函数进行仿真实验，验证了该算法的有效性。 ( 4 ) 将基于粒子进化的多粒子群优化算法应用于线性瞬时混合的 盲源分离。将该算法的仿真实验结果与标准粒子群优化算法的结果相 比，前者在分离混合信号时所需要的迭代次数少，算法的稳定性高。 ( 5 ) 将基于粒子进化的多粒子群优化算法用于求解非线性方程组。 该算法求解精度高、收敛速度快，而且克服了一些算法对初值的敏感和 需要函数可导的困难，能较快地求出复杂非线性方程组的最优解。数值 仿真结果显示了该算法的有效性和可行性，为求解非线性方程组提供了 一种实用的方法。 关键词：粒子群优化算法，进化计算，群集智能，盲源分离，非线性方 程组 太原理工大学硕士研究生学位论文 m o d i c a t l 0 na n da p p l i c a r i o no fp a r t i c l e s w a r mo p t i m i z a t l 0 na l g o r i t h m a bs t r a c t p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a l g o r i t h mi sas w a r mi n t e l l i g e n t a l g o r i t h mw h i c hi sb a s e do ni m i t a t i n gt h eb i r df l o c k sp r e y i n gb e h a v i o r ，a n d i ti san e wb r a n c h - o ft h ee v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e t h em a i nt r a i t o fp s oi s s i m p l e i n p r i n c i p l e ，f e w i n t u n i n gp a r a m e t e r s ，s p e e d y i n c o n v e r g e n c e a n d e a s y i n i m p l e m e n t a t i o n s o ，t h ep s oa l g o r i t h m i m m e d i a t e l ya t t r a c t st h es c h o l a r s e x t e n s i v ea t t e n t i o nw h e ni ti sp r o p o s e d g r a d u a l l y , i tb e c o m e s ah o t s p o ti nt h ee v o l u t i o n a r yc o m p u t a t i o nf i e l d n o w , t h ep s oi su s e df o rt h et r a i n i n go fn e u r a ln e t w o r k s ，o p t i m i z a t i o no ff u n c t i o n s a n dm u l t i t a r g e t i to b t a i n sg o o de f f e c t ，a n di t sa p p l i e df o r e g r o u n di sw i d e t h em a i nw o r k so ft h ed i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： ( 1 ) t h i sp a p e rm a k e sab r i e fi n t r o d u c t i o no ft h eb a s i ct h e o r i e sa n d p r e s e n ts i t u a t i o no fp s or e s e a r c h t h ep s oa l g o r i t h mp r i n c i p l e sa n df l o w a r ea n a l y z e di nd e t a i l i nt h ep a p e r , t h ep a r a m e t e r so fp s oa r er e s e a r c h e da n d t h ec o r r e s p o n d i n ge m u l a t o re x p e r i m e n t sa r ec a r r i e do u t ( 2 ) t h ep r o b l e m so fp s oa l g o r i t h ma r ea n a l y z e d i tc o n t a i n st h es e t t i n g r r l 太原理工大学硕士研究生学位论文 o ft h ep a r a m e t e r s ，t h ep r e m a t u r eo fp s oa n dt h es t a b i l i t yo fp s o i np s o a l g o r i t h m ，t h es e t t i n g so fp a r a m e t e rh a v em u c hi n f l u e n c eo nt h er e s u l t s o ， h o wt oc h o o s ep a r a m e t e r st oa c h i e v et h eb e s ts o l u t i o n si st h ep r o b l e mt h a t s h o u l db es o l v e d t h ep r e m a t u r ep r o b l e mi sp r e v a l e n ti nt h eo p t i m i z a t i o n a l g o r i t h m i fp a r t i c l e sc o n v e r g ee a r l y , t h ea l g o r i t h mm a yg e ti n t ol o c a l m i n i m u mv a l u ea n dc a l l tf m dt h eg l o b a lo p t i m i z a t i o n b e c a u s ep a r t i c l e s p o s i t i o n ，s p e e da n ds o m ep a r a m e t e r sa r er a n d o mi n i t i a l i z e d ，t h er e s u l tw i l lb e d i f f e r e n ta te v e r yt u ma n ds o m e t i m e si td i f f e r sal o t i nt h i sw a y , i tl e a d st o t h eu n s t a b l er e s u l t s ( 3 ) 赴而n ga tt h ep r o b l e m so fp s o ，t h ep a r t i c l es w a r m so p t i m i z a t i o n b a s e do np a r t i c l ee v o l u t i o ni sp r o p o s e di nt h ep a p e r i tu s e sl o c a lv e r s i o no f p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mt oi m p r o v et h es t a n d a r dp s oi nt h e t w oa s p e c t so fp a r t i c l ee v o l u t i o na n ds w a r m s t h ei n d e p e n d e n ts e a r c h i n gi n t h es o l u t i o ns p a c eo fp a r t i c l es w a r m sm a k e si td i v e r s i f i e d ，a n dt h e ne n h a n c e s t h eg l o b a ls e a r c h i n ga b i l i t y t h ee v o l u t i o n a lp a r t i c l ew i l lb er e s e ti no r d e rt o f o r c ei tg e t t i n go u to fl o c a l l ym i n i m u m i tm a k e st h ep a r t i c l ee s c a p e df r o m t h e p r e m a t u r ec o n v e r g e n c e a n di n c r e a s e st h e s t a b i l i t y o f a l g o r i t h m c o m p a r a t i v ee x p e r i m e n t so nt e s t i n gf u n c t i o n si n d i c a t et h a t t h ei m p r o v e d a l g o r i t h mi se f f e c t i v e ( 4 ) t h ep a r t i c l es w a r m so p t i m i z a t i o nb a s e do np a r t i c l ee v o l u t i o ni s i v 太原理工大学硕士研究生学位论文 a p p l i e dt ob l i n ds o u r c es e p a r a t i o n c o m p a r e dt os t a n d a r dp s o ，t h ef o r m e r r e s u l t so fe m u l a t o re x p e r i m e n t sn e e df e w e ri t e r a t i v et os e p a r a t et h em i x e d s i g n a l sa n d i t ss t a b i l i t yi sh i g h e r ( 5 ) t h ep a r t i c l es w a r l t l so p t i m i z a t i o nb a s e do np a r t i c l ee v o l u t i o ni su s e d f o rs o l v i n gn o n l i n e a re q u a t i o n s t h e a l g o r i t h mh a sg o o dc o n v e r g e n c e r e l i a b i l i t ya n dc a ng e tt h es o l v i n gr e s u l t sq u i c k l ya n da c c u r a t e l y t h i sm e t h o d o v e r c o m e st h ep r o b l e m so fs o m ea l g o r i t h m s s e n s i t i v i t yt ot h ei n i t i a lv a l u e a n dt h e i rn e e df o rd i f f e r e n t i a lo ff u n c t i o n s ，a n di tc a nf i n dt h eb e s ts o l u t i o no f n o n l i n e a re q u a t i o n sq u i c k l y s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mi s f e a s i b l ea n de f f e c t i v e t h i sa l g o r i t h mp r o v i d e sa p r a c t i c a lm e t h o df o rs o l v i n g n o n l i n e a re q u a t i o n s k e y w o r d s ：p a r t i c l e s w a r l no p t i m i z a t i o n ( p s o ) a l g o r i t h m ，e v o l u t i o n a r y c o m p u t a t i o n ，s w a r mi n t e l l i g e n c e ，b l i n ds o u r c es e p a r a t i o n ( b s s ) ，s y s t e mo fn o n l i n e a re q u a t i o n s v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 论文作者签名：j 斗址 日期：吩岁“ 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件与复印 件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文； 学校可允许学位论文被查阅或借阅；学校可以学术交流为：目的， 复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内 容( 保密学位论文在解密后遵守此规定) 。 签名：卫l1 一 导师签名： 太原理工大学硕士研究生学位论文 第一章绪论 1 1 粒子群优化算法的研究目的和意义 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 算法是e b e r h a r t 和k e n n e d y 【l 】 于1 9 9 5 年在对鸟群捕食行为模拟的基础上提出的一种群集智能算法。该算法的基本 思想是通过群体中个体之间的协作和信息共享来寻找最优解。同其它的进化算法相 比，p s o 的优势在于算法简单、容易实现和较强的全局优化能力，而且没有许多的 参数调节。因此，粒子群优化算法一提出，立刻引起了进化计算等领域学者们的广 泛关注，在短短几年时间里出现大量的研究成果，成为进化计算领域内的一个研究 热点。随着对粒子群优化研究地不断深入，学者们提出了多种改进的p s o 算法，广 泛应用于函数优化，神经网络训练，模式分类，模糊系统控制等多个领域，有着广 阔的前景。尽管如此，粒子群优化算法无论是理论分析还是实践应用都尚未成熟， 有大量的问题值得研究。 目前对于粒子群优化算法的研究主要分为三个方面：算法机制研究、算法改进 研究和算法应用研刭2 1 ，如图1 - 1 所示。其中算法机制研究主要包括：收敛性分析， 复杂性分析和参数分析；算法改进研究主要有：加强局部搜索，多样性保持，算法 融合和离散版本；而算法的应用研究主要是：优化问题，多目标问题，动态问题和 实际应用等。 1 2 研究的基础 粒子群优化算法是一种较新的人工生命计算方法，是一种基于群集智能的进化 计算1 1 。由此可知，粒子群优化算法的理论三基础是一些交叉的学科，包括人工生 命计算( a r t i f i c i a ll i f ec o m p u t a t i o n ) 、进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 和群集智 能( s w a r mi n t e l l i g e n c e ) 等。 太原理工大学硕士研究生学位论文 动态问题 图l l 粒子群优化算法研究的主要内容 f i g 1 - 1t h em a i nc o n t e n to fp s oa l g o r i t h mr e s e a r c h 1 2 1 进化计算理论 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 就是以达尔文的进化论为依据，在研究模拟 自然进化的基础上发展起来的一类随机搜索技术，它包括遗传算法( g e n e t i c a l g o r i t h m ) 、进化策略( e v o l u t i o n a r ys t r a t e g y ) 和进化规划( e v o l u t i o n a r y p r o g r a m m i n g ) 。它们模拟由个体组成的群体的集体学习过程，其中每个个体表示给 定问题搜索空间中的一点。进化算法从任意随机的初始群体出发，通过随机选择( 在 某些算法中是确定的) 、变异和交叉( 在某些算法中被完全省去) 过程，使群体进化到 搜索空间中越来越好的区域。选择过程使群体中适应性好的个体比适应性差的个体 有更多的复制机会；交叉算子可将父辈信息结合在一起并将它们传到子代个体；变 异是在群体中引入新的变种。 群体搜索策略和群体中个体之间的信息交换是进化算法的两大特点【3 】。它们的 优越性主要表现在：首先，进化算法在搜索过程中不容易陷入局部最优，即使在所 定义的适应度函数是不连续的、非规则的或有噪声的情况下，它们也能以很大的概 率找到全局最优解；其次，由于它们固有的并行性，进化算法非常适合于并行计算； 2 太原理工大学硕士研究生学位论文 再者，进化算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决困难的 问题。此外，由于容易嵌入到已有的模型中，并且具有可扩展性，易于同其它技术 混合使用，所以，进化计算已被广泛运用于许多复杂系统的自适应控制和复杂优化 问题等研究领域，如并行计算、机器学习、电路设计、神经网络等。 1 2 2 人工生命计算理论 人工生命( a r t i f i c i a ll i f e ) 的概念是在1 9 8 7 年由c g l a n g t o n l 4 】首先提出来的，它是 以研究具有自然生命特征和生命现象的人造系统为对象的一门新兴学科。自从人工 生命作为- i 0 科学创立以来，许多研究者提出了各种基于人工生命的智能算法。 人工生命计算( a r t i f i c i a ll i f ec o m p u t a t i o n ) 是一种以人工生命为形式、研究人工 生命的信息表达和处理机制，提取相应的计算模型，嵌入相应的智能计算方法模拟 自然界生物进化过程与信息处理机制来求解与优化问题的智能计算方法【4 】。人工生 命计算的概念，是由汪定伟【5 】教授在2 0 0 4 年提出来的，是人工生命的一个研究领域。 人工生命计算是研究如何利用人工生命来研究科学计算问题的一种方法，是进 化计算的一个子集。与传统优化算法相比，人工生命计算具有以下几个特性【4 】： ( 1 ) “自下而上”的设计原则。人工生命计算更多的是注重设计它的底层规则， 而非集中控制约束的方式来实现全局最优搜索，因此算法更具有鲁棒性。 ( 2 ) 突现与突现计算。人工生命的最重要的特点是突现，即人工生命群体微观的 相互作用可以导致在整个系统中产生群体突现，基于群体智能来实现全局寻优的过 程。 ( 3 ) 人工生命计算是异步进行的，可充分利用多处理器，非常适合于并行操作。 ( 4 ) 人工生命计算对问题定义的连续性无特殊要求，无需函数的梯度信息。 1 2 3 群集智能理论 我们经常能够看到成群的鸟、鱼或其它生物，这些生物的聚集行为有利于它们 觅食和逃避捕食者。生物的群落动辄以十、百、干甚至万计，它们是如何迅速完成 聚集、移动等行为呢? 这些群落一般都不存在一个统一的指挥者，那么一定有某种 潜在的能力或者规则保证了这些行为的同步。科学家们普遍认为上述行为是基于不 太原理工大学硕士研究生学位论文 可预知的种群社会行为中的群集智能。 群集智能( s w a r mi n t e l l i g e n c e ) 指的是众多无智能的简单个体组成的群体，通过 相互间的简单合作表现出智能行为的特性。群居生物涌现的群集智能正越来越得到 人们的重视，成为近年来人工智能研究的一个热点课题。m i l l o n a s 1 1 在开发人工生命 算法时提出了群集智能的概念，并提出五点原则： 1 接近性原则：群体应能够实现简单的时空计算； 2 优质性原则：群体能够响应环境要素； 3 变化相应原则：群体不应把自己的活动限制在一个狭小的范围； 4 稳定性原则：群体不应每次随环境改变自己的模式； 5 适应性原则：群体的模式应在计算代价值得的时候改变。 1 3 粒子群优化算法的研究现状 1 3 1 理论研究现状 在粒子群优化算法的理论研究方面，由于p s o 算法对参数的选择没有规范，而 且算法容易“早熟”，因此很多学者都对算法提出了改进。有些学者对算法的收敛 性进行了分析，对参数选择提出了好的建议；更多的学者则致力于研究算法的结构 和性能的改善，包括参数分析，拓扑结构，粒子多样性保持，算法融合和性能比较 等。 在基本粒子群优化算法【l 】的基础上，s h i 和e b e r h a r t l 6 1 首次提出了惯性权重的概 念，对基本算法中的速度更新公式进行修正。惯性权重的引入更好地控制了粒子的 开发( e x p l o i t a t i o n ) 和探索( e x p l o r a t i o n ) ，提高了算法性能。惯性权重在多数情况下被 设置为随时间递减的时变权重。改进后的算法称为标准粒子群优化算法，为大多数 研究者所使用。之后，k e n n e d y 7 1 提出了簇丛分析( c l u s t e ra n a l y s i s ) 的方法。簇丛分析 方法是在微粒群体中选择一些微粒作为中心，再将离它最近的n 个微粒和中心微粒 作为一簇，然后计算每个簇的中心位置，并以这些中心位置来替换p b e 或或者g b c 立。结 4 太原理工大学硕士研究生学位论文 果表明，用簇中心替换p b e 啦时，部分测试函数的解得到了较好的改进，其余的函数只 是略微差一点。如果用全局的簇中心替换g b c 。时，几乎所有函数的结果都较差。此 外，簇分析的方法虽然使收敛速度有所加快，但同时引入了一些附加计算，通常需 要标准p s o 算法计算时间的7 4 2 0 0 t 引。a n g e l i n ep j t 9 j 利用选择( s e l e c t i o n ) 的方法 改进p s o 算法。结果表明，改进后的方法提高了大部分函数的性能。这是由于选择 方法加快了对当前较好区域的开发过程，使得算法收敛速度加快，但也增加了陷入 局部解的可能性。标准粒子群优化算法有3 个权重因子，这使得算法调整很自由，但 也为找到最好的参数组合带来难度。因此，c l e r c t l 们提出一个简化的p s o 算法，只有 一个公式和一个社会信心参数。该算法定义了一个无希望( n o h o p e ) 收敛规则和一 个重新希望( r e h o p e ) 方法，以便不时地根据对目标函数的梯度估计和先前的初始化 重新初始化群体位置，算法还考虑了粒子群体的引力中心( g r a v i t yc e n t e r ) 。用该算 法对一些函数进行测试得到了较好的结果。 1 3 2 应用研究现状 粒子群优化算法最早应用于非线性连续函数的优化和神经元网络的训练【1 1 1 ，后 来也被用于解决约束优化问题。e b e r h a r t 用p s o 算法来分析人类的帕金森综合症等颤 抖类疾病。r o b i n s o n 等将p s o 算法用于剖面波状喇叭天线的优化，并与g a 的优化效 果进行了比较，研究了二者混合应用的可行性。c i u p r i n a 提出一种智能p s o ( i n t e l l i g e n t p s o ) 用于电磁线圈尺寸的优化。a b i d o 将p s o 算法用于解决最优功率通量( o p f ) 问 题。国内也有越来越多的学者关注p s o 算法，将其应用于非线性规划、参数优化、 车辆路径、约束布局优化、新产品组合投入、多目标优化等问题【2 】。还有一些学者 尝试将p s o 算法应用于解决动态优化问题，也取得了较好的效果【l o 】。 粒子群优化算法由于其算法简单，参数少，易于实现等特点，在连续非线性优 化问题和组合优化问题中都表现出良好的效果。但是目前关于粒子群优化算法在盲 源分离中应用的研究还相对较少。因此，刘俊豪1 2 1 做了将p s o 算法应用于盲源分离 的初步研究。该算法用粒子群算法代替常规的最陡梯度下降法，对线性瞬时混合的 盲信号进行了分离，解决了梯度算法易陷入局部最小点以及对初值和步长依赖性大 的缺点。 太原理工大学硕士研究生学位论文 基于以上研究成果，论文将在分析粒子群优化算法缺点的基础上对其做进一步 的改进，以提高算法在复杂、高维情况下的优化性能，使算法能有效避免搜索过程 中的“早熟”问题，提高算法的稳定性。 1 4 粒子群优化算法的应用 粒子群优化( p s o ) 算法概念简单，易于实现，同时又有深刻的智能背景，既适 合科学研究，又适合于工程应用。由于该算法具有很强的通用性，而且无需问题的 特殊信息，因此，算法一提出就吸引了广泛的关注，不断涌现出各种关于p s o 算法 应用的研究成果，有力地推动了p s o 算法的应用研究。 1 4 1 神经网络训练 粒子群优化算法最早最成功的应用就是在神经网络的训练领域。在神经网络的 训练中，主要包含3 个方面：网络连接权重、网络拓扑结构、学习算法3 j 。每个粒 子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的。与 b p 算法相比，使用p s o 算法训练神经网络的优点在于不需要梯度信息，可使用一 些不可微的传递函数。多数情况下其训练结果优于b p 算法，而且训练速度非常快。 1 4 2 函数优化 粒子群优化算法最直接的应用就是多元函数的优化问题，包括带约束的优化问 题。通常这些函数是非常复杂的，主要表现为规模大、维数高、非线性和不可微等 特点，而且有的函数存在大量局部极值。许多传统的确定性优化算法收敛速度较快， 计算精度高，但对初值敏感，易陷入局部最小。而一些具有全局性的优化算法，如 遗传算法、模拟退火算法、进化规划等，受限于各自的机理和单一结构，对于高维 复杂函数难以实现高效优化。p s o 算法通过改进或结合其它算法，对高维复杂函数 可以实现高效优化。 1 4 3 其他应用 一般而言，粒子群优化算法与其他演化算法一样，能用于求解大多数优化问题。 6 太原理工大学硕士研究生学位论文 除了以上领域外，p s o 算法的应用包括系统设计、多目标优化、分类、模式识 别、调度、信号处理、决策、机器人应用等。其中具体应用实例有：模糊控制器设 计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等 1 4 , 1 5 1 。 总之，p s o 算法的应用十分广泛，有着较好的发展前景。目前p s o 算法的应用 研究尚处于初期，还有许多问题需要进一步的研究。 1 5 论文的结构安排 论文共分为六章，第一章主要是对粒子群优化算法的起源、相关理论基础和目 前研究状态的简要概述；第二章主要对基本粒子群优化算法和标准粒子群优化算法 理论知识的详细阐述：第三章分析了p s o 算法存在的问题，提出了一种基于粒子进 化的多粒子群优化算法；第四章是基于粒子进化的多粒子群优化算法在线性瞬时混 合盲源分离中的应用；第五章将基于粒子进化的多粒子群优化算法应用于非线性方 程组的求解中；第六章是本文的最后一章，对全文进行总结，指出未来课题的研究 方向。下面是关于各章内容的详细介绍： 第一章介绍了研究粒子群优化算法的目的和意义，对p s o 算法的理论基础和研 究现状做了简要的分析，综述了目前国内外的研究现状，总结了粒子群优化算法在 函数优化、神经网络训练等方面的应用。 第二章对基本粒子群优化算法和标准粒子群优化算法进行了详细介绍。该章对 基本粒子群优化算法的起源、基本理论、算法流程等作了详细的阐述，对标准粒子 群优化算法的惯性权重、压缩因子进行了讨论，对算法的参数选择给出了建议。 第三章简要介绍了粒子群优化算法存在的问题，对算法进行了改进，提出了一 种基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子群优化方法，多个 粒子群彼此独立地搜索解空间；利用粒子进化的方法使陷入局部值的粒子迅速摆脱， 从而有效地避免了“早熟”问题，提高了算法的稳定性。通过4 个测试函数对算法 进行了对比实验，结果表明该算法优于标准粒子群优化算法。 第四章简要介绍了线性瞬时混合盲源分离的基本理论，总结了盲源分离的一些 常用分离标准，并将基于粒子进化的多粒子群优化算法用于线性瞬时混合盲源分离， 7 太原理工大学硕士研究生学位论文 通过计算机仿真实验验证了改进后算法的有效性和可靠性。 第五章将改进后的粒子群算法用于非线性方程组的求解问题，通过仿真表明了 算法的有效性和可行性，这不仅为非线性方程组的求解提供了一种可行的方法，而 且进一步拓宽了粒子群优化算法的应用领域。 第六章总结了全文所做的工作，对进一步的研究方向进行了展望。 太原理工大学硕士研究生学位论文 第二章粒子群优化算法 2 1 基本粒子群优化算法 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 算法的基本思想是通过 群体中个体之间的协作和信息共享来寻找最优解，它包含有进化计算和群集智能的 特点。起初k e n n e d y 和e b e r h a r t 1 1 只是设想模拟鸟群觅食的过程，但后来发现p s o 算法是一种很好的优化工具。 设想这样一个场景：一群乌在空间中随机的搜索食物。在这个区域里只有一块 食物，所有的鸟都不知道食物在哪几，但是它们知道自己当前的位置距离食物还有 多远。那么找到食物的最优策略是什么? 最简单有效的方法就是搜寻目前距离食物 最近的鸟的周围区域，通过鸟之间的集体协作与竞争使群体达到目的。这是一种信 息共享机制，在心理学中对应的是在寻求一致的认知过程中，个体往往记住它们的 信念，同时考虑其它个体的信念。当个体察觉其它个体的信念较好的时候，它将进 行适应性地调型1 1 。p s o 算法就是从这种模型中得到启示并用于解决优化问题的。 如果我们把一个优化问题看作是在空中觅食的鸟群，那么在空中飞行的一只觅 食的“鸟”就是p s o 算法中在解空间中进行搜索的一个“粒子 ( p a r t i c l e ) ，也是优 化问题的一个解。“食物 就是优化问题的最优解。粒子的概念是一个折衷的选择， 它只有速度和位置用于本身状态的调整，而没有质量和体积。“群 ( s w a r m ) 的概念 来自于人工生命，满足群集智能的五个基本原则【l 】。因此p s o 算法也可以看作是对 简化了的社会模型的模拟，社会群体中的信息共享是推动算法的主要机制。 2 1 1 基本理论 e b e r h a r t 和k e n n e d y f l 提出的基本粒子群优化算法可描述如下：设在一个d 维的 目标搜索空间中，有m 个粒子组成一个群落，第i 个粒子的位置用向量 9 太原理工大学硕士研究生学位论文 x i x 矿x 驴，x i 。】表示，飞行速度用v i = v 矿v i ：，v b 】表示，第i 个粒子搜索到的最 优位置为p ；= p i 。，p i ：，p ；。】，整个群体搜索到的最优位置为p 。= 【p i 。，p 。：，p 。】，则用 下式更新粒子的速度和位置： v i ( n + 1 ) 2 v i ( n ) + c l ( n x i ( n ) ) + c 2 1 2 ( p g - x i ( n ) ) ( 2 1 ) x i ( + 1 ) = x i ( n ) + v i ( n ) ( 2 2 ) 式中，i - 1 ，2 ，m ，分别表示不同的粒子。c ，c ：为大于零的学习因子或称作加 速系数，分别调节该粒子向自身己寻找到的最优位置和同伴己寻找到的最优位置方 向飞行的最大步长，通常情况下取c 。= c ：- - - 2 ；x l , r ：为介于 o ，1 】之间的随机数；n 为 迭代次数，即粒子的飞行步数。将v ，限定一个范围，使粒子每一维的运动速度都被 限制在 一，一，v 一】之间，以防止粒子运动速度过快而错过最优解，这里的v 邮根据 实际问题来确定。当粒子的飞行速度足够小或达到预设的迭代步数时，算法停止迭 代，输出最优解。 从社会学的角度来看，公式( 2 1 ) 的第一部分是“记忆”项，是粒子先前的速度， 表示粒子当前的速度要受到上一次速度的影响；公式第二部分是“自身认知”项， 是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部 分，可以认为是粒子自身的思考；公式的第三部分是“群体认知项，是一个从当 前点指向种群最好点的矢量，反映了粒子间的协同合作和信息共享。粒子正是通过 自己的经验和同伴中最好的经验来决定下一步的运动。公式( 2 1 ) 中的第一部分起到 了平衡全局和局部搜索能力的作用：第二部分使粒子拥有的局部搜索能力，能更好 的开发解空间；第三部分体现了粒子间的信息共享，使粒子能在空间更广阔的探索； 只有在这三个部分的共同作用下粒子才能有效的搜索到最好的位置。 2 1 2 算法流程 基本粒子群优化算法的步骤描述如下： 1 0 太原理工大学硕士研究生学位论文 步骤1 ：初始化粒子群，包括群体规模、粒子的初始速度和位置等； 步骤2 ：计算每个粒子的适应度( f i t n e s s ) ，存储每个粒子的最好位置p b e 甜和 f i t n e s s ，并从种群中选择f i m e s s 最好的粒子位置作为种群的g b c s t ； 步骤3 ：根据方程( 2 1 ) 和( 2 2 ) 更新每个粒子的速度和位置； 步骤4 ：计算位置更新后每个粒子的适应度，将每个粒子的f i t n e s s 与其以前经 历过的最好位置p b c 啦时所对应的f i t n e s s 比较，如果较好，则将其当前的位置作为该 粒子的p 眦； 步骤5 ：将每一个粒子的适应度( f i m e s s ) 与全体粒子所经历过的最好位置瓯醴 比较，如果较好，则将更新雠趾的值； 步骤6 ：判断搜索结果是否满足算法设定的结束条件( 通常为足够好的适应值或 达到预设的最大迭代步数) ，如果没有达到预设条件，则返回步骤3 ；如果满足预设 条件，则停止迭代，输出最优解。 基本粒子群优化算法的流程图见图2 1 ： 太原理工大学硕士研究生学位论文 i 在整个搜索空间随机初始 l 化粒子位置和初始速度 计算各粒子的适应度l - 土 更新粒子的p b e s 。和g b c s 。 上 根据公式( 2 - 1 ) 和( 2 2 ) 更新 每个粒子的速度和位置 上 彳会否 图2 1 粒子群优化算法流程图 f i g 2 1t h ef l o wc h a r to fp s oa l g o r i t h m 2 1 3 全局模式与局部模式 根据对邻近粒子的定义不同，粒子群优化算法分为全局模式p s o 算法和局部模 式p s o 算法【1 1 1 。对于全局模式的p s o 算法来说，邻近粒子指整个粒子群体；对于局 部模式的p s o 算法来说，邻近粒子仅指几个拓扑相邻或空间相邻的粒子。 在粒子群优化算法中，当把整个种群定义为同伴时，算法被称为全局版( g l o b a l v e r s i o n ) 的粒子群优化算法；当同伴仅指种群中的一部分粒子时，称为局部版( 1 0 c a l v e r s i o n ) 的粒子群优化算法【1 1 1 。也就是说，在全局版本的p s o 算法中，粒子跟踪两 个极值，自身极值p 哪和种群全局极值g b e s t ；而在局部版本的p s o 算法中，指粒子 除了追随自身极值p k 吼外，不跟踪全局极值g 嘲，而是追随拓扑近邻粒子当中的局 部极值k 髓。在该版本中，每个粒子需记录自己和它所在局部的最优值，而不需要 1 2 太原理工大学硕士研究生学位论文 记录整个群体的最优值。下面给出局部版本的粒子群优化算法公式： v f ( ，l + 1 ) = v f ( ，1 ) + c l ，i ( p f x i ( ，z ) ) + c 2 ( p l x i ( ，2 ) ) x i ( n + 1 ) = x i ( n ) + v i ( ，z ) ( 2 3 ) ( 2 4 ) 公式( 2 3 ) 只是将公式( 2 1 ) d p 全局最优值p g 用局部种群中的最优值p l 代替。对于局 部版本的p s o 算法的算法流程，只需将上述步骤中第3 步的公式( 2 1 ) 改为公式( 2 3 ) 。 通过上面对两种不同版本算法的比较可以看出，由于局部版的p s o 算法允许粒 子与其邻域内粒子比较当前搜索到的最优位置，从而相互之间施加影响，即便其值 比种群最好值要差，该影响可以使较差个体进化为较好的个体。而全局版的p s o 算 法中所有粒子都能够信息共享，所以粒子向当前最优解收敛的趋势非常明显，因而 全局模型通常搜索到最优值的速度比局部版的p s o 算法要快；但由于全局版的p s o 算法中所有粒子都迅速趋向与同一最优值，因而全局模型比局部模型更易陷入局部 极小，出现“早熟”现象。 2 1 4 同步模式与异步模式 粒子群优化算法可以按粒子更新的方式分为同步模型( s y n c h r o n i z a t i o n ) 和异步 ( a s y n c h r o n i z a t i o n ) 模型。同步模型是指在每一次迭代中，所有粒子都并行同步更新 自身位置和速度后再从中选择种群最优粒子作为咄盟，如图2 2 所示。而粒子群优 化算法中的异步模型是指当粒子群中的任何一个粒子更新后，都要与种群中的最优 粒子进行比较，及时更新种群最优粒子的信息，如图2 3 所示。通过实验仿真发现， 在多数情况下，异步模型比同步模型能更快地找到问题的最优解。 太原理工大学硕士研究生学位论文 匿 2 - 2 同步p s o 模式结构图 f i g 2 - 2t h ef r a m eo fs y n c h r o n o u sp s oa l g o r i t h m p s o 椭鬏i 粒子 覃新、 9 一著n 岁 粒子l | 图2 3 异步p s o 模式结构图 f i g 2 - 3t h ef r a m eo fa s y n c h r o n o u sp s oa i g o d t h m 2 2 标准粒子群优化算法 2 2 1 惯性权重 在基本粒子群优化算法的基础上，s h i f 6 1 等学者在1 9 9 8 年的进化计算的国际会 议上发表了一篇论文a m o d i f i e d p a r t i c l es w a r m o p t i m i z e r ) ) 对前面的公式( 2 - 1 ) 进行 了修正，引入惯性权重因子缈： v i ( ，l + 1 ) = o ) v i ( ，z ) + q ，i ( p f x f ( ，z ) ) + c 2 r 2 ( p g x f ( ，1 ) ) ( 2 5 ) 1 4 太原理工大学硕士研究生学位论文 惯性权重c o 是用来控制粒子以前速度对当前速度的影响，它将影响粒子的全局 和局部搜索能力。选择一个合适的0 9 可以平衡全局和局部搜索能力，这样可以使算 法以最少的迭代次数，迅速找到最优解。初始时，s h i 将缈取为常数，后来实验发 现，动态