（计算机应用技术专业论文）粒子群优化算法应用研究.pdf

粒子群优化算法应用研究中文摘要 粒子群优化算法应用研究 中文摘要 粒子群优化算法起源于鸟类群体智能，是一种基于群体的新型随机元启发搜索算 法。自1 9 9 5 年提出以来，引起了研究者的广泛关注，成为研究热点。但粒子群优化 算法在更多领域内的应用还处于尝试和拓展阶段，开拓粒子群优化算法的应用领域， 是很有意义的工作。 本文学习了粒子群优化算法在连续优化问题方面的应用，将粒子群优化算法应用 n - 维t o y 模型中进行蛋白质折叠结构预测，提出了一种随机扰动粒子群优化算法， 并与爬山算法、模拟退火算法融合，给出了在f i b o n a c c i 测试序列及真实蛋白质序列 上的测试结果，取得了良好的效果。 本文尝试了粒子群优化算法在离散优化问题上的应用求解二次分配问题。针 对二次分配问题的特点，对标准粒子群优化算法进行改进，与遗传算法、禁忌搜索算 法进行融合，提出了一种求解二次分配问题的混合离散粒子群优化算法，给出了在 q a p l i b 数据上的测试结果，取得了良好的效果。为进一步验证算法的有效性及加速 运行，本文还实现了相应的基于o p e n m p 的并行粒子群优化算法。运行结果表明，并 行算法比串行算法具有更好的性能。 本文工作开拓了粒子群优化算法在两个优化困难问题上的应用，探索了元启发算 法的融合技术。 关键词：粒子群优化算法，元启发融合，2 d 蛋白质折叠，二次分配问题 作者：周洪斌 指导老师：吕强 a b s t r a c t 粒子群优化算法应用研究 a s t u d yo na p p l y i n g 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 a bs t r a c t p a r t i c l es w a m io p t i m i z a t i o n ( p s o ) i san e w s t o c h a s t i c ，p o p u l a t i o n - b a s e dh e u r i s t i cs e a r c h a p p r o a c hi n s p i r e db yb i r d ss w a r mi n t e l l i g e n c e p s oa t t r a c t sw i d ea t t e n t i o n so fr e s e a r c h e r sa n d b e c o m e sar e s e a r c hh o t s p o ts i n c ei t sp r o p o s a lo n19 9 5 a l t h o u g hp s oa l g o r i t h m sh a v eb e e n s u c c e s s f u l l ya p p l i e di nm a n yf i e l d s ，i ti so fg r e a tv a l u et od e v e l o pt h ea p p l i c a t i o nt om o r eb r o a d d o m a i n s t h i sp a p e rf i r s tl e a r n sh o wt oa p p l yp s ot ot h ec o n t i n u o u so p t i m i z a t i o np r o b l e m s ，a n d s t u d i e sh o wt os o l v et h et w o - d i m e n s i o n a lp r o t e i nf o l d i n gp r e d i c t i o np r o b l e mb a s e do nt o y m o d e lb yp s oa l g o r i t h m t h i sp a p e rp u t sf o r w a r das t o c h a s t i cp e r t u r b a t i o np s o a l g o r i t h m , c o m b i n i n gw i t ht h ei d e a sf r o mh i l l - c l i m b i n ga n ds i m u l a t e da n n e a l i n ga l g o r i t h m t h en e w a l g o r i t h ma c h i e v e sg o o dr e s u l t sw h e ni ti sa p p l i e dt op r e d i c tt h eb e s t2 ds t r u c t u r eo fs o m e b e n c h m a r kf i b o n a c c is e q u e n c e sa n dr e a lp r o t e i ns e q u e n c e s t h es e c o n dw o r ko ft h i sp a p e ri st os t u d yh o wt oa p p l yp s oa l g o r i t h mt oad i s c r e t e o p t i m i z a t i o np r o b l e m ，q u a d r a t i ca s s i g n m e n tp r o b l e m ( q a p ) c o n s i d e r i n gt h ep r o p e r t i e so f q a p , t h i sp a p e rp r e s e n t sad i s c r e t ep s oa l g o r i t h mo nt h eb a s i so fp s of r a m e w o r k , i n t e g r a t i n g w i t ht h ei d e a sf r o mg e n e t i ca l g o r i t h ma n dt a b us e a r c ha l g o r i t h m t h en e w a l g o r i t h ma c h i e v e s g o o dr e s u l t sw h e ni ti sa p p l i e dt ob e n c h m a r ko fq a p t of u r t h e re v a l u a t et h ea l g o r i t h ma n d s p e e du pt h ea l g o r i t h m ，t h i sp a p e rd e s i g n sa n di m p l e m e n t sap a r a l l e lv e r s i o nw i t ht h es u p p o r to f o p e n m p , a n dt h ep a r a l l e lc o m p u t i n gr e s u l ts h o w sg r e a tp e r f o r m a n c eo fo u ra l g o r i t h m c o m p a r i n g 、舫mo u rs e r i a l v e r s i o n t h i sp a p e rn o to n l ye x p l o r e sa p p l y i n gp s o a l g o r i t h m st ot w oh a r do p t i m i z a t i o np r o b l e m s , b u ta l s oe x p l o i t st h eh y b r i d i z i n gm e t a - h e u r i s t i ca l g o r i t h m s 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 n , h y b r i d i z i n gm e t a - h e u r i s t i c ，2 dp r o t e i nf o l d i n g ， q u a d r a t i ca s s i g n m e n tp r o b l e m w r i t t e nb yz h o uh o n g b i n s u p e r v i s e db yl uq i a n g i l 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：j 互遂盛e l 期：墅丑聋! ! 旦! 鸯目 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电弓：文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：! 蜀遂塑： 日期：垒幽釜! l 目! 墨旦 导师签名： 粒子群优化算法应用研究第一章绪论 第一章绪论 本章简要介绍了粒子群优化算法的起源及研究意义，说明了本文的主要工作及论 文结构。 1 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 ) 是由美国的k e n n e d y 和 e b e r h a r t 在1 9 9 5 年提出的【1 】。在粒子群优化算法中，每个粒子作为优化问题的一个 可行解，并由目标函数为其确定一个适应值，粒子在搜索空间中以一定的速度飞行。 每个粒子在搜索时，追随自己搜索到的历史最优值和群体历史最优值，在此基础上进 行速度和位置的更新。 p s o 基本模型与遗传算法类似，是一种基于迭代的优化工具。但是在算法实现过 程中没有交叉、变异操作，而是以粒子对解空间中最优粒子的追随进行解空间的搜索。 同遗传算法相比，p s o 的优点在于流程简单，容易实现，算法参数简洁，无需复杂的 调整。因此，粒子群优化算法一提出，立刻引起了进化计算等领域学者们的广泛关注， 在短短几年时间里出现大量的研究成果，成为进化计算领域内的一个研究热点。 粒子群优化算法最早应用于连续函数优化和人工神经网络训练【2 】。随后，p s o 算法在约束优化、数据聚类、模式识别、电力系统等问题中均得到了成功的应用。随 着对p s o 研究地不断深入，学者们提出了多种改进的p s o 算法，广泛应用于函数优 化、集成电路设计、模糊系统控制等多个领域。 当然，p s o 还是一种新兴的智能优化算法，研究粒子群优化算法与其他元启发算 法的融合，进一步拓展其应用领域是值得关注的热点，更是一项非常有意义的工作。 1 2 本文主要工作及论文结构 1 2 1 本文主要工作 学习了粒子群优化算法、模拟退火算法、遗传算法、禁忌搜索算法等常用元启发 算法，研究了粒子群优化算法与其他元启发算法的融合技术，拓展了粒子群优化算法 的应用。 第一章绪论粒子群优化算法应用研究 对蛋白质折叠结构的预测和研究在蛋白质工程中有着极其重要的意义。传统的蛋 白质结构测定方法，如x 射线晶体衍射方法、核磁共振技术的测定速度都比较缓慢， 只能限于较短序列的蛋白质结构测定 3 】。因而，利用计算机的高效计算能力来预测 蛋白质结构已成为当前的研究热点，但其计算量却非常惊人，折叠空间随着蛋白质序 列的长度的增长呈指数级增长。为此，相关学者提出了各种简化模型。s t i l l i n g e r 等提 出的t o y 模型比h p 格点模型更接近真实蛋白质。目前，已有学者采用元启发式算法 应用到t o y 模型中进行蛋白质折叠结构预测。 二次分配问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ，q a p ) 是一个经典的组合优化问题 4 】，目的是寻找n 个设备到n 个位置的最优布局。该问题具有重要的理论与实用价 值，许多实际的问题，如：大学校园中建筑物的布局、医院中科室的安排、键盘布局 问题等都可以转化为q n p 来解决 5 ，6 】。q a p 是一个n p - h a r d 问题 7 】，无法寻找求解 q a v 的多项式时间算法。一般来说，当问题规模n 2 0 时就很难找到最优解。为了实 际可行地解决二次分配问题，人们广泛采用元启发式算法，以便在较短的时间内求得 较优解。 本文对粒子群优化算法进行改进，并分别与爬山算法、模拟退火算法和遗传算法、 禁忌搜索算法进行融合，形成了随机扰动粒子群爬山算法和混合离散粒子群优化算 法，分别用于蛋白质折叠结构预测和求解二次分配问题，拓展了粒子群优化算法的应 用，取得了良好的效果，并探讨了混合离散粒子群优化算法在o p e n m p 上的并行实现 技术。 1 2 2 论文结构 全文共分为五章，各章的内容安排如下： 第一章首先介绍了粒子群优化算法的研究意义，给出了本文主要工作和论文结 构。 第二章详细介绍了标准粒子群优化算法的原理，分析了粒子群优化算法的研究现 状，并简要介绍了与本文相关的其他元启发算法。 第三章采用粒子群优化算法求解连续优化问题应用到二维t o y 模型中进行 蛋白质折叠结构预测。介绍了蛋白质折叠结构预测中的相关知识，其中包括蛋白质结 构功能的关系、蛋白质结构预测问题的发展及其重要性、h p 格点模型以及t o y 模型。 2 粒了群优化算法应用研究第一章绪论 提出了一种随机扰动粒子群优化算法，并与爬山算法融合，应用到二维t o y 模型中进 行蛋白质折叠结构预测，并给出了在f i b o n a c c i 测试序列及真实蛋白质序列上的测试 结果。 第四章针对目前p s 0 算法对离散优化问题研究甚少的情况，尝试了粒子群优化算 法在离散优化问题上的应用求解二次分配问题。对二次分配问题作了详细介绍， 对标准粒子群优化算法进行改进，与遗传算法、禁忌搜索算法进行融合，提出了一种 求解二次分配问题的混合离散粒子群优化算法，并给出了在q a p l i b 数据上的测试结 果。为了进一步验证本章算法的有效性及加速运行，研究了基于o p e n m p 的并行算法 及其实现。 第五章是对本文的总结与展望。 论文结构如图1 1 所示。 l 经典元启发算法介绍 ( 2 1 节) l旺! 、i ，1 1 一上 l 卖优化问题j j 之熙i t o y 模型求解 - i ( 第3 章) i ，一n ， 新型元启发算法p s o l旱行算怯 ( 2 2 节) - - 1 ( 4 3 、4 4 节) q a p 问题求解 离散优化问题求解( 第4 章) r 0 p e n l l p 算法 总结与展望 - ( 4 5 节) ( 第5 章) 图1 1 论文结构图 第二章粒子群优化算法及其相关算法概述粒子群优化算法应用研究 第二章粒子群优化算法及其相关算法概述 元启发算法已在n p h a r d 问题上得到了广泛应用。本章对本文中所用到的经典元 启发算法做了概要介绍，较为详细的介绍了新型元启发算法粒子群优化算法的原 理、应用领域和研究现状，以及本文所用算法与这些算法之间的关系。 2 1 元启发算法概述 g l o v e r 在1 9 8 6 年首先提出了元启发的概念 8 】，指出：元启发就是“高效”遍历 搜索空间的一组抽象策略，它将实例化产生符合这一组策略思想的各种多样的搜索算 法。元启发具有如下的重要特征： ( 1 ) 近似性：元启发算法是近似算法，元启发的目标是更有效地考察搜索空间， 找到最优或近似最优解。 ( 2 ) 随机性：元启发大多引入某种有“启发 的随机性，即使对同一个问题实 例，同一组算法参数，多次运行该算法的返回结果可能会不一样。 ( 3 ) 混合性：元启发往往混合了各种搜索策略和技术，所以，元启发算法包含 从简单局部搜索算法到复杂的学习过程的许多搜索技术。 当前应用非常广泛的元启发算法主要有粒子群优化算法( 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 ) 、模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 、遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、禁忌搜索( t a b us e a r c h ) 算法等。 2 1 1 模拟退火算法 模拟退火算法( s i m u l m e da n n e a l i n g ，s a ) 由k i r k p a t r i c k 提出 9 1 ，在局部搜索中， 模拟固体退火过程，使得解从局部最优达到全局最优。s a 综合了统计物理学和局部 搜索算法的思想。固体退火原理由m e t r o p o l i s 提出，过程如下：先对处在某一温度的 固体升温，使之达到最大温度，在此温度下固体中所有分子获得了充分的自由度，成 为液体；再对液体进行冷却，随着温度的逐渐下降，液体状态的物理分子能重新安排 其位置。退火可保证，在初始温度足够高，冷却速度充分慢时，晶体中所有分子都能 达到基稳态所对应的结晶点阵结构的相应位置，此时整个固体达到基稳态。 4 粒了群优化算法应用研究第二章粒子群优化算法及其相关算法概述 k i r k p a t r i c k 等人从m e t r o p o l i s 的固体退火得到启发，得到了类似固体退火过程的 迭代优化算法，称之为“模拟退火算法 ，详细描述见算法l ： 算法1 模拟退火算法 ( 1 ) 设定内循环次数，在一足够高的初始温度t ( t ) 下，随机选取一个初始态x 。， 计算由( x 。) ； ( 2 ) 内部循环次数设为1 ； ( 3 ) 根据某种准则，产生邻域解x m ； ( 4 ) 计算由( x 州) ，如果巾( x ) r ，则用x 州取代x 。，否则保持x 。不变；内循环次数加1 ； ( 5 ) 判断是否达到预设的内循环次数，如果未达到预定的内循环次数，转到步 骤( 3 ) ；否则，根据降温公式，计算下一步的温度t ( t + 1 ) ，回到步骤( 2 ) ，重复以 上过程，直到由达到某个预定的精度范围。 由于s a 能够有效地解决具有n p 复杂性的问题，避免陷入局部最优解，目前已 在工程中得到了广泛的应用。但在实际应用中要使s a 终止于最优解，必须在算法设 计过程中同时满足下列条件： 1 ) 初始温度足够高 2 ) 热平衡时间足够长 3 ) 终止温度足够低 4 ) 降温过程足够慢 另外，由于s a 会接受性能较差的解，所以其最终解可能比运算过程中产生的最 好解性能要差。因此，需要在s a 运行过程中记录历史最优解。当算法终止时，输出 历史最优解。 2 1 2 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是近几十年发展起来的一种全局优化算法 1 0 】， 它借用了生物遗传学的观点，通过自然选择、交叉、变异等作用机制，实现各个个体 第二章粒子群优化算法及其相关算法概述粒子群优化算法应用研究 的适应性的提高。这一点体现了自然界中“物竞天择、适者生存 进化过程。 遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进 行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的 操作对象是一组个体，即种群。这里每一个个体都对应问题的一个解。从初始种群出 发，采用基于适应值大小的选择策略在当前种群中选择个体，使用交叉和变异来产生 下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。 遗传算法的术语： 染色体( c h r o m o s o m e ) ：遗传物质的基本载体，由多个遗传因子基因组成。 遗传因子( g e n e ) ：d n a 长链结构中占有一定位置的基本遗传单位，也称为基因。 表现型( p h e n o t y p e ) 由染色体决定性状的外部表现。 基因型( g e n o t y p e ) 由染色体决定性状的内部表现。 个体( i n d i v i d u a l ) ：染色体带有特征的实体。 种群( p o p u l a t i o n ) ：染色体带有特征的个体集合。该集合内个体数称为种群大小。 进化( e v o l u t i o n ) ：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品 质不断得到改良的生命现象。 编码( c o d i n g ) ：从表现型到基因型的映射。 解码( d e c o d i n g ) ：从基因型到表现型的映射。 选择( s e l e c t i o n ) ：决定以一定的概率从种群中选择若干个体的操作。 变异( m u t a t i o n ) ：在细胞复制的时候可能以很小的概率产生某些复制差错，从而 使d n a 发生某种变异，产生出新的染色体，这些染色体表现出新的性状。 交叉( c r o s s o v e r ) ：两个染色体的某一相同位置处d n a 被切断，其前后的两串分 别交叉组合形成两个新的染色体。又称基因重组( r e c o m b i n a t i o n ) 。 适应度( f i m e s s ) ：度量某个物种对于生存环境的适应程度。对生存环境适应较高 的物种将获得更多的繁殖机会，而对生存环境适应度较低的物种，则生存机会较少， 甚至会被淘汰。 6 粒了群优化算法应用研究第二章粒子群优化算法及其相关算法概述 遗传算法描述请见算法2 ： 算法2 遗传算法 ( 1 ) 按照问题的特点随机产生一个拥有n 个个体的种群； ( 2 ) 适应度计算：用适应度函数f ( x ) 计算种群中每一个个体的适应度； ( 3 ) 产生新的种群：重复步骤( 4 ) 、( 5 ) 、( 6 ) ，一直到新的种群建立起来为止； ( 4 ) 选择：按照种群中各个个体的适应度选择两个父代个体； ( 5 ) 交叉：以一定的交叉概率交叉两个父代的基因以产生子代； ( 6 ) 变异：以一定的概率对子代进行变异； ( 7 ) 计算子代的适应度，把新产生的子代放到新的种群中去，判断是否满足终 止条件，如果满足终止条件则结束，否则，转到步骤( 3 ) 。 2 1 3 禁忌搜索算法 禁忌搜索( t a b us e a r c h ，t s ) 算法模仿人类的记忆功能，使用禁忌表来封锁刚 搜索过的区域来避免迂回搜索，同时赦免禁忌区域中的一些优良状态，进而保证搜索 的多样性，从而达到全局最优。迄今为止，禁忌搜索算法已经成功应用于组合优化、 生产调度、机器学习等领域【1 1 】。基本禁忌搜索算法描述请见算法3 ： 算法3 禁忌搜索算法 ( 1 ) 给定算法参数，随机产生初始解，置禁忌表为空； ( 2 ) 判断算法终止条件是否满足。如果满足，则结束算法并输出优化结果；否 则，继续以下步骤； ( 3 ) 判断候选解中的最优解是否满足渴望水平。如果满足，更新渴望水平，更 新当前解，转到步骤( 5 ) ，否则转到步骤( 4 ) ； ( 4 ) 选择候选解中不在禁忌表中的最优解作为当前解； ( 5 ) 更新禁忌表； ( 6 ) 转步骤( 2 ) 。 7 第二章粒子群优化算法及其相关算法概述粒子群优化算法应用研究 禁忌搜索算法构成要素： 禁忌表：用来防止搜索过程中出现循环，避免陷入局部最优。通常记录最近接受 的若干次移动，在一定次数之内禁止再次被访问；过了一定次数之后，这些移动可从 禁忌表中退出，可以被重新访问。 渴望水平：在某些特定条件下，不管某个移动是否在禁忌表中，都接受这个移动， 并更新当前解和历史最优解。通常将这种特定条件称为渴望水平或蔑视准则。 2 2 标准粒子群优化算法 2 2 1 标准粒子群优化算法原理 p s o 模拟鸟群的捕食行为。在p s o 中，每个优化问题的解看作是搜索空间中的 一只鸟，我们称之为粒子。粒子的位置代表优化问题在搜索空间中的潜在解，粒子的 速度决定它们飞行的方向和距离，所有的粒子都有一个被优化的函数决定的适应值。 假设在一个d 维的目标搜索空间中，m 个粒子组成一个群落。第i 个粒子的位置表 示为矢量x ( x l ，x 2 ，x d ) ，飞行速度表示为v ( v l ，v 2 ，v d ) 。每个粒子通过跟踪两个“最 好位置 来更新自己，一个是粒子本身目前所找到的最好位置( p b e s t ) ，另一个是目前 整个群体中所有粒子发现的最好位置( g b e s t ) ，g b e s t 是在p b e s t 中的最好值。对于第k 次迭代，每个粒子是按照式( 2 1 ) 、( 2 2 ) 进行变化的。 1 ，争1 = w 宰v 耐k + c l * r a n d o * ( p 肼一x 刍) + c 2 母r a n d ( ) 幸( p 一x 刍) ( 2 1 ) x 譬1 = 砀k + v 箩1 ( 2 2 ) 式( 2 1 ) 、( 2 2 ) 中：i = l ，2 , - - - m 吃第k 次迭代粒子i 飞行速度矢量的第d 维分量；x 乞一第k 次迭代粒子i 位置矢量的第d 维分量；p i d - 粒子i 个体最好位置 p b e s t 的第d 维分量；p g 厂群体最好位置曲e s t 的第d 维分量；c i 、c 厂学 - j 因子；w 一惯性权重，为非负数；啪d ( ) 一随机函数，产生 o ，1 】的随机数。 2 2 2 标准粒子群优化算法构成要素 在标准粒子群优化算法中有3 个参数：惯性权重w 、学习因子c l 和c 2 。 式( 2 1 ) 中如果没有第一部分，即w - - - 0 ，则速度只取决于粒子当前位置和其历 8 粒子群优化算法应用研究第二章粒子群优化算法及其相关算法概述 史最好位置p g e s t 和g b e s t ，速度本身没有记忆性。假设一个粒子位于全局最好位置， 它将保持静止。而其他粒子则飞向它本身最好位置p b e s t 和全局最好位置曲e s t 的加 权中心。在这种条件下，粒子群将收缩到当前的全局最好位置，更像一个局部算法。 在加上第一部分后，粒子有扩展搜索空间的趋势，即第一部分有全局搜索能力。这也 使得w 的作用为针对不同的搜索问题，调整算法全局和局部搜索能力的平衡。研究 发现，w 较大时，算法具有较强的全局搜索能力，w 较小时算法倾向于局部搜索。 一般的做法是将w 从、m 舣随迭代次数的增加线性递减至w m i n ，由如下式子确定： ，= 、m 舣一( 、m 戤- w m i n ) x i t e r i t e r m 瓠，其中：w m 觚、w m i n 分别为w 的最大值和最小值；i t e r 、 i t e r m 舣分别为当前迭代次数和最大迭代次数。目前，大多以带有惯性权重的粒子群优 化算法为研究对象，称之为标准粒子群优化算法，并在此基础上进行分析、扩展。 如果没有第二部分，即c 1 _ o ，则粒子没有认知能力，也就是“只有社会的模 型。在粒子的相互作用下，有能力达到新的搜索空间。它的收敛速度较快，但对复杂 问题，则比较容易陷入局部最优值。 如果没有第三部分，即c 2 = 0 ，则粒子之间缺乏信息交流，没有社会信息共享。因 为个体间没有交互，一个规模为1 1 1 的群体等价于运行了m 个单个粒子，因而得到最 优解的概率非常小。 学习因子c 1 和c 2 使粒子具有自我总结和向群体中优秀个体学习的能力，从而向 群体内或邻域内最优点靠近。c l 和c 2 通常等于2 ，不过在文献中也有其他的取值。但 是一般c l 和c 2 相等，并且范围在0 和4 之间。 9 第二章粒子群优化算法及其相关算法概述粒子群优化算法应用研究 2 2 3 标准粒子群优化算法流程 标准粒子群优化算法描述见算法4 ： 算法4 标准粒子群优化算法 ( 1 ) 初始化所有粒子，根据求解的优化问题，对每个粒子随机给定一个初始位 置和初始速度；每个粒子的p b e s t 设为其初始位置，p b e s t 中的最好值设为g b e s t ； ( 2 ) 根据目标函数，计算出每个粒子的适应值； ( 3 ) 对每个粒子，根据步骤( 2 ) 中计算出的适应值与其经历过的最好位置p b e s t 对应的适应值进行比较，如果优于p b e s t ，则将其作为当前的最好位置p b e s t ； ( 4 ) 对每个粒子，将其适应值p b e s t 与群体所经历过的最好位置g b e s t 进行比 较，如果优于g b e s t ，则用该粒子适应值p b e s t 取代原群体最优适应值动g b e s t ，同时 用该粒子位置取代群体最优粒子位置； ( 5 ) 根据式( 2 1 ) 、( 2 2 ) 更新每个粒子的速度和位置； ( 6 ) 检查终止条件( 达到给定的迭代次数或者满足了足够好的适应值，或者最优 解停滞不再变化) ，若上述条件满足，终止迭代，输出相关结果；否则返回步骤( 2 ) 。 2 2 4 粒子群优化算法与遗传算法的比较 1 、相同点： 粒子群优化算法与遗传算法有相似之处： ( 1 ) 粒子群优化算法和遗传算法都基于“种群 概念，用于表示一组解空间中 的个体集合。它们都随机初始化种群，使用适应度值来评价个体。 ( 2 ) 都具有一定的选择机制，若子代具有更好的适应度值，则子代将替换父代。 ( 3 ) 两种算法在搜索过程中都隐含并行性：对于粒子群优化算法而言，初始解 产生、目标函数适应值计算、粒子飞行、更新自身位置是相互独立的，因此具有天然 的并行性；而遗传算法的初始解产生、个体适应值计算、个体变异操作也可并行进行。 ( 4 ) 都是根据个体的适应值进行搜索，因此不受函数约束条件的限制，如连续 性、可导性等；但它们对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点， l o 粒子群优化算法应用研究第二章粒子群优化算法及其相关算法概述 都无法保证收敛到最优值。 2 、不同点： ( 1 ) 粒子群优化算法在进化过程中同时记忆位置和速度信息，而遗传算法通常 只记忆位置信息。 ( 2 ) 信息通信机制不同：粒子群优化算法的整个搜索更新过程是跟随粒子自身 最优解和全局最优解的过程，而遗传算法中个体通过交叉操作进行通信。由于p s o 算法没有交叉和变异操作，因此原理更简单、参数更少、实现更容易。 2 3 粒子群优化算法的应用领域 p s o 最直接的应用是函数优化问题。大量的实验研究发现 1 2 】，粒子群优化算法 在解决一些典型函数优化问题时，能够取得比遗传算法更好的优化效果。这就说明粒 子群优化算法在解决很多实际问题时具有很好的应用前景，因为许多实际问题都可以 归结为函数优化问题。p s o 还可用于多元函数优化、带约束优化问题【1 3 】。文献 1 4 】 将粒子群优化算法用于求解网络广告资源优化模型，文献 1 5 将p s o 用于新产品组合 投入的应用，均取得了较好的效果。 p s o 是一种非常有潜力的神经网络训练算法，它操作简单，可以方便地调节神经 网络的连接权值和阈值，已被成功地用来解决许多实际问题。如：基于p s o 的神经 网络应用于医疗诊断【1 6 】，实现了对人类肢体颤抖现象的分析，并完成了对正常颤抖 和帕金森氏症的诊断功能。 p s o 被成功地应用于电力系统领域，如使用p s o 对一个电气设备的功率反馈和 电压进行控制【1 7 】，采用一种二进制与实数混合的p s o 算法来决定对连续和离散的控 制变量的控制策略，以得到稳定的电压。 在半导体器件设计方面 1 8 】，需要在给定的搜索空间内根据所期望的器件特性来 得到符合要求的设计参数，而所能利用的器件模拟器通常得到的特性空间是高度非线 性的。用p s o 替换g a 进行了计算，发现p s o 能比g a 更快地找到较高质量的设计 参数。 除了以上领域外，p s o 在多目标优化、自动目标检测、决策调度等方面也取得了 一定的成果。目前，在模糊控制器设置、车间作业调度和图像分割等方面已经有成功 应用的先例。 第二章粒子群优化算法及其相关算法概述 粒子群优化算法应用研究 2 4 粒子群优化算法的研究现状 粒子群优化算法是一种新型的优化搜索方法，自提出到至今，研究者做了大量的 改进工作，主要体现在如下几方面： a n g e l i n e 1 9 借鉴进化计算中的选择概念，将其引入p s o 算法中。通过比较各个 粒子的适应值，淘汰掉适应值差的粒子，而将具有较高适应值的粒子进行复制，以此 来提高算法的收敛性。 文献 2 0 】提出了一种协同p s o 算法，其基本思想是用k 个相互独立的粒子群分 别在d 维的目标搜索空间中的不同维度方向上进行搜索。这种算法比基本的p s o 算 法更易跳出局部极小点，达到较高的收敛精度。 h i g a s h i 2 1 等人提出了变异p s o 算法，基本思路是通过引入变异算子跳出局部极 值点，从而提高算法的全局搜索能力，得到较高的搜索成功率。 文献 2 2 】提出了二次微粒群算法及其参数自适应策略，结果说明二次微粒群算法 采用参数自适应比参数固定时性能有很大提高，说明了这种参数自适应策略的正确性 和有效性。 p s o 是一种新兴的基于群体智能的进化算法，还没有像遗传算法那样具有系统的 分析方法和良好的理论基础，许多问题还有待于进一步研究： ( 1 ) 应用领域的拓展。虽然p s o 已被成功地用于函数优化及神经网络的训练等 领域，但在更多领域的应用还处于研究阶段。开拓p s o 新的应用领域，是很有价值 的工作。如根据不同的优化问题，将p s o 与其它技术相结合，提出相应的算法，是 p s o 当前的研究热点。 ( 2 ) 算法的改进研究。由于实际问题的多样性和复杂性，尽管已出现了许多改 进的p s o ，但远不能满足需要。研究新的改进的p s o 以便能更好地用于实际问题的 求解也是很有意义的工作。 ( 3 ) 算法参数的确定。p s o 中的一些参数，如w 、c l 、0 2 、粒子数目以及迭代次 数等往往依赖于具体问题，依据应用经验，经多次测试来定，并不具有通用性。因此， 如何方便有效地选择算法参数，也是迫切需要研究的问题。 ( 4 ) 算法的基础理论研究。p s o 的数学基础显得相对薄弱，缺乏深刻且具有普 遍意义的理论分析。虽然p s o 的有效性、收敛性等在一些实例和函数的仿真研究中 1 2 粒子群优化算法应用研究第二章粒子群优化算法及其相关算法概述 得到验证，但没能在理论上进行严谨推敲和严格证明。因此，对p s o 的基础理论研 究非常重要。 2 5 多种搜索算法的融合 多种启发式搜索算法往往各具优势和缺点，根据著名的n of r e el u n c h 定理【2 3 】 的推论，不可能有一种搜索算法能够很好的适用所有目标问题。所以，针对某个具体 的目标问题，融合各种搜索算法的思想，或者基于某种搜索算法的主体，嵌入其他算 法的思想，已经成为元启发搜索算法的开发趋势。本文就是以p s o 为基本框架，针 对一个连续型优化问题和一个离散优化问题，研究和探讨嵌入其他优秀启发式搜索算 法。 本文在求解基于t o y 模型的蛋白质折叠结构预测问题时将模拟退火算法与爬山 算法结合，对粒子群优化算法求得的解进行局部寻优。在p s o 中，极有可能在最优 粒子到了最优解附近由于飞行不当而漏过最优解，在产生局部最优解的时候利用爬山 算法进行临近搜索，可以更为有效的搜索到全局最优解。 由于标准p s o 算法对粒子状态及运动规律的描述都是连续的，目前对p s o 算法 的研究主要集中在连续型优化问题的求解，要将其应用于解决组合优化问题，存在着 一定的困难。为此，本文在求解二次分配问题时，将遗传算法的交叉操作引入粒子群 优化算法中，提出了一种混合离散粒子群优化算法。同时，本文采用t a l l i a r d 的 r o - t s 2 4 作为混合离散粒子群优化算法的局部搜索算法，用于解的增强。局部搜索 算法描述见算法5 ： 算法5r o - t s 算法 ( 1 ) s - - g e t s o l u t i o n f r o m p s o0 ： ( 2 ) i n i t i a l i z e t a b u l i s t s ( t l i ，t l 。) ： ( 3 ) 重复下面的步骤，直到满足循环结束条件： ( 4 ) a l l o w e d s e t ( s ) 一 s n ( s ) ls 并不违反禁忌条件，或满足至少一条藐视 准则 ： ( 5 ) s - c h o o s e b e s t o f ( a l l o w e d s e t ) ： ( 6 ) u p d a t e t a b u l i s t a n d a s p i r a t i o n c o n d i t i o n s0 ： 1 3 第三章随机扰动粒子群- 爬山算法在t o y 模型中的应用 粒子群优化算法应用研究 第三章随机扰动粒子群一爬山算法在t o y 模型中的应用 本章介绍了蛋白质折叠结构预测问题、h p 格点模型以及t o y 模型，提出了一种 随机扰动粒子群爬山算法，应用到二维t o y 模型中进行蛋白质折叠结构预测，并给 出了在f i b o n a c c i 测试序列及真实蛋白质序列上的测试结果。 3 1 蛋白质结构预测问题及其研究模型 3 1 1 蛋白质结构预测问题 生物信息学是一门综合学科，包含生物信息的获取、处理、存储、分发、分析和 解释等在内的所有方面，它综合运用数学、计算机科学和生物学的各种工具，来阐明 和理解大量数据所包含的生物学意义。蛋白质结构预测是生物信息学中最重要的课题 之一。蛋白质是组成生物体的重要成分，在生物体的生命活动中起着重要作用，对其 结构以及功能进行研究，对揭开有关生物体生长、发育、衰老、患病的秘密有着很重 要的意义。而蛋白质的结构和功能是统一的，a n f i n s e n 2 5 指出蛋白质的生物功能是 由它们的空间折叠结构决定的，蛋白质只有形成特定的结构才能执行特定的功能。蛋 白质折叠结构的细微变化，将极大地影响蛋白质的生物性质。因而进行蛋白质结构预 测对于理解蛋白质结构与功能的关系，并在此基础上进行突变设计以及基于结构的药 物设计具有重要意义，在医学和生物工程领域具有极大的应用价值。 蛋白质结构预测是指由一个给定的蛋白质序列预测出蛋白质的天然结构，1 9 7 3 年，a n f i n s e n 通过对核糖核酸酶a 的经典研究表明去折叠的蛋白质在体外可以自发 的进行再折叠，仅仅是序列本身已经包括了蛋白质正确折叠的所有信息，并提出蛋白 质折叠的热力学假说：一个蛋白质在正常的生理环境( 溶液、p h 、离子强度、其他离 子或非朊基团有无以及温度等) 中固有的三维结构是这样一种结构，整个系统中的 g i b b s ( 吉布斯：吸收单位，1 g i b b s = 1 0 。1 0 m o l c m 的表面浓度) 自由能最小，即固有构象 完全由分子间相互作用决定。即一个蛋白质的序列决定其三维结构以及蛋白质的天然 结构对应于全局最小自由能。天然结构可以通过x 射线晶体学和核磁共振( n m r ) 来获得，但是非常费时且成本很高。到目前为止，仅有1 序列的三维结构是已知的。 因此，通过计算机的高性能计算来预测蛋白质结构仍是一种可取的方法。 1 4 粒子群优化算法应用研究第三章随机扰动粒了群- 爬山算法在t o y 模型中的应用 到目前为止，研究人员提出了很多高度简化的模型，虽然是高度简化但计算量仍 然是惊人的，据研究，进行蛋白质预测所需要的计算量达到千万亿次级别。最为简化 的是由d i l l 等人提出的h p 格点模型( h pl a t t i c em o d e l ) 【2 6 ，在此模型中，蛋白质 由疏水氨基酸( h y d r o p h o b i c 用h 表示) 和亲水氨基酸( p o l a r ，用p 表示) 组成，相 邻残基之间的角度只能是直角或平角。比h p 格点模型稍微复杂一点的是由s t i l l i n g e r 等提出的t o y 模型( a bo f f - l a t t i c em o d e l ) 【2 7 ，该模型同样是将氨基酸分为亲水和 疏水两类，考虑骨架扭曲势能和非键间相互作用( n o b o n d e di n t e r a c t i o n s ) ，而且相邻残 基之间的夹角是任意的。二者相比较来看，t o y 模型更接近真实蛋白质。 3 1 2t o y 模型 s t i l l i n g e r 于19 9 3 年首先提出t o y 模型。该模型将二十种氨基酸根据疏水性、亲 水性分为两类，分别用a ( h y d r o p h o b i co rn o n - p o l a r ) 和b ( h y d r o p h i l i co rp o l a r ) 来表示， 用单位长的键把a 和b 连成一个没有方向的线性链。任何一个由n 个残基组成的蛋 白质序列( 如图3 1 ) ，对应n - 2 个角度02 0n 1 ，其中0i 的取值范围是【一丌，丌】， 0i - o 时，表示相邻的三个氨基酸在一条直线上。 图3 1 多个连续残基形成的蛋白质序列在二维平面的表示 1 5 第三章随机扰动粒子群- 爬山算法在t o y 模型中的应用 粒子群优化算法应用研究 t o y 模型的能量由骨架弯曲势能( v 1 ) 和任意两个不相邻的残基之间的能量( v 2 ) 组成。前者与残基的极性无关，只和弯