Web服务组合中基于QoS改进型遗传算法.docVIP

Web服务组合中基于QoS改进型遗传算法 　　收稿日期：2007-12-03；修回日期：2008-07-18 　　基金项目：国家科技支撑计划资助项目（2007BAH08B04）; 国家“863”计划资助项目（2006AA102233）;国家博士点基金资助项目（20050611027）；重庆市教委科技项目（KJ081701） 　　 　　作者简介：龚小勇（1970-），男，CCF高级会员，博士研究生，主要研究方向为Web服务、电子商务、服务质量（g_x_y_h_m@）；朱庆生（1958-），男，教授，博导，主要研究方向为软件工程、电子商务、图像处理等；武春岭（1975-），男，硕士，主要研究方向为面向服务的计算和Web服务组合?豹?* 　　 　　（1. 重庆大学 计算机学院，重庆 400044；2. 重庆电子工程职业学院 计算机系，重庆 401331） 　　摘 要：提出了一种在Web服务组合中基于QoS的改进型遗传算法。该算法通过计算个体间服务质量的海明距离提高了服务组合的质量；通过指定用户总时间限制和实施优良解保留策略解决了算法运行时间对服务质量的影响问题。实验结果表明了算法的有效性。 　　关键词：服务质量；Web服务组合；海明距离；遗传算法 　　中图分类号：TP393 　　文献标志码：A 　　文章编号：1001-3695(2008)10-2922-03 　　Improved genetic algorithm based on QoS in Web services composition 　　GONG Xiao-yong1,2,ZHU Qing-sheng1,WU Chun-ling2 　　(1. School of Computer, Chongqing University, Chongqing 400044, China; 2. Dept. of Computer, Chongqing College of Electronic Enginee-ring, Chongqing 401331, China) 　　Abstract:This paper proposed an improved genetic algorithm based on QoS in the Web services composition. The algorithm improved the quality of the services composition by means of calculating Hamming distance of QoS among individuals; solved the problem that algorithm’s executive time impaired the QoS of services composition by prescribing a total time limit and implementing a fine solutions reservation strategy. The experimental results indicate the feasibility of this algorithm. 　　Key words：QoS; Web services composition; Hamming distance; genetic algorithm 　　 　　 　　Web服务作为目前最新颖的分布式计算模型，有力地整合了Internet上的各种资源。越来越多的企业将自己的应用程序作为Web服务发布，相应地，用户对服务的功能和质量要求也越来越高，单个服务很难满足用户的实际需要，因此，服务组合成为必然。服务组合最有挑战性的问题之一就是面向服务质量（QoS）的组合问题[1]。随着Web服务数量的增多，出现了许多服务提供者提供的服务具有相同功能不同的QoS，因此，在服务组合过程中，需要根据用户的QoS要求对Web服务进行选择。目前服务组合的算法主要有穷尽计算法[2]、线性规划法[3]、遗传算法[4]等。文献[4]针对在服务组合中出现的分支、循环、并发等情况，对服务组合的QoS属性计算进行了分析，提出了使用遗传算法进行服务选择和再次选择。但文献[4]存在两方面的问题：a)在计算个体的适应值时，未考虑个体的多样性保持，使最终选择的服务可能不是最优的；b)没有考虑在服务执行过程中，服务再次选择算法本身的执行时间给服务质量带来的影响。为此，本文提出了在Web服务组合中基于QoS的改进型遗传算法。 　　1 服务组合结构及QoS计算 　　Web服务组合的功能可以分成多个子功能，本文称这些子功能为任务（task，简称t，是构成服务