（计算机应用技术专业论文）多目标粒子群算法在web服务组合中的应用研究.pdf

河南大学研究生硕士学位论文 摘要 近年来w e bs e r v i c e s 作为一种新技术广受关注。w e bs e r v i c e s 中的接口定义语 言w s d l 和内容传输格式s o a p 已经成为w 3 c 的草案和建议标准。然而，在实际 应用中，单个w e b 服务通常无法满足复杂应用的需要。因此，如何集成单一的w 曲 服务形成功能更强大的w 曲服务组合从而满足不同用户的复杂应用已成为一个新 的研究热点。本文围绕w e b 服务组合相关关键技术并结合多目标粒子群算法展开研 究。本文主要工作如下： l 、提出了一种改进的多目标粒子群算法( i d m p s o ) 。通过对多目标粒子群算法 的分析研究，发现传统的多目标粒子群算法存在效率低、早熟等问题。本文对传统 多目标粒子群算法进行了改进，主要改进包括：p a r e t o 最优解的保留策略和全局最 优粒子的选取。在p a r e t o 最优解的保留方面，本文通过引入辅助容器和临时容器来 实现p a r e t o 最优解的保留，并通过密集距离来删除临时容器中多余的粒子。在全局 最优粒子的选取方面，本文将密集距离和欧式距离结合起来提出一种新的全局最优 粒子的选取方法。 2 、在收敛性和多样性两个方面对改进的算法进行测试，通过三个典型的测试 函数并与不同的算法进行对比，证明算法在收敛性和多样性方面均具有良好的性 能。最后将改进算法所得到的测试函数的p a r e t o 曲线与理论上的p a r e t o 曲线进行比 较，更进一步验证了算法具有良好的性能。 3 、将i d m p s o 算法应用于基于q o s 的w e b 服务组合问题，并与c m p s o 算法 进行比较，发现i d m p s o 算法虽然运行时间比c m s 0 算法的运行时间略长，但是 所得到的解比c m p s o 算法得到的解较优，验证了i d m p s o 算法的可行性和有效性。 关键词：w e b 服务组合；服务质量；多目标粒子群算法；密集距离 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t i nr e c e n ty e a r s ，w e bs e r v i c eh a sb e e nw i d e s p r e a dc o n c e r na san e w t e c h n i q u e t h e i n t e r f a c ed e f i n i t i o n l a n g u a g ew s d la n dc o n t e n td e l i v e r yf o r m a ts o a pi nw e b s e r v i c e sh a sb e c o m eaw 3 cd r a f ta n dp r o p o s e ds t a n d a r d h o w e v e r , as i n g l ew e bs e r v i c e i so f t e nu n a b l et om e e tt h en e e d so fc o m p l e xa p p l i c a t i o ni np r a c t i c a l a p p l i c a t i o n s t h e r e f o r e ，h o wt oi n t e g r a t et h ef o r m a t i o no fas i n g l ew e bs e r v i c em o r ep o w e r f u l p o r t f o l i oo fs e r v i c e st om e e tt h ed i f f e r e n tu s e r so fc o m p l e xa p p l i c a t i o n sh a v eb e e n r e f e r r e dt oa san e wr e s e a r c hh o ts p o t w i t hw e bs e r v i c eg r o w i n gr a p i d l y , i ti sak e y p r o b l e mh o wt os e l e c tw e bs e r v i c ei nc o m p o s i t i n gm u l t i p l es i m p l ew e bs e r v i c e st oa c o m p l e xw e bs e r v i c e t h et h e s i sm a i n l yf o c u s e so ns t u d y i n gk e yt e c h n o l o g i e so fw e b s e r v i c ec o m p o s i t i o nr e l a t e dt o m u l t i - o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n t h em a i n w o r ki n c l u d e s ： f i r s t l y , t h i sp a p e rp r o p o s e s a l l i m p r o v e dm u l t i - o b j e c t i v ep a r t i c l e s w a r m o p t i m i z a t i o n w i t ht h es t u d ya n dr e s e a r c ho nm u l t i o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n , t h el o we f f i c i e n c ya n dt h ee a r l y m a t u r i n go fs i m p l em u l t i - o b j e c t i v ep a r t i c l es w a r n l o p t i m i z a t i o na r ed i s c o v e r e d s ot h i sp a p e ri m p r o v e ss o m ea s p e c t so fm u l t i o b j e c t i v e p a r t i c l es w a r mo p t i m i z a t i o nu s e dt od e a l 、 ，i t l lt h el o we f f i c i e n c ya n dt h ee a r l y - m a t u r i n g o fs i m p l em u l t i - o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n , s u c ha st h er e t e n t i o ns t r a t e g yo f p a r e t oo p t i m a ls o l u t i o na n dt h eg l o b a lo p t i m u ms e l e c t i o no fp a r t i c l e i nr e s p e c to fp a r e t o o p t i m a ls o l u t i o no ft h er e s e r v a t i o n ，t h i sp a p e ri n t r o d u c t i o n sa u x i l i a r yc o n t a i n e ra n d t e m p o r a r yc o n t a i n e rt oa c h i e v et h er e s e r v a t i o no fp a r e t oo p t i m a ls o l u t i o n ，a n dr e m o v e s e x t r ap a r t i c l e si nt h et e m p o r a r yc o n t a i n e rt h r o u g ht h ei n t e n s i v ed i s t a n c e i nr e s p e c to f s e l e c t i o no ft h eg l o b a lb e s tp a r t i c l e ，t h i sp a p e rp r o p o s e san e wm e t h o do fs e l e c t i n gt h e g l o b a lb e s tp a r t i c l et h r o u g ht h ei n t e n s i v ec o m b i n a t i o no fd i s t a n c ea n de u c l i d e a n d i s t a n c e s e c o n d l y , t h i sp a p e rt e s t st h ei m p r o v e dm u l t i - o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n i nt w oa s p e c t so fc o n v e r g e n c ea n dd i v e r s i t y , a n dc o m p a r e st h et e s tr e s u l t sw i t l lo t h e r a l g o r i t h m sw i t ht r e et y p i c a lt e s tf u n c t i o n t h et e s tr e s u l t ss h o wt h a tt h ei m p r o v e d m u l t i - o b j e c t i v ep a r t i c l es w a r ma l g o r i t h mh a v eg o o dp e r f o r m a n c ei nt w oa s p e c t so f 河南大学研究生硕士学位论文第i 页 c o n v e r g e n c ea n dd i v e r s i t y t h i sp a p e rc o m p a r e st h ep a r e t oc u r v eo ft e s t f u n c t i o n s r e c e i v e db yt h ei m p r o v e dm u l t i o b j e c t i v ep a r t i c l es w a r n la l g o r i t h mw i t ht h et h e o r e t i c a l p a r e t oc u r v e f u r t h e r , t h i ss h o w st h a tt h ei m p r o v e da l g o r i t h mh a sg o o dp e r f o r m a n c e t h i r d l y , t h i sp a p e ra p p l i e si d m p s oa l g o r i t h mt o t h ep r o b l e mo fq o s - b a s e dw e b s e r v i c ec o m p o s i t i o n , a n dc o m p a r e sw i t hc m p s oa l g o r i t h m st ot h es p e c i f i cw e bs e r v i c e c o m p o s i t i o n t h ee x p e r i m e n t a lr e s u l t ss h o wt h a ti d m p s oa l g o r i t h mn e e d ss l i g h t l y l o n g e rr u n n i n gt i m et h a nc m p s oa l g o r i t h m ，b u ti tc a l lg e tb e t t e rs o l u t i o n st h a nc m p s o a l g o r i t h m t h i ss h o wt h a tt 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 i d m p s o a l g o r i t h m k e y w o r d s ：w e bs e r v i c ec o m p o s i t i o n ；q u a l i t y o fs e r v i c e ；m u l t i o b j e c t i v ep a r t i c l es w a r m o p t i m i z a t i o n ；i n t e n s i v ed i s t a n c e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学住申请。本人郑重声明：所呈交的学住论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学住或证书而 使用过番勺材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并袁示了谢意。 学位申请人，( 学位论文作者) ：签名：至隆堡旦 御l o 年易7 月牛曰 关于学位论文著作权使甩授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文韵要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和电于文本) 以供公众检索、查阅。、本人授权河i 葑大学出于宣扬、展览学校 学术发展和进行学术交流等。卧的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内睿酌学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：至：隆里金 2 0 【口年6 月 学住论文指导教师釜缉釜! 丑 2 d ( 口年g 月够曰 河南大学研究生硕士学位论文第1 页 1 1 论文课题意义 第1 章绪论 w e b 服务为自包含的、自描述的、模块化的和可以通过i n t e m e t 发布、定位和 调用的应用程序【l 】。它不仅是一种技术，而且还代表了软件产业的新革命，作为一 种新型的分布式计算模型，近年来得到了工业界和学术界的极大关注。然而，在实 际的应用中，单个w e b 服务提供的功能通常都比较单一，无法满足复杂应用的需求。 因此，如果集成单一的w 曲服务形成功能更强大的w 曲服务组合从而满足不同用 户的复杂应用已成为一个新的研究热点。 服务组合是指将现有的一组服务按照一定的业务逻辑进行集成，构建服务执行 流程，从而更好地满足用户的需求。服务组合广义上可以分为手工组合、半自动组 合和自动组合【2 】。在w e b 环境中，服务是经常变化的，手工组合的方式并不能满足 实际的应用需求，而且，完全智能化的自动组合方式是一个非常复杂的过程，因此， 很多关于服务组合的应用和研究工作都侧重于半自动化方式 9 1 。半自动化组合方法 首先由业务人员根据特定的行业背景建立适合具体应用需求的通用服务组合流程 模型。服务组合流程模型由多个服务结点组成，各服务结点仅包含功能需求描述， 并不指定具体的服务调用实例。在w e b 环境下，随着w e b 服务的增多，满足相同 功能需求而具有不同q o s 参数的w e b 服务存在多个，如何从中选择满足各服务结 点功能需求的具体w e b 服务，形成一个可执行的服务链来完成用户的需求就成为 w e b 服务组合中的一个关键问题。目前w e b 服务组合的基本目标是针对不同的应 用，从候选服务集中选择一组w e b 服务，使其q o s 达到p a r e t o 最优。 粒子群算法是一种新兴的群体智能优化技术，是由e b e r h a r t 和k e n n i d y 4 1 于1 9 9 5 年共同提出的一种模仿鸟类群体行为的智能优化方法。由于算法思想简单、容易实 现、具有较高的执行效率且只有少数参数需要调整，因此得到了广泛的应用并在短 期内涌现出了大量的研究成果。目前p s o 算法已广泛应用于函数优化、神经网络训 练、模糊系统控制及其他遗传算法的应用领域。很多学者试图用它去解决组合优化 第2 页河南大学研究生硕士学位论文 问题，并且已经取得了一定的成果。 服务组合问题属于n p c o m p l e t e 问题【5 】o 本文将w r e b 服务选择问题转化为一个 带q o s 约束的多目标w e b 服务组合优化问题，多目标是指在进行w e b 服务组合的 过程中，w e b 服务组合要兼顾执行时间、执行费用、信誉等级和可靠性等一系列目 标要求。利用多目标粒子群算法的智能优化原理，通过同时优化多个目标参数，即 在不同的目标之间取平衡，最终产生一组满足约束条件的最优非劣解集嘲，用户可 以根据特定的需要从中选择最满意的w e b 服务组合流程，同时未被选中的最优非劣 解可以作为备选方案，以便在所选w e b 服务组合流程发生意外时启用。本论文研究 的内容为w e b 服务组合的研究打下了良好的基础，具有广泛的经济价值和社会价 值。 1 2 课题研究现状 2 0 世纪9 0 年代末，随着分布式对象技术和x m l 技术的发展，出现了w e b 服 务( w e bs e r v i c e s ) 技术，基于w e b 服务的分布式计算模式正逐渐成为技术发展的趋 势。w e b 服务吸收了分布式计算、g r i d 计算和x m l 等各种技术的优点，通过采用 w s d l 、u d d i 和s o a p 等基于x m l 的标准和协议，解决了异构分布式计算以及代 码与数据重用等问题，具有高度的互操作性、跨平台性和松耦合性等特点，引起了 世界范围内学术界和工业界的极大兴趣。 w e b 服务组合就是通过合成多个由不同提供者提供的w e b 服务来为用户提供 一个功能更强的系统。如何进行w e b 服务组合成为近年来软件业研究的热点。尤其 是随着w e b 服务的增多，如何自动地根据服务请求进行w e b 服务的动态组合成为 一个迫切需要解决的问题【刁，如何动态地进行w e b 服务组合引起了大家的广泛关注 【8 】 o 在w e b 服务组合方面，学术界和工业界从不同角度对其进行了大量的研究，服 务组合技术主要分为以下几类： 1 基于工作流技术的w e b 服务组合 w e b 服务组合是将多个具有不同功能、完成不同任务的w e b 服务组合起来，用 河南大学研究生硕士学位论文第3 页 来完成一个大型的任务。而传统的工作流技术所要解决的主要问题是：使在多个参 与者之间按照某种预定义的规则传递文档、信息或任务的过程自动进行，从而实现 某个预期的业务目标，或者是促使此目标的实现。因此，w e b 服务组合可以借鉴工 作流技术中的建模方法。 2 基于语义的w e b 服务组合 语义w e b 是对未来w e b 体系结构的一个伟大构想，它的目的是让w e b 上的数 据可以被机器理解和自动化处理，使计算机可以智能地处理和集成这些信息，结合 语义w e b 技术的w e b 服务将是一种更为智能的服务，从而使w e b 提供的服务实现 质的飞跃。 3 基于人工智能动态规划的w e b 服务组合 人工智能动态规划是w e b 服务自动组合的重要工具，当前这方面的研究主要集 中在：情景演算、p d d l 和r u l e - b a s e dp l a n n i n g 等几个方面。文献【9 】在这方面进行 了研究。 w e b 服务组合已经出现了许多方法，其中既有工业化标准，又有许多抽象的服 务建模方法。虽然在w e b 服务组合方面出现了不同层次的自动组合，但是由于w e b 服务处于高度复杂的动态环境中，所以并不是w e b 服务组合的自动化程度越高就意 味着组合技术越好。w e b 服务组合包含了一系列的不确定因素，如w e b 服务自身及 w 曲服务所处的环境。全自动的w e b 服务组合目前还存在一些需要解决的问题【1 0 1 。 目前，基于q o s 的w e b 服务选择问题已成为w e b 服务组合领域的一个重要研 究方向，国内外的研究组织都对其进行了一系列相关的研究并取得了一定的成果。 基于q o s 的服务选择问题主要分为两类：基于q o s 语义的服务选择问题和基于q o s 属性计算的服务选择问题。文献 1 1 ，1 2 主要介绍了基于q o s 语义的服务选择问题； 文献【1 3 ，1 4 】主要介绍了基于q o s 属性计算的服务选择问题。根据本文的需要，我们 在这里主要介绍一下基于q o s 属性计算的服务组合问题。 基于q o s 全局最优的服务组合问题是从一系列的服务组合流程中选择出满足 要求的服务组合流程，这属于组合优化的范畴。解决这类问题主要有两种方法：一 第4 页河南大学研究生硕士学位论文 类是穷尽计算，该类算法将所有的服务组合流程按照一定的规则进行计算并从中选 择出最理想的方案。文献 1 3 】采用的方法属于穷尽算法。另一类是近似算法，该类 算法可以得到满足要求的无限逼近理想方案的方案，但是该类算法所得到的方案并 不一定是问题的最理想方案。文献0 5 采用的方法属于近似算法。但是当组合的规 模很大时，穷举算法的计算量会增大很多，这就表现出了穷举算法的局限性。它需 要在计算出所有可能解的情况下，才能得到最优解。而在组合优化领域，还存在基 于概率的随机搜索算法，从而得出最优解或次优解，多目标粒子群算法就属于这一 类，基于q o s 的w e b 服务组合问题属于n p 难问题，采用穷举计算的组合优化方法 存在扩展性差、计算量大的弊端，相比之下，多目标粒子群算法更适于解决这类问 题。文献 1 6 】基于多目标粒子群算法对w 曲服务组合优化进行了有益的探讨。 文献 1 7 对于w e b 服务组合流程模型中的每个w e b 子服务，将其候选服务集中 满足功能需求的每个服务的q o s 参数进行加权和排序，按照这种方法，依次为w e b 服务组合流程中的每个w e b 子服务选择加权和最大的服务来执行服务结点的功能。 由于该方法对于每一个w e b 子服务的服务实例的选择是相互独立的，所以这种方法 并不能有效解决基于q o s 全局最优的服务组合问题。 文献d 8 将量子理论引入粒子群算法，提出一种基于量子衍生方法的多目标粒 子群算法，并采用p a r e t o 支配关系来更新粒子的个体最优值和全局最优值。通过定 义极大极小距离，并使用该距离方法来裁剪非支配解。并将该算法应用于多维0 1 背包问题及军队任务调度和指派的高级逻辑( a l p ) i n 题。验证了该方法的可行性和 有效性。 文献【1 9 鉴于粒子群优化算法易陷入局部最优的缺点，提出了基于阶段进化策 略的粒子群算法和将粒子群与鱼群混合的优化算法。在基于阶段进化策略的粒子群 算法中，当判断出算法可能陷入局部最优时，适时的按一定比例给一些粒子重新赋 值，从而使算法跳出局部最优，像全局极值靠近。基于粒子群和鱼群混合的优化算 法结合粒子群算法收敛速度快且能够保留每个粒子自身经过的最优状态及鱼群算 法的全局寻优能力，最后通过经典函数的测试，验证了算法具有令人满意的优化性 能。 河南大学研究生硕士学位论文第5 页 文献 2 0 1 为了解决多目标优化问题，提出了一个改进的多目标粒子群算法。该 算法使用了归档技术和s p e a 2 算法中使用的环境选择和配对策略，最后采用标准 的测试函数进行实验，验证了算法能较快的收敛到p a r e t o 最优解，并且p a r e t o 解的 分布比较均匀。 文献1 2 1 提出了一系列解决单目标优化问题和多目标优化问题的进化算法。分 别提出了求解单目标优化、较复杂的约束单目标优化、无约束多目标优化等问题的 进化算法。并通过实验验证了算法的有效性。 文献【2 2 为了求解多目标优化问题，提出了一个改进的多目标粒子群算法。为 了使算法所得到的p a r e t o 解集具有良好的分布性，算法采用强占关系对外部集合进 行更新。同时为了避免算法陷入局部最优解，在算法中加入了自适应变异算子。最 后采用一系列的函数进行实验，验证了算法在收敛性、稳定性和p a r e t o 最优解的分 布性方面均具有良好的性能。 文献【2 3 】根据支配的概念构造远小于原子服务集的新子服务集，最后基于多目 标粒子群优化算法求解由新子服务集构成的服务选择问题，从而获得一组满足约束 的p a r e t o 最优解。最后与g a 算法进行比较，验证了算法能用更短的时间求出更多 高质量的解。 文献【6 为了解决服务聚合中基于q o s 的服务动态选择问题，将基于q o s 的服 务动态选择问题转化为一个带q o s 约束的服务组合问题，并提出了一个多目标优化 算法，该算法能得到一组满足约束条件的p a r e t o 最优解。最后通过实验验证了算法 的有效性。 文献【2 4 通过计算个体间服务质量的海明距离提高了服务组合的质量，通过指 定用户总时间限制和实施优良解保留策略解决了算法运行时间对服务质量的影响 问题。最后证明了算法的有效性。 文献 2 5 1 研究了基于多维q o s 的带偏好和约束的服务组合优化问题，提出了基 于q o s 的全局最优问题模型，并设计了一种遗传算法求解。模拟结果表明遗传算法 适合求解一般的服务组合优化问题。 文献 2 6 在国内外对组合服务质量的研究较少的情况下对组合服务质量进行了 第6 页河南大学研究生硕士学位论文 研究，该文献建立了w e b 服务组合优化模型并将乙醇算法引入w e b 服务组合，提 出了种基于遗传算法的w e b 服务组合优化方法。该算法可以显著的提高组合服务 的质量和组合的效率，并且能够使所提供的w e b 组合服务满足个性化需求。 1 3 本文组织结构 本文主要对w e b 服务组合问题的发展和应用现状进行研究，并对基本的粒子群 算法和多目标进化算法进行了研究，在此基础上，提出了一种改进的多目标粒子群 算法。并选用了几个大部分多目标进化算法常用的测试函数在多样性和收敛性方面 对改进多目标粒子群算法进行测试，验证了所改进算法在收敛性和多样性方面均具 有良好的性能。用改进的多目标粒子群算法求解w e b 服务组合问题的多目标优化模 型，从而得到一组高质量最优解。最后与c m p s o 算法进行比较，验证了算法的有 效性和可行性。 本文内容组织如下： 第1 章：绪论。介绍了本文的研究背景及意义、研究现状及本文的主要工作和 组织结构安排。 第2 章：介绍了粒子群算法的基本理论和算法的流程，并对粒子群算法的重要 改进方法进行了研究。最后对粒子群算法的应用进行了简单的介绍。 第3 章：介绍了多目标优化问题的概念，并对一些经典的多目标优化算法进行 了研究，提出了多目标优化算法改进的方向。 第4 章：对传统的多目标粒子群算法进行改进，并选用三个大部分多目标算法 都采用的测试函数对算法进行测试，并与s p e a 2 、n s g a 2 等算法在收敛性和多样 性方面进行比较，验证了本文所提出的算法在收敛性和多样性方面均具有良好的性 能。并将本文算法所得到的p a r e t o 曲线与理论上的p a r e t o 曲线进行比较，发现本文 算法所得到的p a r e t o 曲线能很好的逼近理论上的p a r e t o 曲线，并且算法所得到的解 分布比较均匀。 第5 章：介绍了服务组合流程的基本模型、q o s 的计算方法和w e b 服务组合的 基于q o s 的多目标优化模型，并将改进后的多目标粒子群算法应用于w e b 服务组 河南大学研究生硕士学位论文第7 页 合问题，最后通过与算法c m p s o 进行比较，验证了算法的有效性和可行性。 总结与展望部分，对全文的内容进行概括总结，提出对未来工作的展望。 第8 页河南大学研究生硕士学位论文 第2 章粒子群算法 粒子群算法从1 9 9 5 年产生至今，由于其概念简单且易于实现得到了相关领域 专家的广泛关注，其应用领域在不断扩大。本章首先对粒子群算法进行简单的介绍， 然后给出基本粒子群算法的原理、算法描述和算法流程图。然后对粒子群算法的重 要改进方法进行了研究。最后对粒子群算法的应用进行了介绍。 2 1 粒子群算法简介 粒子群算法( 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 f i t h m ) 是一种新兴的进化计算方法。 它不同于其它的进化计算方法，是e b e r h a r t 和k e n n e d y 基于对生物的群体行为模拟 于1 9 9 5 年提出来的。p s o 算法源于对鸟群捕食行为的研究，一群鸟在随机搜寻食 物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目 前离食物最近的鸟的周围区域。p s o 算法就是从这种模型中得到启示而产生并用于 解决优化问题。由于其容易理解、易于实现，在许多优化问题中得到了成功的应用。 在粒子群算法中，算法将鸟群运动模型中的栖息地比作所求问题空间中可能解 的位置，通过群体中个体间的信息传递，引导整个群体向可能解的方向移动，在求 解过程中逐步增加发现较优解的可能性。 在粒子群算法中，群体中的鸟被抽象成没有质量和体积的“粒子，通过群体 中的这些“粒子 间的相互协作和信息共享，使群体中每个粒子的运动速度和运动 方向受到粒子自身的最优位置和群体的最优位置的影响，从而有利于群体在复杂的 解空间中进行寻优操作。 p s o 算法简单、易于实现且有深刻的智能背景，既适合科学研究，又适合工程 应用。因此，p s o 算法一经提出，短期内迅速得到了国际演化计算研究领域的认可， 并受到了广泛的关注，在短短的十几年时间里涌现出大量的研究成果，成为计算智 能领域当前的一个研究热点。目前已被广泛应用于多目标优化、模式识别、信号处 理、组合优化等领域，并被列为“国际进化计算会议”的一个讨论专题。 河南大学研究生硕士学位论文第9 页 2 2 基本粒子群算法 粒子群算法实现简单，且能够有效地优化各种函数。从某种程度上说，此算法 介于遗传算法和进化规划之间。此算法和进化规划的相似之处是二者都非常依赖于 随机的过程。此算法和遗传算法的相似之处是此算法中朝局部最优和全局最优的调 整非常类似于遗传算法中的交叉算子。在粒子群算法中，每个个体被称为一个“粒 子 ，而每个粒子都代表着所优化问题的一个潜在的解。 例如，在一个d 维的目标搜索空间中，每个粒子都可以看成是空间内的一个点。 设粒子群由1 1 个粒子构成。n 称为粒子群的规模。设x i = ( x i i , x i 2 ，, x i d ) 为第i 个粒 子( i - 1 ，, - - - - - , n ) 的d 维位置矢量，根据事先设定的适应值函数计算x i 当前的适应值， 即可衡量粒子位置的优劣。v i = ( v i l , v i 2 ，- - , v i d ，v i d ) 为第i 个粒子的飞行速度， p i = ( p i l ，p t 2 ，p i d ，p i d ) 为第i 个粒子迄今为止搜索到的最优位置， p g _ ( p 9 1 ，p 9 2 ，p g d ，p g d ) 为整个粒子群迄今为止搜索到的最优位置。我们可以通过适 应值来衡量粒子位置的优劣，而每个粒子的适应值需要通过适应值计算函数计算出 来。 在每次迭代中，采用以下两个式子来更新粒子的速度和位置： v i d k + 1 = 、，i d l r l d - x i d k ) + c 2 r 2 ( p g d - x i d k ) ( 2 1 ) x i d k + 1 - - - - - x i d k + v i d k + 1( 2 2 ) 其中，i - - 1 ，2 ，n ；d = l ，, - - - - - , d ；k 为迭代次数，r l 和r 2 为 0 ，1 】之间的随机数， 这两个参数主要用来保持群体的多样性。c l 和c 2 为学习因子，这两个参数使粒子具 有自我总结和向群体中的优秀粒子学习的能力，从而使粒子向粒子本身的历史最优 点以及整个粒子群的历史最优点靠近。由于粒子群算法没有实际的机制来控制粒子 速度，所以有必要对粒子的速度进行限制，当速度超过阀值v m a x 时，将其设置为v m 戤， 这个参数非常重要，值太大会导致粒子跳过最好解，太小的话会导致不充分搜索。 此外速度v i 的最小取值为v m i n ，由此可得速度的取值范围为v m i 。v m a x 位置x i 的取值 范围为x m i n x m a x 。 公式2 1 的第二项是“认知”部分，代表了粒子的自我总结。公式2 1 的第三 第10 页河南大学研究生硕士学位论文 项是“社会 部分( s o c i a lp a r t ) ，代表着粒子l 旬的协作。公式2 1 是粒子根据它前一 次的迭代速度、当前位置和自身最好位置与粒子群的最好位置之间的距离来更新速 度。公式2 2 表示粒子将飞向新的位置。 粒子群算法主要遵循了五个基本原则【2 7 】：临近原则、品质原则、多样性反应原 则、定性原则和适应性原则。 2 3 粒子群算法流程 标准粒子群算法的流程如图2 1 所示，文字描述如下： s t e p1 ：初始化粒子群( 群体规模为n ) ，随机生成粒子的初始位置和速度，将每 个粒子的局部最优位置l y r e 。设为其初始位置，并将局部最优位置p b c 吼中的最好值设 为全局最优位置g b , s t 。 s t e p2 ：根据适应度函数，计算每个粒子的适应值。 s t e p3 ：对粒子群中的每一个粒子，将其适应值与其经历过的最好位置p 嘁的 适应值进行比较，如果该适应值优于p b e s t 所对应的适应值，则将其作为该粒子当前 的局部最好位置p b c s t 。 s t e p4 ：对粒子群中的每一个粒子，将其适应值与群体所经过的最好位置g b 。s t 的适应值进行比较，如果该适应值优于g b 。s t 所对应的适应值，则将其作为粒子群的 全局最优位置g t 埒 s t 。 s t e p5 ：根据公式2 1 和公式2 2 调整当前粒子的位置和速度。 s t e p6 ：检查终止条件( 通常为达到最大迭代次数或者得到了足够好的适应值) ， 若上述条件满足，终止迭代。否则返回s t e p 2 。 河南大学研究生硕士学位论文第1 1 页 2 4 粒子群算法的改进 是 由 图2 - 1 粒子群算法流程图( 简化) 2 4 1 带惯性权重的粒子群算法 s h i 和e b e r h a r t l 2 8 1 在1 9 9 8 年的i e e e 国际进化计算学术会议上发表了题为“a m o d i f i e dp a r t i c l es w a r mo p t i m i z e r 的论文，首次引入了惯性权重，改善了基本粒子 群算法的收敛性能。 考虑到在不同的问题中，对粒子群的局部最优能力和全局最优能力的权衡不一 样，s h i 和e b e r h a r t 在速度的更新公式中引入了惯性权重，粒子的速度更新公式如 下所示： v i d k + 1 = v i d 。+ c r ( p i d z i d k ) + e 2 r 2 ( p g d z i d k ) ( 2 3 ) 其位置更新公式与基本粒子群算法的位置更新公式相同，其中称为惯性权 重，起着权衡局部最优能力和全局最优能力的作用。基本粒子群算法是惯性权重为 1 的特殊情况。 惯性权重0 3 表明粒子以前速度得到保留的程度。在这里我们假设粒子的初始速 第12 页河南大学研究生硕士学位论文 度不为零，当c l = c 2 = o 且1 0 1 时，粒子会 加速至v m 戤。当c i = j 壬o 且c 2 ：# 0 时，情况会比较复杂，但文献 3 7 】的实验结果表明， 在这种情况下，= 1 的时候要好一些。 惯性权重0 3 类似于模拟退火中的温度，较大的使得粒子具有较强的全局搜索 能力，而较小的使得粒子具有较强的局部搜索能力。因此，随着迭代的进行，惯 性权重t o 应不断减少，从而使得粒子群算法在初期具有较强的全局搜索能力，而晚 期具有较强的局部收敛能力。为此，可将c o 设定为随着迭代次数而线性减少，惯性 权重的函数形式通常为： = 腿一( o m t a x - - m i n 。k( 2 4 ) ，【m “ 式中m 戤为初始惯性权重，c o m i n 为最终惯性权重，k m 戤为最大迭代次数，k 为当前 迭代次数。 这种方式使得粒子群算法在刚开始的时候倾向于开掘( e x p l o i t a t i o n ) ，而在后期 将逐渐转向于开拓( e x p l o r a t i o n ) ，从而使得在局部区域调整解。这些改进使得粒子群 算法的性能得到很大的提高。 2 4 2 带收缩因子的粒子群算法 c l e r c 提出了带收缩因子的粒子群算法，并通过实验证明了带收缩因子的粒子 群算法能够保证算法收敛。收缩因子) c 是一个关于参数c l 和c 2 的函数，一个简单的 带收缩因子的粒子群算法的速度更新公式定义如下： v i d k + 1 = x v i d k + c m ( p i d z i d k ) + c 2 r 2 ( p g d z i d l ( ) 】 ( 2 5 ) z = j f ，l = c 1 + c 2 ，l 4 ( 2 6 ) 1 2 - 1 一z - 4 1 公式中的1 为4 1 ，故收缩因子z 为0 7 2 9 。与使用惯性权重的粒子群算法相比， 带收缩因子的粒子群算法具有更好的收敛性。但是c l e r c 在实验的早期认为，采用 收缩因子方法时，不需要限制粒子的最大速度。然而，后来的研究发现限制粒子的 最大速度可以有效地提高算法的性能。 河南大学研究生硕士学位论文第13 页 2 4 3 利用遗传思想改进粒子群算法 1 利用选择的方法 在基本粒子群算法中，每个粒子最优位置的确定隐含地包含了选择机制，而文 献 2 9 提出的改进粒子群算法引入了明显的选择机制，其仿真结果表明该算法对某 些测试函数具有优越性。该算法使用的算子为锦标赛选择算子( t o u m a m e ms e l e c t i o n m e t h o d ) ，算法流程为： ( 1 ) 对于种群中的每一个个体，将该个体的适应度与种群中其它个体的适应度 逐一进行比较，当该个体的适应度优于其它某个个体的适应度时，每次赋予该个体 一分。 ( 2 ) 依据上一步所计算出的种群中个体所得的分数将种群中的个体按所得分数 由大至0 小扫 序。 ( 3 ) 选择并复制种群中顶部的一半个体，用其取代种群底部的一半个体，在此 过程中最佳个体的适应度并未改变。 2 借鉴杂交的方法 a n g e l i n e 首次将杂交方法引入到粒子群算法中，提出了杂交粒子群算法。在该 算法中，粒子群中的每一个粒子均被赋予一个由用户决定的杂交概率，该杂交概率 与粒子的适应度没有关系。在算法的每次迭代中，算法将依据前面指定的杂交概率 选择指定数目的粒子，并将其放入杂交池中。池中的每个粒子随机地两两杂交并产 生相同数目的子代，并用子代的粒子来取代父代的粒子进行迭代。 文献 3 0 】表明将杂交的方法引入到了粒子群算法中解决单峰值函数的优化时， 杂交的方法使单峰值函数的收敛性下降。但是在拥有多个局部最小值的函数中，引 入杂交的方法则能显著提升算法的收敛性。 3 借鉴变异的方法 由于标准粒子群算法在优化前期收敛速度快，而在优化后期收敛速度比较慢。 这主要是因为标准粒子群算法难以摆脱局部极值，这就导致标准粒子群算法收敛精 第14 页河南大学研究生硕士学位论文 度比较低。为了解决这一问题，文献 3 1 】将变异的方法引入到标准的粒子群算法中。 在标准粒子群算法中，粒子摆脱局部极值主要有两种途径：粒子在聚集过程 中发现比g b e s t 更优的解。调整粒子的个体极值和全局极值，使所有粒子飞向新的 位置，去搜索新的路径和领域，这就使得发现更优解的概率较大。情况可以通过 调整粒子位置的方法来使粒子摆脱局部极值。针对情况，文献 3 2 】给出了一种使 粒子摆脱局部极值的方法。 2 4 4 二进制离散粒子群优化算法 基本粒子群算法主要用来解决连续函数的优化。由于许多实际工程问题都被描 述为离散的组合优化问题，k e n n e d y 和e b e r h a r t 于1 9 9 7 年提出了一种二进制离散粒 子群优化算法。离散粒子群优化算法在解决离散问题时，虽然其运算结果已经非常 接近全局最优值，但其仍存在局部收敛等缺陷。 由于基本的二进制离散粒子群算法在运动过程中可能由于产生惰性而发生早 熟收敛。杨红孺等口3 1 提出了一种改进的二值离散粒子群优化算法，新算法利用基本 粒子群算法中“粒子依赖自身经验及粒子群全体经验，同时克服自身飞行惰性 的 思想，改进了粒子的更新运动公式，并将离散的二值由0 、1 改为1 、l 。改进的二 值离散粒子群优化算法在c d m a 多用户监测问题上能够有效减小粒子的惰性，避 免了算法的早熟收敛。 2 4 5 小生境粒子群优化算法 b r i t s 等在2 0 0 2 年将小生境技术引入到粒子群优化算法中，提出了小生境粒子 群算法( n i c h ev s o ) 。小生境粒子群