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

doi:10.11772/j.issn.1001-9081.2021091556

Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (10): 3162-3169.DOI: 10.11772/j.issn.1001-9081.2021091556

• Computer software technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

针对大规模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

CLC Number:

TP311

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.

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

Figures/Tables 14

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$

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$

Fig. 1 Large-scale Web service composition method framework

Fig. 2 Example of abstract service composition sequence

Fig. 3 LDA topic model

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个单词

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个单词

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

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

Fig. 4 Convergence factor change curve

Fig. 5 Composite service encoding pattern

Tab. 5 Structure of key-value pair

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

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

Fig. 7 Precision under different JS divergence thresholds

Fig. 8 Performance comparison with different iteration times

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

References 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]	Yun OU, Kaiqing ZHOU, Pengfei YIN, Xuewei LIU. Improved grey wolf optimizer algorithm based on dual convergence factor strategy [J]. Journal of Computer Applications, 2023, 43(9): 2679-2685.
[2]	Sheng YE, Jing WANG, Jianfeng XIN, Guiling WANG, Chenhong GUO. Dynamic evolution method for microservice composition systems in cloud-edge environment [J]. Journal of Computer Applications, 2023, 43(6): 1696-1704.
[3]	Yumei CHEN, Hongchao HU, Yawen WANG. Quality of service and loss evaluation method for multi-variant system [J]. Journal of Computer Applications, 2023, 43(3): 876-884.
[4]	Lei ZHONG, Yunsheng ZHOU, Dunhui YU, Haibo CUI. Reviewer recommendation algorithm based on affinity and research direction coverage [J]. Journal of Computer Applications, 2023, 43(2): 430-436.
[5]	WU Renbiao, ZHANG Zhenchi, JIA Yunfei, QIAO Han. Adaptive scheduling strategy based on deadline under cloud platform [J]. Journal of Computer Applications, 2023, 43(1): 176-184.
[6]	ZHOU Shuo, QIU Runhe, TANG Minjun. Power allocation algorithm for CR-NOMA system based on tabu search and Q-learning [J]. Journal of Computer Applications, 2021, 41(7): 2026-2032.
[7]	ZHAO Qiuyun, WEI Le, SHU Hongping. Construction method of cloud manufacturing virtual workshop for manufacturing tasks [J]. Journal of Computer Applications, 2021, 41(7): 2003-2011.
[8]	XU Feixue, LIU Qinming, OUYANG Hailing, YE Chunming. Optimization of maintenance strategy model for multi-component system based on performance-based contract [J]. Journal of Computer Applications, 2021, 41(4): 1184-1191.
[9]	YANG Fengrui, HUO Na, ZHANG Xuhong, WEI Wei. Topic-expanded emotional conversation generation based on attention mechanism [J]. Journal of Computer Applications, 2021, 41(4): 1078-1083.
[10]	Shuicong LIAO, Peng SUN, Xingchen LIU, Yun ZHONG. Service composition optimization based on improved krill herd algorithm [J]. Journal of Computer Applications, 2021, 41(12): 3652-3657.
[11]	Ying LEI, Wanbo ZHENG, Wei WEI, Yunni XIA, Xiaobo LI, Chengwu LIU, Hong XIE. Task offloading method based on probabilistic performance awareness and evolutionary game strategy in “cloud + edge” hybrid environment [J]. Journal of Computer Applications, 2021, 41(11): 3302-3308.
[12]	YANG Weiya, YU Zhengtao, GAO Shengxiang, SONG Ran. Chinese-Vietnamese news topic discovery method based on cross-language neural topic model [J]. Journal of Computer Applications, 2021, 41(10): 2879-2884.
[13]	HAO Pengfei, CHI Rui, QU Zhijian, TU Hongbin, CHI Xuexin, ZHANG Diyou. Improved grey wolf optimizer for location selection problem of railway logistics distribution center [J]. Journal of Computer Applications, 2021, 41(10): 2905-2911.
[14]	ZHU Simiao, Wei Shiwei, WEI Siheng, YU Dunhui. Video recommendation algorithm based on danmaku sentiment analysis and topic model [J]. Journal of Computer Applications, 2021, 41(10): 2813-2819.
[15]	YIN Chunyong, ZHANG Sun. End-to-end adversarial variational Bayes method for short text sentiment classification [J]. Journal of Computer Applications, 2020, 40(9): 2536-2542.

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

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 21

Related Articles 15

Recommended Articles

Metrics