求解Web服务组合QoS优化的多属性决策及自适应遗传算法

doi:10.11896/j.issn.1002-137X.2019.02.029

摘要/Abstract

摘要： 随着面向服务计算(Service-oriented Computing,SOC)的不断发展,基于服务质量(Quality of Service,QoS)的Web服务组合研究成为了必然趋势。鉴于QoS属性的多维性及相互矛盾性,提出将基于QoS的Web服务组合优化问题转化为多属性决策问题进行求解。采用折中系数对每个组合服务实例到正负理想点的距离进行累加求和,最终得到一组最优服务排序结果,用户可以根据自身偏好进行选择。传统的多属性决策方法无法有效地处理大规模的组合服务搜索空间,因此,为了有效地解决Web服务组合优化这一NP难题,提出一种结合多属性决策方法和自适应遗传算法的新型优化算法来解决该问题。实验采用真实的QoS综合服务数据集进行验证,实验结果表明,该方法能够在较短时间内找到全局近似最优解,且解集的排序结果接近于实际的最优服务排序。同时,该方法对于解决大规模的Web服务组合优化问题具有良好的可伸缩性。

关键词: QoS, Web服务组合, 多属性决策, 遗传算法

Abstract: 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.

Key words: Genetic algorithm, Multi-attribute decision making, Quality of service, Web service composition

中图分类号:

TP301

鲁城华, 寇纪淞. 求解Web服务组合QoS优化的多属性决策及自适应遗传算法[J]. 计算机科学, 2019, 46(2): 187-195. https://doi.org/10.11896/j.issn.1002-137X.2019.02.029

LU Cheng-hua, KOU Ji-song. Multi-attribute Decision Making and Adaptive Genetic Algorithm for Solving QoS Optimization of Web Service Composition[J]. Computer Science, 2019, 46(2): 187-195. https://doi.org/10.11896/j.issn.1002-137X.2019.02.029

参考文献

[1]XU L,LI Y H,CHEN L,et al.A Testing Method for Web Servi- ces 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 servi- ces composition framework [J].International Journal of Business Information Systems,2017,17(1):94.
[5]JATOTH C,GANGADHARAN G R,BUYYA R.Computa- tional Intelligence based QoS-aware Web Service Composition:A Systematic Literature Review [J].IEEE Transactions on Ser-vices 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’10 Proceedings 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 Multi-objective 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 network-aware 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 dyna- mic 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 Mecha-nics & 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 multi-objective 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.

相关文章 15

[1]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[2]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[3]	吴善杰, 王新. 基于AGA-DBSCAN优化的RBF神经网络构造煤厚度预测方法 Prediction of Tectonic Coal Thickness Based on AGA-DBSCAN Optimized RBF Neural Networks 计算机科学, 2021, 48(7): 308-315. https://doi.org/10.11896/jsjkx.200800110
[4]	郑增乾, 王锟, 赵涛, 蒋维, 孟利民. 带宽和时延受限的流媒体服务器集群负载均衡机制 Load Balancing Mechanism for Bandwidth and Time-delay Constrained Streaming Media Server Cluster 计算机科学, 2021, 48(6): 261-267. https://doi.org/10.11896/jsjkx.200400131
[5]	王金恒, 单志龙, 谭汉松, 王煜林. 基于遗传优化PNN神经网络的网络安全态势评估 Network Security Situation Assessment Based on Genetic Optimized PNN Neural Network 计算机科学, 2021, 48(6): 338-342. https://doi.org/10.11896/jsjkx.201200239
[6]	左剑凯, 吴杰宏, 陈嘉彤, 刘泽源, 李忠智. 异构无人机编队防御及评估策略研究 Study on Heterogeneous UAV Formation Defense and Evaluation Strategy 计算机科学, 2021, 48(2): 55-63. https://doi.org/10.11896/jsjkx.191100053
[7]	高帅, 夏良斌, 盛亮, 杜宏亮, 袁媛, 韩和同. 基于投影圆度和遗传算法的空间圆柱面拟合方法 Spatial Cylinder Fitting Based on Projection Roundness and Genetic Algorithm 计算机科学, 2021, 48(11A): 166-169. https://doi.org/10.11896/jsjkx.201100057
[8]	姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191
[9]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案 Multi-edge Collaborative Computing Unloading Scheme Based on Genetic Algorithm 计算机科学, 2021, 48(1): 72-80. https://doi.org/10.11896/jsjkx.200800088
[10]	吉顺慧, 张鹏程. 基于支配关系的数据流测试用例生成方法 Test Case Generation Approach for Data Flow Based on Dominance Relations 计算机科学, 2020, 47(9): 40-46. https://doi.org/10.11896/jsjkx.200700021
[11]	董明刚, 黄宇扬, 敬超. 基于遗传实例和特征选择的K近邻训练集优化方法 K-Nearest Neighbor Classification Training Set Optimization Method Based on Genetic Instance and Feature Selection 计算机科学, 2020, 47(8): 178-184. https://doi.org/10.11896/jsjkx.190700089
[12]	梁正友, 何景琳, 孙宇. 一种用于微表情自动识别的三维卷积神经网络进化方法 Three-dimensional Convolutional Neural Network Evolution Method for Facial Micro-expression Auto-recognition 计算机科学, 2020, 47(8): 227-232. https://doi.org/10.11896/jsjkx.190700009
[13]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14]	包振山, 郭俊南, 谢源, 张文博. 基于LSTM-GA的股票价格涨跌预测模型 Model for Stock Price Trend Prediction Based on LSTM and GA 计算机科学, 2020, 47(6A): 467-473. https://doi.org/10.11896/JsJkx.190900128
[15]	马创, 吕孝飞, 梁炎明. 基于GA-SVM的农产品质量分类 Agricultural Product Quality Classification Based on GA-SVM 计算机科学, 2020, 47(6A): 517-520. https://doi.org/10.11896/JsJkx.190900184

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed