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

doi:10.11772/j.issn.1001-9081.2015.08.2238

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (8): 2238-2243.DOI: 10.11772/j.issn.1001-9081.2015.08.2238

Previous Articles Next Articles

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

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

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

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

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

Abstract

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

摘要：

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

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

CLC Number:

TP183

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.

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

References

[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.)

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[2]	LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417.
[3]	WEI Mingyan, CHEN Yu, ZHANG Liang. Coevolutionary ant colony optimization algorithm for mixed-variable optimization problem [J]. Journal of Computer Applications, 2021, 41(5): 1412-1418.
[4]	FAN Xiaomao, XIONG Honglin, ZHAO Gansen. Cleaning scheduling model with constraints and its solution [J]. Journal of Computer Applications, 2021, 41(2): 577-582.
[5]	WANG Hongyu, ZHANG Yu, YANG Heng, MU Nan. Salient object detection in weak light images based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2021, 41(10): 2970-2978.
[6]	XIONG Yong, ZHANG Jia, YU Jiajun, ZHANG Benren, LIANG Xuanzhuo, ZHU Qige. Intelligent layout optimization algorithm for 3D pipelines of ships [J]. Journal of Computer Applications, 2020, 40(7): 2164-2170.
[7]	XU Yingxin, SUN Lei, ZHAO Jiancheng, GUO Songhui. Virtual field programmable gate array placement strategy based on ant colony optimization algorithm [J]. Journal of Computer Applications, 2020, 40(3): 747-752.
[8]	ZHAO Shicao, XIAO Yonghao, DUAN Bowen, LI Yufeng. HSWAP: numerical simulation workflow management platform suitable for high performance computing environment [J]. Journal of Computer Applications, 2019, 39(6): 1569-1576.
[9]	WANG Qingrong, WANG Ruifeng. Reconfiguration strategy of distribution network based on improved particle swarm optimization [J]. Journal of Computer Applications, 2018, 38(9): 2720-2724.
[10]	QI Pan, BAO Kaiyang, MA Xiaoyuan. WSN hierarchical routing algorithm based on fuzzy C-means clustering and swarm intelligence [J]. Journal of Computer Applications, 2018, 38(7): 1974-1980.
[11]	CHEN Xuan, XU Jianwei, LONG Dan. Resource scheduling algorithm of cloud computing based on ant colony optimization-shuffled frog leading algorithm [J]. Journal of Computer Applications, 2018, 38(6): 1670-1674.
[12]	MAO Yingchi, MU Chao, BAO Wei, LI Xiaofang. Multi-type task assignment and scheduling oriented to spatial crowdsourcing [J]. Journal of Computer Applications, 2018, 38(1): 6-12.
[13]	XU Kaibo, LU Haiyan, CHENG Biyun, HUANG Yang. Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP [J]. Journal of Computer Applications, 2017, 37(6): 1686-1691.
[14]	BAO Zhenhua, KANG Baosheng, ZHANG Lei, ZHANG Jing. Sketch-based image retrieval method using local geometry moment invariant [J]. Journal of Computer Applications, 2017, 37(6): 1753-1758.
[15]	GAO Guodong, LIN Ming, XU Lan. New PSO particle filter method based on likelihood-adjustment [J]. Journal of Computer Applications, 2017, 37(4): 980-985.