基于蚁群算法的服务组合方法的研究
|
摘要
随着Web服务近年来的蓬勃发展,越来越多稳定易用的Web服务在网络上共享。单个Web服务已经不能满足实际需求,需要将网络上的Web服务组合起来,提供更为强大的服务功能。如何快速、有效地从众多服务中找出最优的服务,己经成为现在迫切需要得到解决的问题。本文在详细分析、研究当前较为流行的BPEL4WS、eFlow、SWORD、SELF-SERV等Web服务组合方法的基础上,发现它们或多或少存在算法复杂、效率不高、并行度低等缺点,进而提出了一种效率和并行度较高的基于蚁群算法的服务组合方法。
论文首先论述了Web服务组合及其关键技术,详细介绍了蚁群算法的基本原理、基本模型与特点。然后,通过对服务组合问题的研究,发现服务组合问题可以转化为联盟生成问题来解决,而蚁群算法在解决联盟生成问题上已经有了广泛的应用,因此本文应用蚁群算法来解决Web服务组合问题。文章从算法模型建立、模型参数定义、信息素的初始值确定、信息素更新策略改进、服务匹配机制建立、算法流程设计等方面来设计和实现基于蚁群算法的服务组合方法。最后,对算法的性能给出了评价,蚁群算法有效地解决了服务组合中算法复杂,效率低等缺点。
With Web service developed in recent years, more and more stable-to-use Web serivices share on the network. But, individual Web service can no longer meets the actual demand, we need together web services in the network to provide a more powerful service functions. However, how quickly and effectively from many services to find the most suitable services, which has been a urgent question need to be resolved. On the basis of detailed analysising and researching Web service combination of methods such as BPEL4WS, eFlow, SWORD, SELF-SERV, this paper finds these methods more and less exist complicated algorithm, inefficient and low degree of parallelism, so brings up a kind of high efficient and high degree of parallelism service composition method based on ant colony algorithm.
First, this paper discusses Web services composition and its key technologies, and detailed introduces the basic principles of the ant colony algorithm, the basic model and the characteristics. Then, by researching of Web service composition method, we find the problem of service composition can be solved by translating into the coalition generation problem. The paper from seting up algorithm model, defining the parameters of the model, determining the initial value of the pheromone, improving the renewal strategy, seting up services matching mechanism, and designing algorithm flow to design and achieve the service composition method based on ant colony algorthm. Finally, the algorithm gives the performance evaluation: the ant colony algorithm effectively solves the complex algorithm, low efficiency of the shortcomings in the services composition.
论文首先论述了Web服务组合及其关键技术,详细介绍了蚁群算法的基本原理、基本模型与特点。然后,通过对服务组合问题的研究,发现服务组合问题可以转化为联盟生成问题来解决,而蚁群算法在解决联盟生成问题上已经有了广泛的应用,因此本文应用蚁群算法来解决Web服务组合问题。文章从算法模型建立、模型参数定义、信息素的初始值确定、信息素更新策略改进、服务匹配机制建立、算法流程设计等方面来设计和实现基于蚁群算法的服务组合方法。最后,对算法的性能给出了评价,蚁群算法有效地解决了服务组合中算法复杂,效率低等缺点。
With Web service developed in recent years, more and more stable-to-use Web serivices share on the network. But, individual Web service can no longer meets the actual demand, we need together web services in the network to provide a more powerful service functions. However, how quickly and effectively from many services to find the most suitable services, which has been a urgent question need to be resolved. On the basis of detailed analysising and researching Web service combination of methods such as BPEL4WS, eFlow, SWORD, SELF-SERV, this paper finds these methods more and less exist complicated algorithm, inefficient and low degree of parallelism, so brings up a kind of high efficient and high degree of parallelism service composition method based on ant colony algorithm.
First, this paper discusses Web services composition and its key technologies, and detailed introduces the basic principles of the ant colony algorithm, the basic model and the characteristics. Then, by researching of Web service composition method, we find the problem of service composition can be solved by translating into the coalition generation problem. The paper from seting up algorithm model, defining the parameters of the model, determining the initial value of the pheromone, improving the renewal strategy, seting up services matching mechanism, and designing algorithm flow to design and achieve the service composition method based on ant colony algorthm. Finally, the algorithm gives the performance evaluation: the ant colony algorithm effectively solves the complex algorithm, low efficiency of the shortcomings in the services composition.
引文
[1] Papazoglou MP,Georgakopoulos D.Service oriented computing.Communications of the ACM,2003,46(10):25-28
[2]蒋建国,夏娜,齐关彬等.一种基于蚁群算法的多任务联盟串行生成算法.电子学报,2005,33(12):2178-2182
[3]胡海涛,李刚,韩燕波.一种面向业务用户的大粒度服务组合方法.计算机学报,2005,28(4):693-703
[4]刘必欣,王玉峰,贾焰等.一种基于角色的分布式动态服务组合方法.软件学报,2005,16(9):1859-1867
[5]廖军,谭浩,刘景德.基于Pi-演算的web服务组合的描述和验证.计算机学报,2005,28(4):635-643
[6] Ponnekami,S.R,Fox,A.SWORD:A Developer Toolkit for Web Service Composition,To appear in The Eleventh World Wide Web Conference(Web Engineering Track),Honolulu,Hawaii,May 7-11,2002
[7] F.casati,S.Ilnicki,L.Jin,and M-C,Shan.Advanced Information Systems Engineering(CAiSE),Stockh’m,Sweden,June,2000
[8] Chandrasekaran,S.,Madden,S.,lonescu,M.:Ninja Paths:An Architecture for Composing Services over Wide Area Networks CS262 Class project writeup,LC Berkeley(2000).URL:http://nnja.cs.berkeley.edu/disVpapers/path,ps.gz,Otc,2002
[9] METEOR-S Flash Demo,http://lsdis.Cs.uga.edu/~rohit/demo/METER-S-6.swf, 2004
[10] http://lsdis.cs.uga.edu/proj/meteor/swp.htm
[11]李景山,廖华明,侯紫峰等.普及计算中基于接口语义描述的动态服务组合方法.计算机研究与发展,2004,41(7):1124-1134
[12]韩永国,孙世新.动态服务组合构造与最优组合服务算法研究.计算机科学,2005,32(12):104-105
[13]柴晓路.Web服务架构与开放互操作技术.北京:清华大学出版社,2002,120-212
[14] J Casillas,O Cordon,F Herrera. Learning Fuzzy Rules Using Ant ColonyOptimization Algorithms.Proc.ANTS2000-Form Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms,2000,13-21
[15] The Workflow Reference Model.Workflow Management Coalition,2001
[16]廖渊,唐磊,李明书.一种基于QoS的服务构件组合方法.计算机学报,2005,28(4):627-634
[17]杨胜文,史美林.一种支持QoS约束的Web服务发现模型.计算机学报,2005
[18]范语顺.工作流管理技术基础—实现企业业务过程重组、过程管理与过程自动化的核心技术.清华大学出版社,2001
[19]庄昌文.基于协同工作方式的一种蚁群布线系统.半导体学报,1999,20 (5):400-406
[20]叶志伟,郑肇葆.蚁群算法中参数α、β、ρ设置的研究,武汉大学学报信息科学版,2004,29(7):597-601
[21]李曼,王大治,杜小勇等.基于领域本体的web服务动态组合.计算机学报,2005,28(4):644-650
[22]周根春,曹健,张申生等.基于约束Agent的面向服务性能的服务复合方案.计算机集成制造系统,2005,11(8):1184-1190
[23]何清华,肖人彬,师汉民.蚂蚁算法在机构同构判定中的实现[J].模式识别与人工智能,2001,14(4):406-412
[24] Dorigo,M.,Gambardella,L.M.Ant colony system:a cooperative learning approach to the traveling salesman problem.IEEE Transactions on Evolutionary Computing,1997,1(1):53-56
[25] Gambardella,L.M.,Dorigo,M.Ant-Q:a reinforcement learning approach to the traveling salesman problem.In:Prieditis,A.Russell,S.,eds.Proc eedings of the 12th International Conference on Machine Learning.Tahoe,CA:M organ Kaufman 1995,252-260
[26]庄昌文,范明钮,李春辉等.基于协同工作方式的一种蚁群布线系统.半导体学报,1999,20(5):400-406
[27]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005
[28]姜长元.蚁群算法的理论及其应用.计算机时代,2004,6:1-3
[29]罗军红,韩洪江等.基于Web Service的多层分布式体系结构.合肥工业大学学报(自然科学版),2004,27(1),18-22
[30] M Dorigo,V Maniezzo,A Colorni. The ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man,and Cybernetics-Part B, 1996,26(1):29~41
[31] Dorigo M,et a1.Guest editorial: special section on ant colony optimization [J].IEEE Transactions on Evolutionary Computation,2002,6(4):3l7~3l9
[32]彭喜元,彭宇,戴毓丰.群智能理论及应用.电子学报,2003,31(12A):1982-1988
[33] J Casillas,et al.Learning Cooperative Fuzzy Rules Using ant Colony Optimization Algorithms.Technical RePort-00119,Spain:Department of Computer Science and Artificial lntelligence,University of Granada,2000
[34]段海滨,王道波,于秀芬.蚁群算法的研究进展评述.自然科学史,2006,28(2):101-105
[35]岳昆,王晓玲,周傲英.Web服务核心支撑技术:研究综述.软件学报,2004,15(3):428-442
[36] Dorigo,M.,Maniezzo,V.,Colorni,A.Ant system:optimization by a colony of cooperating agents.IEEE Transactions on SMC,1996,26(1):8-41
[37]顾军华.基于蚂蚁算法QoS组播路由问题求解.河北工业大学学报,2002,31 (4):19-24
[38]张徐亮,张晋斌.基于协同学习的蚁群电缆敷设系统.计算机工程与应用,2000,5:181-182
[39] Dorigo,M.,Luca,M.A study of some properties of Ant-Q.Technical Report, IRIDIA Universit Librede Bruxelles,1996
[40]沈洁,秦玲.蚁群算法求解连续空间优化问题的一种方法.软件学报,2002,13(12)
[41] Aphrodite Tsalgatidou,Thomi Pilioura.An overview of standards and related technology in web services.Distributed and Parallel Databases,2002,12:135-162
[42] Sivashanmugam K,Miller J,Sheth A,et a1.Framework for semantic web process composition , semantic web services and theirrole in enterprise application integration and Ecommerce.Intemationa1 Jouma1 of Electronic Commerce,2004,9(2):71-106
[43]侯立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用.上海交通大学学报,2001,35(6):930-933
[44]张素兵,刘泽民.基于蚂蚁算法的分级QoS路由调度方法.北京邮电大学学报,2000,23(4):11-15
[45]Michael Stal.Web services:Beyond component-based computing.Communications of the ACM,2002,45(10):71-76
[46] F.curbera.business process execution language for web services
[47] Shen Jiquan , HuangFu Caihong . An Intelligent Service Composition Algorithm.Conference on Information Technology and Environmental System Sciences 2008.2008,Volum 2
[48]胡建强,邹鹏,王怀民等.Web服务描述语言QWSDL和服务匹配模型研究.计算机学报,2005,28(4):504-513
[2]蒋建国,夏娜,齐关彬等.一种基于蚁群算法的多任务联盟串行生成算法.电子学报,2005,33(12):2178-2182
[3]胡海涛,李刚,韩燕波.一种面向业务用户的大粒度服务组合方法.计算机学报,2005,28(4):693-703
[4]刘必欣,王玉峰,贾焰等.一种基于角色的分布式动态服务组合方法.软件学报,2005,16(9):1859-1867
[5]廖军,谭浩,刘景德.基于Pi-演算的web服务组合的描述和验证.计算机学报,2005,28(4):635-643
[6] Ponnekami,S.R,Fox,A.SWORD:A Developer Toolkit for Web Service Composition,To appear in The Eleventh World Wide Web Conference(Web Engineering Track),Honolulu,Hawaii,May 7-11,2002
[7] F.casati,S.Ilnicki,L.Jin,and M-C,Shan.Advanced Information Systems Engineering(CAiSE),Stockh’m,Sweden,June,2000
[8] Chandrasekaran,S.,Madden,S.,lonescu,M.:Ninja Paths:An Architecture for Composing Services over Wide Area Networks CS262 Class project writeup,LC Berkeley(2000).URL:http://nnja.cs.berkeley.edu/disVpapers/path,ps.gz,Otc,2002
[9] METEOR-S Flash Demo,http://lsdis.Cs.uga.edu/~rohit/demo/METER-S-6.swf, 2004
[10] http://lsdis.cs.uga.edu/proj/meteor/swp.htm
[11]李景山,廖华明,侯紫峰等.普及计算中基于接口语义描述的动态服务组合方法.计算机研究与发展,2004,41(7):1124-1134
[12]韩永国,孙世新.动态服务组合构造与最优组合服务算法研究.计算机科学,2005,32(12):104-105
[13]柴晓路.Web服务架构与开放互操作技术.北京:清华大学出版社,2002,120-212
[14] J Casillas,O Cordon,F Herrera. Learning Fuzzy Rules Using Ant ColonyOptimization Algorithms.Proc.ANTS2000-Form Ant Colonies to Artificial Ants: Second International Workshop on Ant Algorithms,2000,13-21
[15] The Workflow Reference Model.Workflow Management Coalition,2001
[16]廖渊,唐磊,李明书.一种基于QoS的服务构件组合方法.计算机学报,2005,28(4):627-634
[17]杨胜文,史美林.一种支持QoS约束的Web服务发现模型.计算机学报,2005
[18]范语顺.工作流管理技术基础—实现企业业务过程重组、过程管理与过程自动化的核心技术.清华大学出版社,2001
[19]庄昌文.基于协同工作方式的一种蚁群布线系统.半导体学报,1999,20 (5):400-406
[20]叶志伟,郑肇葆.蚁群算法中参数α、β、ρ设置的研究,武汉大学学报信息科学版,2004,29(7):597-601
[21]李曼,王大治,杜小勇等.基于领域本体的web服务动态组合.计算机学报,2005,28(4):644-650
[22]周根春,曹健,张申生等.基于约束Agent的面向服务性能的服务复合方案.计算机集成制造系统,2005,11(8):1184-1190
[23]何清华,肖人彬,师汉民.蚂蚁算法在机构同构判定中的实现[J].模式识别与人工智能,2001,14(4):406-412
[24] Dorigo,M.,Gambardella,L.M.Ant colony system:a cooperative learning approach to the traveling salesman problem.IEEE Transactions on Evolutionary Computing,1997,1(1):53-56
[25] Gambardella,L.M.,Dorigo,M.Ant-Q:a reinforcement learning approach to the traveling salesman problem.In:Prieditis,A.Russell,S.,eds.Proc eedings of the 12th International Conference on Machine Learning.Tahoe,CA:M organ Kaufman 1995,252-260
[26]庄昌文,范明钮,李春辉等.基于协同工作方式的一种蚁群布线系统.半导体学报,1999,20(5):400-406
[27]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005
[28]姜长元.蚁群算法的理论及其应用.计算机时代,2004,6:1-3
[29]罗军红,韩洪江等.基于Web Service的多层分布式体系结构.合肥工业大学学报(自然科学版),2004,27(1),18-22
[30] M Dorigo,V Maniezzo,A Colorni. The ant system: optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man,and Cybernetics-Part B, 1996,26(1):29~41
[31] Dorigo M,et a1.Guest editorial: special section on ant colony optimization [J].IEEE Transactions on Evolutionary Computation,2002,6(4):3l7~3l9
[32]彭喜元,彭宇,戴毓丰.群智能理论及应用.电子学报,2003,31(12A):1982-1988
[33] J Casillas,et al.Learning Cooperative Fuzzy Rules Using ant Colony Optimization Algorithms.Technical RePort-00119,Spain:Department of Computer Science and Artificial lntelligence,University of Granada,2000
[34]段海滨,王道波,于秀芬.蚁群算法的研究进展评述.自然科学史,2006,28(2):101-105
[35]岳昆,王晓玲,周傲英.Web服务核心支撑技术:研究综述.软件学报,2004,15(3):428-442
[36] Dorigo,M.,Maniezzo,V.,Colorni,A.Ant system:optimization by a colony of cooperating agents.IEEE Transactions on SMC,1996,26(1):8-41
[37]顾军华.基于蚂蚁算法QoS组播路由问题求解.河北工业大学学报,2002,31 (4):19-24
[38]张徐亮,张晋斌.基于协同学习的蚁群电缆敷设系统.计算机工程与应用,2000,5:181-182
[39] Dorigo,M.,Luca,M.A study of some properties of Ant-Q.Technical Report, IRIDIA Universit Librede Bruxelles,1996
[40]沈洁,秦玲.蚁群算法求解连续空间优化问题的一种方法.软件学报,2002,13(12)
[41] Aphrodite Tsalgatidou,Thomi Pilioura.An overview of standards and related technology in web services.Distributed and Parallel Databases,2002,12:135-162
[42] Sivashanmugam K,Miller J,Sheth A,et a1.Framework for semantic web process composition , semantic web services and theirrole in enterprise application integration and Ecommerce.Intemationa1 Jouma1 of Electronic Commerce,2004,9(2):71-106
[43]侯立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用.上海交通大学学报,2001,35(6):930-933
[44]张素兵,刘泽民.基于蚂蚁算法的分级QoS路由调度方法.北京邮电大学学报,2000,23(4):11-15
[45]Michael Stal.Web services:Beyond component-based computing.Communications of the ACM,2002,45(10):71-76
[46] F.curbera.business process execution language for web services
[47] Shen Jiquan , HuangFu Caihong . An Intelligent Service Composition Algorithm.Conference on Information Technology and Environmental System Sciences 2008.2008,Volum 2
[48]胡建强,邹鹏,王怀民等.Web服务描述语言QWSDL和服务匹配模型研究.计算机学报,2005,28(4):504-513