Two-stage Multi-objective Ant Colony Optimization for Solving Logistics Web Service Composition

Abstract

Abstract: A two-stage multi-objective ACO(TMACO) was proposed to solve logistics Web services composition optimization problems. First, to solve the time increases rised by candidate services which was dominated in the raw data, a pre-optimization strategy was proposed based on Pareto dominated ideology; secondly, since the weights of each attribute were difficult to determine, a non-dependent weight pheromone update strategy and inspiration information policy were included in the TMACO; and finally, the basic ACO was easy to fall into local optimum problem, a lazy ant strategy was proposed to solve this problem. The experimental results show that TMACO algorithm has good performance. Its optimization capability is better than that of the basic ACO,the improved ACO which used the distance of the solution and the ideal solution to update the pheromone,the basic genetic algorithm and improved genetic algorithm which applied the dominant factor to evaluate a solution, TMACO optimization algorithm has a higher ability to find more and better Pareto solutions.

Key words: logistics service, ant colony optimization (ACO), service composition problem, Pareto optimal solution, multi-objective optimization

摘要： 针对基于QoS的物流Web服务组合优化问题，提出了两阶段多目标蚁群优化(TMACO)算法。首先，针对原始数据集中存在被支配候选服务而增加算法求解时间的问题，提出了基于Pareto支配的预优化策略；其次，针对属性权重难以确定的问题，提出了不依赖权重的信息素更新策略和启发信息策略；最后，针对基础蚁群算法容易陷入局部最优的问题，提出了懒蚂蚁策略。实验结果表明，TMACO算法具有良好性能，相对于基础蚁群算法、利用解与理想解距离来更新信息素的改进蚁群算法、遗传算法以及用支配程度作为解的个体评价的改进遗传算法，TMACO算法有更高的寻优能力，能够找到更多更优的非劣解。

关键词: 物流服务, 蚁群算法, 服务组合问题, Pareto最优解, 多目标优化

CLC Number:

TP181

Fang Qinghua, Ni Liping, Li Yiming. Two-stage Multi-objective Ant Colony Optimization for Solving Logistics Web Service Composition[J]. China Mechanical Engineering.

方清华, 倪丽萍, 李一鸣. 求解物流Web服务组合问题的两阶段多目标蚁群算法[J]. 中国机械工程.

References

[1]Guinard D, Trifa V, Karnouskos S, et al. Interacting with the SOA-based Internet of Things Discovery, Query, Selection, and On-demand Provisioning of Web Services[J]. Transactions on Services Computing， 2010,3(3):223-235.

[2]Schuldt A, Hribernik K A, Gehrke J D, et al. Cloud Computing for Autonomous Control in Logistics[C]∥Proceedings of 40th Annual Conference of the German Society for Computer Science. Berlin, 2010:305-310.

[3]Holtkamp B, Steinbuss S, Gsell H, et al. Towards a Logistics Cloud[C]∥ Proceedings of the Sixth International Conference on Semantics. Beijing,2010:305-308.

[4]Garruzzo S, Rosaci D, Sarnè G M L. Integrating Trust Measures in Multi-agent Systems[J].International Journal of Intelligent Systems， 2012,27:1-15.

[5]刘磊,杨冬.求解服务等级感知服务组合问题的多目标遗传算法[J].吉林大学学报,2015，45(1)：267-273.

Liu Lei,Yang Dong. Multi-objective Genetic Optimization Algorithm for SLA-aware Service Composition Problem[J]. Journal of Jilin University,2015，45(1)：267-273.

[6]刘志中,宋成,薛霄,等.情景感知的物流Web服务动态优化组合研究[J].计算机工程与科学,2013,35(9):51-56.

Liu Zhizhong, Song Cheng, Xue Xiao, et al. Research on Dynamic Optimal Composition of Context-aware Logistics Web Service[J].Computer Engineering & Science, 2013,35(9):51-56.

[7]盛国军,温涛,郭权,等.基于改进粒子群的Web服务组合[J].计算机学报,2013, 36(5):1031-1045.

Sheng Guojun, Wen Tao, Guo Quan, et al. Web Service Composition Based on Modified Particle Swarm Optimization[J]. Chinese Journal of Computer,2013, 36(5): 1031-1045.

[8]王秀亭,马力.基于蚁群算法的Web服务选择[J].现代电子技术, 2013,36(12):9-11. Wang Xiuting, Ma Li. Web Service Selection Base on Ant Colony Algorithm[J]. Modern Electronics Technique, 2013,36(12):9 -11.

[9]Wei Z, Carl K, Taiming F, et al. QoS-based Dynamic Web Service Composition with Ant Colony Optimization[C]// ACSAC 2010:IEEE 34th Annual Computer Software and Applications Conference. Vasteras,Sweden,2010:493-502.

[10]张焕焕,薛霄,刘志中,等.基于遗传社会认知算法的物流Web服务优化组合研究[J].计算机应用研究,2014,31(6):1752-1754.

Zhang Huanhuan, Xue Xiao, Liu Zhizhong,et al. Research on Optimization of Logistics Web Service Based on Genrtic Social Congnitive Optimization Algorithm[J]. Application Research of Computers, 2014,31(6):1752-1754.

[11]Zhao S, Ma L, Wang L,et al. An improved Ant Colony Optimization Algorithm for QoS-aware Synamic Web Service Composition[C]// ICICEE 2012: International Conference on Industrial Control and Electronics Engineering. Xi'an, 2012:1998-2001.

[12]Sahoo J, Mohapatra S, Lath R. Virtualization: a Survey on Concepts, Taxonomy and Associated Security Issues[C]//ICCNT 2010: Proceedings of 2nd International Conference on Computer and Network Technology. Bangkok, Thailand, 2010:222- 226.

[13]Li Wenfeng, Zhong Ye, Wang Xun, et al.Resource Virtualization and Service Selection in Cloud Logistics [J]. Journal of Network and Computer Applications, 2013,36(6): 1696-1704.

[14]Atzori L, Iera A, Morabito G. The Internet of Things: a Survey[J]. Computer Networks,2010,54: 2787-2805.

[15]Canfora G, Penta M D, Espesito R,et al. A Lightweight Approach for QoS-aware Service Composition[C]//PICSOC 2004: Proceedings of the 2nd International Conference on Service Oriented Computing.New York:ACM, 2004:36-47.

[16]郑彦兴,田菁,窦文华.基于Pareto最优的QoS 路由算法[J],软件学报,2005, 16(8): 1484-1489. Zheng Yanxing, Tian Jing, Dou Wenhua. A QoS Routing Algorithm Based on Pareto optimal [J]. Journal of Software,2005,16(8): 1484-1489.

[17]罗仕奎.懒蚂蚁效应——懒于杂务,才能勤于动脑[J].北京农业,2011,36(8):13-14.

Luo Shikui. Lazy Ant Effect—Lazy Chores to Be Diligent in Their Brains[J]. Beijing Agriculture, 2011,36(8):13-14.

[18]杨亚南.蚁群算法参数优化及其应用[D].南京:南京理工大学,2008.

[19]方周,陈荣平,蔡美玲.遗传算法在Web服务组合中的应用[J].计算机与现代化,2007, 48(12): 118-121.

Fang Zhou, Chen Rongping,Cai Meiling. Application of Genetic Algorithms in Web Service Composition[J]. Computer and Modernization, 2007,48(12):118-121.