改进蚁群算法在基于服务质量的Web服务组合优化中的应用

doi:10.11772/j.issn.1001-9081.2015.08.2238

计算机应用 ›› 2015, Vol. 35 ›› Issue (8): 2238-2243.DOI: 10.11772/j.issn.1001-9081.2015.08.2238

改进蚁群算法在基于服务质量的Web服务组合优化中的应用

倪志伟^1,2, 方清华^1,2, 李蓉蓉^1,2, 李一鸣^1,2

1. 合肥工业大学管理学院, 合肥 230009;
2. 过程优化与智能决策教育部重点实验室(合肥工业大学), 合肥 230009

收稿日期:2015-03-16 修回日期:2015-05-18 出版日期:2015-08-10 发布日期:2015-08-14
通讯作者: 方清华(1990-),女(壮族),广西南宁人,硕士研究生,主要研究方向:数据挖掘、群体智能,qinghua565@163.com
作者简介:倪志伟(1963-),男,安徽合肥人,教授,博士生导师,主要研究方向:人工智能、机器学习; 李蓉蓉(1990-),女(回族),福建泉州人,硕士研究生,主要研究方向:群智能算法、云计算; 李一鸣(990-),男,山东聊城人,硕士研究生,主要研究方向:数据挖掘、机器学习。
基金资助:
国家自然科学基金资助项目(71271071,71490725);国家自然科学基金青年项目(71301041);国家863计划项目(2011AA040501)。

Improved ant colony optimization for QoS-based Web service composition optimization

NI Zhiwei^1,2, FANG Qinghua^1,2, LI Rongrong^1,2, LI Yiming^1,2

1. School of Management, Hefei University of Technology, Hefei Anhui 230009, China;
2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education (Hefei University of Technology), Hefei Anhui 230009, China

Received:2015-03-16 Revised:2015-05-18 Online:2015-08-10 Published:2015-08-14

摘要/Abstract

摘要：

为了克服基础蚁群算法存在的前期搜索速度较慢、后期极易陷入局部最优解的缺点,提出初始信息素分布策略和局部优化策略;同时还提出了依赖解的质量的信息素更新依据,以增强算法过程中信息素的有效积累。将该改进蚁群算法应用于基于服务质量(QoS)的Web服务组合优化问题中,通过在数据集QWS2.0上的实验对改进蚁群算法的可用性和有效性进行了验证。结果表明改进的蚁群算法与基础蚁群算法、利用解与理想解距离更新信息素的改进蚁群算法以及用支配程度作为解的个体评价的改进遗传算法相比,能够找到更多的非劣解,寻优能力更优,表现出了较稳定的性能。

关键词: Web服务, 服务组合技术, 蚁群算法, Pareto最优解, 局部优化

Abstract:

The basic Ant Colony Optimization (ACO) has slow searching speed at prior period and being easy to fall into local optimum at later period. To overcome these shortcomings, the initial pheromone distribution strategy and local optimization strategy were proposed, and a new pheromone updating rule was put forward to strengthen the effective accumulation of pheromone. The improved ACO was used in QoS-based Web service composition optimization problem, and the feasibility and effectiveness of it was verified on QWS2.0 dataset. The experimental results show that, compared with the basic ACO, the improved ACO which updates the pheromone with the distance of the solution and the ideal solution, and the improved genetic algorithm which introduces individual domination strength into the environment selection, the proposed ACO can find more Pareto solutions, and has stronger optimizing capacity and stable performance.

Key words: Web service, service composition technique, Ant Colony Optimization (ACO), Pareto optimal solution, local optimization

中图分类号:

TP183

倪志伟, 方清华, 李蓉蓉, 李一鸣. 改进蚁群算法在基于服务质量的Web服务组合优化中的应用[J]. 计算机应用, 2015, 35(8): 2238-2243.

NI Zhiwei, FANG Qinghua, LI Rongrong, LI Yiming. Improved ant colony optimization for QoS-based Web service composition optimization[J]. Journal of Computer Applications, 2015, 35(8): 2238-2243.

参考文献

[1] CANFORA G, PENTA M D, ESPESITO R, et al. A lightweight approach for QoS-aware service composition [C]//ICSOC'04: Proceedings of the 2nd International Conference on Service Oriented Computing. New York: ACM, 2004: 36-47.
[2] LIU S, LIU Y, ZHANG F, et al. A dynamic Web services selection algorithm with QoS global optimal in Web services composition [J]. Journal of Software, 2007, 18(3): 646-656. (刘书雷,刘云翔,张帆,等.一种服务聚合中QoS全局最优服务动态选择算法[J].软件学报,2007,18(3):646-656.)
[3] ZHANG C, SU S, CHEN J. Genetical gorithm on Web services selection supporting QoS [J]. Chinese Journal of Computers, 2006, 29(7): 1029-1037. (张成文,苏森,陈俊亮.基于遗传算法的QoS感知的Web服务选择[J].计算机学报,2006,29(7):1029-1037.)
[4] SHENG G, WEN T, GUO Q, et al. Web service composition based on modified particle swarm optimization [J]. Chinese Journal of Computers, 2013, 36(5): 1031-1045. (盛国军,温涛,郭权,等.基于改进粒子群的Web服务组合[J].计算机学报,2013,36(5):1031-1045.)
[5] XIA H, LI Z. A particle swarm optimization algorithm for service selection problem based on quality of service in Web services composition [J].Journal of Beijing University of Posts and Telecommunications, 2009, 32(4): 63-67. (夏虹,李增智.粒子群算法求解Web服务组合中基于QoS的服务选择[J].北京邮电大学学报,2009,32(4):63-67.)
[6] XIA Y, CHENG B, CHEN J, et al. Optimizaing services composition based on improved ant colony algorithm [J]. Chinese Journal of Computers, 2012, 35(2): 270-281. (夏亚梅,程渤,陈俊亮,等.基于改进蚁群算法的服务组合优化[J].计算机学报,2012,35(2):270-281.)
[7] ZHAO S, WANG L, MA L, et al. An improved ant colony optimization algorithm for QoS-aware dynamic Web service composition [C]//ICICEE 2012: Proceedings of the 2012 International Conference on Industrial Control and Electronics Engineering. Washington, DC: IEEE Computer Society, 2012: 1998-2001.
[8] LIU L, YANG D. Multi-objective genetic optimization algorithm for SLA-aware service composition problem [J]. Journal of Jilin University: Engineering and Technology Edition, 2015,45(1):267-273. (刘磊,杨冬.求解服务等级感知服务组合问题的多目标遗传算法[J].吉林大学学报:工学版,2015,45(1):267-273.)
[9] WANG X, MA L. Web service selection based on ant colony algorithm [J]. Modern Electronics Technique, 2013, 36(12): 9-11. (王秀亭,马力.基于蚁群算法的Web服务选择[J].现代电子技术,2013,36(12):9-11.)
[10] ZHAO C, WANG J, QIN J, et al. A hybrid algorithm combining ant colony algorithm and genetic algorithm for dynamic Web service composition [J]. The Open Cybernetics & Systemics Journal, 2014, 8: 146-154.
[11] ZHANG W, CHANG C K, FENG T, et al. QoS-based dynamic Web service composition with ant colony optimization [C]//ACSAC 2010: Proceedings of the IEEE 34th Annual Computer Software and Applications Conference. Piscataway: IEEE, 2010: 493-502.
[12] DAI Y, YANG L, ZHANG B, et al. QoS for composite Web services and optimizing [J]. Chinese Journal of Computers,2006,29(7): 1167-1178. (代钰,杨雷,张斌,等.支持组合服务选取的QoS模型及优化求解[J].计算机学报,2006,29(7):1167-1178.)
[13] KONG W, LIU Q, YANG Z, et al. Composition of Web services based on two-dimension QoS model [J]. Computer Science, 2008, 35(11): 131-134. (孔维梁,刘清堂,杨宗凯,等.基于二维QoS模型的Web服务组合[J].计算机科学,2008,35(11):131-134.)
[14] YANG S, SHI M. A model for Web service discovery with QoS constraints [J]. Chinese Journal of Computers, 2005, 28(4): 589-594. (杨胜文,史美林.一种支持QoS约束的Web服务发现模型[J].计算机学报,2005,28(4):589-594.)
[15] HE Y, WU Z. Performance analysis of dynamic Web service composition key technologies [M]. Beijing: Tsinghua University Press, 2011: 48. (何炎祥,吴钊.动态Web服务组合关键技术与性能分析[M].北京:清华大学出版社,2011:48.)
[16] LI J, XIA J, TANG W, et al. Survey on Web services selection algorithms based on QoS [J]. Application Research of Computers, 2010, 27(10): 3622-3627. (李金忠,夏洁武,唐卫东,等.基于QoS的Web服务选择算法综述[J].计算机应用研究,2010,27(10):3622-3627.)
[17] ZHENG Y, TIAN J, DOU W. A QoS routing algorithm based on Pareto optimal [J]. Journal of Software,2005,16(8): 1484-1489. (郑彦兴,田菁,窦文华.基于Pareto最优的QoS路由算法[J].软件学报,2005,16(8):1484-1489.)
[18] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies [C]//PECAL 1991: Proceedings of the 1st European Conference on Artificial Life. New York: Elsevier Publishing, 1991: 134-142.
[19] AL-MASRI E, MAHMOUD Q H. Investigating Web services on the world wide Web [C]//WWW 2008: Proceedings of the 17th International Conference on World Wide Web. New York: ACM, 2008: 795-84.
[20] YANG Y. Parameter optimization and applications of ant colony algorithm [D]. Nanjing: Nanjing University of Technology, 2008:12. (杨亚南.蚁群算法参数优化及其应用[D].南京:南京理工大学,2008:12.)

改进蚁群算法在基于服务质量的Web服务组合优化中的应用

Improved ant colony optimization for QoS-based Web service composition optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[2]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[3]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[4]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[5]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[6]	赵士操, 肖永浩, 段博文, 李于锋. HSWAP:适用于高性能计算环境的数值模拟工作流管理平台[J]. 计算机应用, 2019, 39(6): 1569-1576.
[7]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[8]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[9]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.
[10]	王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.
[11]	魏亚茹, 朱瑾. 自动化码头双场桥调度与集装箱存储选位建模[J]. 计算机应用, 2018, 38(4): 1189-1194.
[12]	王超, 朱明, 王敏. 基于管制员认知负荷和改进蚁群算法的扇区动态通行能力评估[J]. 计算机应用, 2018, 38(1): 277-283.
[13]	史兵, 段锁林, 李菊, 王朋, 朱益飞. 基于无线传感器网络的室内移动灭火机器人系统设计[J]. 计算机应用, 2018, 38(1): 284-289.
[14]	许凯波, 鲁海燕, 程毕芸, 黄洋. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6): 1686-1691.
[15]	鲍振华, 康宝生, 张雷, 张婧. 基于草图局部几何不变矩的图像检索方法[J]. 计算机应用, 2017, 37(6): 1753-1758.