（计算机应用技术专业论文）微粒群算法的改进及其在蛋白质折叠结构预测中的应用.pdf

武汉科技大学 研究生学位论文创新性声明 i i j|ill l l y 1 7 3 9 岩1 “2 。 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进 行研究所取得的成果。除了文中已经注明引用的内容或属合作研究共 同完成的工作外，本论文不包含任何其他个人或集体已经发表或撰写 过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文 中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名：雅 研究生学位论文版权使用授权书 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它 单位的名义发表。本人完全了解武汉科技大学有关保留、使用学位论 文的规定，同意学校保留并向有关部门( 按照武汉科技大学关于研 究生学位论文收录工作的规定执行) 送交论文的复印件和电子版本， 允许论文被查阅和借阅，同意学校将本论文的全部或部分内容编入有 关数据库进行检索。 论文作者签名：剃 指导教师签名：生丝绉 日 期：玉也主：至， 武汉科技大学硕士学位论文 第1 页 摘要 自然界的很多行为都表现为群体性。利用这些群体行为来建立的模型称为群体智能算 法。群体智能算法中有许多算法，微粒群优化算法就是其中一个，它已经被广泛应用于很 多优化问题，并表现出了其高效性。但是随着被优化问题维数和局部最小区域的增多，微 粒群优化算法也将表现出其难收敛性，并易陷入局部最小区域。 蛋白质是组成生物体的基本物质，是生命活动的主要承担者。蛋白质的空间折叠结构 决定其功能和特性。在计算生物学中，通过蛋白质氨基酸链来预测其空间折叠结构是极具 挑战性的科研工作。蛋白质分子的原子和周围溶剂相互作用，当蛋白质自由能量最低时形 成的结构就是蛋白质的天然结构。基于此自由能量最低理论，提出了很多简化的蛋白质模 型来预测蛋白质的结构。其中t o y 模型就是由s t i l l i n g e r 提出的一个最为简单和有效的蛋白 质模型，但随着氨基酸节点长度的增加。用t o y 模型来预测蛋白质结构需要极大的计算量。 因此对快速预测带来了很大的困难。 本文对基本的微粒群算法进行改进，得到了一种改进算法叫作欧氏微粒群算法。此算 法改善了其跳出局部最小的能力，通过一些标准实验函数测试，已经证实了其优秀的性能。 并将此新算法应用于二维t o y 模型的蛋白质折叠结构预测问题，对人工蛋白和真实蛋白的 结构做了预测，并将其结果与其他典型文献中的结果做了对比。实验结果证实此新算法在 t o y 模型的蛋白质折叠结构预测问题中是非常有效的。 关键词：群体智能算法；欧氏微粒群算法；蛋白质结构预测；自由能量；t o y 模型 a b s t r a c t n a t u r a lc r e a t u r e ss o m e t i m e sb e h a v ea sas w a r m s w a r mi n t e l l i g e n c ea l g o r i t h m su t i l i z e s t h e s eb e h a v i o ri ne s t a b l i s h i n gm o d e l s t h e r ea r em a n ys w a r mi n t e l l i g e n to p t i m i z a t i o n , p a r t i c l e s w a r ma l g o r i t h m ( p s o ) i so n eo ft h a ta l g o r i t h m s ，w h i c hh a sb e e ns u c c e s s f u l l ya p p l i e dt om a n y o p t i m i z a t i o np r o b l e m sa n ds h o w ni t sh i g hs e a r c hs p e e di nt h e s ea p p l i c a t i o n s h o w e v e r , a st h e d i m e n s i o na n dt h en u m b e ro fl o c a lo p t i m ao fp r o b l e m si n c r e a s e ，p s oi se a s i l yt r a p p e di nl o c a l o p t i m a p r o t e i ni sa ni m p o r t a n tc o m p o n e n to fl i v i n go r g a n i s m s ，w h i c hi st h em a i nb e a r e ro fl i f e a c t i v i t i e s t h es t r u c t u r eo fp r o t e i nd e t e r m i n e si t sf u n c t i o ni nm o l e c u l a r p r e d i c t i n gt h es t r u c t u r e o fp r o t e i nt h r o u g hi t s s e q u e n c eo fa m i n oa c i d si sac o m p l e xa n dc h a l l e n g i n gp r o b l e mi n c o m p u t a t i o n a lb i o l o g y t h en a t i v es t r u c t u r eo fap r o t e i ni sa s s o c i a t e dw i t ht h es t r u c t u r eo ft h e g l o b a lm i n i m u mo ft h ef r e ee n e r g yc o n s i s t i n go ft h ei n t r a - m o l e c u l a ri n t e r a c t i o na m o n gp r o t e i n a t o m sa n db e t w e e nt h ep r o t e i n sa n ds u r r o u n d i n gs o l v e n tm o l e c u l e s b a s e do nt h i sm i n i m u m f r e e e n e r g yt h e o r y , m a n ys i m p l i f i e dp r o t e i nm o d e l sh a v eb e e np r o p o s e dt o p r e d i c tt h es t r u c t u r eo f p r o t e i n t o ym o d e li so n eo ft h es i m p l e s ta n dm o s te f f e c t i v ep r o t e i nm o d e l sp r o p o s e db y s t i l l i n g e r t h o u g ht o ym o d e li so n eo ft h es i m p l e s ta n de f f e c t i v em o d e l s ，i ti ss t i l lr e q u i r ev e r y e x t e n s i v ec o m p u t a t i o nt op r e d i c tl t ss t r u c t u r ea st h ei n c r e a s eo fa m i n oa c i d s s oi ti sd i 伍c u l tt o p r e d i c tt h es t r u c t u r er a p i d l y i nt h i sp a p e r , h a v ep r o p o s e da l l i m p r o v e dp s oa l g o r i t h m ，c a l l e de p s o ( e u c l i d e a np a r t i c l e s w a r mo p t i m i z a t i o n ) ，w h i c hh a sg r e a t l yi m p r o v e dt h ea b i l i t yo f e s c a p i n gf o r ml o c a lo p t i m a , a n d i th a sc o n f i r m e di t se x c e l l e n t p e r f o r m a n c ei nb e n c h m a r kf u n c t i o n s t h e na p p l i e dt h en e w a l g o r i t h mt ot h es t r u c t u r ep r e d i c t i o no ft o ym o d e lb o t ho na r t i f i c i a la n dr e a lp r o t e i ns e q u e n c e s a n d c o m p a r e d w i t ht h er e s u l t s r e p o r t e d i no t h e rl i t e r a t u r e s t h e e x p e r i m e n t a lr e s u l t s d e m o n s t r a t e dt h a tt h en e w a l g o r i t h mw a se f f i c i e n ti np r o t e i ns t r u c t u r ep r e d i c t i o np r o b l e mi nt o y m o d e l k e y w o r d s ：s w a r mi n t e l l i g e n c ea l g o r i t h m ；e u c l i d e a np a r t i c l es w a r mo p t i m i z a t i o n ；f r e ee n e r g y ； p r o t e i ns t r u c t u r ep r e d i c t i o n ；t o ym o d e l ； 武汉科技大学硕士学位论文 第1 i i 页 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景及意义l 1 2 国内外研究现状2 1 3 本文主要工作3 1 4 本文的结构安排4 第二章微粒群优化算法5 2 1 基本微粒群优化算法( p s o ) 5 2 1 1 基本微粒群算法简介5 2 1 2 微粒群算法的基本原理5 2 1 3 微粒群算法的流程6 2 2 微粒群算法的发展7 2 3 微粒群优化算法的应用9 2 3 本章小结9 第三章欧氏微粒群算法。o 1 0 3 1 欧氏微粒群算法提出背景1 0 3 2 欧氏微粒群算法原理1 0 3 3 欧氏微粒群算法及流程1 2 3 4 实验与分析1 3 3 4 1 实验测试函数简介1 3 3 4 2 欧氏微粒群算法参数的测定1 6 3 4 3 实验与比较l8 3 4 本章小结2 0 第四章蛋白质的结构与模型2 1 4 1 蛋白质简介2 1 4 2 蛋白质的功能2 l 4 3 蛋白质的结构2 2 4 4 蛋白质结构预测与模拟2 3 4 5 蛋白质结构预测的优化模型2 4 4 5 1h p 格点蛋白质模型2 4 4 5 2t o y 蛋白质模型2 5 4 6 本章小结2 7 第五章基于e p s 0 幂l ：l t o y 模型的蛋白质结构预测2 8 5 1 基于t o y 模型的人工蛋白质序列结构预测2 8 5 1 1 人工实验数据结构预测2 8 5 1 2 裴波纳契序列结构预测2 9 5 2 基于t o y 模型的真实蛋白质序列结构预测3 0 5 2 1 蛋白质数据库简介3 0 5 2 2 较短真实蛋白质序列结构预测3 l 5 2 31 a g t 和1 a h o 真实蛋白质序列结构预测3 3 5 2 3 较长真实蛋白质序列结构预测3 4 第1 v 页 武汉科技大学硕士学位论文 5 3 本章小结3 7 第六章总结与展望3 8 6 1 工作总结3 8 6 2 研究展望3 8 参考文献4 0 致谢4 4 附录a 攻读学位期间发表的论文4 5 附录b 攻读学位期间参与科研项目4 5 武汉科技大学硕士学位论文 第l 页 1 1 研究背景及意义 第一章绪论 自然界中的很多生物体均具有一定的群体行为，通常群体行为可以由几条简单的规则 来进行建模。虽然每一个个体具有非常简单的行为规则，但它的群体行为却表现为非常复 杂。美国社会心理学家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 基于他们早期对许多 鸟类群体行为建模与仿真研究启发，在1 9 9 5 年共同提出了微粒群优化算法i l 2 。( 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 ) 。由于p s o 具有原理简单，易于实现，收敛速度快等优点，在很 多领域得到了应用，包括在蛋白质折叠结构预测的应用【3 j ，目前已形成学术界一个新的研究 热点。 p s o 算法出色的解决了很多多维复杂的n p 难问题。但是针对像蛋白质折叠结构预测 问题等具有极多局部极值和维数的情况，p s o 也往往会陷入局部最小和早熟收敛。主要原 因是算法中所有粒子具有快速飞向自身历史最优位置和微粒群全局最优位置的特点，当当 前最优位置处于局部极值点时，极大多数微粒都会聚集在局部极值区域【4 j ，致使微粒速度 越来越小，几乎停滞，缺乏微粒的多样性，很难逃离局部极值区域。因此采取策略给微粒 施加刺激，对p s o 优化算法进行改进，使微粒能够逃离局部极值区域。以此来提高算法收 敛精度和避免进入早熟收敛，对算法性能的提高有着重大的意义。然后再把改进了的算法 应用于蛋白质折叠预测领域，既保持了算法本身的快速收敛性，又能够逃离局部最小区域 找到蛋白质结构更稳定的折叠构象，对蛋白质结构预测的研究有着长远的意义。 蛋白质是形成生物体的基本组成物质，是生命活动的主要承担者，在生物的生命活动 中起了主要的作用。蛋白质的结构与功能是一个统一体，由a n f i n s e n 【5 】提出了蛋白质的生 物功能是由其空间折叠结构决定的理论，特定的蛋白质结构对应其特定的功能。蛋白质折 叠结构细微的变化，会极大的影响其生物性质。很多疾病，如疯牛病、老年痴呆症、白内 障和部分癌症等都是由于蛋白质的错误折叠形成的【6 】【7 1 ，但这些错误的蛋白质分子的一级 或二级结构与正常的却完全相同，只有空间稍微有所不同。由此，对蛋白质折叠结构预测 的研究不仅在生物和医学工程上具有极大应用价值，而且对揭开人体生老病死的秘密有着 重要意义。 蛋白质折叠结构预测就是通过蛋白质的一级结构，来预测出蛋白质的空间构象。2 0 世 纪7 0 年代初由a n f i n s e n 提出的理论认为，蛋白质的空间结构完全取决于蛋白质的一级结 构【5 1 ，由此获得了诺贝尔奖。大量科学实验也充分说明氨基酸序列和蛋白质空间结构之间 确实存在一定联系，但蛋白质空间折叠结构是如何由其氨基酸序列的多肽链决定的，这一 过程又是怎样遵循热力学和动力学规律的等分子生物学中心法则问题至今尚未解决，此问 题便称为蛋白质的折叠问题，也称为中心法则的第二遗传密码问题【8 j 。蛋白质结构预测， 特别是基于热力学定律的蛋白质结构预测则能够有助于了解蛋白质折叠机理，并且揭示蛋 白质的折叠密码。 第2 页武汉科技大学硕士学位论文 1 2 国内外研究现状 微粒群优化算法( p s o ) 是由k e n n e d y 与e b e r h a r t 共同提出的，在1 9 9 5 年的i e e e 国际 神经网络学术会议上发表了题为“p a r t i c l es w a r mo p t i m i z a t i o n 的文掣5 1 ，此标志着微粒 群算法的诞生。此算法源于对鸟群捕食行为的研究。由于p s o 原理简单，易于模拟实现，具 有较强的全局收敛性和鲁棒性，已经在很多领域得到了应用，早已形成学术界一个新的研 究热点。s h iye b e r h a r tr 对基本p s o 的做了改进，在速度更新公式中引进了惯性权因子 ，进一步提高算法的性能，此改进的算法被后人当做作标准微粒群算法s p s 0 1 1 9 】。c l e r e 提出了带收敛因子的微粒群算法c p s o t 2 们，与s p s o 相比，使用收敛因子的p s o 有更好的 收敛速度。p e a e rj a n g e l i n e 将进化计算中的锦标赛选择算子引入了p s o 算法中1 2 ，使得 算法的搜索能力增强。r e n a t oa k r o h l i n g 利用高斯公式，使系数取符合均值为0 8 ，标准 差为0 6 的高斯分布的随机数，并命名为高斯微粒群算法g p s o t 2 2 1 ，和进化算法一样，当 被优化问题局部极小区域和维数增多时，此算法也常常会陷入局部极小【2 3 1 。 微粒群算法虽然存在参数少，容易实现，效率高等优点，但微粒的数目、权值等应该 随着被优化问题复杂度和适应度等因素变化而变化。c h e nd o n g 等认为，算法寻优过程中 当适应值较好、微粒数较多、维数交少时权值应该变小来提高局部搜索能力，加快收敛速 度。当适应值较差、微粒数较少、维数交多时，应该增大权值来提高全局搜索的能力。由 此实现了自适应权值的微粒群算法【2 4 1 。但自适应权值公式参数较多，很难调节，收敛速度 有所提高，收敛精度往往达不到有求。 蛋白质是生物体的重要组成部分，研究清楚蛋白质的空间构象至关重要。蛋白质空间 折叠结构预测的方法主要可以分为两类【4 】。第一类是假定当蛋白质分子能量最低，热力学 最稳定的状态的结构为蛋白质的天然构象，并且考虑蛋白质分子中的所有原子间存在着相 互作用，蛋白质分子和溶剂之间也存在着相互作用，最后采用寻找分子能量最低值的来计 算出蛋白质分子的天然空间结构。第二类方法则是基于知识的预测方法【9 1 。基于第一类自 由能量最低理论，人们提出了很多简化的蛋白质模型来预测蛋白质的结构。而对这些模型 的求解都极为复杂，都为n p 问题，人们又努力寻求解决此问题的各种工具和方法。 通过对蛋白质结构的理论抽象，蛋白质被认为是由疏水氨基酸( h y d r o p h o b i c ) 和亲水 氨基酸( h y d r o p h i l i c ) 组成。目前主要有格点模型( l a t t i c em o d e l ) 和非格点模型( o f f - l a t t i c e m o d e l ) 两种。h p 格点模型【lu j ( h p l a t t i c em o d e l ) 是由d i l l 等人提出的，它是最简单的格 点模型，然而虽然它是最简化的模型之一，计算蛋白质序列的最低能量时构象仍然是一个 n p 难题【l ，其求解时间呈指数形增长，随着序列长度n 的增大，求解变得非常困难。1 9 9 3 年，f r a n kh s t i l l i n g e r 2 1 等人提出了t o y 模型也称作a b 非格点模型( a bo f f - l a t t i c e m o d e l ) ，并且给出了相应的能量计算公式。与格点模型区别在于它的折叠角度，连接三个 氨基酸残基的两个肽键之间的角度是可以任意变化的，也就是说两两相邻的键是可以任意 转动的，而且该模型同时又考虑了不相邻链上的单体之间存在着的势能，以及相邻两个键 之间存在的势能。t o y 模型无疑是h p 模型的一个改进模型，更能够体现出蛋白质的真实 武汉科技大学硕士学位论文 第3 页 折叠结构。 国内许多研究者也在蛋白质结构处理方面做了很多工作。中国科学院院士，王志新教 授在从事这一尖端课题的研究工作中，成功地解决了与蛋白质二级结构有关的几个重要理 论问题。李元乐【1 3 】提出一种基于小波核支持向量机分类模型，将其用于s a r s 蛋白质结构 预测。苏计国【1 4 】对删p 模型进行了深入研究，把2 0 种氨基酸简化为3 类，疏水性氨基酸、 亲水性氨基酸和中性氨基酸，以相对熵做优化函数进行蛋白质结构预测。张晓龙、林晓丽、 朱红兵等将遗传退火算法( q 认) ，局部微调遗传退火算法( l a g s ) ，禁忌算法( t a b u ) 应用到蛋白质a b 非格模型的预测【b 。18 1 。目前这种可靠的全局优化方法的确定仍是蛋白质 结构预测的一个研究热点。 一般p s o 算法在处理像蛋白质折叠结构预测等极多维数和局部最小问题时往往会陷 入局部最小和早熟收敛。所以有必要先对标准的微粒群算法作改进，使其能够逃离局部最 小区域，提高收敛精度。然后再将其应用于a b 非格点模型的蛋白质折叠结构预测中，找 到其更低的能量值，预测出更为稳定的结构。 1 3 本文主要工作 研究内容： 本文的主要研究方向是对微粒群算法的改进以及在蛋白质折叠结构预测中的应用。鉴 于微粒群群算法是一种高效的智能群体优化算法，但随着维数和局部最小的增多而难以收 敛，一方面先研究微粒群算法的原理，及其存在的缺陷，并搞清楚其原因。然后针对存在 缺陷的原因设计改进微粒群算法的策略和方法。通过对微粒群算法的改进，使得改进后的 微粒群算法能够保留其收敛速度快的特性的同时，当算法陷入局部最小区域时使其跳出局 部最小区域，提高收敛能力和精度。最后用几组标准的测试函数来验证改进算法的性能， 并与先前很多版本的算法进行比较，结果表明改进后的算法性能更加高效。 另一方面，由于蛋白质空间结构的预测是个具有重要意义且复杂的问题，研究a b 非 格蛋白质折叠模型及其能量函数，并将其与微粒群算法结合起来。用改进后的微粒群算应 用于此问题，在一定程度上解决了预测蛋白质结构的复杂问题，更好的验证了改进后的微 粒群算法的性能。在实验中用二维t o y 模型分别对多组人工蛋白序列和蛋白质库中的真实 序列进行计算，得出他们的稳定能量和折叠构象。通过比较，改进的算法更容易找到能量 最低值，且随着蛋白质氨基酸链节点的增加算法性能更加明显。 第4 页武汉科技大学硕士学位论文 1 4 本文的结构安排 本文分为七章，各章内容组织如下： 第一章简要介绍了蛋白质空间结构预测和微粒群算法改进的研究背景和意义，并且 分析其国内外研究现状，介绍了本文所做的主要工作和文章结构安排。 第二章介绍了微粒群算法的基本原理，算法的起源和发展，并且介绍了微粒群算法 的应用领域。 第三章对基本微粒群算法的不足进行分析，并对其做了改进，得到新的改进算法， 称作欧氏微粒群算法，并且用实验来测定参数的设定和证实改进算法的性能。 第四章对蛋白质的基础知识做了介绍，特别是蛋白质的功能结构和组成。介绍了蛋 白质模型的来历及分类。 第五章对典型的人工蛋白和真实蛋白序列做了介绍。将欧氏微粒群算法应用于二维 t o y 模型的蛋白质空间折叠结构预测问题，通过实验测得了蛋白质序列的最 低能量和折叠构象并与其他论文中的结果作了对比。 第六章总结了本文工作的创新与不足，并简要分析了蛋白质结构预测存在的难点， 最后对此研究领域将来的工作作出了展望。 武汉科技大学硕士学位论文 第5 页 第二章微粒群优化算法 2 1 基本微粒群优化算法( p s o ) 2 1 1 基本微粒群算法简介 在自然界中，很多生物体都表现为一定的群体行为，这些群体行为通常会遵循几条简 单的规则，通过这些规则可以建模形成一种仿生算法。虽然每个离散的个体行为规则非常 简单，但其群体行为却表现出极大的复杂性。r e y n o l d s 通过研究发现鸟群在觅食的飞行过 程中通常会遵照以下三条简单规则： ( 1 ) 尽量飞离离自己最近的个体，以免发生碰撞。 ( 2 ) 飞向觅食目标。 ( 3 ) 飞向整个群体中心。 群体内的每一个体行为可以采用以上规则进行描述，这就是微粒群算法基本概念之一。 b o y d 和r i c h e r s o n 在研究人类的决策过程的时候，发现了个体学习与文化传递的概念。 他们发现人们在决策时通常会使用两种重要信息。第一种是自己的经验，第二种是别人的 经验。这是微粒群算法的另外一个基本概念。 通过以上理论基础，微粒群算法在1 9 9 5 年由美国电气工程r u s s e l le b e r h a r t 和社会心 理学家j a m e sk e n n e d y 共同提出【5 】，称作微粒群优化算法( p s 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 ) 。其基本思想是受到他们早期对许多鸟类群体行为的观察并进行建模与仿真 得出的结果。而微粒群算法的模型及仿真算法主要采用了生物学家f r a n kh e p p n e r 所创建 的模型。 微粒群优化算法的基本思想是来源于对鸟群简化社会的研究以及行为模拟，微粒群优 化算法与其它演化算法相似之处是，依照对环境的不同适应度将群体中的个体移动到较好 的区域中去。微粒群算法的原理是将每一个个体看作是寻优空间中的一个没有质量和体积 的微粒，并在搜索空间中以一定速度飞行，学习与适应其优化环境，并根据个体和群体的 飞行经验综合分析出结果来动态调整其飞行速度。 2 1 2 微粒群算法的基本原理 在基本微粒群算法模型中，每一个个体可以看作是寻优空间中一个没有质量也没有体 积的微粒，并在搜索空间中以一定速度飞行，根据个体自身的飞行经验及同伴飞行经验来 调整自己的飞行速度，即每一个个体根据迭代过程中统计自身的最优值和种群最优值来不 断地修改自身前进的方向和速度的大小，从而形成了寻优正反馈的机制，并继续在空间搜 索，最终寻找出问题最优的解。在连续寻优空间中，第f 个微粒同时受到自身的和历史的 最优位置p u g e t 和种群的最优位置p 拟的吸引，来更改方向和速度，直到满足停止条件。 第6 页武汉科技大学硕士学位论文 设在玎维的目标搜索空间中，有所个微粒组成一个微粒群，其中第f 个微粒在力维的 搜索空间中的所处位置为x f = ( x x ，2 x 抽) 。将而代入相应的目标函数中即可得到相应 的适应值，算法根据当前适应值大小来衡量微粒所处位置嗣的优劣。设第f 个微粒的飞行 速度为l ，= ( ，v ，2 ) 。记第f 个微粒至今为止寻找到的最优位置为该微粒的历史最优 位置p ，= ( 鼽，p ，2 p 加) ，其相对应的适应值则为该微粒的历史最优适应值矗吲。群体 中所有微粒经历的最好位置为该微粒群的全局最优位置段，其相应的适应值为当前全局 最优适应值石脚。k e n n e d y 和b e r h a r t 最早提出的p s o 算法采用公式( 2 1 ) 和( 2 2 ) 通过迭代 对粒子飞行速度和位置进行更新操作，直到条件终止。 l ，i = y ，+ c r a n d ( p ，一x ，) + c 2 r a n d ( p g x i ) x “12x ，+ y ， ( 2 1 ) ( 2 2 ) 其中c 卜c 2 为加速常数，其取值区间通常在【0 ，2 】，r a n d 和r a n d 是服从u ( 0 ，1 ) 的两个相互 独立的随机函数。 从以上微粒进化方程可看出，c j 调节的是微粒飞向自身最优位置方向的步长，勿调节 的是微粒飞向全局最好位置的步长。微粒在进化过程中会离开搜索空间，为了减少其可能 性，耽通常被限定在一定范围内，即v ，【- v 一，v 一】。如果要使问题的搜索空间限定在 t 【一x 一，x 一】内，则可设定v m 戤= k x m 积，o 1 k 1 0 。f f 式( 2 1 ) 主要是通过三个 部分来计算微粒f 的更新速度：微粒f 前一时刻速度v i ，微粒f 当前位置和自身历史最优 位置之间的距离p i 一均，微粒f 当前位置与群体最优位置之间的距离妇一鼢，粒子位置而 通过公式( 2 2 ) 计算。 2 1 3 微粒群算法的流程 微粒群算法原理简单，流程简洁，其基本的算法和流程如下所示： s t e p l ：初始化，对微粒群的随机位置、速度、速度区间、空问区问进行初始设定； s t e p 2 ：先计算每一个微粒的适应值： s t e p 3 ：对于每个微粒，将它的适应值和自己所经历过的最好位置肌的适应值，进行 比较，如果较好，则将当前适应值对应的位置作为当前的最好位置； s t e p 4 ：将每个微粒的适应值与全局所经历的最好位置忍的适应值厶瓣比较，若较好， 则将其作为当前全局最优位置： s t e p 5 ：根据公式( 2 1 ) 和( 2 2 ) 对微粒的速度和位置进行修正； s t e p 6 ：判断是否达到结束条件( 通常为足够好的适应值或达到一个预设最大迭代次数) ， 如果没有则返回s t e p 2 。 武汉科技大学硕士学位论文 第7 页 基本微粒群算法流程图如下： 2 2 微粒群算法的发展 图2 1 基本p s o 算法流程图 微粒群算法的搜索性能主要取决于对全局搜索能力与局部搜索能力的平衡，这很大程 度上都依赖于算法本身的控制参数。因此1 9 9 8 年s h iye b e r h a r tr 对基本的微粒群算法做 了改进【1 2 】，在速度更新公式中引入了惯性权因子，如公式( 2 3 ) ，( 2 4 ) 所示，为了让算法 进一步提高性能，提出了自适应调整的策略，随着迭代循环的进行，线性的减小的值， 即从0 9 线性下降到0 4 。这样算法在搜索初期有较强的搜索能力，而在搜索后期又能得到 较精确的结果。人们把这算法看作p s o 算法的标准版本( s p s o ，s t a n d a r dp a r t i c l es w a r m o p t i m i z a t i o n ) 。 l ，j = w ，+ c l r a n d ( p j x j ) + c 2 r a n d ( p g i t ) i t + i 2 x ，+ 屹 ( 2 3 ) ( 2 4 ) 后来c l e r c 对p s o 做了改进，提出带收敛因子的微粒群算法【2 0 ( c p s o ，p a r t i c l es w a r m o p t i m i z a t i o nw i t hac o n s t r i c t i o nf a c t o r ) ，通过实验证明，与带有惯性权重的p s o 相l t ，c p s o 有更快的收敛速度。此方法描述了选择w ，c l 和c 2 值的方法，以保证算法收敛性。通过 第8 页武汉科技大学硕士学位论文 正确选择这些控制参数，就无需将的值限制在卜v m a x ，v 一之中。经过修正后的微粒速 度更新公式如下式所示： 屹= k v i + f ，r a n d ( p f x j ) + c 2 r a n d ( p g x ，) 】 ( 2 5 ) k = 2 i2 - 9 - q 2 4 ( p w h e r e 币= c l + c 2 , q 4 r ，6 、 e b e r h a r t 和s h i 分别将带权值和收缩因子的两种算法性能作了比较【3 6 1 ，结果表明，带 收缩因子的算法比带权值的算法通常要具有更好的收敛率。但是在某些测试函数的求解 中，使用收缩因子的微粒群算法在给定的迭代次数内无法找到全局极值点。后来e b e r h a r t 和s h i 得出结论，这是因为微粒偏离了所期望的搜索空间太遥远而造成的。 在微粒群算法中，每个微粒的最好位置的确定就像一个隐含的选择机制。p e t t e r j a n g e l i n e 将进化计算中的锦标赛选择算子引入了p s o 算法中【3 刀。此算法依据适应度对所 有微粒进行排序，并用群体中当前位置和速度最好的一半微粒替换最差的一半微粒。这样， 当每次迭代后，一半微粒将会移动到搜索空间相对较好的位置，这些移动的微粒会仍保留 着它们个体的极值，以便用于下一次位置更新。实验结果表明，引入选择方法增强了算法 的搜索能力。 n a t s u k ih i g a s h i ，h i t o s h ii b a 将来源于进化计算的高斯变异算子与p s o 进行杂交 7 1 。该 方法在传统速度与位置更新规则中引进高斯变异，其变异公式为： x i + i = x ，( 1 + g a u s s i a n ( o ) ) ( 2 7 ) 其中斯，为变异之后微粒位置，o 则为搜索空间一维长度的0 1 倍。在搜索过程中，根 据先验概率选择变异的个体，并且以高斯分布概率来决定它们的新位置。与基本微粒群算 法相比，该算法在一定程度上可避免陷入局部最优。 通过证实表明肌一粒和p g x l 的系数的平均值处于o 7 2 9 t 3 8 】或o 8 5 【3 9 1 时算法将具有很好 的性能，所以系数的均值在区间【o 7 2 9 ，0 8 5 上取值并且为正时收敛效果较好。r e n a t oa k r o h l i n g 利用高斯公式，使系数取符合均值为0 8 ，标准差为0 6 的高斯分布的随机数，并 命名为高斯微粒群算法【2 2 1 ，其修正后的速度更新公式如下： ，= lr a n di ( p f x j ) + lr a n dl ( p g x ，) ，q 、 厶u ， 其 l r a n a l 和i r a n a l 是符合高斯分布a b s n ( 0 ，1 ) 】的正随机数。高斯微粒群算法有参数少， 不用限定速度，不需带权值因子，根据高斯分布自适应调节系数等优点，较标准微粒群算 法有更好的效率和避免陷入局部最小的能力。但和进化算法一样，当被优化问题局部极小 区域和维数增多时，此算法也常常会陷入局部极j x 2 3 1 。 微粒群算法虽然参数较少，但微粒数目、权值等应该随着被优化问题复杂度和适应度 等因素而变化。c h e nd o n g 等认为，算法寻优过程中当适应值较好、微粒数较多、维数交 少时权值应该变小来提高局部搜索能力，加快收敛速度。当适应值较差、微粒数较少、维 数交多时，应该增大权值来提高全局搜索的能力。他们设计了权值和微粒数、维数、适应 度相关的自适应权值公式： 武汉科技大学硕士学位论文 第9 页 w - - 1 3 一e x p ( 一s 2 0 0 ) + ( r 8 d ) 2 】一 ( 2 9 ) 其中w 为权值，s 为微粒数，r 为适应值，d 为被优化问题的维数。由此称作自适应 权值的微粒群算法【加1 。但自适应权值公式参数较多，很难调节，收敛速度有所提高，收敛 精度往往达不到要求。 2 3 微粒群优化算法的应用 微粒群优化算法是一种新的进化计算技术，由于它参数少，收敛效率高等优点在很多 领域得到了广泛的应用。p s o 早期就应用于神经网络权值学习当中，也广泛应用于工程领 域中各类优化问题的计算，并起到良好的效果，对于微粒群算法的应用时代才刚刚开始。 以下图表显示p s o 在广泛的领域得到的应用。其中最后八个应用都是p s o 在电力和能量 系统中的应用，其中p s o 优化热电联产的技术已经在日本汽车工业中得到有效的应用。 表2 1 微粒群算法的应用 p s o 应用领域 参考文献 n e u r a ln e t w o r kl e a r n i n ga l g o r i t h m h u m a nt r e m o ra n a l y s i s r u l ee x t r a c t i o ni nf u z z yn e u r a ln e t w o r k b a t t e r yp a c ks t a t e - o f - c h a r g ee s t i m a t i o n c o m p u t e rn u m e r i c a l l yc o n t r o l l e dm i l l i n go p t i m i z a t i o n r e a c t i v ep o w e ra n dv o l t a g ec o n t r o l d i s t r i b u t i o ns t a t ee s t i m a t i o n p o w e rs y s t e ms t a b i l i z e rd e s i g n f a u l ts t a t ep o w e rs u p p l yr e l i a b i l i t ye n h a n c e m e n t d y n a m i cs e c u r i t ya s s e s s m e n t e c o n o m i cd i s p a t c h s h o r t - t e r ml o a df o r e c a s t i n g o p t i m a lo p e r a t i o no fc o g e n e r a t i o n 【4 1 ，4 2 】 4 3 】 4 4 】 【4 5 】 【4 6 】 【4 7 ，4 8 ，4 9 】 【5 0 】 【5 l 】 【5 2 】 【5 3 】 【5 4 ，5 5 【5 6 】 【5 0 2 3 本章小结 本章首先对微粒群优化算法做了详细介绍，包括算法的起源、基本原理及算法的流程 等。其次介绍了微粒群算法的发展状况及展望，并简要介绍了几种典型的微粒群算法的改 进版本以及它们的优缺点。最后对微粒群算法的应用领域做了介绍，列出了相关成熟的具 体应用领域并详细列出了其应用的文献及来源。 第1 0 页 武汉科技大学硕士学位论文 3 1 欧氏微粒群算法提出背景 第三章欧氏微粒群算法 微粒群算法由于其原理简单、易实现、参数少、收敛速度快等优点出色的解决了很多 多维复杂的n p 难问题。但是针对具有极多局部极值区域的优化问题或随着被优化问题解 维数的增加，微粒群算法也常常会陷入局部晟小。其主要原因是微粒群所有粒子具有飞向 自身历史最优位置肌和微粒群全局最优位置段的特点，当当前最优位置处于局部极值点时， 极大多数微粒都聚集在局部极值区域，此时第二章公式( 2 3 ) 中的第二和三项趋于零 4 1 ，致 使微粒速度越来越小，几乎停滞，缺乏微粒的多样性，此时局部搜索能力极强，缺乏全局 搜索能力，很难逃离局部极值区域。因此在这时候应该采取某种策略给微粒施加刺激，使 多数粒子逃离局部极值区域飞向其他位置寻找最优位置，留下适应值最好的一个微粒在原 处进行局部搜索来保证不错过全局最优位置。以此思想为基础本文对p s o 做了改进，新的 改进算法称作欧氏微粒群算法，在以下章节中将介绍其原理和性能，并作出实验进行比较。 3 2 欧氏微粒群算法原理 针对以上背景，本文对s p s o 作了改进，新算法命名为欧氏微粒群算法【5 8 1 ( e p s o ，