（计算机应用技术专业论文）自适应变异量子粒子群优化算法及其应用研究.pdf

摘要 摘要 粒子群优化p s o ( p a r t i c l es w a r mo p t i m i z a t i o n ) 算法是由k e n n e d y 和e b e r h a n 于1 9 9 5 年 提出的一种优化算法。它源于鸟群集体行为的启发，与其它进化算法相比，它是很有竞 争力的神经网络学习算法。由于粒子群的聚集性，群体多样性的丢失不可避免。在搜索 的后期，粒子聚集成群，搜索空间十分有限，粒子群可能陷入局部极值点。量子粒子群 优化q p s o ( q u a n t u m b e h a v e dp a r t i c l e s w a r mo p t i m i z a t i o n ) 算法是从量子力学的角度出 发提出的一种新的p s o 算法模型，这种模型以d e l t a 势阱为基础，认为粒子具有量子的行 为。为了避免陷入局部极值点，本文在q p s o 算法基础上引入变异机制，以自适应变异 概率对个体进行变异，以此来增加种群的多样性，同时，为了防止最优值的丢失，首次 采用精英保留策略，建立精英个体序列库，提出了自适应变异量子粒子群优化a m q p s o ( a d a p t i v eq p s o w i t hm u t a t i o no p e r a t o r ) 算法。 系统辨识是研究建立生产过程数学模型的一种理论和方法，其辨识方法很多，但都 存在各方面的局限性，我们利用a m q p s o 算法进行系统参数的辨识；同时，将非线性方 程组的求解问题转化为函数优化问题，利用a m q p s o 算法求解非线性方程和方程组的 解；如何确定模糊产生式规则的各项参数对模糊p e t r i 网( f p n ) 的建立具有非常重要的意 义，并且也是目前的研究热点之一，我们将一种充分结合a m q p s o 算法年f i b p 网络学习算 法各自优点的混合算法a b h a ( a m q p s oa n db ph y b r i da l g o r i t h m ) z jl 入到模糊p e t r i 网的 参数寻优过程。本文的主要工作如下： 1 q p s o 算法与a m q p s o 算法分析及研究。 2 a m q p s o 算法在系统辨识中的应用。 3 a m q p s o 算法在求解非线性方程和方程组的解中的应用。 4 a b h a 在模糊p e t r i 网参数优化中的应用。 本文将a m q p s o 应用到系统参数的辨识中，辨识结果表明该算法能有效地克服传统 辨识算法存在的一些局限性，具有参数辨识精度高，抗噪声能力强，对输入信号通用性 强，也适用于非线性系统参数辫识，具有重要的工程应用价值；利用a m q p s o 算法解非 线性方程和方程组，这种算法有高度的适应性、鲁棒性和并行性，是一种不需使用导数 信息和初始点的高效智能算法，实验结果表明了算法的有效性。将a b h a 引入到模糊p e t r i 网的参数寻优过程，仿真实例表明，这种混合算法计算简单，收敛速度快，能够明显减 少迭代次数，具有更好的全局收敛性能，由此训练出的参数正确率较高，所得的f p n 具 有很强的泛化能力和自适应性。 关键词：自适应变异量子粒子群优化算法系统辨识b p 网络学习算法非线性系统模糊 p e t r i 网产生式规则模糊推理非线性方程组 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 mo p t i m i z a t i o n 口s o ) i si n t r o d u c e db yk e n n e d ya n de b e r h a r ti n19 9 5 【1 】，i t i sap o p u l a t i o nb a s e de v o l u t i o n a r yo p t i m i z a t i o na n di n s p i r e db yt h ec o l l e c t i v eb e h a v i o r so f b i r d s i th a sa l r e a d yb e e ns h o w nt h a tp s oh a se v e rs i n c et u r n e do u tt ob eac o m p e t i t o ri n p e r f o r m a n c ew i t ho t h e re v o l u t i o n a r ya l g o r i t h m s t h el o s so fd i v e r s i t yi nt h ep o p u l a t i o ni s i n e v i t a b l ed u et ot h ec o l l e c t i v e n e s s ，d u r i n gt h e1 a t t e rs e a r c hp e r i o d t h ep a r t i c l e sa r e i n v e s t i g a t e dt oc l u s t e rt o g e t h e ra n di t ss e a r c ha r e ai ss ol i m i t e dt h a tt h ew h o l es w a r mi sv e r y p o s s i b l et ob et r a p p e di nal o c a lm i n i m a q u a n t u m - b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o n ( q p s o ) i san o v e lp s oa l g o r i t h mm o d e li nt e r m so fq u a n t u mm e c h a n i c s t h em o d e li sb a s e d o nd e l t ap o t e n t i a la n dt h i n kt h ep a r t i c l eh a dt h eb e h a v i o ro fq u a n t a b a s e do nq p s o a l g o r i t h m ，t h em e c h a n i s mo fm u t a t i n gi sp r o p o s e dt oe s c a p el o c a lo p t i m a m u t a t i n gt h e i n d i v i d u a l si na d a p t i v em u t a t i n gp r o b a b i l i t y ，a n di n c r e a s i n gi t sd i v e r s i t yo ft h es w a r m ，a tt h e s a m et i m e ，u s i n gf i r s t l yt h es t r a t e g yo fr e m a i n i n gc a d r e m a na n de s t a b l i s h i n gc a d r e m a n s e q u e n c ew a r e h o u s ei no r d e rt oa v o i dt h el o s so ft h eo p t i m u mv a l u e a na d a p t i v e q u a n t u m - b e h a v e dp 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 mw i t hm u t a t i o no p e r a t o r ( a m q p s o ) w a sp r o p o s e d s y s t e mi d e n t i f i c a t i o ni sat h e o r ya n dm e t h o ds t u d i e dh o wt oe s t a b l i s hm a t h e m a t i c s m o d e li np r o d u c ep r o c e s s a i t h o u g ht h e r ea r em a n ym e a n s ，t h e yh a v ev a r i o u sl i m i t s t h e a m q p s ow a su s e dt oi d e n t i f yt h es y s t e mp a r a m e t e r s t h ep r o b l e m so ns o l v i n gn o n l i n e a r e q u a t i o n si st r a n s f o r m e di n t ot h a to ff u n c t i o no p t i m i z a t i o n t h ea m q p s 0w a su s e dt os o l v e s y s t e m so fn o n l i n e a re q u a t i o n s h o wt od e t e r m i n ep a r a m e t e r so ff u z z yp r o d u c t i o nr u l e si s s i g n i f i c a n tf o rb u i l d i n gaf u z z yp e t r in e t ，i ti so n eo fr e s e a r c hh o t s p o t s ，a l s o ah y b r i d a l g o r i t h ma b h a t h a tt a k e sf u l la d v a n t a g e so fa m q p s oa n db pi so r i g i n a l l yi n t r o d u c e di n t o t h ep r o c e d u r eo f e x p l o r i n gt h ep a r a m e t e r so ff p n i nt h ep a p e lo u rm a i nw o r kh a sb e e n d o n e a sf o l l o w s l 2 3 4 a n a l y z ea n dt a l l yu pq p s oa n da m q p s o t h ea m q p s o a p p l i c a t i o ni ns y s t e mp a r a m e t e ri d e n t i f i c a t i o n t h ea m q p s o a p p l i c a t i o n i ns l o v i n gn o n l i n e a r s y s t e mo fe q u a t i o n s t h ea b h aw a si n t r o d u c e di n t ot h ep r o c e d u r eo fe x p l o r i n gt h ep a r a m e t e r so ff p n i nt h ep a p e r , t h ea m q p s ow a s a p p l i e dt oi d e n t i f ys y s t e mp a r a m e t e r t h ei d e n t i f i c a t i o n r e s u l t ss h o wt h a tt h i sm e t h o dh a st h ec a p a b i l i t yo fo v e r c o m i n gt h el i m i t st r a d i t i o n a l i d e n t i f y i n ga l g o r i t h m ，t h ea d v a n t a g e so fh i g hp a r a m e t e ri d e n t i f i c a t i o np r e c i s i o n ，s g o n ga b i l i t y o fr e s i s t a n c et ot h en o i s e ，g o o di n p u ts i g n a lg e n e r a l i t ya n di d e n t i f i c a t i o no ft h en o n l i n e a r s y s t e m ，s oi th a si m p o r t a n tp r a c t i c a lv a l u e s t h ea m q p s oa l g o r i t h mi su s e df o rs o l v i n g p r o b l e mf o rn o n l i n e a rs y s t e m so fe q u a t i o n s ，n u m e r i c a lr e s u l t ss h o wt h ef e a s i b i l i t ya n d e f f i c i e n c yo ft h i sm e t h o d t h ea b h aw a so r i 西n a l l yi n 仃o d u c e di n t ot h ep r o c e d u r eo f e x p l o r i n gt h ep a r a m e t e r so f f p n s i m u l a t e de x p e r i m e n ts h o w e dt h a tt h i sh y b r i da l g o r i t h mh a s e a s i e rc o m p u t a t i o n ，m o r er a p i dc o n v e r g e n c ec o m p a r e dw i t ho t h e rt r a d i t i o n a l l e a r n i n g a l g o r i t h m s , r e d u c en u m b e ro ft r a i n i n g ，i t sg l o b a lc o n v e r g e n c ea b i l i t yi sb e t t e r , t h et r a i n e d p a r a m e t e r sg a i n e df r o ma b o v ea l g o r i t h mw e r eh i g h l ya c c u r a t ea n dt h er e s u l t a n tf p nm o d e l o w n e ds t r o n gg e n e r a l i z i n gc a p a b i l i t ya n ds e l f - a d j u s t i n gp u r p o s e a b s t r a c t k e y w o r d s ：a d a p t i v eq u a n t u m b e h a v e d p a n i c l es w a r mo p t i m i z a t i o n a l g o r i t h m w i t h m u t a t i o no p e r a t o r ；s y s t e mi d e n t i f i c a t i o n ；b pn e u r a ln e t w o r k sl e a r n i n ga l g o r i t h m ；n o n l i n e a rs y s t e m ； f p n ；p r o d u c t i o nr u l e ；f u z z yr e a s o n i n g ；n o n l i n e a rs y s t e mo fe q u a t i o n s i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对劣+ - j o f 究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 签名： ：夔童旌 日 期：丝翌：q 基厦 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签 名：盗立超 导师签名： 真i 盘经 日 期： 边星翌厶2 第一章绪论 第一章绪论帚一早三百了匕 1 1 课题研究的目的、意义 粒子群优化p s o 算法是由k e n n e d v 和e b e r h a n 于1 9 9 5 年提出的一种优化算法。它源于 鸟群集体行为的启发，与其它进化算法相比，它是很有竞争力的神经网络学习算法。由 于粒子群的聚集性，群体多样性的丢失不可避免。在搜索的后期，粒子聚集成群，搜索 空间十分有限，粒子群可能陷入局部极值点。量子粒子群优化q p s o 算法是从量子力学 的角度出发提出的一种新的p s o 算法模型，这种模型以d e l t a 势阱为基础，认为粒子具有 量子的行为。为了避免陷入局部极值点，在q p s o 算法基础上，本文引入变异机制，在搜 索后期，以自适应变异概率对个体进行变异，以此来增加种群的多样性，提出了自适应变 异量子粒子群优化a m q p s o 算法。同时，为防止最优值的丢失，首次采用精英保留策略， 建立精英个体序列库。通过本文可得出，引入变异机制和采用精英保留策略的a m q p s o 算法在全局优化能力和快速收敛能力上都有较大的提高。 要定量、准确地分析设计一个控制系统，一定要建立控制对象的数学模型。精确地 确立对象的数学模型，这是控制理论能否成功地用于实际的关键之一。系统辨识【1 , 2 , 3 j 就 是研究建立生产过程数学模型的一种理论和方法，其辨识方法很多，传统的最小二乘法 【4 j 和极大似然法【5j 等系统辨识方法要求目标函数连续可导，以及采用梯度信息进行搜 索，因此很容易陷入局部最小，从而得不到理想的结果；尤其是最小二乘法在干扰十分 严重的情况下，几乎不能适用。遗传算法【6 , 7 , 8j 在解决一些复杂问题时存在着早熟收敛和 收敛速度慢的缺陷。上述辨识方法存在各方面的局限性，要求数据所含必须是较小的白 噪声；要求所辨识的系统为线性系统；对系统的输入信号不具有通用型，辨识精度不高 等问题。将a m q p s o 算法应用到系统参数的辨识中，辨识结果表明本文提出的算法能有 效地克服传统辨识算法存在的一些局限性，具有参数辨识精度高，抗噪声能力强，对输 入信号通用性强，也适用于非线性系统参数辫识，具有重要的工程应用价值。 寻求求解非线性方程组的有效方法一直是工程技术界和应用数学界的难点之一。近 2 0 年来，国内外的许多数学家对非线性方程组的求解问题进行了大量研究，提出了许多 有效解法，但都存在各种弱点。利用a m q p s o 算法求解非线性方程组，同传统的优化 方法相比，a m q p s o 具有更强的全局优化能力，也能较快地收敛于可接受解。实验结果 表明了算法的有效性。 模糊p e t r i 网【9 j 是基于模糊产生式规则的知识库系统的良好建模工具，使得知识的 表示简单而又清晰；又具有模糊系统的模糊推理能力，便于知识的分析、推理、测试以 及决策支持等，但自学习能力差是模糊系统的一个缺陷。模糊产生式规则是用i f n t h e n 结构来表示知识的，其中的一些参数，例如权值、阈值、确信度等的确定很大程度上依 赖于人的经验，难以精确获得，有时甚至无法获得，这阻碍了模糊p e t r i 网的知识推理 和泛化能力。关于模糊p e t r i 网学习能力的研究时间不长，近年来提出了一些算法，取 得了一些成果。但是，这些算法都存在着不足，对f p n 进行参数优化无法取得比较好 的效果。自适应变异量子粒子群优化算法和b p 网络学习算法相结合的混合算法a b h a ， 江南大学硕士学位论文 此算法简单方便，收敛速度快，能够明显减少迭代次数，具有更好的全局收敛性能，在 参数寻优方面已经有成功应用的例子。所以f p n 的参数优化问题用混合算法a b h a 来 实现在理论上是可行的。 1 2 目前研究现状及存在的问题 粒子群算法是最新的群体智能技术，属于基于种群的随机全局优化算法类，其主要 思想起源于社会心理学和人工生命。该算法模仿生物群体的社会认知过程( 社会规范的 涌现) ，将该过程建模成为简单个体间的交互与协作，用于发现适应度空间中的全局最 优点。 p s o 算法自1 9 9 5 年被提出之后，得到了数值优化领域的广泛关注，吸引了大量研究 者的工作。如何加快算法的收敛速度和避免早熟收敛问题，一粒子群算法及其在p i d 参 数整定中的应用研究直是大多数研究者关注的重点，也是所有随机搜索算法共同面临的 两个主要难题。这两个问题之间本身就存在很复杂的关系，在很多情况下是互相冲突的 两个目标。在避免早熟收敛方面，现有的大量研究涉及如何让算法跳出局部最优点。在 加快收敛速度方面，主要的工作集中在如何选择最优的算法参数，以及从其他智能优化 算法中借鉴一些思想对p s o 算法的主要框架加以修正。从可得的文献中，看到一些研究 者报告了非常鼓舞人心的改善结果。 目前，有关p s o 算法的研究大多以带惯性权重的p s o 算法为基础进行扩展和修改， 为此将带惯性权重的p s o 算法称之为标准p s o 算法。关于粒子收敛行为的分析，要保证 算法的收敛性，每个粒子必须收敛于各自的p 点，这是由粒子的追随性和粒子群的聚集 性决定的。在标准p s o 粒子群系统中，粒子的收敛是以轨道的形式实现的，且粒子的速 度总是有限的，因此在搜索过程中粒子的搜索空间是一个有限的区域，不能覆盖整个可 行的空间。所以标准p s o 算法不能保证以概率1 收敛到全局最优解，这正是其最大的缺 点。为了克服这一缺点，从量子力学的角度出发提出了一种新的p s o 算法模型，这种模 型以d e l t a 势阱为基础，认为粒子具有量子的行为，并根据这种模型提出了量子粒子群 算法。在量子空间中，粒子的速度和位置是不能同时确定的，通过波函数沙g ，f ) 来描述 粒子的状态，并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数。 近年来，传统的最d - 乘法和极大似然法等系统辨识方法已得到了很大改进，但由 于这些方法要求目标函数连续可导，以及采用梯度信息进行搜索，因此很容易陷入局部 最小，从而得不到理想的结果；遗传算法作为一种全局优化算法，在进行的搜索过程中， 对于待寻优的函数基本无限制，不要求参数空间的连续性和可导性，所以在系统辨识中 取得了很大的成功，它可以克服其他许多优化算法的缺点，但同时遗传算法在全局搜索 中也存在早熟问题，不能保证收敛于全局最优点，因此，有时会造成寻优失败。 对非线性方程及方程数与变量数一致的非线性方程组问题。传统数值方法多使用目 标函数的导数信息，具有较快的、与初值有关的局部收敛性。如牛顿法，是一种非常有 效的局部搜索迭代方法。对一些强非线性方程和方程组，传统方法易导致失败，有效性 低。因此，研究针对强非线性方程和方程组的高效算法是一个较有意义的问题。 p e t r i 网作为一种高效的建模和分析工具，近年来得到了快速的发展，但是p e t r i 网作 2 第一章绪论 为一种纯理论工具，并不能适合所有领域的应用需求。所以，针对不同领域的研究对象， 很多学者提出了各种各样改进的p e t f i 网理论，如近年来得到普遍应用的随机p e t f i 网、着 色p e t f i 网等，模糊p e t r i 网作为p e t r i 网的一个重要分支，也越来越多地引起了人们的兴 趣。模糊p e t r i 网由于更符合人类的思维和认知方式，在描述和分析许多物理系统乃至 社会系统的并行和并发行为时具有广泛的意义。特别是应用在人类知识的表示和人工智 能中非常合适，在这一方面，已有许多学者进行了研究。但是，其中的一些参数，例如 权值、阈值、确信度等的确定很大程度上依赖于人的经验，难以精确获得，有时甚至无 法获得，这阻碍了模糊p e t r i 网的知识推理和泛化能力。如何确定模糊产生式规则的各项 参数对模糊p e t f i 网的建立具有非常重要的意义，一直是尚未解决的难题。 1 3 课题主要完成的工作 1 提出a m q p s o 算法 首先分析了基本粒子群优化算法和量子粒子群优化算法及其缺陷，然后在q p s o 算 法基础上引入变异机制，以自适应变异概率对个体进行变异，以此来增加种群的多样性， 同时，为了防止最优值的丢失，首次采用精英保留策略，建立精英个体序列库，提出了 自适应变异量子粒子群优化a m q p s o 算法。 2 利用a m q p s o 进行系统参数的辨识 本文将a m q p s o 应用到系统参数的辨识中，辨识结果表明该算法能有效地克服传 统辨识算法存在的一些局限性，具有参数辨识精度高，抗噪声能力强，对输入信号通用 性强，也适用于非线性系统参数辫识，具有重要的工程应用价值。 3 将a m q p s o 算法应用到求解非线性方程和方程组问题。 由于该算法的收敛结果不依赖于初值，且整个过程毋须导数信息，因此收敛性较好。 对于多解的非线性方程组，可以通过独立计算多次来得到多个完全数值解。数值实验 表明，应用a m q p s o 求解非线性方程组具有算法简单、控制参数少且能求出多个完全 解等优点，是一种值得推广的求解非线性系统的实用算法。 4 将a b h a 引入到模糊p e t r i 网的参数寻优过程 本文将a b h a 引入到模糊p e t f i 网的参数寻优过程，仿真实例表明，这种混合算法计算 简单，收敛速度快，能够明显减少迭代次数，具有更好的全局收敛性能。由此训练出的 参数正确率较高，所得的f p n 具有很强的泛化能力和自适应性。 1 4 本文章节安排 第一章绪论部分，介绍了本课题研究的目的、意义，以及本课题的研究现状和存在 的问题，同时提出了将a m q p s o 应用到系统参数的辨识、求解非线性方程和方程组问 题中以及将a b h a 引入到模糊p e t r i 网的参数寻优过程的新方法。 第二章自适应变异量子粒子群优化算法分析及研究，首先论述了基本粒子群优化 算法，然后在此基础上，阐述了q p s o 和a m q p s o 算法，最后，采用一个典型的大海 捞针类问题( n i h 问题) ，分析a m q p s o 算法的搜索优化性能。 第三章a m q p s o 在系统辨识中的应用，首先介绍了系统辨识的概念，然后通过实 验结果和对比，说明算法的有效性。 3 江南大学硕士学位论文 第四章a m q p s o 在求解非线性方程和方程组中的应用，首先介绍了非线性方程和 方程组的一般情况以及一些求解算法，然后通过实验结果和分析，说明其是一种有效的 实用算法。 第五章基于a m q p s o 和b p 算法的混合算法a b h a 的提出与分析。 第六章混合算法a b h a 优化模糊p e t f i 网的参数，首先对模糊p e t r i 网进行了探讨， 介绍了模糊p e t r i 网的概念和模糊推理函数，最后通过试验说明a b h a 优于其它算法。 第七章结论和展望部分，简要总结了本文的工作，并提出了需要改进的部分。 4 第二章自适应变异量子粒子群优化算法及其优化性能 第二章自适应变异量子粒子群优化算法及其优化性能 2 1 粒子群优化概述 2 1 1 群智能和粒子群优化概念 可把群定义为某种交互作用的组织或a g e n t 之结构集合。在群智能计算研究中，群 的个体组织包括蚂蚁、白蚁：蜜蜂、黄蜂、鱼群和鸟群等。在这些群体中，个体在结构 上是很简单的，而它们的集体行为却可能变得相当复杂。 社会组织的全局群行为是由群内个体行为以非线性方式出现的。于是，在个体行为 和全局群行为之间存在某种紧密的联系。这些个体的集体行为构成和支配了群行为。另 一方面，群行为又决定了个体执行其作用的条件。这些作用可能改变环境，因而也可能 改变这些个体自身的行为及其地位。由群行为决定的条件包括空间和时间两种模式。 群行为不能仅由独立于其他个体的个体行为所确定。个体间的交互作用在构建群行 为中起到重要的作用。个体间的交互作用帮助改善对环境的经验知识，增强了到达优化 的群进程。个体间的交互作用或合作是由遗传学或通过社会交互确定的。社会交互作用 可以是直接的、间接的。直接交互作用是通过视觉、听觉或化学接触，而间接交互作用 是在某一个体改变环境，而其他个体反映该新的环境时出现的。 群社会网络结构形成该群存在的一个集合，它提供了个体间交换经验知识的通信通 道。群社会网络结构的一个惊人的结果是它们在建立最佳蚁巢结构、分配劳力和收集食 物等方面的组织能力。 群计算建模已获得许多成功的应用，例如，功能优化、发现最佳路径、调度、结构 优化以及图像和数据分析等。从不同的群研究得到不同的群应用。其中，最引入注目的 是对鸟群和蚁群的研究工作。粒子群优化方法是由模拟鸟群的社会行为发展起来的。 p s o 算法是一种基于群体搜索的算法，它建立在模拟鸟群社会的基础上。粒子群概 念的最初含义是通过图形来模拟鸟群优美和不可预测的舞蹈动作，发现鸟群支配同步飞 行和以最佳队形突然改变飞行方向并重新编队的能力。这个概念已被包含在一个简单和 有效的优化算法中。 在粒子群优化中，被称为粒子( p a r t i c l e ) 的个体是通过超维搜索空间“流动”的。粒 子在搜索空间的位置变化是以个体成功地超过其他个体的社会心理意向为基础的。因 此，群中粒子的变化是受其邻近粒子( 个体) 的经验或知识影响的。一个粒子的搜索行 为受到群中其他粒子的搜索行为的影响。由此可见，粒子群优化是一种共生合作算法。 建立这种社会行为模型的结果是：在搜索过程中，粒子随机地回到搜索空间中一个原先 成功的区域。 2 1 2 粒子群优化算法 粒子群优化是以邻域原理( n e i 曲b o r h o o dp r i n c i p l e ) 为基础进行操作的，该原理来源于 社会网络结构研究中。驱动粒子群优化的特性是社会交互作用。群中的个体( 粒子) 相 鎏堕奎兰堡主堂垡笙塞 互学习，而且基于获得的知识移动到更相似于它们的、较好的邻近区域。邻域内的个体 进行相互通信。 群是由粒子的集合组成的，而每个粒子代表一个潜在的解答。粒子在超空间流动， 每个粒子的位置按照其经验和邻近粒子的位置而发生变化。令一o ) 表示f 时刻只在超空 间的位置。把速度矢量v ，o ) 加至当前位置，则位置只变为 一o ) = t o 一1 ) + ，o ) 速度矢量推动优化过程，并反映社会所交换的信息。下面给出了三种不同的粒子群 优化算法，它们对社会信息交换扩展程度是不同的。这些算法概括了初始的p s o 算法。 对于个体最佳( i n d i v i d u a lb e s t ) 算法，每一个体只把它的当前位置与自己的最佳位置 p b e s t 相比较，而不使用其他粒子的信息。具体算法如下： ( 1 ) 对粒子群尸o ) 初始化，使得f = 0 时每个粒子只尸o ) 在超空间中的位置t o ) 是 随机的。 ( 2 ) 通过每个粒子的当前位置评价其性能孝。 ( 3 ) 比较每个个体的当前性能与其至今有过的最佳性能，如果 善g ，o ” p b e s t ，那么 f p b e s t ，= 孝g ，o ) ) 1 x 煳= 墨o ) ( 4 ) 改变每个粒子的速度矢量 v ，o ) = y ，o 一1 ) + p b m 一薯o ) ) 其中，p 为一位置随机数。 每个粒子移至新位置 f 薯o ) = o 一1 ) + 1 ，o ) 1 t = f + 1 式中，v ，o ) = qo ) f ，而垃：1 ，所以ko ) f = vo ) 。 ( 5 ) 转回第( 2 ) 步，重复递归直至收敛。 上述算法中粒子离开其先前发现的最佳解答越远，使该粒子( 个体) 移回它的最佳 解答所需要的速度就越大。随机值p 的上限为用户规定的系统参数。p 的上限越大，粒 子轨迹振荡就越大。较小的p 值能够保证粒子的平滑轨迹。 对于全局最佳 o b a lb e s t ) 算法，粒子群的全局优化方案g b e s t 反映出一种被称为星 形( s t a r ) 的邻域拓扑结构。在该结构中，每个粒子能与其他粒子( 个体) 进行通信，形成 一个全连接的社会网络，如图2 1 ( a ) 所示。用于驱动各粒子移动的社会知识包括全群中 选出的最佳粒子位置。此外，每个粒子还根据先前已发现的最好的解答来运用它的历史 经验。 全局最佳算法如下： ( 1 ) 对粒子群尸o ) 初始化，使得f = 0 时每个粒子只p o ) 在超空间中的位置to ) 随 6 第二覃自适应变异量子粒子群优化算法及其优化性能 机的。 ( 2 ) 通过每个粒子的当前位置o ) 评价其性能孝。 ( 3 ) 比较每个个体的当前性能与其至今有过的最佳性能，如果 孝k o ) ) p b e s t ，那么 f p b e s t ，= 善g 。o ) ) 1 x p b e s = t o ) ( 4 ) 把每个粒子的性能与全局最佳粒子的性能进行比较，如果 孝 o ) ) g b e s t i ，那么 f g b e s t ；= 孝g ，o ) ) 1 x 驴毗= to ) 改变每个粒子的速度矢量 匕o ) = m o o + p 。b 加嘶一x ，o ) ) + p ：g 矗耐一墨o ) ) 其中，届和p ：为随机数变量。称上式中的第2 式为认知分量，而最后一项为社会分量。 把每个粒子移至新位置 f o ) = t o 一1 ) + ，o ) 1 t = t + l 转向第( 2 ) 步，重复递归直至收敛。 对于全局最佳算法，粒子离开全局最佳位置和它自己的最佳解答越远，使该粒子回 到它的最佳解答所需的速度变化也越大。随机值p l 和p ：确定为p 。= 厂l c 。，p ：= r 2 c ：，其 中c 。和c ：为正加速常数，而，2 v ( o ，1 ) 。 局部最佳( 1 0 c a lb e s t ) 算法用粒子群优化的最佳方案l b e s t 反映一种称为环形( r i n g ) 的 邻域拓扑结构。该结构中每个粒子与它的n 个中间邻近粒子通信。如果n = 2 ，那么一个 粒子与它的中间相邻粒子的通信如图2 1 ( b ) 所示。粒子受它们邻域的最佳位置和自己过 去经验的影响。 彳 。 乏联娜垒 潞藏髟 n 矿 ( a ) 星形领l 或拓扑结构 ( b ) 环形领 或拓扑结构 图2 1 粒子群优化的邻域拓扑结构 f i g 2 - ln e i g h b o r h o o dt o p o l o g i c a la r c h i t e c t u r eo fp s o 7 江南大学硕士学位论文 本算法与全局算法不同之处仅在第( 4 ) 步和第( 5 ) 步中，以l b e s t 取代咖p 盯。在收敛方 面，局部最佳算法要比全局最佳算法慢得多，但局部最佳算法能够求得更好的解答。 以上各种算法的第( 2 ) 步检测各粒子的性能。其中，采用一个函数来测量相应解答与 最佳解答的接近度。在进化计算中，称这种接近度为适应度函数。 上述各算法继续运行直至其达到收敛为止。通常对一个固定的迭代数或适应度函数 估计执行粒子群优化算法。此外，如果所有粒子的速度变化接近于0 ，那么就中止粒子 群优化算法。这时，粒子位置将不再变化。标准的粒子群优化算法受问题维数、个体( 粒 子) 数、p 的上限、最大速度上限、邻域规模和惯量这6 个参数的影响。 除了上面讨论过的几种算法，即p b e s t ，g b e s t ，l b e s t 以外，近年来的研究使这些 原来的算法得以改进，其中包括改善其收敛性和提高其适应性。 粒子群优化己用于求解非线性函数的极大值和极小值，也成功地应用于神经网络训 练。这时，每个粒子表示一个权矢量，代表一个神经网络。粒子群优化也成功地应用于 人体颤抖分析，以便诊断帕金森疾病。 总而言之，粒子群优化算法已显示出它的有效性和鲁棒性，并具有算法的简单性。 不过，需要开展更进一步的研究，以便充分利用这种优化算法的益处。 2 2 量子粒子群优化算法 2 2 1 标准p s o 算法的进化方程 目前，有关p s o 算法的研究大多以带惯性权重的p s o 算法为基础进行扩展和修改， 为此将带惯性权重的p s o 算法称之为标准p s o 算法。p s o 算法将每个粒子看作是在刀维 搜索空间中的一个没有重量和体积的微粒，并在搜索空问中以一定的速度飞行。该飞行 速度由粒子的飞行经验和群体的飞行经验进行动态调整。 设x ，= g n ，一：，) 为粒子f 的当前位置；v = 0 n ，1 ，m ，) 为粒子f 的当前飞行 速度；只= n ，只：，p 加) 为粒子f 所经历的最好位置，也就是粒子f 所经历过的具有最 好适应值的位置，称为个体最好位置( p b e s t ) 。只= 仂一p 9 2 ，p 朋) 为群体中所有粒子 所经过的最好的位置( g b e s t ) 。c 。，c 2 为加速常数，c o 为惯性权重，= “。，：，吒。) ， 厂2 = ( ，2 ，吃：，吃。) 为两两相互独立的 o ，1 】范围内变化的随机数。 标准p s o 算法的进化方程为： y 玎o + 1 ) = v o o ) + q 木b ，o ) 一x 玎o ) ) + c ：，2 0 ) b 蔚o ) 一x 耵o ) ) ( 1 ) p + 1 ) = x f ，q ) + v _ f j ( t + 1 j ( 2 ) 设厂( x ) 为最小化的目标函数，则粒子i 的当前最好位置由下式确定： 咖1 ) _ 胤+ 1 ) 舅鬣g ：舄器箔 设群体中的粒子数为s ，群体中所有粒子所经历的最好位置只( f ) 由下式确定： 乞o ) 识o ) ，只o ) ，e o ) ) i f ( p z ( t ) ) = m i n 沙化o ) ) 化o ) ) ，奴o ) ) ) ( 4 ) 根据文献 1 3 关于粒子收敛行为的分析，要保证算法的收敛性，每个粒子必须收敛 8 第二章自适应变异量子粒子群优化算法及其优化性能 于各自的尸点，这是由粒子的追随性和粒子群的聚集性决定的。第i 个粒子尸点的第维 坐标为： p ，= 1 p ，+ f 0 2 j p 百) b j + 缈2 ，)纯，= c i r l j ，妒2 ，= c 2 r 2 j ( 5 ) 从动力学的角度看，粒子群算法中粒子的收敛过程是以尸点为吸引子，随着速度的 减小不断地接近p 点，最后收敛到尸点。因此在整个过程中，在p 点处实际上存在某种 形式的吸引势能场吸引着粒子，这正是整个粒子能保持聚集性的原因。但是在标准p s o 粒子群系统中，粒子的收敛是以轨道的形式实现的，且粒子的速度总是有限的，因此在 搜索过程中粒子的搜索空间是一个有限的区域，不能覆盖整个可行的空间。所以标准 p s o 算法不能保证以概率l 收敛到全局最优解，这正是其最大的缺点。 2 2 2 量子粒子群算法 文献 1 4 从量子力学的角度出发提出了一种新的p s o 算法模型，这种模型以d e l t a 势阱为基础，认为粒子具有量子的行为，并根据这种模型提出了量子粒子群算法。 在量子空间中粒子的满足聚集态的性质完全不同，它可以在整个可行解空问中进行 搜索，因而q p s o 算法的全局搜索性能远远优于标准p s o 算法。在量子空间中，粒子的 速度和位置是不能同时确定的，文献【1 4 】通过波函数 ，t ) ( 其物理意义为：波函数的平 方是粒子在空间某一点出现的概率密度) 来描述粒子的状态，波函数( i ，f ) 如下： 鼍絮 i 例d x d y d z = iq d x d y d z = 1 ( 6 ) - - 0 0 一 式中：q 为粒子在时刻t 出现在( x y ，z ) 位置的概率，并通过求解薛定谔方程得到粒子在 空间某一点出现的概率密度函数。随后通过蒙特卡罗随机模拟的方式得到粒子的位置方 程为 x o ) = 尸妻l n o i z ，) ( 7 ) 材为 o ，1 范围内变化的随机数，文献 7 】中三被定义为： 三q + 1 ) = 2 宰im b e s t x q ) i( 8 ) mfmmm、 m b e s t = 只m = l 翻m , 猕m , 璐ml ( 9 ) 工一 l 一一 一 i 、 i = 1 = - 1 i = li = - i 其中称为收缩扩张系数，m 为粒子的数目，d 为粒子的维数，只为第i 个粒子的 p b e s t ，m b e s t 为平均最优值。最后得到粒子的位置方程为： x ( t + 1 ) = p + f l * lm b e s t - x ( t ) * l n ( 1 u ) ( 1 0 ) 在迭代过程中，是由( o ，1 ) 之间产生的随机数决定，当产生的随机数大于0 5 时取一， 其余取+ 。 综上所述，q p s o