求解Web服务组合QoS优化的多属性决策及自适应遗传算法
|
摘要
随着面向服务计算(Service-oriented Computing,SOC)的不断发展,基于服务质量(Quality of Service,QoS)的Web服务组合研究成为了必然趋势。鉴于QoS属性的多维性及相互矛盾性,提出将基于QoS的Web服务组合优化问题转化为多属性决策问题进行求解。采用折中系数对每个组合服务实例到正负理想点的距离进行累加求和,最终得到一组最优服务排序结果,用户可以根据自身偏好进行选择。传统的多属性决策方法无法有效地处理大规模的组合服务搜索空间,因此,为了有效地解决Web服务组合优化这一NP难题,提出一种结合多属性决策方法和自适应遗传算法的新型优化算法来解决该问题。实验采用真实的QoS综合服务数据集进行验证,实验结果表明,该方法能够在较短时间内找到全局近似最优解,且解集的排序结果接近于实际的最优服务排序。同时,该方法对于解决大规模的Web服务组合优化问题具有良好的可伸缩性。
With the increasing of service-oriented computing,the research on Web service composition based on quality of service(QoS)becomes an inevitable trend.With respect of the multi-dimensional nature and mutual contradiction,this paper transformed the optimization of Web service composition based on QoS into the problem of multi-attribute decision making to resolve it.The distances of each solution to the positive ideal solution(PIS)and the negative ideal solution(NIS)were summed up by means of a compromise coefficient.Finally,a set of ranked Web services were provided to users for a flexible choice.The traditional multi-attribute decision making method can not effectively solve the large-scale search space of Web service composition.Therefore,in order to solve the NP-hard problem of Web service composition optimization better,this paper developed an approach combining the multi-attribute decision making and adaptive genetic algorithm(MADMAGA).The experiments were conducted on a real and comprehensive QoS dataset.The experimental results indicate that the method can find the globally optimal solution in a short period of time.The ranking result of solutions is close to the true sort.Moreover,the proposed method has better scalability for solving the large-scale problem of Web service composition optimization.
With the increasing of service-oriented computing,the research on Web service composition based on quality of service(QoS)becomes an inevitable trend.With respect of the multi-dimensional nature and mutual contradiction,this paper transformed the optimization of Web service composition based on QoS into the problem of multi-attribute decision making to resolve it.The distances of each solution to the positive ideal solution(PIS)and the negative ideal solution(NIS)were summed up by means of a compromise coefficient.Finally,a set of ranked Web services were provided to users for a flexible choice.The traditional multi-attribute decision making method can not effectively solve the large-scale search space of Web service composition.Therefore,in order to solve the NP-hard problem of Web service composition optimization better,this paper developed an approach combining the multi-attribute decision making and adaptive genetic algorithm(MADMAGA).The experiments were conducted on a real and comprehensive QoS dataset.The experimental results indicate that the method can find the globally optimal solution in a short period of time.The ranking result of solutions is close to the true sort.Moreover,the proposed method has better scalability for solving the large-scale problem of Web service composition optimization.
引文
[1] XU L,LI Y H,CHEN L,et al.A Testing Method for Web Services Focusing on User Requirements[J].Chinese Journal of Computers,2014,37(3):512-521.(in Chinese)许蕾,李言辉,陈林,等.一种面向用户需求的Web服务测试方法[J].计算机学报,2014,37(3):512-521.
[2] WU Y P,BAO W D,ZHANG W M,et al.Web Service Composition Systems Survey[J].Computer Science,2011,38(9):1-4.(in Chinese)武云鹏,包卫东,张维明,等.Web服务组合系统研究综述[J].计算机科学,2011,38(9):1-4.
[3] WANG P W,DING Z J,JIANG C J,et al.Constraint-Aware Approach to Web Service Composition[J].IEEE Transactions on Systems Man&Cybernetics Systems,2017,44(6):770-784.
[4] ROUACHED M,SALLAY H.A semantic QoS-aware web services composition framework[J].International Journal of Business Information Systems,2017,17(1):94.
[5] JATOTH C,GANGADHARAN G R,BUYYA R.Computational Intelligence based QoS-aware Web Service Composition:A Systematic Literature Review[J].IEEE Transactions on Services Computing,2017,PP(99):1.
[6] BENSLIMANE S M,HUCHARD M,et al.QoS-aware optimal and automated semantic web service composition with user’s constraints[J].Service Oriented Computing&Applications,2017,11(2):1-19.
[7] LI J,ZHAO Y,LIU M,et al.An adaptive heuristic approach for distributed QoS-based service composition[C]∥ISCC’10Proceedings of the IEEE Symposium on Computer and Communications.2010:687-694.
[8] ZHANG K,GAO H H,ZHU Y H,et al.QoS Dynamic Web Services Composition Method Based on Improved Simulated Annealing Algorithm[J].Journal of Applied Sciences,2017,35(5):570-584.(in Chinese)张康,高洪皓,朱永华,等.一种基于改进模拟退火算法的QoS动态服务组合方法[J].应用科学学报,2017,35(5):570-584.
[9] WANG L,ZHAO S S.Research on the Two-stage Heuristic Algorithm Based Web Service Composition Optimization[J].Electronic Technology,2012(10):19-24.(in Chinese)王雷,赵山山.基于两阶段启发式算法的Web服务组合优化[J].电子技术,2012(10):19-24.
[10]LI J,QIAO R,LIU Z Z.Solution of Web Service Composition Scheduling Problem Combining with Game Theory and Multiobjective MILP[J].Computer Engineering,2016,42(1):11-17.(in Chinese)李靖,乔蕊,刘志中.结合对策论与多目标MILP的Web服务组合调度问题求解[J].计算机工程,2016,42(1):11-17.
[11]WANG P,CHAO K M,LO C C.On optimal decision for QoS-aware composite service selection[J].Expert Systems with Applications,2010,9(6):440-449.
[12]LUO Y S,YANG K,TANG Q,et al.A multi-criteria networkaware service composition algorithm in wireless environments[J].Computer Communications,2012,35(15):1882-1892.
[13]MARDUKHI F,NEMATBAKHSH N,ZAMANIFAR K,et al.QoS decomposition for service composition using genetic algorithm[J].Applied Soft Computing,2013,13(7):3409-3421.
[14]ANGARITA R,RUKOZ M,CARDINALE Y.Modeling dynamic recovery strategy for composite web services execution[J].World Wide Web-internet&Web Information Systems,2016,19(1):1-21.
[15]GAO H,YAN J,MU Y.Trust-oriented QoS-aware composite service selection based on genetic algorithms[J].Concurrency&Computation Practice&Experience,2014,26(2):500-515.
[16]WU Q L,ZHOU T H.Research on Quality of Service-based Dynamic Web Service Composition Method[J].Computer Application and Software,2016,33(5):20-23.(in Chinese)吴青林,周天宏.基于服务质量的动态Web服务组合方法研究[J].计算机应用与软件,2016,33(5):20-23.
[17]ZHANG Y P,JING Z H,ZHANG Y W,et al.Dynamic Web Service Composition Based on Discrete Particle Swarm Optimization[J].Computer Science,2015,42(6):71-75.(in Chinese)张燕平,荆紫慧,张以文,等.基于离散粒子群算法的动态Web服务组合[J].计算机科学,2015,42(6):71-75.
[18]WANG L,SHEN J,LUO J.Facilitating an ant colony algorithm for multi-objective data-intensive service provision[J].Journal of Computer&System Sciences,2015,81(4):734-746.
[19]TRAN V X,TSUJI H,MASUDA R.A new QoS ontology and its QoS-based ranking algorithm for Web services[J].Simulation Modelling Practice&Theory,2009,17(8):1378-1398.
[20]FANG X R.Study on Filter Algorithm of QoS-Based Fuzzy Multi-Attribute Web Service Composition[J].Applied Mechanics&Materials,2012,182-183:2131-2135.
[21]YANG J,LI D F,LAI L B.Composite Service Multi-attribute Selection Method Based on Message Negotiation Under the Web Service Environment[J].Operations Research and Management Science,2015(3):134-141.(in Chinese)杨洁,李登峰,赖礼邦.Web服务环境下基于信息协商的组合服务多属性选择方法[J].运筹与管理,2015(3):134-141.
[22]WANG L,SHEN J,LUO J.Facilitating an ant colony algorithm for multi-objective data-intensive service provision[J].Journal of Computer&System Sciences,2015,81(4):734-746.
[23]LIAO J,LIU Y,WANG J,et al.Lightweight approach for multiobjective web service composition[J].IET Software,2016,10(4):116-124.
[24]SILVA A S D,MEI Y,MA H,et al.Fragment-based genetic programming for fully automated multi-objective web service composition[C]∥The Genetic and Evolutionary Computation Conference.2017:353-360.
[25]SUN S X.A decomposition-based approach for service composition with global QoS guarantees[J].Information Sciences,2012,199(15):138-153.
[26]WANG T C,LEE H D.Developing a fuzzy TOPSIS approach based on subjective weights and objective weights[J].Expert Systems with Applications,2009,36(5):8980-8985.
[27]LAUMANNS M,THIELE L,DEB K,et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation,2014,10(3):263-282.
[28]AL-MASRI E,MAHMOUD Q H.Investigating Web Services on the World Wide Web[C]∥International Conference on World Wide Web,WWW 2008,Beijing,China,April.DBLP,2008:795-804.
[29]WANG H.Robust Control of the Output Probability Density Functions for Multivariable Stochastic Systems[J].IEEE Transactions on Automatic Control,1999,44(11):2103-2107.
[2] WU Y P,BAO W D,ZHANG W M,et al.Web Service Composition Systems Survey[J].Computer Science,2011,38(9):1-4.(in Chinese)武云鹏,包卫东,张维明,等.Web服务组合系统研究综述[J].计算机科学,2011,38(9):1-4.
[3] WANG P W,DING Z J,JIANG C J,et al.Constraint-Aware Approach to Web Service Composition[J].IEEE Transactions on Systems Man&Cybernetics Systems,2017,44(6):770-784.
[4] ROUACHED M,SALLAY H.A semantic QoS-aware web services composition framework[J].International Journal of Business Information Systems,2017,17(1):94.
[5] JATOTH C,GANGADHARAN G R,BUYYA R.Computational Intelligence based QoS-aware Web Service Composition:A Systematic Literature Review[J].IEEE Transactions on Services Computing,2017,PP(99):1.
[6] BENSLIMANE S M,HUCHARD M,et al.QoS-aware optimal and automated semantic web service composition with user’s constraints[J].Service Oriented Computing&Applications,2017,11(2):1-19.
[7] LI J,ZHAO Y,LIU M,et al.An adaptive heuristic approach for distributed QoS-based service composition[C]∥ISCC’10Proceedings of the IEEE Symposium on Computer and Communications.2010:687-694.
[8] ZHANG K,GAO H H,ZHU Y H,et al.QoS Dynamic Web Services Composition Method Based on Improved Simulated Annealing Algorithm[J].Journal of Applied Sciences,2017,35(5):570-584.(in Chinese)张康,高洪皓,朱永华,等.一种基于改进模拟退火算法的QoS动态服务组合方法[J].应用科学学报,2017,35(5):570-584.
[9] WANG L,ZHAO S S.Research on the Two-stage Heuristic Algorithm Based Web Service Composition Optimization[J].Electronic Technology,2012(10):19-24.(in Chinese)王雷,赵山山.基于两阶段启发式算法的Web服务组合优化[J].电子技术,2012(10):19-24.
[10]LI J,QIAO R,LIU Z Z.Solution of Web Service Composition Scheduling Problem Combining with Game Theory and Multiobjective MILP[J].Computer Engineering,2016,42(1):11-17.(in Chinese)李靖,乔蕊,刘志中.结合对策论与多目标MILP的Web服务组合调度问题求解[J].计算机工程,2016,42(1):11-17.
[11]WANG P,CHAO K M,LO C C.On optimal decision for QoS-aware composite service selection[J].Expert Systems with Applications,2010,9(6):440-449.
[12]LUO Y S,YANG K,TANG Q,et al.A multi-criteria networkaware service composition algorithm in wireless environments[J].Computer Communications,2012,35(15):1882-1892.
[13]MARDUKHI F,NEMATBAKHSH N,ZAMANIFAR K,et al.QoS decomposition for service composition using genetic algorithm[J].Applied Soft Computing,2013,13(7):3409-3421.
[14]ANGARITA R,RUKOZ M,CARDINALE Y.Modeling dynamic recovery strategy for composite web services execution[J].World Wide Web-internet&Web Information Systems,2016,19(1):1-21.
[15]GAO H,YAN J,MU Y.Trust-oriented QoS-aware composite service selection based on genetic algorithms[J].Concurrency&Computation Practice&Experience,2014,26(2):500-515.
[16]WU Q L,ZHOU T H.Research on Quality of Service-based Dynamic Web Service Composition Method[J].Computer Application and Software,2016,33(5):20-23.(in Chinese)吴青林,周天宏.基于服务质量的动态Web服务组合方法研究[J].计算机应用与软件,2016,33(5):20-23.
[17]ZHANG Y P,JING Z H,ZHANG Y W,et al.Dynamic Web Service Composition Based on Discrete Particle Swarm Optimization[J].Computer Science,2015,42(6):71-75.(in Chinese)张燕平,荆紫慧,张以文,等.基于离散粒子群算法的动态Web服务组合[J].计算机科学,2015,42(6):71-75.
[18]WANG L,SHEN J,LUO J.Facilitating an ant colony algorithm for multi-objective data-intensive service provision[J].Journal of Computer&System Sciences,2015,81(4):734-746.
[19]TRAN V X,TSUJI H,MASUDA R.A new QoS ontology and its QoS-based ranking algorithm for Web services[J].Simulation Modelling Practice&Theory,2009,17(8):1378-1398.
[20]FANG X R.Study on Filter Algorithm of QoS-Based Fuzzy Multi-Attribute Web Service Composition[J].Applied Mechanics&Materials,2012,182-183:2131-2135.
[21]YANG J,LI D F,LAI L B.Composite Service Multi-attribute Selection Method Based on Message Negotiation Under the Web Service Environment[J].Operations Research and Management Science,2015(3):134-141.(in Chinese)杨洁,李登峰,赖礼邦.Web服务环境下基于信息协商的组合服务多属性选择方法[J].运筹与管理,2015(3):134-141.
[22]WANG L,SHEN J,LUO J.Facilitating an ant colony algorithm for multi-objective data-intensive service provision[J].Journal of Computer&System Sciences,2015,81(4):734-746.
[23]LIAO J,LIU Y,WANG J,et al.Lightweight approach for multiobjective web service composition[J].IET Software,2016,10(4):116-124.
[24]SILVA A S D,MEI Y,MA H,et al.Fragment-based genetic programming for fully automated multi-objective web service composition[C]∥The Genetic and Evolutionary Computation Conference.2017:353-360.
[25]SUN S X.A decomposition-based approach for service composition with global QoS guarantees[J].Information Sciences,2012,199(15):138-153.
[26]WANG T C,LEE H D.Developing a fuzzy TOPSIS approach based on subjective weights and objective weights[J].Expert Systems with Applications,2009,36(5):8980-8985.
[27]LAUMANNS M,THIELE L,DEB K,et al.Combining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation,2014,10(3):263-282.
[28]AL-MASRI E,MAHMOUD Q H.Investigating Web Services on the World Wide Web[C]∥International Conference on World Wide Web,WWW 2008,Beijing,China,April.DBLP,2008:795-804.
[29]WANG H.Robust Control of the Output Probability Density Functions for Multivariable Stochastic Systems[J].IEEE Transactions on Automatic Control,1999,44(11):2103-2107.