[1]孙学胜,曹玖新,刘波,等.基于多目标粒子群优化的服务选择算法[J].东南大学学报(自然科学版),2009,39(4):684-689.[doi:10.3969/j.issn.1001-0505.2009.04.007]
 Sun Xuesheng,Cao Jiuxin,Liu Bo,et al.Service selection algorithm based on multi-objective particle swarm optimization[J].Journal of Southeast University (Natural Science Edition),2009,39(4):684-689.[doi:10.3969/j.issn.1001-0505.2009.04.007]
点击复制

基于多目标粒子群优化的服务选择算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
39
期数:
2009年第4期
页码:
684-689
栏目:
计算机科学与工程
出版日期:
2009-07-20

文章信息/Info

Title:
Service selection algorithm based on multi-objective particle swarm optimization
作者:
孙学胜 曹玖新 刘波 胡波 李和光
东南大学计算机科学与工程学院,南京 210096
Author(s):
Sun Xuesheng Cao Jiuxin Liu Bo Hu Bo Li Heguang
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
关键词:
服务组合 服务选择 pareto最优解 多目标优化 粒子群优化
Keywords:
service composition service selection pareto optimal solution multi-objective optimization particle swarm optimization
分类号:
TP301.6;TP393.4
DOI:
10.3969/j.issn.1001-0505.2009.04.007
摘要:
基于多目标粒子群优化算法提出一种高效的服务选择算法(MOPSOSS).首先将服务选择问题建模为带QoS约束的多目标组合优化问题; 其次,根据支配的概念构造远小于原子服务集的新子服务集; 最后基于多目标粒子群优化算法求解由新子服务集构成的服务选择问题,从而获得一组满足约束的pareto最优解.理论分析表明,MOPSOSS能正确、高效地求出原问题的全局最优解.与遗传算法(GA)的对比结果表明当问题规模大于150时,MOPSOSS的平均运行时间仅为GA的7%,求出的解的个数是GA的1.15倍,75%的解能支配GA求出的解,分布广度是GA的1.5倍.随着约束强度的增加,MOPSOSS的平均运行时间减少,而解的质量并无显著下降.与GA相比,MOPSOSS能用更短的时间求出更多高质量的解.
Abstract:
An efficient service selection algorithm based on a multi-objective particle swarm optimization algorithm, MOPSOSS, is proposed. First, the service selection problem is modeled as a multi-objective constrained combinatorial optimization problem. Then according to the domination concept, new component service set, whose size is far less than the original one, is constructed. The multi-objective particle swarm optimization is employed and then pareto optimal solutions are obtained. The theoretical analysis proves that MOPSOSS can correctly obtain global optimal solutions. Comparison with the genetic algorithm(GA)shows that under the problem size of greater than 150, the average running time of MOPSOSS is 7% of that of GA, that solution number and distribution scope is respectively 1.15 and 1.5 times higher than GA. Moreover, 75% of MOPSOSS solutions can dominate GA ones. As restriction strength increasing, MOPSOSS running time decreases and the solution quality does not evidently decrease. MOPSOSS can obtain adequate high quality solutions in a shorter time than GA.

参考文献/References:

[1] Casati F,Ilnicki S,Jin L J,et al.eFlow:a platform for developing and managing composition e-services,HPL-2000-36 [R].HP Laboratories Palo Alto,2000.
[2] Liu Y T,Anne H H,Zeng L Z.QoS computation and policing in dynamic Web service selection[C] //Proc of the 13th International World Wide Web Conference on Alternate Track Papers and Posters.New York:ACM,2004:66-73.
[3] 张成文,苏森,陈俊亮.基于遗传算法的QoS感知的Web服务选择[J].计算机学报,2006,29(7):1029-1037.
  Zhang Chengwen,Su Sen,Chen Junliang.Genetic algorithm on Web services selection supporting QoS[J].Chinese Journal of Computers,2006,29(7):1029-1037.(in Chinese)
[4] Canfora G,Penta M D,Esposito R,et al.An approach for QoS-aware service composition based on genetic algorithms[C] //Proc of the 2005 Conference on Genetic and Evolutionary Computation.New York:ACM,2005:1069-1075.
[5] Canfora G,Penta M D,Esposito R,et al.QoS-aware replanning of composite Web services[C] //Proc of the IEEE International Conference on Web Services.Washington DC:IEEE Computer Society,2005:121-129.
[6] 刘书雷,刘云翔,张帆,等.一种服务聚合中QoS全局最优服务动态选择算法[J].软件学报,2007,18(3):646-656.
  Liu Shulei,Liu Yunxiang,Zhang Fan,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.(in Chinese)
[7] Zeng L Z,Benatallah B,Ngu A H H,et al.QoS-aware middleware for Web services composition[J]. IEEE Transactions on Software Engineering,2004,30(5):311-327.
[8] Yu T,Lin K J.The design of QoS broker algorithms for QoS-capable Web services[C] //Proc of the 2004 IEEE International Conference on e-Technology,e-Commerce and e-Service.Washington DC:IEEE Computer Society,2004:17-24.
[9] Yu T,Lin K J.A broker-based framework for QoS-aware Web service composition[C] //Proc of the 2005 IEEE International Conference on e-Technology,e-Commerce and e-Service.Washington DC:IEEE Computer Society,2005:22-29.
[10] Berner R,Spahn M,Repp N,et al.Heuristics for QoS-aware Web service composition[C] //Proc of the IEEE International Conference on Web Services.Washington DC:IEEE Computer Society,2006:72-82.
[11] Zitzler E,Laumanns M,Thiele L,et al.Why quality assessment of multiobjective optimizers is difficult[C] //Proc of the 2002 Genetic and Evolutionary Computation Conference.California:Morgan Kaufmann Publishers Inc,2002:666-673.
[12] Garey M R,Johnson D S. Computers and intractability:a guide to the theory of NP completeness[M].New York:W.H.Freeman & Co,1990:120-190.
[13] 杨维,李岐强.粒子群优化算法综述[J].中国工程科学,2004,6(5):87-94.
  Yang Wei,Li Qiqiang.An overview:particle swarm optimization[J].Engineering Science,2004,6(5):87-94.(in Chinese)
[14] Eberhart R,Shi Y.Particle swarm optimization:developments,applications and resources[C] //Proc of the 2001 Congress on Evolutionary Computation.Washington DC:IEEE Computer Society,2001:81-86.
[15] Coello Coello C A,Pulido G T,Lechuga M S.Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.
[16] Zitzler E,Thiele L,Laumanns M,et al.Performance assessment of multi-objective optimizers:an analysis and review[J]. IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.

相似文献/References:

[1]贺正求,吴礼发,李华波,等.请求驱动的服务组合访问控制[J].东南大学学报(自然科学版),2011,41(3):443.[doi:10.3969/j.issn.1001-0505.2011.03.002]
 He Zhengqiu,Wu Lifa,Li Huabo,et al.Request-driven access control for service composition[J].Journal of Southeast University (Natural Science Edition),2011,41(4):443.[doi:10.3969/j.issn.1001-0505.2011.03.002]
[2]谢海军,齐连永,窦万春.基于Skyline和局部选择的启发式服务组合方法[J].东南大学学报(自然科学版),2011,41(3):449.[doi:10.3969/j.issn.1001-0505.2011.03.003]
 Xie Haijun,Qi Lianyong,Dou Wanchun.Combining Skyline and local selection for heuristic Web service composition[J].Journal of Southeast University (Natural Science Edition),2011,41(4):449.[doi:10.3969/j.issn.1001-0505.2011.03.003]
[3]王海艳,白圆圆.支持二分图语义匹配的组合服务选择方法[J].东南大学学报(自然科学版),2014,44(3):510.[doi:10.3969/j.issn.1001-0505.2014.03.011]
 Wang Haiyan,Bai Yuanyuan.Composite service selection method supporting semantic matching based on bipartite graph[J].Journal of Southeast University (Natural Science Edition),2014,44(4):510.[doi:10.3969/j.issn.1001-0505.2014.03.011]

备注/Memo

备注/Memo:
作者简介: 孙学胜(1983—),男,硕士生; 曹玖新(联系人),男,博士,副教授,jx.cao@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(90604004,60773103)、高等学校博士学科点专项科研基金资助项目(200802860031)、江苏省自然科学基金重点资助项目(BK2007708,BK2008030)、江苏省网络与信息安全重点实验室资助项目(BM2003201)、东南大学计算机网络和信息集成教育部重点实验室资助项目(93K-9).
引文格式: 孙学胜,曹玖新,刘波,等.基于多目标粒子群优化的服务选择算法[J].东南大学学报:自然科学版,2009,39(4):684-689.[doi:10.3969/j.issn.1001-0505.2009.04.007]
更新日期/Last Update: 2009-07-20