（检测技术与自动化装置专业论文）改进粒子群优化算法及其在水库优化调度问题中的应用.pdf

河海大学硕士学位论文摘要 摘要 粒子群优化算法是一种启发式群智能优化算法，其基本思想源自于对鸟群觅 食行为的模拟。粒子群优化算法适用于求解非线性、不可微的复杂优化问题，具 有原理简单、容易实现、收敛速度快等优点，并在实践应用中取得了很大的成功。 但粒子群优化算法也存在易早熟、局部搜索能力较差等缺点。基于此，本文进行 了以下研究： 第一，针对粒子群优化算法易陷入局部最优点的缺点，基于混沌思想提出了 一种改进算法一混沌粒子群优化算法。该算法将混沌搜索融入到粒子群优化算法 当中，利用混沌搜索的随机性、遍历性来提高算法的多样性和全局寻优能力，并 建立了早熟收敛判断和处理机制。当发现算法有早熟迹象时，则利用混沌搜索进 行局部搜索，而当混沌搜索没有找到更好的解时，则对种群中的部分粒子进行混 沌初始化，帮助种群摆脱局部最优点。在上述研究的基础上，进一步将混沌搜索 与协调粒子群优化算法相结合，增强粒子问的信息交流。 第二。对粒子群优化算法的寻优机制进行了深入的研究，结合社会规律，分 析了粒子群优化算法速度计算公式的缺点，并提出了种新的速度计算公式。新 的速度计算公式将原公式分解为两个子公式：其中一个保留了全局极值点的指导 作用，并引入了全局次极点，在增强了粒子间的信息交流的同时，通过调整学习 因子，强调全局极值点的指导作用，提高了算法的局部寻优能力；另一个保留了 个体极值点的指导作用，并引入一个随机点，增强了种群的多样性，提高了算法 的全局寻优能力。 第三，对水库优化调度问题的数学模型和约束条件进行了讨论，并将上述改 进算法应用于水库优化调度问题的求解。 研究表明上述改进算法的搜索能力都要优于基本粒子群优化算法，并且能较 好的解决水库优化调度问题。 关键字：粒子群优化算法；水库优化调度；混沌搜索；早熟收敛判断；改进速度 公式 河海大学硕士学疰论文a b s t r a c t a b s t r a c t p a r t i c l es w a r n lo p t i m i z a t i o n ( v s o ) a l g o r i t h mi sap o p u l a t i o n - b a s e ds w a r m i n t e l l i g e n c ea l g o r i t h mb a s e do nt h eb i o l o g i c a lc o m m u n i t y sp r e y i n g i ti sa p p l i c a b l ei n s o l v i n gn o n - l i n e a rd i f f e r e u t i a b l ec o m p l i c a t e dp r o b l e m s p s oi ss i m p l e ，r o b u s ta n dh a s g a i n e dt r e m e n d o u ss u c c e s s e si np r a c t i c a la p p l i c a t i o n s b u ti ta l s oh a ss o m e d i s a d v a n t a g e s , s u c ha se a s i l yt r a p p e di n t ol o c a lo p t i m aa n db a dl o c a ls e a r c ha b i l i t y t oo v e r c o m et h e s ed i s a d v a n t a g e s , t h ef o l l o w i n gw o r k sh a v eb e e nd o n e f i r s t l y , i no r d e rt oo v e r c o m et h ed i s a d v a n t a g eo f e a s i l yt r a p p e di n t ol o c a lo p t i m a , t h i st h e s i sp r o p o s e sam o d i f i e da l g o r i t h mb a s e do nc h a o t i cs e a r c h t h em o d i f i e d a l g o r i t h mm a k e su s eo ft h es t o c h a s t i cp r o p e r t ya n de r g o d i c i t yo fc h a o t i cs e a r c h i n t h i sm o d i f i e da l g o r i t h m , c h a o t i cs e a r c hi sa p p l i e dw h e nt h ef i t n e s sv a r i a n c ei ss m a l l e r t h a nas e tn u m b e r a n dh a l fo ft h ep o p u l a t i o ni sr e i n i t i a l i z e dw h e nc h a o t i cs e a r c h c a n tg a i na n yi m p r o v e m e n t s b a s e do nt h er e s e a r c ha b o v e ，af l l l - t h e rr e s e a r c ho n c o m b i n i n gc h a o t i cs e a r c hw i t hh a r m o n yp a r t i c l es w a r ma l g o r i t h mi sc a r r i e do u t ，a n d i ti n t r o d u c e sc o m m u n i c a t i o n sb e t w e e np a r t i c l e si n t ot h ea l g o r i t h m s e c o n d l y , t h i st h e s i sr e s e a r c h e st h ed i s a d v a n t a g e so fv e l o c i t ye q u a t i o ni np s o a l g o r i t h m , a n dp r o p o s e san e wv e l o c i t ye q u a t i o n t h en e we q u a t i o ni n c l u d e st w os u b e q u a t i o n s t h ef i r s ts u be q u a t i o ni sg i l i d e db yg l o b a lo p t i m aa n ds u bo p t i m a , a n d e m p h a s i z e st h ee f f e c to fg l o b a lo p t i m a i ti m p r o v e st h ea b i l i t yo fl o c a ls e a r c h i n g n e s e c o n do n ei sg u i d e db yi n d i v i d u a lo p t i m aa n dar a n d o mp o i n t , a n de m p h a s i z e st h e e f f e c to f t h er a n d o mp o i n t i ti m p r o v e st h ea b i l i t yo f g l o b a ls e a r c h i n g t h i r d l y , t h i st h e s i sr e s e a r c h e st h em o d e la n dc o n s t r a i n so fh y d r o p o w e rs t a t i o n s c h e d u l i n gp r o b l e m ，a n dt h et w om o d i f i e da l g o r i t h m sa b o v ea r ea p p l i e dt os o l v i n g t h i sp r o b l e m s i m u l a t i o nr e s u l t ss h o wt h a tb o t l lo ft h em o d i f i e da l g o r i t h m sa r cm o e f f e c t i v e t h a nb a s i cp s o a l g o r i t h m , a n dh a v eg o o dp e r f o r m a n c e si ns o l v i n gh y d r o p o w e rs t a t i o n s c h e d u l i n gp r o b l e m k e y w o r d s ：p a r t i c l es w a i t l lo p t i m i z a t i o n ；h y d r o p o w e rs t a t i o ns c h e d u l i n g ；c h a o t i c s e a r c h ；p r e m a t u r e j u d g m e n t ；m o d i f i e dv e l o c i t ye q u a t i o n ； i i 学位论文独创性声明： 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。如不实，本人负全部责任。 论文作者( 签名) ：玺墨圣2 0 0 8 年3 月嘶日 学位论文使用授权说明： 河海大学、中国科学技术信息研究所( 含万方数据库) 、国家图 书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位 论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存 论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内 的保密论文外，允许论文被查阅和借阅论文全部或部分内容的公布 ( 包括刊登) 授权河海大学研究生院办理。 论文作者( 签名) ：盘墨墨2 0 0 8 年，月z 日 第一章绪论 1 1 智能优化算法概述 许多实际问题的求解大多可转化为求解最优化问题，最优化方法即是解决最 优化问题的方法。最优化问题是指在一定的约束条件下，决定某个或某些可控制 的因素应有的合理取值，使所选定的目标达到最优的问题。最优化方法在数学上 是一种求极值的方法，为应用数学的一个分支，是新兴的数学理论之一。现今， 最优化方法在工程技术及管理领域的发展已经形成了一门重要的技术科学，它是 现代工程分析最佳设计的四种主要方法( 有限元分析、最优化方法、动态设计和 数值仿真) 之一。 最优化算法包括传统优化算法和智能优化算法。在传统优化算法中，又大致 分为梯度搜索和非梯度搜索l 。对于梯度搜索，首先需要已知目标函数是否连续 可导，且需要可导的解析表达式，利用函数的一阶、二阶导数及偏导数矩阵来确 定最优方向和最优步长。其代表性的方法有最优梯度法、共轭梯度法、牛顿法及 变尺度法等。梯度搜索一般利用函数在某一点附近的梯度信息，这是目标函数的 一个局部的性质，并不是全局性质，所以初始值的选取会影响到是否收敛到全局 最优点。非梯度搜索无需知道函数是否连续可导，只需要知道该点的函数值，通 过函数值的比较来确定最优化的方向和步长。其代表性的方法有进退法、黄金分 割法及坐标转换法等。梯度搜索收敛速度快，但是应用条件苛刻，不能广泛使用， 且计算复杂。非梯度搜索应用范围广泛，适应性强，计算简单易行，但搜索速度 相对较慢，精度也较差。 现代工程优化应用中的大多数问题，经过数学建模后得到的数学函数，往往 是带有多种约束条件的复杂函数，而且大都是不连续可微的隐函数。梯度搜索无 法优化不连续可微的函数，因此不适合处理该问题。非梯度搜索虽然适应性强， 但对于强约束的多维复杂函数的搜索速度慢、精度差，无法满足工程对速度和精 度的需要。为了满足工程优化的要求，需要一种全新的优化方法。随着对客观世 界更深入的了解，人们发现自然界中的某些现象或生物的某些生活规律，对解决 优化问题具有借鉴作用。人们借鉴自然现象，提出了模拟退火法( s a ) 、遗传算法 ( g a ) 、神经网络( n n ) ；人们通过学习生物的生活规律，提出了蚁群算法( a c ) 、 粒子群优化算法o s o ) 。人们将这些模仿自然现象及生物体的各种原理和机理的 方法，称为智能优化算法1 2 1 。这类方法为启发式随机算法，对函数是否连续可微 没有要求，也不用考虑初始值的选取，适应性强，适用于多维复杂函数，对约束 河海大学硕士学位论文第章绪论 条件的处理也比较方便，搜索速度较快，精度较高。但同时也存在着容易陷入局 部最优点的缺点。 1 2 粒子群优化算法产生的背景 二十一世纪是信息社会，人们在享受到信息社会给我们带来无尽便利的同 时，也深刻感受到了海量信息带给我们的挑战。面对海量信息的挑战，人们有两 个基本的策略，一个是计算得更快：在这方面，我们看到信息技术的代表一c p u 在不断地“进化”，从3 8 6 ，4 8 6 到奔腾3 、奔腾4 ，然而c p u 的进化速度似乎 始终赶不上信息增长、传播的速度。目前，c p u 技术陷入了“摩尔定律”失效的 境地。人类的另外一个基本策略就是计算得更加“智能”：在这方面大自然始终 是人类的老师，人类受到社会系统、物理系统、生物系统等运行机制启发，建立 和发展起一个个研究工具和手段来解决和攻克研究过程中遇到的困难。典型的有 遗传算法( g e n e t i ca l g o r i t h m ，g a ) p 4 j 、人工神经网络( a r t i f i c i a l n e u r a ln e t w o r k s ， a n n ) 1 5 - 6 1 、进化规划( e v o l u l i o n a lp r o g r a m m i n g ，e v ) t n 、蚁群优化算法( a n tc o l o n y o p t i m i z a t i o n ，a c o ) 隅】等。这些方法已经被广泛应用于工程实践，有许多很成功 的实例。而在计算智能( c o m p u t a t i o n a li n t e l l i g e n c e ，c i ) 一l 领域中，有两种基于群 体智能( s w a r mi n t e l l i g e n c e ，s i ) 的算法：蚁群优化算法和粒子群优化算法。前者 是对蚂蚁群落搜索食物行为的模拟，已经成功运用在很多组合优化问题上；后者 就是本文将要介绍的粒子群优化算法。 与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同的是，粒子 群优化算法是通过个体之间的协作来寻找最优解的。例如自然界中的许多群居动 物，其社会网络有助于共同照顾年轻个体，群体捕食比单独捕食更容易成功，捕 食效率也更高。并且，在天敌入侵时能提供警告并集体防御。这种现象在人类社 会中也是普遍存在的，人们在进行决策时，在总结自己以往经历的同时，也非常 注重借鉴他人的成功经验。可见，群体中的一员可以从群体经验中得到好处，同 时该成员的经验也为其它成员所借鉴，虽然成员之间的竞争不可避免。但交流合 作产生的好处具有压倒性的优势，并最终推动群体的进步。 粒子群优化算法具有传统优化算法( 如数学规划、动态规划等) 所不具备的优 点： 一、它是一类不确定性的方法。不确定性体现了自然界的生理机制，并且在 求解某些特定问题方面优于确定性算法。 二、它是一类基于多个智能体的智能算法。各智能体通过自学习不断提高自 身的适应性，同时通过相互之间的协作来更好地适应环境。 三、它具有潜在的并行性。搜索过程不是从一个点出发，而是同时从多个点 2 河海大学硕士学位论文第一章绪论 同时进行。这种分布式的多个智能体的协作过程是异步并发进行的，分布并行模 式将大大提高整个算法的运行效率和收敛速度。 而与其它智能优化算法( 如遗传算法、蚁群算法) 相比，粒子群优化算法概念 简单，容易实现，适应性强。 1 3 本文主要工作 本文主要工作在于改进粒子群优化算法的性能，以满足实际应用的需要。 作者对粒子群优化算法作了以下几方面的研究： 第一，详细分析了粒子群优化算法的结构特点、搜索方式、基本流程及优缺 点，尤其是对粒子群优化算法容易陷入局部最优点的原因进行了深入的研究，并 对已有的几种改进算法进行了研究。在上述研究的基础上提出了几种改进的粒子 群优化算法。 第二。对混沌搜索进行了详细的研究，在此基础上提出了一种基于混沌思想 的改进粒子群优化算法混沌粒子群优化算法。该算法使用混沌变量初始化种 群的位置和速度，并在整个进化过程中对种群的进化情况进行跟踪和监视，当发 现种群有陷入局部最优点的迹象时，则进行变尺度混沌搜索或者混沌初始化，从 而使种群有更大的机会摆脱局部最优点。对几种标准测试函数进行仿真实验的结 果表明该改进算法的寻优性能明显优于基本粒子群优化算法。 第三，对协调粒子群优化算法进行详细的研究，将混沌思想其中，提出了基 于混沌思想的协调粒子群优化算法。并将其与混沌粒子群优化算法进行性能比 较。 第四，对粒子群优化算法的速度进化公式进行了研究，分析了原有速度更新 公式的优缺点，并在此基础上提出了一种改进的速度更新公式。对几种标准测试 函数进行仿真实验的结果表明使用改进速度公式的粒子群优化算法比基本粒子 群优化算法具有更好的寻优性能。 第五，分析和研究水库优化调度问题，在此基础上确定该优化问题的目标函 数，并将上述改进粒子群优化算法应用于该优化问题。 1 4 章节安排 本文的章节安排如下： 第一章：绪论，介绍本文的研究背景、研究现状和主要研究方向等。 第二章：介绍基本粒子优化算法以及几种改进算法。 第三章：对混沌搜索进行研究：提出一种基于混沌思想的改进粒子群优化算 法一混沌粒子群优化算法；提出一种基于混沌思想的协调粒子群 河海大学硕士学位论文 第一章绪论 优化算法。 第四章：介绍水库优化调度问题及几种常用的求解水库优化调度问题的方 法。 第五章：将混沌粒子群优化算法应用于水库优化调度问题。 第六章；对粒子群优化算法的速度更新公式进行了分析和改迸，提出了一种 基于改进速度公式的粒子群优化算法，并将其应用于水库优化调度 问题 第七章：对本文进行总结，提出今后研究的方向。 4 第二章基本粒子群优化算法 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 ) 算法是由e b e r h a r t 和 k e n n e d y 于1 9 9 5 年提出的【1 0 i l 】，它是基于对鸟群捕食行为的模拟而产生的。粒 子群优化算法同遗传算法类似，是一种基于迭代进化的优化算法，系统初始化为 一组随机解，通过迭代搜寻最优解。但是粒子群优化算法并没有遗传算法所采用 的交叉与变异操作。同遗传算法比较，粒子群优化算法的优势在于需要调整的参 数少，结构简单，收敛速度快。 由于粒子群优化算法因其思想简单、易于实现、应用效果明显等优点而被众 多应用领域所接受，并已广泛的应用于神经网络训裂1 2 】，t s p 求解【1 3 l 、模糊系 统控制【1 4 】以及其他的应用领域。粒子群优化算法具有较强的鲁棒性，特别是对 于一些大型、复杂优化非线性系统，更显示出其优越的性能和巨大的发展潜力。 粒子群优化算法作为- - f - j 新兴学科，各种理论、方法尚未成熟，有待进一步发展 和完善。在粒子群优化算法的研究和应用过程中会出现许多难题，但随着人们对 这些难题的研究，同时也产生了许多新的算法设计思想和改进方法，从而不断完 善和提高粒子群优化算法的性能，其广阔的发展前景激励着各类专业技术人员把 粒子群优化算法的理论和方法运用到自己的工作实践中。 2 1 1 粒子群优化算法基本思想 粒子群优化算法是一种基于群体的智能优化算法，r e y n o l d s 对鸟群飞行的研 究发现，绝大部分的鸟在飞行时，仅仅是追踪其相邻的有限数量的邻居，但最终 的结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则 的相互作用产生的。粒子群优化算法的基本概念源于对鸟群的觅食行为的研究， 一群鸟在随机搜寻食物时，如果这个区域内只有一块食物，那么找到食物的最简 单有效的策略就是搜寻目前距离食物最近的鸟的周围区域 e b e r h a r t 和k e n n e d y 对鸟群的觅食活动进行了抽象化，将鸟群的活动范围抽 象 维搜索空间，将每只鸟抽象为空间中的一个点，这些点被称为“粒子”( p a r t i c l e ) 或“主体”( a g e n t ) ，而所有粒子组成了一个种群( s w a r m ) 。在使用粒子群优化算 法求解优化问题时，问题的一个潜在解对应于搜索空间中一个粒子，每个粒子采 用“速度位置”搜索模型，其中第j 个粒子在d 维搜索空间中的位置向量表示 河海大学硕士学位论文第二章基本粒子群优化算法 为五= ( z 。，x j 2 , - ) ，速度向量表示为k = ( 巧。，_ ：，) ，位置向量反映了 粒子在每次进化后的位置，速度向量则决定粒子每次进化时的位移。与其它进化 算法比较，粒子群优化算法保留了基于种群的全局搜索策略，但是其采用的“速 度位置”模型操作简单，避免了复杂的迸化操作。它特有的记忆功能使其可以 动态跟踪当前整个种群的最优粒子。 在粒子群优化算法中，每个粒子除了有自己的位置和速度( 决定飞行的方向 和距离) 之外，还有一个由目标函数决定的适应度。各个粒子记忆、追随当前具 有最优适应度的粒子，在搜索空间中进行搜索。每次迭代的过程不是完全随机的， 如果找到更好的解，将会以此为依据来寻找下一个解。粒子群优化算法的初始种 群为一组随机粒子( 随机解) ，在每一次迭代中，粒子通过跟踪两个“极值”来更 新自己：第一个极值点就是粒子本身目前所找到的最好解，称为个体极值点( 用 = ( 只。，只：，昂) 表示) 。全局版p s o 算法的另一个极值点是整个种群目前找 到的最好解，称为全局极值点( 用g 。= ( g i 。，g j ：，g 0 ) 表示) ；而在局部版p s o 算法中，个体是用其中一部分邻近的粒子作为邻居，所有邻居中的最好解称为局 部极值点( 用上。= ( l t t , ：，k ) 表示) 。图2 - 1 所示的就是p s o 算法的粒子运 动方向示意图。 暴 扣 x 轴 图2 1p s o 算法粒子运动方向示意图 6 河海大学硕士学位论文第二章基本粒子群优化算法 在图2 一l 中，可以清楚地看出粒子的运动轨迹受到( k 和的综合影响。 在找到这两个最好解后，粒子根据式( 2 1 ) 和式( 2 2 ) 更新自己的速度和位置： v i 一( 七+ 1 ) = 口v ，一( 七) + c l m d ( c ，d 一工州( 七) ) + c 2 r a n d ( 工，d x j d ( 七) ) ( 2 1 ) 】f _ d ( 七+ 1 ) = x i , d ( 七) + v i , d ( t + 1 ) ( 2 - 2 ) 式中，d 代表维数；k 表示进化的次数；脚称为惯性权重，是与前一次速度有关 的一个比例因子；q 、岛称为学习因子，分别调节向全局极值点和个体极值点 方向飞行的最大步长：学习因子太小，则粒子可能远离目标区域缓慢地飞行；学 习因子太大，则会导致突然向目标区域飞去，或飞过目标区域，合适的c i 、c ，可 以加快收敛且不易陷入局部最优；r a n d 是【o ，l 】之间的随机数。为防止粒子远离 搜索空间，粒子的每一维速度u 一都会被限制在【一。，。】之间。假设将搜索 空间的第d 维定义为区间【x 。，以。】，则通常屹。= 后+ ( 以一一k 。) ， o 1 k 1 ，在大多数问题中，每一维都采用相同的设置。分析式( 2 1 ) 的形式可 以发现，新速度由3 部分组成。第l 部分反映粒子维持原速度的程度；第2 部分 反映粒子的“自我认知”，表示粒子对自身过去成功经验的肯定；第3 部分反映 粒子间的“社会交流”，表示粒子间的信息交流与合作。粒子在搜索空间不断跟 踪个体极值点和全局极值点进行搜索，直到结果满足终止条件或者达到最大进化 代数为止。 2 1 2 粒子群优化算法的基本流程 粒子群优化算法的算法流程描述如下： s t e p l 种群初始化。随机生成掰个粒子作为初始种群。 s t e p 2 个体评价( 适应度评价) 计算种群中各粒子的适应度。粒子群优化算 法在搜索进化过程中一般不需要其他外部信息，仅用目标函数值来评价粒子或解 的优劣，并作为以后种群进化操作的依据。目标函数值又称为适应度( f i m e s s ) 。 s t e p 3 根据式( 2 1 ) 、( 2 2 ) 更新粒子的速度和位置。这是整个粒子群优化算法 中最关键的一步，种群的“个体学习”和“社会学习”都在这一步实现。 s t e p 4 终止条件判断。若满足终止条件( 达到最大进化代数或满足最小误差标 准) ，则以进化过程中所得到的具有最好适应度的个体作为最优解输出，终止计 算；否则，转至步骤b ，继续迭代。 粒子群优化算法的流程如图2 - 2 所示： 河海大学硕士学位论文第二章基本粒子群优化算法 y e s 图2 - 2 基本粒子群优化算法流程图 2 1 3 粒子群优化算法的特点 粒子群优化算法在思想和结构上具有很高的独创性，与传统的优化算法相 比，它采用了许多独特的技术和方法： 1 ) 传统的优化算法都是从一个初始点出发，再逐步迭代以求最优解。p s o 则不然，它是以一个群体，多点同时出发经过不断迭代进化求得满意解。 河海大学硕士学位论文第二章基本粒子群优化算法 2 ) 传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导 数值等其它一些辅助信息才能确定搜索方向。粒子群优化算法仅使用由目标函数 值变换来的适应度函数值就可以确定进一步的搜索方向和搜索范围，无需其它辅 助信息。 3 ) 传统的优化算法大都采用确定性的搜索方法，一个点到另一个点的搜索 转移有确定的转移关系和转移方向，这种确定性往往使得搜索可能永远达不到最 优点，因而限制了算法的应用范围。而粒子群优化算法属于一种自适应随机搜索 技术，增加了其搜索过程的灵活性。 2 2 粒子群优化算法的发展状况 粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作 产生的群体智能来指导优化搜索。与一般进化算法比较，粒子群优化算法是一种 更高效的并行搜索算法，其概念简单，容易实现，一般代码只有短短的几行，优 点显著。 作为一种模拟生物活动规律及人类社会规律的群体智能优化算法，粒子群 优化算法目前还缺乏比较严格的数学证明，但是在实际应用中已经被证明其有效 性。虽然粒子群优化算法有很多优点，但是也存在着一些缺点。在对一些多维的 复杂的优化问题进行优化时，粒子群优化算法容易陷入局部最优点，这是由于粒 子群优化算法的收敛性较强，各粒子会迅速的向当前的全局极值点收敛，而当前 的全局极值点可能不是问题的全局最优点，因此影响了算法的全局搜索能力。粒 子群优化算法的精度较低，这是由于在算法收敛的情况下，所有的粒子都向全局 极值点的方向移动，所有的粒子趋向同一，失去了粒子间的多样性，粒子的运动 速度不断减小，甚至趋进于0 ，使得后期的收敛速度明显变慢，算法收敛到一定 精度时，算法无法继续优化，算法所能够达到的精度较低。以上缺点影响了粒子 群优化算法的性能。 针对这些缺点，国内外的学者、学者做了大量的工作，提出了很多的改进 算法。以下介绍几种比较成功的改进算法： 2 2 1 惯性权重法 在式( 2 1 ) 中，等式右边第一部分讲v s , d ( j ) 是对粒子之前进化中运动速度的记 忆。由称为惯性因子，通过调节c o 可以控制之前速度对当前速度产生影响的大小。 较大的m 有扩大搜索空间、探索新的搜索区域的趋势，因此具有较强的全局搜索 能力；较小的c o 则倾向于局部搜索，有利于种群收敛及提高精度。在进行优化问 9 河海大学硕士学位论文 第二章基本粒子群优化算法 题求解时，往往希望先采用全局搜索，使搜索区间快速收敛到某一区域，然后再 采用局部搜索以获得高精度的解。针对这种需要，s h i 和e b e r h a r t 提出了动态改 变惯性权重的策略【1 5 】。最先提出的是让国随进化过程线性递减的改进方法，即 国：一丝竺芒型，其中d 。，分别是缈的最大值，最小值，娩 l f p 是最大的进化代数，娩，为目前的进化代数。改进过的算法对优化大多数的 b e n c h m a r k 方程较之基本p s o 算法有了明显的改进。但是p s o 算法的实际搜索 过程是非线性的且复杂的，幽惯性递减的方法往往不能反映实际的搜索过程。因 此s h i 和e b e r h a r t 于2 0 0 1 年提出采用模糊系统动态的改变惯性权重的策略1 1 “， 该模糊系统定义了九个控制规则，包含两个输入和一个输出。第一个输入是当前 的全局极值点，第二个输入是当前的惯性权重，输出为惯性权重的改变量。 2 2 2 多粒子群协同优化算法 对式( 2 1 ) 、( 2 - 2 ) 进行分析可以发现，种群在进行搜索时，每个粒子总是追随 当前的全局极值点和自己迄今搜索到的最优点，因此当以上两个最优点在一段时 间无更新时，粒子的速度会很快接近于0 ，导致种群陷入局部最优点，这种现象 削弱了粒子群优化算法的全局搜索能力，限制了种群的搜索范围。增加种群中的 粒子或减弱粒子对两个极值点的追逐对克服这一问题有所帮助，但增加粒子数将 导致算法计算复杂度及计算时间增加，而减弱粒子对全局极值点的追逐又存在算 法不易收敛的缺点，因此效果都不很理想。 针对上面的问题，一些学者提出多子群协同粒子群优化算法【1 7 】，即利用s 个 独立的子群进行协同优化。前s 1 个子群根据该子群迄今搜索到的最优点来修正 群中粒子的速度，而第s 个子群则是根据整个种群迄今搜索到的最优点修正群中 粒子的速度。这样既利用前s 1 个子群的独立搜索来保证寻优过程可以在较大范 围内进行，又利用第s 个子群追逐当前全局极值点来保证算法的收敛性，从而兼 顾优化过程的精度和效率。 2 2 3 杂交粒子群优化算法 借鉴遗传算法的思想，a n g e l i n e 提出了杂交粒子群优化( h y b r i dp a r t i c l e s w a r mo p t i m i z a t i o n ，简称h p s o ) 算法的概念瑚。l o v b ! j e r g 、r a s m u s s e r l 和k r i n k 在此基础上，进一步的提出了具有繁殖能力和子群的杂交粒子群优化算法。该改 迸算法在基本p s o 算法的基础上赋予种群一个杂交概率。在每次迭代中，依据 杂交概率选取一定数量的粒子放入一个池中，池中的粒子随机两两杂交，产生同 1 0 河海大学硕士学位论文第二章基本粒子群优化算法 样数目的子粒子，并甩子粒子代替父粒子，以保持种群中的粒子数目不变。子粒 子的位置由父粒子的位置的算术加权和得到，即： c h i l d i ( x ) = p + p a r e n t l o ) + ( 1 一力+ p a r e n t 2 ( d ( 2 - 3 ) c h i l d 2 ( x ) = ( 1 一力+ p a r e n t t ( 磅+ p p a r e n t 2 ( x ) ( 2 - 4 ) 其中p ( p 【o ，l 】) 为一个随机数，x 为位置向量，p a r e n t ( x ) 和c h i l d ( x ) 分别为父粒 子和子粒子的位置向量。子粒子的速度由以下公式得到： c h i l d j ( v ) 2 j , m p a r e n t f l l ( w v ) 十+ m p a r e n t 2 2 ( 叫v ) , p a r e n t l ( v h c h i l d ：( v ) = 面p a r 瓦e n t t 万( v ) + 丽p a 赢r e n t 砑2 ( v ) p a r e n h ( v ) l 一 其中v 为速度向量，p a r e n t ( v ) 和c h i t d ( v ) 分别为父粒子和子粒子的速度向量。 杂交粒子群优化算法与基本粒子群优化算法的区别在于粒子在进行速度和位 置的更新后还要进行上述的杂交操作，并用产生的子粒子取代父粒子。杂交操作 使子粒子继承了父粒子的优点，在理论上加强了对粒子间区域的搜索能力。例如 两个父粒子均处于不同的局部最优区域，那么两者杂交产生的子粒子往往能够摆 脱局部最优点，而获得改进的搜索结果。实验证明，与基本p s o 及基本g a 算 法比较，h p s o 搜索速度快，收敛精度高。目前，利用杂交操作改进基本p s o 算法的探索仍在继续。 2 2 4 离散粒子群优化算法 在粒子群优化算法中，将一个优化问题的可行解从其搜索空间转换到粒子群 优化算法所能处理的搜索空间的过程称为编码。对于所有智能优化算法，编码都 是一个非常关键的步骤。在粒子群优化算法中，编码大致分为两类：实数编码和 二进制编码。 粒子群优化算法最初是用来求解连续优化问题的，所以一般采用实数编码。 但在实际生活中存在着许多组合优化问题( 如旅行商问题) ，这类问题无法进行实 数编码，因此，k c n n 既l y 和e b e r h a r t 博士在基本粒子群优化算法的基础上发展了 离散粒子群优化( d i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o n ，简称d p s o ) 算法来解决这 一类问题f i 9 1 。 d p s o 算法与基本p s o 算法的主要区别在于位置更新公式的不同。d p s o 算 法的速度和位置更新公式为： 1 ，一( 七十1 ) = 彩q 一( 置) + q r a n d ( 只，d x ，d ( 七”+ c 2 r a n d ( 匕一一工，一( 七) ) ( 2 - 6 ) 河海大学硕士学位论文 第二章基本粒子群优化算法 驴 o 以嚣吒j p ， 在式( 2 - 7 ) 中，j i g f r ：, , + - ) 2i ；1 i ：哥j 是s i g m o 埘函数；n “【o ，1 】是一个随机值。 在离散粒子群优化算法中，粒子的位置只有0 、1 两种状态，速度值越大，则粒 子位置取1 的可能性越大，反之越小。 在式( 2 7 ) 中为防止速度y 过大，需设置一个速度最大值p 幺及最小值j n ， 使s i g m o i d 函数不会过于接近0 或1 ，以保证一定的概率使粒子从一种状态跃迁 到另一种状态。 2 3 粒子群优化算法的研究现状与应用 粒子群优化算法一提出就吸引了广泛的注意，各种关于p s o 算法应用研究 的成果不断涌现，有力地推动了p s o 算法研究。在具体应用方面：p s o 算法广 泛应用于神经网络的训练，各类连续问题和离散问题的参数优化( 在模糊控制器 的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果) ， 还应用于组合优化的问题当中。除了以上领域外，p s o 算法在多目标优化、自动 目标检测、生物信号识别、决策调度、系统辨识以及游戏训练等方面也取得了一 定的成果。 粒子群优化算法具有较强的鲁棒性，特别是对于一些大型、复杂的非线性系 统，更显示出其优越的性能。粒子群优化算法作为一门新兴学科，各种理论、方 法尚未成熟，有待进一步发展和完善。尽管粒子群优化算法自身仍存在着许多有 待解决的问题，如早熟收敛、控制参数的选择等，但是目前已经开发出了很多种 各不相同的改进型粒子群优化算法，使其性能不断地得至q 提高。更重要的是，粒 子群优化算法在目前的各种应用实践已经展现出了其优异的性能和巨大的发展 潜力，它的发展前景激励着各类专业技术人员把粒子群优化算法的理论和方法运 用到自己的工作实践中。 2 4 测试函数 为了测试算法的性能，常采用一些著名的测试函数( b e n c h m a r kf u n c t i o n ) 作为 仿真试验的对象。为了测试本文提出的改进粒子群优化算法的性能，选取了以下 的测试函数： 河海大学硕士学位论文 第二章基本粒子群优化算法 冗：r o s e n b r o c k 函数 厂( x ) = 1 0 0 ( x , 2 一x ，。) 2 + ( 1 - - x i 一，) 2 】 f 2 , r a s t r i g i n 函数 厂( 工) = 1 0 聆+ “2 - 1 0 c o s ( 2 戤) ) f 3 ：g i r e w a n k 函数 八工) = 萎n 盍矗2 一冉c 。s 吨，- ) + ， f 4 ：s c h a f f e rf 6 函数 八砷-o5一面(sin2而4x12丽+x22-05) 这理个函数均为较复杂的多蜂函数，并各具特色。蜀是r o u m b r o c k 函数， 它是一个非凸函数，它在( 1 ，1 一，1 ) 处达到极小值0 ；，2 是r a s 啊g i n 函数， 它是一个多峰函数，它在【- 5 1 2 ，5 1 2 】内大约有1 0 * n 个局部极小值点( n 为函数的 维数) ；f 3 是g i r e w a n k 函数，它是一个非凸函数，它在( o ，0 ，o ) 处达到极小 值o ；f 4 为s c h a 商e r f 6 函数，不但最小值所在区域较小，而且主峰也不突出，同 时其最小峰 o , 0 1 的周围有一个环形谷，取值均约为0 0 1 ，很多算法在进行优化时 极容易陷入这些局部最优点。 第三章基于混沌的改进粒子群优化算法 3 1 混沌运动 一般将由确定性方程得到的具有随机性的运动状态称为混沌运动。混沌运动 是自然界中一种常见的现象，其变化过程看似杂乱无章，但并不是完全混乱，而 是含有内在的规律性。呈现混沌状态的一组变量称为混沌变量，混沌变量具有随 机性、确定性、初值敏感性和遍历性的特点。混沌变量的随机性是指混沌变量的 起始点是随机的( 不动点除外) ，并且混沌变量的表现形式如随机变量一样杂乱、 没有规律；混沌运动的确定性是指产生混沌运动的方程是确定的，从同一起始点 出发产生的混沌交量也是确定的；初值敏感性是指混沌变量对初始值十分敏感， 当初始值发生细微的变化时，得到的混沌变量会完全不同；遍历性是指混沌变量 能从任意初始值( 不动点除外) 出发，按照确定的方程，访问到搜索空间中的每一 个位置。 3 1 1 混沌方程 混沌方程是指具有确定的形式并且能够产生混沌变量的方程。目前使用最为 广泛的混沌方程为l o g i s t i c 方程1 2 0 l ，它属于迭代混沌自映射方程，其表达式如式 3 1 所示； 上。+ l = ，压。( 1 一】_ ) i t = 1 , 2 , 3 ， ( 3 一1 ) 式中为控制参量，, t = 4 ，工。【0 ，l 】。 混沌变量在具有随机性、遍历性等优点的同时还存在着一些缺点1 2 1 1 。首先， 混沌变量对初始点有一定的要求，即初始点不能为不动点。对于l o g i s t i c 方程， 不动点包括0 、0 2 5 、0 5 、0 7 5 、l 。其次，由于混沌变量是有限的，不可能完全 遍历到搜索空间中的每个状态，因此混沌变量的遍历性不是绝对的、而是相对而 言的。最后，对于有限的混沌变量，他在搜索空间内不是完全均匀、随机的，混 沌交量在分布上存在着在边缘区域较密集，中心区域较稀疏的问题。 混沌变量虽然存在着上述问题，但除了在个别区域相对密集或稀疏外，混沌 变量的分布是比较均匀的，可以很好覆盖搜索空间中的各个区域，因此可以较好 的反应问题在搜索空间中的空间分布特性，指导对优化问题的求解。 1 4 河海大学硕士学位论文 第三章基于j 昆沌思想的改进粒子群优化算法 3 1 2 混沌搜索 国内外的一些学者利用混沌变量遍历性的特点，提出了混沌搜索方法1 2 2 , 2 3 1 ， 用于解决优化问题。混沌搜索的基本思想是把混沌变量线性映射到优化变量的取 值区间，然后进行搜索。混沌搜索过程可分为两个阶段：首先，基于确定性方程 产生的混沌变量对整个搜索空间进行考察。当满足一定精度或终止条件时，认为 搜索过程中发现了问题的最优解或已接近最优解，并以此作为第二阶段的搜索起 始点。然后，以第一阶段得到的结果为中心，通过减小搜索区间进一步进行局部 区域内的细搜索，直至满足算法终止条件。混沌搜索的基本方法即是“粗搜” 和“细搜”相结合的二次搜索方法。 对几个测试函数优化的仿真结果表明，混沌搜索对于维数较低搜索空间较小 的优化问题有非常显著的效果，寻优效率优于模拟退火、遗传算法等其它随机搜 索算法。然而进一步的仿真表明，当搜索空间的维数和范围较大时，混沌搜索所 需的时间会大大增加，精度也会明显下降。由于现实生产生活中的优化问题大多 是多维的大范围的菲线性优化问题，因此混沌搜索的实用性受到了限制。 现在国内外的学者针对混沌运动的研究主要分为两个方向：一是对上述的混 沌搜索算法进行研究和改进，通过提出新的混沌方程或改进搜索机制以提高其搜 索能力；二是将混沌搜索与遗传算法【2 4 搿2 6 1 、蚁群算法等算法结合1 2 7 1 ，通过在其 它算法中引入混沌搜索环节，提高算法整体的性能。本文中所提出的改进算法方 法中的一种就是将混沌搜索与粒子群优化算法相结合，利用混沌搜索的遍历性来 克服粒子群优化算法容易陷入局部最优点的缺点。 3 2 早熟现象及早熟判断机制 粒子群优化算法一般采用实数编码，由于没有选择、