基于优化的灰狼算法的大规模Web服务组合

doi:10.11772/j.issn.1001-9081.2021091556

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (10): 3162-3169.DOI: 10.11772/j.issn.1001-9081.2021091556

基于优化的灰狼算法的大规模Web服务组合

徐雪敏, 张秀国, 肖媛元, 曹志英

大连海事大学信息科学技术学院，辽宁大连 116026

收稿日期:2021-09-02 修回日期:2021-12-13 接受日期:2021-12-23 发布日期:2022-04-15 出版日期:2022-10-10
通讯作者: 张秀国
作者简介:第一联系人：徐雪敏（1996—），女，山东淄博人，硕士研究生，主要研究方向：服务计算
张秀国（1971—），女，山东聊城人，教授，博士，主要研究方向：服务计算、软件服务工程； zhangxg@dlmu.edu.cn
肖媛元（1998—），女，吉林松原人，硕士研究生，主要研究方向：服务计算
曹志英（1970—），女，山东烟台人，副教授，硕士，主要研究方向：Web服务、软件工程。
基金资助:
国家重点研发计划项目(2018YFB1601502)

Large-scale Web service composition based on optimized grey wolf optimizer

Xuemin XU, Xiuguo ZHANG, Yuanyuan XIAO, Zhiying CAO

Information Science and Technology College，Dalian Maritime University，Dalian Liaoning 116026，China

Received:2021-09-02 Revised:2021-12-13 Accepted:2021-12-23 Online:2022-04-15 Published:2022-10-10
Contact: Xiuguo ZHANG
About author:XU Xuemin, born in 1996， M. S. candidate. Her research interests include service computing.
ZHANG Xiuguo, born in 1971， Ph. D. ， professor. Her research interests include service computing， software service engineering.
XIAO Yuanyuan, born in 1998， M. S. candidate. Her research interests include service computing.
CAO Zhiying, born in 1970， M. S. ， associate professor. Her research interests include Web service， software engineering.
Supported by:
National Key Research and Development Program of China(2018YFB1601502)

摘要/Abstract

摘要：

针对大规模Web服务环境中难以获得整体性能高的组合服务的问题，提出了一种大规模Web服务组合方法。首先，采用文档对象模型（DOM）对XML格式的用户需求描述文档进行解析，以生成抽象Web服务组合序列；然后，采用服务主题模型进行服务筛选，并为每个抽象Web服务选取Top-k个具体Web服务从而缩减组合空间；接着，为提高服务组合质量和组合效率，提出了一种基于Logistic混沌映射和非线性收敛因子的优化的灰狼算法（OGWO/LN）来进行最优服务组合方案选择；该算法采用混沌映射来生成初始种群以增加服务组合方案的多样性，并避免了多次局部寻优；同时，提出一种非线性收敛因子来调节算法的搜索能力以提高算法的寻优性能；最后，采用MapReduce框架对OGWO/LN进行了并行实现。在真实数据集上的实验结果表明，所提算法与IFOA4WSC、MR-IDPSO、MR-GA等算法相比，平均适应度值分别提高了8.69%、7.94%和12.25%，在解决大规模Web服务组合问题时具有更好的寻优性能和稳定性。

关键词: 主题模型, 服务组合, 灰狼算法, 服务质量, MapReduce

Abstract:

In order to solve the problem that it is difficult to obtain a composite service with high overall performance in a large-scale Web service environment， a large-scale Web service composition method was proposed. Firstly， Document Object Model （DOM） was used to parse the user demand document in XML format to generate an abstract Web service composition sequence. Secondly， the service topic model was used for service filtering， and Top-k specific Web services were selected for each abstract Web service to reduce the composition space. Thirdly， in order to improve the quality and efficiency of service composition， an Optimized Grey Wolf Optimizer based on Logistic chaotic map and Nonlinear convergence factor （OGWO/LN） was proposed to select the optimal service composition plan. In this algorithm， chaotic map was used to generate the initial population for increasing the diversity of service composition plans and avoiding multiple local optimizations. At the same time， a nonlinear convergence factor was proposed to improve the optimization performance of the algorithm by adjusting the algorithm search ability. Finally， OGWO/LN was realized in a parallel way by MapReduce framework. Experimental results on real datasets show that compared with algorithms such as IFOA4WSC （Improved Fruit Fly Optimization Algorithm for Web Service Composition）， MR-IDPSO （MapReduce based on Improved Discrete Particle Swarm Optimization） and MR-GA （MapReduce based on Genetic Algorithm）， the proposed algorithm has the average fitness value increased by 8.69%， 7.94% and 12.25% respectively， and has better optimization performance and stability in solving the problem of large-scale Web service composition.

Key words: topic model, service composition, Grey Wolf Optimizer (GWO), Quality of Service (QoS), MapReduce

中图分类号:

TP311

徐雪敏, 张秀国, 肖媛元, 曹志英. 基于优化的灰狼算法的大规模Web服务组合[J]. 计算机应用, 2022, 42(10): 3162-3169.

Xuemin XU, Xiuguo ZHANG, Yuanyuan XIAO, Zhiying CAO. Large-scale Web service composition based on optimized grey wolf optimizer[J]. Journal of Computer Applications, 2022, 42(10): 3162-3169.

图/表 14

表1 组合服务QoS计算方法

Tab. 1 QoS calculation methods of composite service

控制结构	响应时间	吞吐量	控制结构	响应时间	吞吐量
顺序	$∑ i = 1 n R T i$	$m i n i = 1 n T i$	并行	$m a x i = 1 n R T i$	$m i n i = 1 n T i$
选择	$∑ i = 1 n R T i × p i$	$∑ i = 1 n T i × p i$	循环	$∑ i = 1 n R T i × c$	$∑ i = 1 n T i / m$

表1 组合服务QoS计算方法

Tab. 1 QoS calculation methods of composite service

控制结构	响应时间	吞吐量	控制结构	响应时间	吞吐量
顺序	$∑ i = 1 n R T i$	$m i n i = 1 n T i$	并行	$m a x i = 1 n R T i$	$m i n i = 1 n T i$
选择	$∑ i = 1 n R T i × p i$	$∑ i = 1 n T i × p i$	循环	$∑ i = 1 n R T i × c$	$∑ i = 1 n T i / m$

图1 大规模Web服务组合方法框架

Fig. 1 Large-scale Web service composition method framework

图2 抽象服务组合序列示例

Fig. 2 Example of abstract service composition sequence

图3 LDA主题模型

Fig. 3 LDA topic model

表2 LDA主题模型符号

Tab. 2 Symbols of LDA topic model

符号	含义
K	Web服务描述文档共享的主题个数
M	Web服务描述文档个数
$N m$	第m篇Web服务描述文档的单词总数
$α$	生成 $θ m$ 的Dirichlet先验参数
$θ m$	第m篇Web服务描述文档的主题分布
$β$	生成 $φ k$ 的Dirichlet先验参数
$φ k$	第k个主题的词项分布
$Z m, n$	第m篇文档的第n个主题
$w m, n$	第m篇文档的第n个单词

表2 LDA主题模型符号

Tab. 2 Symbols of LDA topic model

符号	含义
K	Web服务描述文档共享的主题个数
M	Web服务描述文档个数
$N m$	第m篇Web服务描述文档的单词总数
$α$	生成 $θ m$ 的Dirichlet先验参数
$θ m$	第m篇Web服务描述文档的主题分布
$β$	生成 $φ k$ 的Dirichlet先验参数
$φ k$	第k个主题的词项分布
$Z m, n$	第m篇文档的第n个主题
$w m, n$	第m篇文档的第n个单词

表3 服务文档?主题矩阵

Tab. 3 Service document-topic matrix

文档	主题
文档	T₁	T₂	…	T_k
d₁	0.284 864 63	0.411 211 46	…	0.053 461 81
d₂	0.060 037 53	0.106 428 97	…	0.529 479 86
d₃	0.474 014 13	0.079 954 53	…	0.047 261 33
︙
d_m	0.282 654 97	0.026 405 54	…	0.478 582 05

表4 在线支付功能需求与部分服务文档的JS散度

Tab. 4 JS divergence of online payment function requirement and part of service documents

文档	JS散度值	文档	JS散度值
d₁	0.104 819 694	d₄	0.097 231 417
d₂	0.255 895 451	d₅	0.165 070 385
d₃	0.037 764 105	d₆	0.338 601 817

图4 收敛因子变化曲线

Fig. 4 Convergence factor change curve

图5 组合服务编码模式

Fig. 5 Composite service encoding pattern

表5 键值对结构

Tab. 5 Structure of key-value pair

Key	Value
i	X_i；lbestagent，fitness（lbestagent）；lsecondagent， fitness（lsecondagent）；lthirdagent，fitness（lthirdagent）

图6 不同主题数对主题一致性值的影响

Fig. 6 Influence of different topic numbers on topic coherence score

图7 不同JS散度阈值下的精确率

Fig. 7 Precision under different JS divergence thresholds

图8 不同迭代次数的性能比较

Fig. 8 Performance comparison with different iteration times

表6 四种算法的性能比较

Tab. 6 Performance comparison of four algorithms

算法	最大适应度值	最小适应度值	平均适应度值	均方差
IFOA4WSC^［6］	2.790 774	2.639 232	2.756 645	0.056 062
MR-IDPSO^［8］	2.794 226	2.620 421	2.775 628	0.058 062
MR-GA^［21］	2.711 152	2.631 241	2.669 081	0.059 062
OGWO/LN	2.998 212	2.890 885	2.996 096	0.044 450

参考文献 21

1	DENG S G， HUANG L T， TAN W， et al. Top-k automatic service composition： a parallel method for large-scale service sets［J］. IEEE Transactions on Automation Science and Engineering， 2014， 11（3）： 891-905. 10.1109/tase.2014.2306931
2	吴洪越，杜玉越. 一种基于逻辑Petri网的Web服务簇组合方法［J］. 计算机学报， 2015， 38（1）：204-218. 10.3724/SP.J.1016.2015.00204
	WU H Y， DU Y Y. A logical Petri net-based approach for Web service cluster composition［J］. Chinese Journal of Computers， 2015， 38（1）：204-218. 10.3724/SP.J.1016.2015.00204
3	WANG H B， LI J J， YU Q， et al. Integrating recurrent neural networks and reinforcement learning for dynamic service composition［J］. Future Generation Computer Systems， 2020， 107： 551-563. 10.1016/j.future.2020.02.030
4	FAN S L， PENG K Y， YANG Y B. Large-scale QoS-aware service composition integrating chained dynamic programming and hybrid pruning［C］// Proceedings of the 2018 International Conference on Web Services， LNCS 10966. Cham： Springer， 2018： 196-211.
5	张苑蕾，邵清，李刘静，等. 融合遗传聚类的可靠Web服务组合优化方法［J］. 小型微型计算机系统， 2020， 41（5）：1030-1035. 10.3969/j.issn.1000-1220.2020.05.021
	ZHANG Y L， SHAO Q， LI L J， et al. Reliable Web service composition optimization method based on genetic clustering［J］. Journal of Chinese Computer Systems， 2020， 41（5）：1030-1035. 10.3969/j.issn.1000-1220.2020.05.021
6	ZHANG Y W， CUI G M， ZHAO S， et al. IFOA4WSC： a quick and effective algorithm for QoS-aware service composition［J］. International Journal of Web and Grid Services， 2016， 12（1）：81-108. 10.1504/ijwgs.2016.074186
7	JATOTH C， GANGADHARAN G R， FIORE U， et al. QoS-aware big service composition using MapReduce based evolutionary algorithm with guided mutation［J］. Future Generation Computer Systems， 2018， 86： 1008-1018. 10.1016/j.future.2017.07.042
8	ZHANG Y P， JING Z H， ZHANG Y W. MR-IDPSO： a novel algorithm for large-scale dynamic service composition［J］. Tsinghua Science Technology， 2015， 20（6）：602-612. 10.1109/tst.2015.7349932
9	OZYURT B， AKCAYOL M A. A new topic modeling based approach for aspect extraction in aspect based sentiment analysis： SS-LDA［J］. Expert Systems with Applications， 2021， 168： No.114231. 10.1016/j.eswa.2020.114231
10	MIRJALILI S， MIRJALILI S M， LEWIS A. Grey wolf optimizer［J］. Advances in Engineering Software， 2014， 69： 46-61. 10.1016/j.advengsoft.2013.12.007
11	HATTA N M， ZAIN A M， SALLEHUDDIN R， et al. Recent studies on optimisation method of Grey Wolf Optimiser （GWO）： a review （2014‒2017）［J］. Artificial Intelligence Review， 2019， 52（4）： 2651-2683. 10.1007/s10462-018-9634-2
12	谈发明，赵俊杰，王琪. 一种改进非线性收敛方式的灰狼优化算法研究［J］. 微电子学与计算机， 2019， 36（5）：89-95.
	TAN F M， ZHAO J J， WANG Q. A grey wolf optimization algorithm with improved nonlinear convergence［J］. Microelectronics and Computer， 2019， 36（5）：89-95.
13	YUAN Y， ZHANG X G， SUN W X， et al. Optimal web service composition based on context-awareness and genetic algorithm［C］// Proceedings of the 2013 International Conference on Information Science and Cloud Computing Companion. Piscataway： IEEE， 2013： 660-667. 10.1109/iscc-c.2013.98
14	龙文，赵东泉，徐松金. 求解约束优化问题的改进灰狼优化算法［J］. 计算机应用， 2015， 35（9）：2590-2595. 10.11772/j.issn.1001-9081.2015.09.2590
	LONG W， ZHAO D Q， XU S J. Improved grey wolf optimization algorithm for constrained optimization problem［J］. Journal of Computer Applications， 2015， 35（9）：2590-2595. 10.11772/j.issn.1001-9081.2015.09.2590
15	郭振洲，刘然，拱长青，等. 基于灰狼算法的改进研究［J］. 计算机应用研究， 2017， 34（12）：3603-3606， 3610. 10.3969/j.issn.1001-3695.2017.12.019
	GUO Z Z， LIU R， GONG C Q， et al. Study on improvement of gray wolf algorithm［J］. Application Research of Computers， 2017， 34（12）：3603-3606， 3610. 10.3969/j.issn.1001-3695.2017.12.019
16	PANDA G， PRADHAN P M， MAJHI B. IIR system identification using cat swarm optimization［J］. Expert Systems with Applications， 2011， 38（10）： 12671-12683. 10.1016/j.eswa.2011.04.054
17	LÄMMEL R. Google’s MapReduce programming model - revisited［J］. Science of Computer Programming， 2008， 70（1）：1-30. 10.1016/j.scico.2007.07.001
18	ZHENG Z B， ZHANG Y L， LYU M R. Investigating QoS of real-world web services［J］. IEEE Transactions on Services Computing， 2014， 7（1）： 32-39. 10.1109/tsc.2012.34
19	石敏，刘建勋，周栋，等. 基于多重关系主题模型的Web服务聚类方法［J］. 计算机学报， 2019， 42（4）：820-836.
	SHI M， LIU J X， ZHOU D， et al. Multi-relational topic model-based approach for Web services clustering［J］. Chinese Journal of Computers， 2019， 42（4）：820-836.
20	STEVENS K， KEGELMEYER P， ANDRZEJEWSKI D， et al. Exploring topic coherence over many models and many topics［C］// Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Stroudsburg， PA： Association for Computational Linguistics， 2012：952-961.
21	KHALID N E A， FADZIL A F A， MANAF M. Adapting MapReduce framework for genetic algorithm with large population［C］// Proceedings of the 2013 IEEE Conference on Systems， Process and Control. Piscataway： IEEE， 2013：36-41. 10.1109/spc.2013.6735099

[1]	叶盛, 王菁, 辛建峰, 王桂玲, 郭陈虹. 云边环境下微服务组合系统的动态演化方法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1696-1704.
[2]	陈玉枚, 扈红超, 王亚文. 多变体系统服务质量及损耗评估方法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 876-884.
[3]	钟磊, 周允升, 余敦辉, 崔海波. 基于亲和力与研究方向覆盖率的审稿人推荐算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 430-436.
[4]	吴仁彪, 张振驰, 贾云飞, 乔晗. 云平台下基于截止时间的自适应调度策略[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 176-184.
[5]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[6]	周烁, 仇润鹤, 唐旻俊. 基于禁忌搜索和Q-learning的CR-NOMA系统的功率分配算法[J]. 计算机应用, 2021, 41(7): 2026-2032.
[7]	杨丰瑞, 霍娜, 张许红, 韦巍. 基于注意力机制的主题扩展情感对话生成[J]. 计算机应用, 2021, 41(4): 1078-1083.
[8]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[9]	廖水聪, 孙鹏, 刘星辰, 钟贇. 基于改进磷虾群算法的服务组合优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3652-3657.
[10]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[11]	杨威亚, 余正涛, 高盛祥, 宋燃. 基于跨语言神经主题模型的汉越新闻话题发现方法[J]. 计算机应用, 2021, 41(10): 2879-2884.
[12]	朱思淼, 魏世伟, 魏思恒, 余敦辉. 基于弹幕情感分析和主题模型的视频推荐算法[J]. 计算机应用, 2021, 41(10): 2813-2819.
[13]	尹春勇, 章荪. 面向短文本情感分类的端到端对抗变分贝叶斯方法[J]. 计算机应用, 2020, 40(9): 2536-2542.
[14]	田保军, 刘爽, 房建东. 融合主题信息和卷积神经网络的混合推荐算法[J]. 计算机应用, 2020, 40(7): 1901-1907.
[15]	徐金荣, 郭彩萍, 童恩栋. 面向服务遥感图像处理平台中时间感知的服务质量预测[J]. 计算机应用, 2020, 40(6): 1714-1721.

基于优化的灰狼算法的大规模Web服务组合

Large-scale Web service composition based on optimized grey wolf optimizer

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 21

相关文章 15

编辑推荐

Metrics