（系统工程专业论文）一种新的交叉粒子群算法及其应用.pdf

摘要 摘要 粒子群算法是基于群集智能、受到人工生命研究结果的启发而提出的一种现 代优化方法。作为一类随机全局优化技术，与传统优化方法相比较，对目标函数 的解析性质要求不高，所以常用于解决些复杂的、大规模的、非线性、不可微 的优化问题，近年来受到学术界的广泛重视。 本文介绍了标准粒子群算法和几种改进粒子群算法，在利用标准粒子群算法 优点的同时，进行了一些改进，例如：在位置更新方程中设置动力参数以限制粒 子在搜索区域内、采用减弱速度更新的策略减少速度更新的次数等。在此基础上 提出一种新的交叉粒子群算法，该算法交叉运行两个不同粒子群算法，提高了算 法的搜索性能。迸一步，在获得局部极小点情形下对函数采用拉伸等措施，给出 了交叉拉伸粒子群算法来搜索全局极小点，该算法也可用来处理多个最优解的问 题。数值实验结果表明，新算法解决高维非线性的无约束优化问题表现出了良好 的性能。 最后，将本文提出的算法应用于两个实际问题：六边形阵列天线方向图优化 设计问题和模式识别领域中的支持向量机训练问题，都取得了良好效果，这也表 明了新算法的有效性。 关键词：粒子群群集智能六边形阵列天线 a b m r a c ti l i a b s t r a c t b a s e do nn l es v ，i n ni n t e l l i g e n c e ，p a n i c l es w a n l lo p t i m i z a t i o n ( p s o ) a l g o r i t h mi sa k i n do fm o d e mo p d m i z a t i o nm e m o di n s p i r e db ym er e s e 神c ho ft h ea m f i c i a ll i f e a sa k i n do fs t o c h a s t i c g l o b a lo p t i m i z a t i o nm e t h o d ，c o m p a r c d、v i 地 t h e 缸a d i t i o n a l o p t i m i z a t i o nm e t h o d s ，p s 0d o e sn o tn e e d 也eh i 曲e rn a t u r eo fm eo b j e c t i v e c t i o n ， a 1 1 di sa l s ou s e dt ot h es o i u t i o no f s o m ec o m p l e x ，i a r g e - s c 鲥e ，n o n i i n e a ro p t i m i z a t i o n p r o b l e mw h i c hm a y b en o n d i 丘b r e m i a b l e t h e r e f b r e ，p s oa t 心a c t sa c a d e m i cr e s e a r c h e r s a t t e n t i o ni nr e c e n ty e a r s t h e 蚍卤d a r dp s oa l g o r i t h ma n dan 嘲b e ro fm o d m e dp s oa l g o r i t h m sa r cd i s c u s s e d i nm i sm e s i s t h 甜墩st ot h ea d v a n t a g e so ft 1 1 es t a n d a r dp s o ，w em o d 坶也ep s o a l g o r i m mi ns o m ea s p e c t s f o re x 锄p i e ，m ed y n a m i cp a r a m e t e ri si n 咖d u c e dt ou p d a t e t h ep o s i t i o ne q u a t i o n ，a r l dt h ep a n i c i e s 盯e1 i m i t e di nt h es e a r c hr e g i o n an e ws 饿a t e g y f o ru p 捌n gt l l es p e e di sa d o p t e d ，i nw h i c ht h es p e e di sw e a k c n e dl i n e 训y ，a t l dt h e n 岫b e ro ft h eu p d a t i n gs p e e di sr e d u c e d t h e nan e wc f o s s e dp s oa l g o r i t h mi s p r o p o s e d t h en e wa l g o r i m mi n t e r s e c t s t w od i f f b r e n 王p s oa l g o r i t h m s ，a n dt h e p e 0 册锄c eo ft l l es e a r c hp r o c e s si si m p r o v e d f 己t r m e m l o f e ，t h es t r e t c h i n gt e c h m q u e i s u s e di nt h en e i g h b o ro ft h el o c a lm i n i m u mf o rf i n d i n gt h eg l o b a lr n i n i m 啪，a i l dt h c n a n o m c rn e wc r o s s e d s t r e t c h i n gp s oa l g o r i t k ni sp r e s e n t e d t h en e wa l g o r i t h mi su s e d t os o l v es o m eu n c o n s t r a i n tn o n l i n e a ro p t i m i z a t i o np r o b l e m sw i 协h 培hd i m e n s i o n s ，a n d t h es i m u l a t e dr e s u l t ss h o wt h a tt l l ep e r f b r n l a n c eo ft h en e wa l g o r i t h mi sv e r y c o r r 巾e t i t i v ew i mo t h e rs i m i l a rp s oa 1 9 0 r i t l l m s i n 也ee n d ，w eu s et h en e w a l g o r i t h m t od e s i g nt l l eh e x a g o na 1 1 t e l l l l aa h a ya i l dt ot r a m m es u p p o r tv e c t o rm a c h i n ei np a t 把mr e c o g 血t i o na r e a ，a n do b t a i ns o m ef a v o r a b l e r e s u l t s ，w h i c ha l s os h o wt h a tt h en e wa l g o r i t h mi se f f 色c t i v e k e yw o r d s ：p a r t i c l es w a h n 叩t i m i z a t i o n ( p s o ) ，s w 黝i n t e l l i g e n c e ，s u p p o r t v e c 幻rm a c h i n e ，h e x a g o na m e i l n aa r r a y 。 v8 5 8 7 3 7 n - 学期删的研究t 作 工 ! 创新性声明 本人声明所呈交的论文是我个人在导帅指导卜进行的研究工作及 取得的研究成果。尽我所知，除r 文中特别加以标注和致谢中所罗列 的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也 不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的i 司志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 本人签名：垂躯面 日期础! 丝： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规 定，即：学校有权保留送交论文的复印件，允许查阅和借阅论文；学 校可以公布沦文的全部或部分内容，可以允许采用影印、缩印或其他 复制手段保存沦文。( 保密的论文在解密号遵守此规定) 本人签名：整盔遗面臼期迎! f ! 冱： 导师签名：丝兰坠口期堡! 摹! ! 兰! 第一章绪论 1 。1 1 课题意义 第一章绪论 1 1 弓l 言 最优化理论与算法1 6 5 】是一个重要的数学分支，是一门应用性很强的年轻学 科。它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优 方案，计算出最优的解。 虽然最优化可以追溯到十分古老的极值问题，然而，它成为一门独立的学科 是在上世纪4 0 年代朱，d a n t z i g 提出求解一般线性规划问题的单纯形法之后形成 的。现在，研究线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、 几何规划、整数规划等各种最优化问题的理论发展迅速，实际应用日益广泛。人 们在科学研究、工程技术和经济管理等诸多领域中经常遇到最优化问题，所以优 化技术一直受到广泛重视。特别是对求解复杂优化问题方法的探索，已成为众多 学科关注的焦点，这不仅在于其内在的复杂性有其重要的理论价值，也在于它们 在现实生活中的很多方面有着广泛的应用。优化算法的研究对改进算法性能，拓 宽算法应用领域完善算法体系起到关键性的作用。 最优化问题的一般形式为： 其中x 是决策变量，( 为目标函数，x c 舻为约束集或可行域。特别地 如果约束集j = r ”，则最优化问题称为无约束最优化问题： 约束最优化问题通常写为 r n i 导厂( x ) f m i n ，( x ) j j q ( j ) = 0 ，瘩西， l( x ) o ， f e ， 这里e 和分别是等式约束的指标集和不等式约束的指标集，q ( z ) 是约束函数a 当目标函数和约束函数均为线性函数时，问题称为线性规划。当目标函数和约束 函数中至少有一个是变量x 的非线性函数时，问题称为非线性规划。此外，根据 决策变量、目标函数和要求的不同，最优化还分成了整数规划、动态规划、网络 砖i ， xm ，j、l 一种新的交叉粒子群算法及j c 成用 规划、非光滑规划、随机规划、几何规划、多目标规划等若干分支。 现有的优化算法大致可以分为以下几类： ( 1 )经典算法：包括线性规划、非线性规划以及随机规划、非光滑规划、多 目标规划、几何规划、整数规划等各种最优化问题常采用的传统算法。 他们对目标函数的解析性质要求较高，而且计算复杂性一般很大，所以 只适应于求解小规模的简单问题，在工程中往往不能广泛应用： ( 2 )构造型算法：通过对问题的分析，希望用构造的方法快速建立问题的解。 通常这样的算法不是很有效，对于庞大复杂的问题，很难满足需要。例 如，调度问题中典型的构造方法有：j o h n s o n 法、g u p t a 法、c d s 法、 p a i m e r 法、d a u n e n b r i n 2 的快速接近法等； ( 3 )基于系统动态演化的方法：通过对自然界生物群体自适应优化现象的模 拟和研究，将优化的过程转换为系统动态的优化过程，如神经网络、粒 子群算法、进化算法和混沌搜索等，他们可以在合理的时间内逼近复杂 研究对象的最优解： ( 4 )混合型算法：根据不同问题的具体需要，利用各种算法的优点，克服其 弊端，从结构或操作上混合而产生的各种算法。实践证明这种方法往往 是快捷有效的。 优化方法涉及的工程领域很广，问题种类繁多，根据描述问题的函数形式， 可以把问题大致分为连续型函数优化问题和离散型函数优化问题两大类。本文主 要研究连续性函数优化问题，在本文以后章节都把它简称为函数优化。 函数优化问题通常可以描述为：s 为的子集( 即变量的定义域) 厂：s 斗尺 为 维实值函数，所谓函数屉s 域上全局最小化，就是寻找点x 。s ，使得厂( m m ) 在s 域上全局最小，即v x s ：厂( x 。) ，( x ) 。 函数优化问题又可以分为两类：无约束优化问题( u n c o n s t r a i n e do p t i m i z a t i o n p r o b l e m ) 和约束优化问题( c o n s t m i n e do p t i m i z a t i o np r o b l e m ) 。 无约束函数优化问题就是不含约束条件的函数优化问题。求解无约束函数优 化问题的优化算法通常分为确定性算法和随机性算法两种。确定性算法按照函数 变化的机理寻找最优解，搜索效率较商，过程可以再现，不足之处是寻优结果与 初值的选取有关，一般只能搜索到局部最优解，并且对函数的解析性质要求比较 高。常用的确定性优化方法有牛顿法、拟牛顿法、共轭梯度法、d f p 法、梯度法、 信赖域法、r o s e n b 而c k 法和p o w e l l 法，其基本思想都是山迭代算法而来，算法的 主要步骤为： 第一章绪论 ( 1 ) 在问题的求解域中选取一个初始点工o ，计算目标函数初始值胁) ； ( 2 ) 选取一个能使目标函数值下降的方向，沿该方向取一下降点x l ，使得 辑1 ) 领枷； ( 3 ) 当不存在下降方向，或虽然存在但点x l 与勒已足够的靠近，则认为找 到了一个最优解，结束求解过程。否则，令抽瑚i ，转( 2 ) 。 不同方法之间的差别主要是用不同的方法选取下降方向和下降点。许多方法 中均包含沿下降方向寻找下降点的问题，这就构成了一个一维搜索问题。求解一 维搜索问题的最优化方法有黄金分割法、二次插值法等。也就是说，无约束最优 化方法的求解是通过将求解一个多维最优化问题转化为求解一系列的一维搜索问 题来实现的。 社会和生产实践中的大量问题可以归结为函数优化问题，然而这些问题所建 立的目标函数是非常复杂的，主要表现为高维、多极值点、非线性、非凸和不可 微等特性，对于这些函数，用确定性算法很难实现寻优。近年来，人们通过研究 和模拟自然界生物群体自适应的优化现象，建立了基于随机搜索的现代优化技术， 例如人工神经网络、禁忌搜索、模拟退火、进化算法、遗传算法、蚁群算法、粒 子群算法及其混合优化策略等，这些现代的优化方法在解决用确定性方法无法解 决的问题时表现出强大的潜能，他们可以在合理的时间内逼近复杂研究对象的最 优解。这些算法的内容和思想涉及数学、物理学、神经科学、人工智能、统计力 学、生物进化等方面，很多都是以自然现象作为基础构造的算法，其中有一些称 为智能优化算法。用这些现代进化技术来解决复杂计算问题已经成为研究的热点， 形成了以群集智能为核心的理论体系，并已在一些实际应用领域取得了突破性的 进展。文献【1 2 】【2 0 】对进化算法中的遗传算法都有详细的介绍。 约束函数优化问题就是含有约束条件的函数优化问题。求解约束函数优化问 题的优化方法可分为问接法和直接法两大类。间接法是先将约束优化设计问题转 化为一系列的无约束优化设计问题，再调用无约束优化方法来求解。常用的方法 有：罚函数法、乘子法等。直接法是在选取下降方向和下降点时直接判断是否在 可行区域内，常用的方法有：可行方向法、约束随机方向法、复合形法等。求解 约束优化问题的方法众多，最常见最基本的是罚函数法。它把约束优化问题转化 为无约束优化问题，再用无约束问题的方法求解。和其它方法相比较，罚函数法 是一种相当有效，成功率较高的方法。 - 1 1 2群体智能( s w a r mi n t e l l i g e n c e ) 文献 4 8 】f 3 7 】都各自给出了群集智能的解释，群集智能的概念正是源于对群居 生物群体行为的观察和研究而得到的。基于群集智能的优化算法是一种仿生自然 种斯的交叉车丘了卅弊矬及其心用 界动物昆虫觅食、筑巢行为的模拟进化算法。 群集智能中的群体( s w a n n ) 指的是一组相互之间可以进行直接通信或者间接 通信( 通过改变局部环境) 的个体这组个体能够合作进行分布问题求解。而所谓的 群集智能指的是众多无智能的简单个体组成的群体，通过相互之间的简单合作表 现出复杂智能行为。这里，简单个体是具有简单能力( 如通信、搬运等) 的个体，这 种能力可以用某一简单的功能函数来表示。简单合作是指个体只能与其邻近的个 体进行某种简单的协同动作或通过改变环境间接地与其他个体进行简单通信。 群集智能在没有集中控制并且不提供全局模型的静提卜，可以为寻找复杂问 题的解决方案提供依据。b o n a b c a u 等人将任何启发于群居性生物群体的集体行为 而设计的算法都称为群体智能。目前主要的群集智能优化算法有：遗传算法、蚁 群算法、粒子群算法以及鱼群算法。他们均是一种随机搜索的迭代算法，对优化 对象的性态无要求。 群集智能的主要特点： ( 1 ) 协作性。协作是群体智能最主要的特点。协作不但有行为上的支持而且 还有信息上的共享。群居生物在捕食、御敌、迁徙和逃脱天敌的过程中， 无不是依靠个体间的协作来完成的。 ( 2 ) 分布性。群体中个体的行为没有集中控制，个体是呈分散状态的。这样 虽然个体的信息是局部的，但通过个体间的信息交流，整个群体的信息 却是全局的，因此群体行为往往可以达到全局最优。这个特点与计算机 网络的工作环境非常类似。 ( 3 ) 鲁棒性。因为群体中个体具有分布性，没有中央控制，因此，不会因为 某一个或者某几个个体的故障而影响整个问题的求解，这样的系统更具 有鲁棒性( r o b u s d 。 ( 4 ) 自适应性和快速性。群体中个体的行为能力都十分简单，往往用几条规 则就可以描述，但这些行为对环境变化都有自适应性和快速性，能根据 环境的变化快速做出反应。 我们研究群体智能是对生物智能( n a t u r a li n t e l l 唔e n c e ) 进行模拟以探求其中的 奥妙并将其用来解决实际问题，从这个意义上来说是人工智能的范畴。 群集智能的协作性、分布性、鲁棒性和快速性的特点使之在没有全局信息的 情况1 、，为寻找复杂问题的解决方案提供了快速可靠的基础，为系统复杂性以及 n p 问题、人工智能、认知科学等领域的基础理论问题研究开辟了新的研究途经， 同时电为诸如组合优化、工业动态生产控制、知识发现、机器人协作、电信路由 控制、无线移动网络基站优化、机场调度、高速公路控制等实际工程问题提供了 第一章 绪论 新的解决方法，因此，群智能研究具有重要的意义和广阔的前景。群集智能包括 多种仿生技术，在智能计算领域有两种典型的基于群集智能的算法：蚁群算法和 粒子群算法，前者是对蚂蚁群落搜索食物行为的模拟，后者是对鸟群搜索食物行 为的模拟。本文将研究群体智能中的粒子群算法( p a m c l es w a 硼o p t i m i z 砒i o n ， p s 0 1 。 1 2 粒子群算法的起源与研究现状 文献 2 4 】中定义人工生命( a r t i f i c i a il i f e ) 是来研究具有某些生命基本特征的人 工系统。人工生命包含两部分的内容：一是如何利用计算技术研究生物现象；二 是如何利用生物技术研究计算问题。这些模拟系统利用局部信息从而可能产生不 可预测的群体行为。现在已经有很多源于生物现象的计算技巧。例如，人工神经 网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 9 0 年代中期，e b e r h a r t 博士和k e n n e d y 博士受到人工生命的研究结果的启发， 提出了一种新的群集智能计算机术粒子群优化算法( p a l t i c l es w 黜 o p t i m i z a t i o n ，p s 0 ) ，其源于对鸟群和鱼群群体运动行为的研究。设想这样一个场 景：一群鸟在随机搜寻食物，在这个区域星只有一块食物，所有的鸟都不知道食物 在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是 什么昵? 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从 这种生物种群行为特性中得到启发并用于求解优化问题。 粒子群优化算法的基本思想是通过群体中个体之间的协作和信息若享来寻找 最优解，是一种基于群集智能方法的演化计算技术。粒子群算法利用生物群体内 个体的合作与竞争等复杂行为产生群体智能，该模型中每个个体都有一定的感知 能力，能够感知自己周围的局部最好位置的个体和整个种群的全局最好位置的个 体的存在，并根据当前的状态，调整自己下一步的行为，从而整个种群表现出一 定的智能性。在解决优化问题时，每个个体被看成二个潜在的解，经过反复迭代 最终得到所需要的全局最优解。粒子群算法概念简单、容易实现、搜索速度快、 搜索范围大、所含参数较少。 由于算法收敛速度快、设置参数少r 近年来受到学术界的广泛重视。但与其 它随机算法一样，它也存在参数控制和早熟收敛的问题，同时与其它随机算法相 比较。随着迭代次数的增加，粒子群算法搜索最优解的能力将会大大降低a 针对 上述问题，研究者提出了一些控制参数的改进方案和其它改进方案来增强算法逃 出局部极小点的能力，同时也提出了随着迭代次数的增加，如何增强算法搜索能 力的方案。经过改进的粒子群优化算法在函数优化、神经网络训练、模式分类、 种新的交叉粒于群箅：泣及具心用 模糊系统控制以及其它工程领域都得到了广泛的应用。 粒子群算法同遗传算法类似，是一种基于种群的优化= i ：具。系统初始化为一组 随机解，通过迭代搜寻最优解。但与遗传算法不同的是：粒子群算法是通过个体 之间的协作来寻找最优解，他利用了生物群体中信息共享会产生进化优势的思想， 而遗传算法是基于达尔文“适者生存，优胜劣汰”的进化思想的；遗传算法运用 交叉以及变异操作来进行搜索，而粒子群算法是通过粒子( 潜在的解) 在搜索空间追 随最优的粒子进行搜索；与遗传算法相比较，粒子群算法的优势在于操作简单， 容易实现同时又有深刻的智能背景，即适合科学研究，又特别适合工程应用。 一些文献的理论分析和实验仿真表明：基本蚁群算法适用于解决离散优化问 题，已经成功的运用在很多的组合优化问题上；基本遗传算法能解决连续参数优 化问题和离散优化问题，遗传算法对多峰极值函数求解，优化能力较弱，易陷入 局部次优解。但对曲面变化平缓的单峰函数一般采用遗传算法优化，其求解的精 度较高，能更接近最优解。标准p s o 适合于解决连续参数优化问题，因此主要是在 连续性优化问题上得到了广泛应用，也在些组合优化问题一卜得到了推广。 目自# ，研究者们已建立了各种粒子群算法：协同粒子群算法含边界变异的粒 子群算法，与其他进化算法相结合的混合粒子群算法，以及与确定性算法相结合 的粒子群算法，离散粒子群算法，自适应粒子群算法等。研究者们针对不同问题， 对标准粒子群算法进行了改进。经过改进的粒子群算法在搜索性能有了很大改进， 求解约束函数优化、多目标函数优化、多极值函数优化以及高维复杂函数优化都 表现出了好的搜索效果。关于粒子群算法的研究现状在文献 3 0 】 3 3 】【3 5 【2 3 】【2 6 4 6 】 f 6 3 1f 4 1 13 4 1 中都有详细介绍，这早不再一描述。 1 3 粒子群算法的应用 p s o 算法一经提出就吸引了广泛的注意，各种关于p s o 算法应用的研究成果不 断涌现，p s o 算法目前主要的应用领域可以划分为：函数优化、神经网络训练、工 业系统优化与控制以及其它遗传算法的应用领域等。下面简要介绍粒予群优化算 法在一些实际应用领域的进展。 在文献【5 7 l 中，将离散p s o 算法用于求解t s p 问题，体现了p s o 算法在解决离 散问题方面的发展；文献 5 8 、【5 9 研究了p s o 算法在噪声和动态环境f 的优化问 题，文献f 6 2 、【6 1 1 分别将p s 0 算法用于训练积单元神经网络( p r o d u c t u n “n e u r a l n e t w o r k s l 进行模式分类和训练模糊前向神经网络进行模式分类，都取得了满意的 效果：文献【6 0 将p s o 算法用于多目标函数优化( m u l t i o b j e c t i v ep r o b l e m s m o ) 问题， 第一章绻论7 文献【6 3 】、 6 4 】分别将p s o 算法用于实际系统的模拟和控制问题，也都得到了很好 的效果。 单纯形法( n o l d 小m e a d ) 是一种确定性搜索算法。本文提出的交叉p s 0 具有全局 随机性搜索的优点。在本文中，将单纯形法( n e l d e r - m e a d ) 和提出的交叉p s o 算法融 合成一种离效、易实现的混合优化算法，并用于解决六边形阵列天线问题和模式 识别领域中的支持向量机问题，都取得了满意的结果。 总的来说，粒子群优化算法与其它进化算法一样，可以解决几乎所有的优化问 题，其中最具应用前景的领域包括多目标问题的优化、系统设计、分类、模式识 别、生物系统建模、规划、信号处理、决策和模拟等等。目前，p s o 算法在模糊控 制器的设计、图像分割、e e g 信号模拟、语音识别、烧伤诊断以及探测移动目标 等方面已经有成功应用的先例。 1 4 论文的主要工作和内容安排 本文主要研究了智能优化算法粒子群算法( p a n i c l es w a n i lo p t i i n i z a t i o n ， p s o ) 。在介绍标准粒子群算法的基础上，介绍了几个改进的粒子群算法。对标准 粒子群算法的改进，主要体现在利用标准粒子群算法优点的同时，通过采用一些 措施，来提高算法的搜索能力。基于将具有全局邻域结构和具有局部邻域结构的 两个粒子群算法相结合的思想，提出了本文的交叉粒子群算法。交叉粒子群算法 是通过交叉运用两个改进的粒子群算法，来提高了算法的搜索性能。对这两个粒 子群算法都作了两点改进：一是在位置更新方程中设置动力参数，目的在于限制 粒子在搜索区域内；二是采用速度减弱策略，尽量减少速度更新的次数。为了进 一步提高算法的全局搜索能力，在交叉粒子群算法的基础上，提出了交叉拉伸粒 子群算法。交叉拉伸粒子群算法是在交叉粒子群算法搜索得到的局部极小点的邻 域内，利用单纯形算法进行精确搜索，在获得的最好点处，对目标函数采用拉伸 和排斥技术，使算法能够逃离局部极小点。 通过函数测试，本文提出的交叉算法在解决非线性的无约束优化问题时，表 现出良好的性能，数值实验表明新算法是有效的。最后，运用本文提出的交叉粒 子群算法来解决两个实际应用阅题，六边形阵列天线优化设计问题和训练模式识 别领域中的支持向量机问题，测试效果良好。 论文的主要内容安排如下： 第一章是绪论，对优化理论和群集智能体做了简单的介绍，指出了课题的研 究意义，叙述了粒子群算法的起源与研究现状。介绍了粒子群算法的应用。 种新的交叉粒子群臂：法及其应用 第二章对标准粒子群算法作了详细的描述，介绍了算法中粒子速度和位置更 新的方程，并分析了算法中三个关键的参数：脚、，、也对算法搜索所起的作用。 第三章介绍了几个改进的粒子群算法，它们分别用到了并行性的思想、调整 邻域结构的策略、自适应的理论、帮助函数逃离局部极小点的函数拉伸等技术。 它们在函数优化方面，与标准粒子群算法相比较，都可达到较好的搜索效果。 第四章提出一种新的交叉粒子群算法，主要借用了遗传算法中的交叉思想， 让具有不同寻优策略的粒子群算法并行交叉，提高了算法的收敛效率。并在算法 中采用了拉伸措施解决算法的早熟问题。最后用不同类型的函数对新算法进行测 试。 第血章将新算法用于训练模式识别领域巾的支持向量机问题和六边形阵列天 线优化设计问题，都取得了良好的效果。 第六章是本文的总结。 第二章标准粒子群算法介绍9 第二章标准粒子群算法介绍 2 1 1 粒子群算法的原理 2 1 粒子群优化算法 粒子群( p s o ) 优化算法是一种群集智能算法，是启发式优化算法的一种。它也 是一种进化算法，能有效的解决无约柬和约束全局优化问题。粒子群算法首先由 e b e f h a n 博士和 沁n n e d y 博士提出，1 9 9 5 年发展并作为一种随机优化方法。与其 他进化算法( 例如遗传算法、进化规划等) 的区别在于它是对社会行为的模拟，基本 思想不是源于自然选择中进化规律的冲突，而是源于群体组织的社会行为，例如 鸟群和鱼群在寻找食物当中，他们共同分享信息，有助于个体根据自己以前的经 历和同伴以前的经历做出正确的判断。这也是粒子群算法、蚁群算法、鱼群算法 的共性。 粒子群在定义的搜索区域内移动，每个粒子的位嚣代表所求解问题的候选解， 通常把粒子的位置带入目标函数来评估粒子的质量。模仿鸟群和鱼群的社会行为， 每个粒予根据它自己的经历和邻域粒子的经历、以及目前循环中，每个粒子和邻 域粒子分别得到的最好位置来调节它的位置。粒子朝着自己经历的最好位置移动 被称为认知学习，即粒子学习自己的经验；雨粒子职着邻域最好位置移动，被称 为社会学习，即粒子与邻域内的粒子分享信息。与邻域内粒子的相互作用，使粒 子对自芒j 的邻域有更多的了解，可帮助粒子决定移动的步长和方向。实际上，相 互作用促使粒子逃离可能的局部极小点并且朝着另一个更好的位置移动。 p s 0 算法已经被成功的应用于许多领域，例如非线性优化，神经网络和模式 识别。许多实验也证明p s o 算法能有效地解决非线性的多极值函数优化问题。 2 1 。2 粒子群算法的数学摸型 在一个以维搜索空间s 和由聊个粒子组成的种群中，第f 个粒子的位置是 用一个一维向量表示的，即葺= ( 蕾。，靠) ，每个粒子的位置都代表所求问题 的一个候选解。这些解得好坏由适应度函数值决定，适应度函数值越好则与之相 关联的解就越好。适应度函数与目标函数有关系，一般要根据具体闯题设定。粒 子的跳跃速度也是一个n 维向量，即v ，= ( v 。v j2 ，v 埘) 。第f 个粒子跳跃过程中所 遇至4 的最好位置是s 空间的一个点，可以表示为只= ( 只，只：，如) 。用g 表示粒 子群在前面跳跃过程中获得的种群最好位置的粒子，成表示种群最好粒子的位嚣。 1 ) 种新的交叉粒了群算法搜l 心用 f 表示此时的循环次数。 粒子群中粒子的初始位置是在搜索区域内随机产生，每个粒子群的初始速度 也是随机给定的。在搜索的过程中，粒子群和每个粒子所经历的最好位置及相应 的适应度函数值部分别被记忆下来。粒子群算法最基本的概念在于加速每个粒子 朝它自己所经历的和种群所经历的最好位置移动，移动过程可以用图2 1 来描述： 图2 1 p s o 粒子移动示意图 根据k e n n e d y 博士和e b e r h a r t 博士最初提出的p s o 算法，粒子群中每个粒子 跳跃的速度和下一次的位置分别由公式( 2 1 ) 和( 2 2 ) 决定： u ( f + 1 ) = ( r ) + c 1 ( 只( ，) 一一( ，) ) + f 2 t ( p x ( ，) 一( f ) ) ( 2 1 ) x ，o + 1 ) = 工，0 ) 十v ，( f + 1 ) ( 2 - 2 ) 其中卢1 ，2 3 ，c i ，c 2 是下的常量，叫做加速常数( a c c e l e r a t i o nc o n s t a n l s ) n 0 是均匀分粕任区间【0 ，l 】的随机数，户l ，2 ，是循环次数。 从( 2 1 1 式可看出，第f 个粒子新速度的计算与粒子前面的速度、粒子当前位置 和粒子个体最好位置的距离、种群所经历的最好位置与第f 个粒子当前位置的距离 有关系。根据( 2 2 ) 式，第f 个粒子将飞到一个新的位置。一般的，每个粒子的好坏 山目标阑数的适应度值决定。 每个粒子的最好解和整个粒子群的最好解是分别按照下列两式更新的，对 f l ，2 ，m j ： 。= p 。( ) ! 厂，( x ，( + 1 ) ) 厂( ，( 。) )f 2 3 1 p f = 1 x ，( f + 1 ) 驴厂( 一( ，+ 1 ) ) ( p ，( ，) ) 。二j p ，= a f g m i n 厂( p ，( f ) ) 厂( p 2 0 ) ) ，厂( p 。，( f ) ) ) ( 2 _ 4 ) 第二二章标准粒子群算法介绍 2 2 1 标准粒子群算法 2 2 标准的粒子群算法 k e n n e d y 博士和e b e r h a n 博士最初提出的p s o 算法的一个缺陷是对速度的大 小的调节缺少一个可靠的依据，这将隐藏着种群分散的危险。为了解决这个问题， 在文献【2 】中，e b e r h a i t 博士和k e n n d y 博士对最初提出的粒子群算法做了进一步的 改进，首先采用给所有粒子的跳越速度的绝对值设定一个最大值。， 一。= i 。，其中0 1 s s l ，。定义了搜索区域，v 取值范围在区间 _ v m 。，v m 。】， 降低了粒子离开搜索区域的可能性。若跳跃速度小于一v 。，则设定这个速度为 。；若大于v m 。，则取此时速度为v 们。最近的研究表明，单独这个修改并没 有增进算法的效率。尽管p s o 算法寻找最优区域比进化算法更快，一旦在这个区 域算法速度减慢，即使调节速度大小也不能找到更好粒子。p s o 算法另一个缺陷 是对指形区域极小值点的搜索能力很差。因此，在上述改进的基础上，采用给粒 予前面的速度设置了一个权系数来提高算法的搜索能力。这时粒予的跳跃速度 和下一次的位鼍分别由公式( 2 5 ) 和( 2 6 ) 决定 v ( ，+ 1 ) = c 巩( ，) + q - ( a ( ，) 一( ，) ) + 吒。t ( 以p ) 一t ( ，) j ( 2 - 5 ) ( ，+ 1 ) = ( f ) 十一p + 1 ) ( 2 6 ) 其中净l ，2 ，3 ，m ，参数国称为惯性权重，c i 、q 是正的常量，分别称为认知参数和 社会参数。小您是均匀分布在区间【o ，l 】的随机数，f = 1 2 ，是循环次数。 本文后面提到的标准p s o 就是经过上述修改的粒子群算法，下面将介绍标准 p s o 算法的工作流程，对它的参数进行分析，并介绍它的一般设置情形。 2 2 2 标准粒子群算法流程及其框图 标准p s o 算法的工作流程如下： 1 ) 选取初始种群，包括m 个粒子，每个粒子都随机给定起始位墅葺和速度q ， 。= 七d ，七i 1 ，l 】及参数设计； 2 ) 计算每个粒子的适应度； 3 ) 对每个粒子，将当前适应度值与其经历过的最好适应度值作比较，若好与 后者，则以当前的适应度值作为p f ，即以当日f 位置作为粒子所经历过的最 好位置，否则，阢不变； 4 ) 把这一循环中得到的种群最好位鬻的适应度值与段比较，若好与后者， 兰i 型坚墨塑塑翌墼业塑 则重新记录段的大小，否则以不变： 5 ) 利用方程( 2 - 5 ) 和( 2 6 ) 分别重新计算每个粒子的速度和位罱； 6 ) 如满足终止条件( 通常为产生足够好的适应度值或达到一一个预设最大代数 g ) ，程序终止，否则转2 1 。 粒子群算法的流程如图2 2 所示 开始 初始化粒子种群 计算每个粒子的适府度 根据粒子的适应度更新个体极值 与全局极值 根据公式( 2 5 ) j 。( 2 6 ) 更新粒子种群 的速度与位置 图2 2 2 2 3 标准粒子群算法参数分析 达到最大迭代次数或 满足最小误差标准 若粒子的速度快速增加，粒子将跳出搜索区域；若粒子的速度迅速下降，粒 子几乎静止：粒子不能逃离局部极小点。以上三方面都有可能造成搜索失败。为 了避免上述不希望出现的状况，对粒子行为和参数的关系应做重点分析，特别是 粒子的分散和收敛。文献f l8 也对粒子群算法的参数做了一定的分析，在本文中我 们也做了如f 分析。 p s 0 参数包括：群体规模，惯性权重，加速常数臼和c 2 ，最大速度。，最 大迭代次数，。 ( 1 ) 最大速度p 。 如果v 一。太高，粒子可能会飞过好解；如果v 。太小，粒子不能跳出局部，在 第二章标准粒子群冀= 法介绍 局部区域之外进行足够的探索，导致陷入局部最小点。 该限制有3 个目的： 1 ) 计算溢出，它将保持静止； 2 ) 实现人工学习和态度转变； 3 ) 决定问题空间搜索的精度。 ( 2 ) 权重因子 在p s o 算法中还有3 个权重因予：惯性权重国，加速常数c 】和c 2 。惯性权重使 粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。 加速常数c l 和c 2 代表将每个粒子推向只和以位置的统计加速项的权重。较小 的值允许粒子在被拉回之前可以在目标区域外徘徊，而较大的值则导致粒子突然 冲向或越过目标区域。 如果没有后两部分，郎c i = c 2 铷，粒子将一宜以当前的速度飞行，直到到达边 界。由于它只能搜索有限的区域，所以很难找到好解。 如果没有第1 部分，即国= o ，则速度只取决于粒子当前位置、历史最好位置b 和 种群最好位置p 。，速度本身没有记忆性。假设一个粒子位于全局最好位置，它将 保持静止。而其它粒予则飞向它本身最好位置只和全局最好位置见的加权中心。 在这种条件下，粒子群将收缩到当前的全局最好位景。更像一个局部算法。加上 第1 部分后，粒子有扩展搜索空间的趋势，即第1 部分有全局搜索能力。这也使得 的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。 如果没有第2 部分，即c l = 0 ，则粒子没有认知能力，也就是“只有社会( s o c i a l o n l y ) ”的模型。在粒子的相互作用下，有能力到达新的搜索空闾。它的收敛速度比 标准p s 0 算法更快，但对复杂问题，则比标准p s o 算法更容易陷入局部最优值点。 如果没有第3 部分，即c 2 = o ，则粒予之间没有社会信息共享，也就是“只有认知 ( c o g n i t i o no n l y ) ”的模型。因为个体间没有交互，一个规模为小的群体等价于运行了 m 个单个粒子的运行，因而得到最优解的几率非常小。 2 2 4 粒子群算法中的参数设置 标准p s 0 算法的搜索过程是非线性和很复杂的，尽管很难，但可以动态的调整 算法的参数，例如权重系数和加速因子，使搜索过程从全局到局部也就是从探测 到开发，来提高算法的搜索能力。标准p s o 算法在早期搜索阶段表现很好，当搜索 到一个优化解的邻近时，与其他算法相比较，则表现得不好。文献 4 4 】 4 3 】f 3 9 】f 2 5 】 也都提到了参数设置与粒子群算法搜索成败有关系。为了克服这个问题，许多研 究学者提出了许多改变p s o 算法参数的方法，一些是基于确定性规则，例如根据循 环次数增加或者减少权薰系数；一些是使用模糊规则，提供一些权重变化的反馈 信息，模糊规则的确定主要根据经验。qkv e n a y a g a f n o o r n l y 通过对权重系数卯动 态调整来提高p s o 算法的非线性搜索能力。权重系数用来控制以前速度对目前速 度的影响，调节了种群的局部和全局探测能力，并影响标准p s o 算法的收敛能力。 一个大的值则有助于全局探测，搜索新区域。然而，值越小，则有助于局部 探测，也就是更好的探测当前的搜索区域。一个合适的值将平衡局部探测和全 局探测的能力，因此也可以减少搜索到局部最优解的循环次数。取一个小值， 算法通常会迅速收敛到一个次优解，国取值太大，则会导致不收敛。值一般采 用线性递减从1 到接近o 或者固定的值。加速系数c i ，c 2 控制粒子在一个单的循环 中移动多远。典型的是把这两个的值都设定为2 ，尽管有时通过设定它俩值不相等 来提高算法的性能。早期的试验将脚固定为1 o ，c i 和c 2 固定为2 0 ，因此v 。成为唯 一需要调节的参数，通常设为每维变化范围的l o 2 0 。引入惯性权重可消除 对v 。的需要，因为它们的作用都是维护全局和局部搜索能力的平衡。这样，当v 。 增加时，可通过减小国来达到平衡搜索。而的减小可使得所需的迭代次数变小。 从这个意义上看，可以将v 。固定为每维变量的变化范围，只对进行调节。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的粒子，而 在后期有较高的开发能力以加快收敛速度。为此可将国设为随时间线性减小，例 如由1 4 至0 0 ，由0 9 至0 0 4 ，由o 9 5 到o 2 等。 2 _ 3 小结 在文献 5 0 4 9 】【3 6 】中，我们都可以了解到粒子群算法的一些优点和缺点。标 准p s d 算法具有自身的一些优点，例如种群中的每个粒子代表了一个候选解，不 需要运用重组、杂交、变异等操作；粒子之间存在一种建设性合作；算法所需参 数不多。每个粒子根据两个点来调整它的位置：到目前为止它自己所达到的最好 位置和它的邻域所达到的最好位置。这两部分的调整分别被称为认知学习和社会 学习。通过与它邻近粒子的相互交流，粒子可以对周围环境得到更多地了解，这 可以帮助它决定移动的方向和步长的大小。事实上，相互阳j 的作用也促进粒子逃 离局部极小点向另一个更好的位置移动。比其它进化算法能更快地找到有质量的 解。 然而，标准p s o 算法也存在一些缺陷，随着循环次数的增加，将不具备进一步 改进解质量的能力。在我们的研究中已经发现标准的p s o 模型存在三方面的主要问 题：早熟收敛：参数控制和缺少动态的速度调节导致无能力继续寻找最优解。造 一一 笙三兰塑堡塾王登墨鲨坌塑 ! ! 成标准p s o 算法搜索失败的主要原因有： ( 1 ) 粒子的速度迅速增加，粒子群将跑到搜索区域的外面： ( 2 ) 粒子的速度迅速减少，粒子群几乎停止； ( 3 ) 粒子群不能跳出局部最优解。 参数控制是进化算