（应用数学专业论文）优化问题的几种智能算法.pdf

摘要 摘要 智能优化算法一般是利用自然、社会等复杂系统与优化问题的某些相似性而 逐步发展起来的，它按照某些概率规则对搜索空间中的一组初始解进行操作，从 而得到下一组可行解。因此算法本身的搜索机制决定了算法的寻优性能。 本文针对粒子群优化算法、混合蛙跳算法和和声搜索算法这三种智能优化算 法作了比较深入的研究，在此基础上将这些算法作了进一步的改进和推广，取得 了较为满意的结果。其主要工作概述如下： 1 针对标准粒子群优化算法在处理复杂函数优化问题时容易陷入局部最优、收 敛精度低的缺点，利用生物学中的吸引排斥机制修正了粒子群优化算法的更 新策略，由此提出了一种基于吸引排斥机制的粒子群优化算法，理论分析和 数值试验表明算法有较好的优化性能。 2 对混合蛙跳算法作了进一步的研究，修正了其搜索机制，维持了子群的多样 性。实验仿真结果表明，改进后的混合蛙跳算法提高了算法的收敛速度，有 效地避免了s f l a 的早熟收敛问题，从而改善了对复杂问题的搜索效率，验证 了算法的可行性和有效性。 3 首先用均匀设计讨论了和声搜索算法参数的设定问题，实验结果证明了这种 确定参数方法的可行性；其次针对单个体的和声搜索算法，提出了两种改进 的和声搜索算法：动态多库和声搜索算法和求解复杂函数优化问题的和声搜 索算法，实验结果表明改进后的算法对复杂函数优化问题表现出了极强的适 应性、稳定性、鲁棒性和全局搜索能力。 关键词：粒子群优化算法混合蛙跳算法和声搜索算法均匀设计 智能优化 a b s t r a c t a b s t r a c t i n t e l l i g e n to p t i m i z a t i o na l g o r i t h mi sg r a d u a l l yd e v e l o p e db yt h eu s eo fc e r t a i n s i m i l a r i t i e sb e t w e e nt h ec o m p l e xs y s t e m s ( e g ，n a t u r a lo rs o c i a l ) a n do p t i m i z a t i o n p r o b l e m s i to b t a i n st h en e x tf e a s i b l es o l u t i o n sb yt h eo p e r a t i o no nas e to fi n i t i a l s o l u t i o n si nt h es e a r c hs p a c ea c c o r d i n gt ot h ec e r t a i nr u l e so fp r o b a b i l i t y t h e r e f o r e ，t h e s e a r c hm e c h a n i s mo ft h ea l g o r i t h md e t e r m i n e si t so p t i m i z a t i o np e r f o r m a n c e t h i st h e s i si sd e v o t e dt ot h r e ei n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ：p a r t i c l es w a r m o p t i m i z a t i o n ( p s o ) a l g o r i t h m ，s h u f f l e df r o gl e a p i n ga l g o r i t h m ( s f l a ) a n dh a r m o n y s e a r c h ( h s ) a l g o r i t h m o nt h eb a s i so ft h e s e ，t h ea l g o r i t h m sa r ef u r t h e ri m p r o v e da n d g e n e r a l i z e dt oo b t a i ns a t i s f a c t o r yr e s u l t s t h em a i nw o r k sa r es u m m a r i z e da sf o l l o w s ： 1 s t a n d a r dp s oa l g o r i t h mt r a p si n t ol o c a lo p t i m ae a s i l ya n dh a sl o wc o n v e r g e n c e a c c u r a c yw h e ni ti su s e dt oa d d r e s sc o m p l e xo p t i m i z a t i o nf u n c t i o n s i no r d e rt o o v e r c o m et h es h o r t c o m i n g s ，t h eu p d a t i n gs t r a t e g yo fp s oa l g o r i t h mi sm o d i f i e d b yt h eu s eo ft h ea t t r a c t i o n - r e p u l s i o nm e c h a n i s mi nt h ef i e l do fb i o l o g y ，a n dt h e n a na t t r a c t i o n - r e p u l s i o nm e c h a n i s m - b a s e dp s oa l g o r i t h mi sp r o p o s e d t h e o r e t i c a l a n a l y s i sa n dn u m e r i c a le x p e r i m e n t sd e m o n s t r a t et h a tt h ep r o p o s e da l g o r i t h mh a sa b e t t e ro p t i m i z a t i o np e r f o r m a n c e 2 t h ef u r t h e rr e s e a r c ho fs f l ai sm a d e s p e c i a l l ys p e a k i n g ，t h es e a r c hm e c h a n i s m o ft h ea l g o r i t h mi sm o d i f i e dt om a i n t a i ni t ss u b p o p u l a t i o nd i v e r s i t y s i m u l a t i o n r e s u l t sd e m o n s t r a t et h ei m p r o v e ds f l ae n h a n c e sc o n v e r g e n c ev e l o c i t ya n da v o i d s p r e m a t u r ec o n v e r g e n c ee f f e c t i v e l y ，t h u si m p r o v i n gt h ee f f i c i e n c yo fs e a r c hf o r c o m p l e x f u n c t i o n sa n dv a l i d a t i n gt h ef e a s i b i l i t ya n de f f e c t i v e n e s so f t h es f l a 3 f i r s t l y ，t h ee s t a b l i s h m e n to fp a r a m e t e r so fh sa l g o r i t h mi sd i s c u s s e db y t h eu s eo f u n i f o r md e s i g n ；e x p e r i m e n t a lr e s u l t ss h o wt h em e t h o di sf e a s i b l e s e c o n d l y , f o r s i n g l ei n d i v i d u a le v o l u t i o n a r yh sa l g o r i t h m ，t w oi m p r o v e dh sa l g o r i t h m sa r e p r o p o s e d ：d y n a m i cm u l t i m e m o r yh sa l g o r i t h ma n dh sa l g o r i t h mf o rs o l v i n g c o m p l e xf u n c t i o n s ，e x p e r i m e n t a l r e s u l t si n d i c a t et h ei m p r o v e da l g o r i t h m sf o r c o m p l e xf u n c t i o n ss h o wt h es t r o n ga d a p t a b i l i t y , s t a b i l i t y , r o b u s t n e s sa n dg l o b a l s e a r c hc a p a b i l i t y k e y w o r d s ：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 m s h u f f l e df r o gl e a p i n ga l g o r i t h m h a r m o n ys e a r c ha l g o r i t h m u n i f o r md e s i g ni n t e l l i g e n to p t i m i z a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定) 导师签名：列兰蟹旦一 日期：切刁歹i i 第一章绪论 第一章绪论 本章首先给出了论文的写作背景及其研究意义，其次简要介绍了近几年来备 受关注的几种新型智能优化算法( 粒子群优化算法、混合蛙跳算法和和声搜索算 法) 的研究概况，最后，扼要介绍了本文的主要工作。 1 1 引言 在科学、社会、经济、军事、管理和工程等领域中，许多最新的进展都依赖 于全局优化方法，即计算出相应优化问题的全局最优解的数值方法。全局优化问 题的来源相当广泛，包括经济建模、金融、网络和运输、通信系统的设计、数据 库和芯片设计、图像处理、核能和机械设计、化学工程设计与控制、分子生物学 以及环境工程【l 】等。目前对全局优化问题的求解研究主要有两个方面：一方面是以 分析与泛函为基础的，对全局优化问题进行严格的理论证明，提出确切的求解算 法一常规的优化方法，这些方法只要求解的问题满足一定的条件，就能求出问题的 最优解；另一方面是以自然、社会等复杂系统中的智能体或非智能体表现出的智 能现象为基础而设计的智能搜索算法，其特点是算法机理简单，易于理解，而且 算法设计简洁，对目标函数没有特殊的要求，易于编程计算。虽然这些算法不能 够保证一定能得到问题的最优解，但很容易应用于各种优化问题，并能在合理的 时间范围内给出所求问题的满意解，达到问题所期望的结果要求。 由于全局优化问题的复杂性、约束性、非线性、多极值性，人们常常无法借 助于常规的优化方法，如单纯形法、牛顿法、共轭梯度法、模式搜索法、区间算 法、分枝定界法和填充函数法等，来求解这些问题。针对优化领域中的这些问题， 随后基于生物学、物理学、和人工智能等的随机智能搜索算法的出现和发展，为 优化领域中的这些问题的解决提供了比较有效的方法。虽然智能搜索算法极大地 依赖于计算机的能力，但当其他算法由于函数不规则或维度过高等原因而失效时， 智能搜索算法仍能在可接受的时间范围内给出问题的满意解。比较典型的智能优 化算法有：遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、模拟退火( s i m u l a t e da n n e a l i n g , s a ) 、 禁忌搜索( t a b us e a r c h ，t s ) 、蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 等，目前， 它们已经成为解决优化问题强有力的工具。 近年来又涌现出了许多新的优化算法，如粒子群优化算法( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) 2 , 3 】、混合分散遗传禁忌( h y b r i ds c a t t e rg e n e t i ct a b u ，h s g t ) 躬、 分形优化方法( f r a c t a lo p t i m i z a t i o na p p r o a c h ，f o a ) 5 1 、列队竞争算法( l i n eu p c o m p e t i t i o na l g o r i t h m ，l c a ) t 6 1 、均匀布点优化方法 7 1 、变异基遗传算法 2优化问题的儿种智能算法 ( m u t a t i o n b a s e dg e n e t i ca l g o r i t h m ，m g a ) t 引、和声搜索算法( h a r m o n ys e a r c h ，h s ) t 9 1 、 统计归纳算法( s t a t i s t i ci n d u c t i v ea l g o r i t h m ，s i a ) 1 0 】、人工鱼群算、法【】、类电磁机制 算法( e l e c t r o m a g n e t i s m 1 i k em e c h a n i s m ，e m ) 1 2 j 、人口迁移算法( p o p u l a t i o nm i g r a t i o n a l g o r i t h m ，p m a ) 【1 3 】、混合蛙跳算法( s h u f f l e df r o gl e a p i n ga l g o r i t h m ，s f l a ) t 1 4 等。 这些新的全局优化方法的出现，表明了人们对全局优化方法的需求远未满足。全 局优化方法的广泛应用以及全局优化问题本身的复杂性导致了这些新的优化方法 的不断出现，对这些优化算法的研究也有助于很多复杂科学、社会、经济、军事、 管理和工程问题的解决。 目前，作为出现不久的三种新型智能优化算法一p s o 算法、s f l a 和h s 算法， 对它们的研究与应用还十分有限，尽管通过一些实验和比较已经显示出了这三种 算法强大的搜索能力和较强的稳定性和鲁棒性，但是当f j 的研究还不十分成熟与 全面，对其研究还远不像其他启发式算法( 如g a ) 那样有系统的分析方法和较好 的数学基础，这就导致了现有研究还存在很多问题，因而在理论和实践方面上有 许多问题需要更深入的研究与解决。由于全局优化这一学科的重要性，研究与发 展p s o 算法、s f l a 和h s 算法，一方面可以进一步丰富全局优化方法，使这三种 智能优化算法的优化性能更加完善；另一方面可以在全局优化中很好地应用p s o 算法、s f l a 、h s 算法解决实际问题，进一步扩大其应用范围。 1 2 三种智能优化算法的研究概况 模仿自然、社会等复杂系统中表现出的群体智能行为为解决复杂、约束、非 线性和多极值的全局优化问题提供了新的思路和手段。下面对p s o 算法、s f l a 和h s 算法的研究概况做一简单的介绍。 1 2 1 粒子群优化算法的研究概况 p s o 算法是由美国社会心理学家j a m e sk e n n e d y 博士和电气工程师r u s s e l l e b e r h a r t 博士于1 9 9 5 年开发的一种演化计算技术，是一种具有群体智慧的概念， 该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简 单的速度位移搜索模型，源自于人工生命( a r t i f i c i a ll i f e ) 和演化计算理论【2 3 】。其中 “群( s w a r m ) 来源于粒子群，它符合m i l l o n a s 在开发应用于人工生命的模型时所 提出的群体智能的五条基本原则【l5 】： ( 1 ) 邻近原贝j j ( p r o x i m i t yp r i n c i p l e ) ( 2 ) 品质原贝l j ( q u a l i t yp r i n c i p l e ) ( 3 ) 多样性反应原, 贝l j ( p r i n c i p l eo fd i v e r s er e s p o n s e ) 第一章绪论 ( 4 ) 稳定性原贝j j ( s t a b i l i t yp r i n c i p l e ) ( 5 ) 适应性原贝j j ( a d a p t a b i l i t yp r i n c i p l e ) 而“粒子则是一个折衷的选择，因为既需要将群体中的成员描述为没有质量、 没有体积，同时也需要描述它的速度和加速状态，其运动速度受到自身和群体的 历史运动状态信息影响，以自身和群体的历史最优信息来对粒子当前的运动方向 和运动速度大小加以影响，较好地协调了粒子本身和群体运动之间的关系。目前 p s o 算法已被“国际演化计算会议 ( c e c ) 歹u 为讨论专题之一，是继a c o 算法之 后的又一种新的群体智能( s w a r mi n t e l l i g e n c e ) 算法。 同g a 相比，p s o 算法的优势在于概念简单、计算快速、容易实现，并且没 有过多参数需要调整。算法自1 9 9 5 年提出以来，由于其简单而明确的实际背景， 以及前述的诸多优点，使得很多研究者加入到对这种算法的改进研究中，主要体 现在以下几个方面：算法的二进制模型【1 6 1 、参数的选择与设计【1 7 之4 1 、群体组织与 进化以及与进化计算等概念相结合的混合算法【2 ”8 】等。这些改进丰富了p s o 算法 的思想，拓展了算法的寻优机理，促使算法得到了快速的发展。由于p s o 算法在 目标函数性态、参数设置、适应度概率进化特征和算法的收敛性等方面，都有其 它演化算法无法比拟的优点，其理论研究【2 9 圳】与应用研究【3 2 别】也取得了很大的进 展，己经在不同学科中得以成功应用，如函数优化、t s p 问题、作业调度优化、 经济分配、神经网络训练、数据挖掘、车辆路径、图像处理、模式分类、模糊系 统控制、参数辨识、电力系统优化等。总的来说，对p s o 算法的这些研究，大体 上可以归结为算法的变形与改进、算法的参数设置、算法的拓扑结构、与其他算 法的融合、应用。 p s o 算法与人工生命，特别是进化算法有着极为特殊的联系，都遵循着自然 界的进化原则，但比进化算法又更多地保留了基于群体的全局搜索策略。它采用 简单的速度位移模型，避免了复杂的遗传操作，同时它特有的记忆功能使其可以 动态地跟踪当前搜索的最优信息并适时地调整其搜索策略，具有较强的全局收敛 能力和鲁棒性，且不需要借助问题的特征信息。因此，p s o 算法是一种更高效的 并行搜索算法，非常适用于对复杂环境中的优化问题的求解。 1 2 2 混合蛙跳算法的研究概况 在我们生存的大自然中，某些物种在它们漫长的进化过程中所形成的生存方 式和觅食行为为人类解决某些问题带来了新的启发。2 0 0 0 年，e u s u f f 和l a n s e y 通 过类比青蛙的觅食行为与优化问题求解的相似性而提出了一种新的基于全局协同 搜索的智能优化方法混合蛙跳算法。作为一种全新的仿生优化算法，s f l a 结合 了m e m e t i c 算法( m 锄e t i ca l g o r i t h m ，m a ) 和p s o 算法两者的优点，是继p s o 算 4 优化问题的儿种智能算法 法之后的又一种新的群体智能优化算法，具有概念简单、参数少、计算速度快、 全局寻优能力强，易于实现等特点，并首次成功地解决了组合优化问题。近年来， 这种算法不断得到完善和广泛的工程应用【1 4 , 5 2 - 5 8 ，如函数优化、地下水管网优化设 计、齿轮问题、t s p 问题、下料问题等，进一步证明了它在解决优化问题上的优 越性。 s f l a 存在群体( 蛙群) 的产生、进化、交叉、信息互换等，拥有更加灵活进 化机制，在局部搜索中采用生物从一个个体向另一个个体传播思想的进化方式， 在任何时刻允许局部搜索中信息的传递，从而可以通过改变个体自身移动步长来 寻找适合自己的最好位置，提高局部优选率。在进行局部最优搜索的基础上更新 全局最优解，最终在满足规定迭代次数和收敛条件下终止算法，否则继续进行寻 优。因而s f l a 具有全局优化与局部精细搜索的优点，可以用来优化连续问题和 离散问题，并且具有较强的鲁棒性和稳定性。 1 2 3 和声搜索算法的研究现概况 在音乐创作过程中，乐师们凭借自己的记忆，通过反复调整乐队中各种乐器 的音调，最终达到一个美妙悦耳的和声状态。g e e m 等人受这一现象的启发，于2 0 0 1 年提出了一种基于乐队和声调谐原理的新算法和声搜索算法【9 】。与其他进化算法 相比，h s 算法机理简单，易于理解，解的产生方式新颖，容易编程实现，且只有 少数参数需要调整。 类似于g a 对进化以及s a 对退火机制的模拟，h s 算法的启发式搜索机制依 赖于和声记忆库( h a r m o n ym e m o r y ，h m ) 和新的解的产生方式，在整个迭代搜索过 程中，较优解的特征能够得到很好地保留，同时最差解的特征在迭代中不断地被 排除。算法首先产生h m s ( h a r m o n ym e m o r ys i z e ) 个初始解( 和声) 放入h m 内， 以概率h m r c ( h a r m o n ym e m o r yc o n s i d e r i n gr a t e ) 在h m 内搜索新的解，以概 率1 - h m r c 在h m 外变量的可行域中搜索。然后算法以概率p a r ( p i t c ha d j u s t i n g r a t e ) 对新的解进行局部扰动。判断新的解的目标函数值是否优于h m 内的最差 解的目标函数值，若是，则替换之；然后不断迭代，直至达到预定的迭代次数为 止。 作为一种全新的智能优化方法，和声搜索算法已经成功应用于科学和工程领 域【9 , 5 9 - - 6 7 】，如函数优化、管道铺设、t s p 问题、结构设计、岩土工程、交通路径以 及环境参数校正等领域，在有关问题上展示了较g a 、s a 和t s 更好的性能【9 】，显 示了这种算法具有较强的鲁棒性、稳定性和广泛的应用前景，是一种搜索能力强 大的全局优化方法。 第一章绪论 1 3 本文的主要工作 本文主要做了三方面的工作：p s o 算法的改进，s f l a 的改进，h s 算法参数 的设定问题及其改进研究。全文共分四章，具体内容安排如下： 第一章首先阐述了本文的选题背景和研究意义，然后对p s o 算法、s f l a 、 h s 算法的发展概况进行简单回顾，最后给出了本文的主要研究工作。 第二章介绍了标准p s o 算法，对其作了进一步的研究，利用粒子间的吸引排 斥机制，构造了新的速度更新公式，给出了一种改进的p s o 算法：基于吸引排斥 机制的p s o 算法，并对改进的算法做了理论分析和数值仿真。 第三章介绍了基本s f l a 的搜索原理及算法流程，借鉴其他启发式搜索算法 的部分思想，将其更新策略做了进一步修正，提出了改进的s f l a ，数值试验验证 了算法的可行性和有效性。 第四章介绍了基本h s 算法的思想，基于均匀设计方法讨论了h s 算法参数的 设定问题，仿真实验说明了这种方法的可行性，提出了两种改进的h s 算法：动态 多库h s 算法和求解复杂函数优化问题的h s 算法，实验证明改进后算法的求解精 度和稳定性较原有算法都有了很大提高，并能很好地求解复杂函数优化问题。 最后是本文的结束语、致谢、参考文献以及作者在攻读硕士学位期间的主要 研究成果。 第二二章求解优化问题的粒子群优化算法 7 第二章求解优化问题的粒子群优化算法 本章介绍了标准p s o 算法的搜索原理，针对标准p s o 算法容易陷入局部最优， 收敛速度慢的问题，利用生物学中的吸引排斥机制，修正了算法的速度更新公式， 由此提出了一个改进的p s o 算法：基于吸引排斥机制的p s o 算法，并用4 个典型 的多峰测试函数对新算法进行了实验，结果表明，新算法在稳定性和收敛性上优 于所比较的p s o 算法，提高了后期迭代的收敛速度，有效地避免了p s o 算法的早 熟收敛问题，而且具有较高的收敛精度和较好的鲁棒性。 2 1 引言 1 9 9 7 年斯坦福大学的w o l p e r t 和m a c r e a d y 教授在i e e et r a n s a c t i o n so n e v o l u t i o n a r yc o m p u t a t i o n 上提出了著名的无免费午餐定理( n of r e el u n c h ， n f l ) 醯】，它是最优化理论研究的一个重要成果，在优化领域有着极为重要的意义。 该定理指出没有一种算法对任何问题都是最优的，不同的算法都有其不同的应用 优势与不足，算法之间存在着互补性。因此，从解决实际问题的角度出发，为进 一步提高算法的优化性能和拓宽算法的适用范围，融合不同类型机制的优化算法， 充分发挥它们各自的优势是解决优化问题的必然发展趋势。 2 2 标准粒子群优化算法 1 9 9 5 年j a m e sk e n n e d y 和r u s s e l le b e r h a r t 在i e e e 国际神经网络学术会议上正 式发表了题为“p a r t i c l e ss w a r mo p t i m i z a t i o n 2 】，的文章，标志着粒子群优化算法的 诞生。随后s h i 等人【3 】在算法中引入惯性权重国来更好地控制收敛( c o n v e r g e n c e ) 和 探索( e x p l o r a t i o n ) ，形成了当前的标准p s o 算法。 从算法结构角度上讲，p s o 算法与其他演化算法( 如g a ) 十分相似，都是基 于群体策略的进化算法模式。p s o 算法通过个体问的协作与竞争实现全局搜索， 是一种基于迭代的优化工具。系统初始化为一组随机解，通过统计迭代过程中自 身的最优和群体的最优来不断地修正自己的前进方向和速度大小，从而形成群体 寻优的正反馈机制，但它没有g a 的交叉算子以及变异算子，而是粒子在搜索空 间追随两个最优的粒子( 个体最优、全局最优) 进行搜索。 2 2 1 标准p s o 算法 在标准p s o 算法中，朋个粒子组成一个群体，每个粒子作为以维搜索空间中 待优化问题的一个可行解，通过粒子之间的协作与竞争来寻找问题的最优解。设 优化问题的儿种智能算法 第i 个粒子的h i s 位置表示为西= ( 五。，薯：，x i n ) ，f i ；s 速度用坼= ( v 。，m 2 ，v i n ) 表 示，迄今为止搜索到的最好位置用p i = ( b 。，p i ：，p i ) 表示，也记为p b e s t ，群体中 所有粒子迄今为止搜索到的最好位置用以= ( 岛。，p g ：，) 表示，也记为g b e s t 。 对第k 次进化，第f 个粒子的第维状态( 1 j n ) 根据如下方程来更新其速度和位 置【3 】 ， 噶+ 1 = 缈呓+ q r l ( p b e s t u 一嘞) + c 2 r 2 ( g b e s t j 一菇) ( 2 - 1 ) 苟“= 苟+ 噶+ 1 ( 2 - 2 ) 其中，扛1 ，2 ，m ，j = 1 ，2 ，以，缈称为惯性权重( i n e r t i aw e i g h t ) 或动量系数， 它决定了粒子历史速度信息对当前速度信息的影响，执行局部搜索与全局搜索之 间的平衡角色，当缈较大时，可以加大粒子群的搜索范围，适宜于对搜索空间进 行大范围探索( e x p l o r a t i o n ) ，对未探测空间搜索能力强，局部精细搜索能力弱，提 高搜索的全局性能；反之，缈较小时，算法的局部搜索能力增强，适宜于进行小 范围开发( e x p l o i t a t i o n ) ，而搜索新空间的能力减弱，粒子的搜索性能得到改善。e l 和 厶称为加速系数( a c c e l e r a t i o nc o e f f i c i e n t ) 或学习因子( 1 e a m i n gf a c t o r ) ，表示粒子受个 体认知和社会认识的影响程度，用来调节向n 和p 。方向飞行的最大移动步长。 ，1 ，r 2 u ( 0 ，1 ) 。 此外，为了控制粒子的最大全局探索能力，粒子i 在不断根据速度调整自己的 位置的时候，还要受到最大速度v 。的限制，即当l 屹i 一一，时，将限定i 屹l = v t 啪， ( 1 ，聆) ，这样可以防止粒子远离搜索空间。 式( 2 1 ) 中的第一部分称为动量部分，表示粒子对当前自身运动状态的信任， 为粒子提供了一个必要的动量，使其依据自身速度进行惯性运动，是粒子能够飞 行的基本保证；第二部分称为个体认知( c o n 舻i t i o n ) 部分，代表了粒子自身的经验 和思考，鼓励粒子飞向自身曾经发现的最好位置；第三部分称为社会( s o c i a l ) 部分， 表示粒子间的信息共享与相互协作，它引导粒子飞向群体中的最好位置。这三个 部分之间的相互平衡和制约决定了算法的主要搜索性能。 p s o 算法的终止条件与g a 基本一致，根据具体问题一般为取得达到设定的优 化精度或达到给定的进化次数，满足进化终止条件则认为优化过程结束。 p s o 算法是一种新的启发式全局优化算法，可以看出它与g a 有相当大的相 似性，都是通过迭代的方法寻得问题的最优解，也采用“群体”和“进化的概 念，同样也根据适应度大小来更新信息。不同的是p s o 算法结构简单，不使用g a 中的遗传、变异等算子。由于是群体粒子的同时并行计算，因此比其它进化算法 有较快的收敛速度。p s o 算法同g a 一样也可以用于解决非线性、不可微、多极 值的复杂优化问题。 第二章求解优化问题的粒子群优化算法 9 2 2 。2 标准p s o 算法流程 s t e p l 设置算法参数，初始化群体，在搜索空间内随机设置粒子的初始位 置和速度，并将各粒子的b 设为初始位置，取p g 为只中的最优的。 s t e p 2 计算每个粒子的适应度。 s t e p 3对每个粒子，将其适应度与其历史最优位置麒的适应度进行比较， 如果优于研，则将其作为当前最优位置易。 s t e p 4对每个粒子，将当前最优位置易与群体历史最优位置以进行比较， 如果优于p 。，则将其作为群体最优位置珞，并重新设置p s 的索引号。 s t e p 5根据式( 2 1 ) 、式( 2 2 ) 更新粒子的速度和位置。 s t e p 6 如未达到终止条件，则返回s t e p 2 ；否则，输出最优适应度的相关信 息。 2 2 3 模型分析 为了便于分析p s o 算法的搜索机制，对式( 2 - 1 ) 、式( 2 - 2 ) 进行简化，仅考虑一 个粒子的一维情形。这里参考了文献 3 0 】的部分内容。有关简化模型的稳定性分析 如下： 令：c 1 ，1 + c 2 r 2 ，p ：q r l p b e s - t + c 2 _ r 2 - g b e s t ，可以看出p 是两个最优的 c 。r l + c ，r 2 加权平均，而u ( o ，e i + c 2 ) 。 通过简单的代换，式( 2 1 ) 和式( 2 2 ) 可以化为式( 2 - 3 ) v ”= 国v + ( p x ) ( 2 - 3 ) 再令y = p x ，则式( 2 3 ) 、( 2 - 2 ) 分别可以化为 v 川= c o y + 咖 ( 2 4 ) y “1 = 一c t y v + ( 1 一) y ( 2 - 5 ) 用矩阵形式表示，即 阱钳升m 阴 协6 ， 其中m 是系数矩阵，从而有 阱m 阴 协7 ， 令 一一 舌羔 协8 ， l o 优化问题的儿种智能算法 其中 ：坐出乒匹 是矩阵m 的特征值，p 为相应的对角阵，则对第尼次进化， ； = p 苫善 ，1 ； ( 2 - 9 ) 粒子的状态可表示为 ( 2 - 1 0 ) 简化模型的性态完全可由线性系统的稳定性理论确定，可以用此来估计粒子 的稳定性。根据稳定性理论，当且仅当i i 1 ，i 五i 1 时，粒子的行为是稳定的。 由于 、五是参数缈和矽的函数，下面分四种情况来讨论： ( 1 ) 缈= 0 由式( 2 - 9 ) 得五= 1 一矽，而h i l ，l 五l i w f r 于o 2 。因而当o o ，故阮i l ，l 五l 1 等价于 五i = i m h x 型二至巫巫 0 ，0 缈 1 。 系统是稳定的且粒子x 收敛到p 。 ( 2 1 1 ) 2 故在条件 缈+ 1 2 石下，当o 国 l ， ( 3 ) 缈+ l 一2 石 矽 国+ 1 + 2 石 当c o + l 一2 石 国+ l + 2 历时，有( 缈+ 1 一矽) 2 4 c o o ，所以力是复数。 呻i - i 些一i = 4 0 j ( 2 1 2 ) 故在条件c o + l 一2 缈 c o + l + 2 国下，当0 缈 1 时，系统是稳定的且粒 子x 收敛到稳定平衡点p 。 ( 4 ) 缈+ l + 2 国 由条件知+ 卜矽 - 2 4 r i 0 ，而当式( 2 9 ) 的分子小于0 时，川取得最大 值。在这种情况下，五 0 ，且 第二章求解优化问题的粒子群优化算法 。：一( 型堕巡岩业) 1 ( 2 - 1 3 ) 时系统是稳定的，因此有 ( 缈+ l 一) 2 4 0 ； 彩一+ 3 ( 2 1 4 ) 当0 缈一矽+ 3 时，得矽 2 + 2 ，又因缈是一非负系数，则有0 功 l 。 故在条件力+ 1 + 2 石 2 0 + 2 下，当0 彩 1 时，系统是稳定的且粒子x 收 敛到稳定平衡点p 。 通过以上分析，对于简化模型，收敛准则l 丑l l 和i 五i l 可以写为 02缈+2(2-15) 0 国 l ( 2 一1 6 ) 2 3 基于吸引排斥机制的粒子群优化算法 e m 算法是一种新型的基于群体的随机全局启发式优化算法，由b i r b i l 和 f a n g 在2 0 0 3 年提出，其基本思想是模拟电磁场中的吸引与排斥机制，与其它算法 的比较表明，e m 算法是一种搜索能力强大的全局优化算法。本节借鉴其计算合 力的思想对标准p s o 算法的搜索机制作了进一步的改进。 2 3 1 引言 p s o 算法是一种新的仿生优化技术，由于其参数较少、参数的调整和设置也 较为方便，不需要问题的梯度信息，易于实施，可以从各个不同的方向进行搜索， 因而是一种很好的问题求解模式，已成功应用于许多领域。但是，它缺乏有效的 局部搜索机制，并且在进化过程中除了单纯地利用个体最优和全局最优信息，再 无其他的信息共享，没有充分利用其他粒子所提供的有利信息，以至于群体多样 性降低，使得搜索方向的启发性不强，缺乏导向性，对复杂优化问题容易陷入局 部最优，且后期收敛速度较慢。与其他进化算法相比，虽然能较快地收敛，但随 着代数的增加，各粒子变得越来越相似，不能对解进行持续优化，而是在局部最 优解附近徘徊，这些是它自身无法克服的缺点。 吸引与排斥反映了自然界物质运动的基本形式，因而在标准p s o 算法中粒子 仅仅跟踪个体最优和全局最优信息是不能充分地反映群体的智能行为的。对一个 粒子群体而言，周围粒子的状态和位置对粒子的行为也会产生不同的影响，即粒 子之间的吸引与排斥对粒子行为的影响( 直接或间接的) ，表现为粒子之间的交 互能力。这些粒子通过相互之间的竞争、协作和学习，互相促使彼此提高性能， 粒子在信息的引导和推拉力的作用下进行移动，从而实现群体的协同进化和发展。 1 2 优化问题的儿种智能算法 2 3 2 基于吸引排斥机制的p s o 算法 改进后的p s o 算法( 记为p s o c ) 把每个粒子看成空间中的一个带电粒子， 每个粒子所带的电荷由待优化的目标函数的适应度决定，这个电荷也决定了该粒 子对其他粒子的吸引或排斥的强弱一适应度越优，吸引就越强；适应度越劣，吸 引就越弱。然后利用电荷为每个粒子提供“加速度 ，以修正算法的速度更新公 式，即通过计算其他粒子施加给该粒子的合力来确定这个“加速度”。与电磁力 的计算相似的是该力是通过将来自其他粒子的力进行矢量叠加而得到的，不同的 是后一次进化中力的计算是在前一次进化中力的计算的基础上进行的，这样可以 充分利用前面进化过程中所积累的各种有利信息，保持力变化的渐进性，对粒子 下一步的移动起一个很好的导向作用。 如图2 3 1 所示，这里选取三个粒子来简要说明其中一个粒子l 如何依据吸引 排斥机制来进行移动。设粒子2 优于粒子l ，而粒子3 劣于粒子1 ，那么粒子2 将对粒子l 有一个吸引力e ，而粒子3 将对粒子1 有一个排斥力只。，这两个力叠 加得到的合力f 将影响粒子1 移动的方向和大小，这样会促使粒子向较优的区域 移动。 3 一 算得 - 2 r 图2 3 1 吸引排斥机制简图 粒子f 的电荷q ，决定了粒子f 所受的吸引力或排斥力的大小。该电荷由式( 2 1 7 ) q ，= e x p ( 一九 ( 西) 一厂( 以) ( ( 气) 一( 以) ) k = l 其中，( ) 为粒子f 的当前适应度，厂( 以) 为当前最优适应度。这样，目标函 数的适应度较优的粒子将拥有较大的电荷，具有更强的吸引力。因式( 2 1 7 ) q b 各粒 子的电荷都是没有正负号的，所以它不同于真正的电荷。在比较两个粒子的目标 函数的适应度后决定两粒子之间作用力的方向，其分力在计算上略有不同，离当 前最优粒子最远的粒子d 和其他粒子在计算分力的方式上略有不同。其中其他粒子 第二章求解优化问题的粒子群优化算法 i ( 1 f i d ) 的分力由式( 2 1 8 ) 计算 巧= ( x , - x i ，尚， ( x k - - x i ，尚， f ( x k ) 厂( 葺) f ( x k ) 厂( 玉) ( 2 1 8 ) 离当前最优粒子最远的粒子d 与其他粒子的力相比有一个扰动过程。因为在进 化过程中，当粒子忽略了某些搜索区域时，过早收敛就会发生。为有效避免过早 收敛，给予离当前最优粒子最远的粒子d 的分力一定的扰动。由于离当前最优粒子 p 。最远的粒子所受p 。对它的吸引力最小，因而选择它作为扰动粒子不会给整体造 成很大扰动，这样可以使粒子在搜索范围内移动到易被忽视的区域，增强其全局 搜索的能力。于是作用在粒子d 上的分力c 则由式( 2 1 9 ) 计算 历= ( 吒一而两y q d q ，他m 纠 ( 2 1 9 ) ( 以训尚，讹阱( 劫) 其中，7 u ( o ，1 ) 。同时，引入一个参数d u ( o ，1 ) ，给予该分力的方向一定的 扰动，即如果随机数y 比参数u 小，那么该分力将反向。 根据式( 2 1 8 ) 和式( 2 1 9 ) ，对于两个粒子而言，目标函数的适应度较优的粒子 将吸引另一个粒子，粒子之间的吸引力引导粒子向较优的区域移动；反之，适应 度较劣的粒子将排斥另一个粒子，排斥力将粒子推到未搜索到的区域。计算合力 的目的就是促使所有粒子都有向比它自身优的粒子移动的趋势，同时远离比自身 差的粒子，有助于提高后期收敛速度，避免算法陷入局部最优。 计算完合力f 后，为了确保粒子移动的可行性，作用在每个粒子上的力都被 做了“归一化”处理，粒子f 在力f 的作用下产生一“加速度。于是其速度更新 公式( 2 1 ) 变为 吻= 彩。+ c , r l ( p b e s t u x u ) + c , r 2 ( g b e s t j 一而) + ( 2 - 2 0 ) f