Service composition optimization based on improved krill herd algorithm

doi:10.11772/j.issn.1001-9081.2021040699

Abstract

Abstract:

In the Service Oriented Architecture （SOA）， an improved Krill Herd algorithm PRKH with adaptive crossover and random perturbation operator was proposed to solve the problem of easily falling into local optimum and high time cost in the process of service composition optimization. Firstly， a service composition optimization model was established based on Quality of Service （QoS）， and the QoS calculation formulas and normalization methods under different structures were given. Then， based on the Krill Herd （KH） algorithm， the adaptive crossover probability and the random disturbance based on the actual offset were added to achieve a good balance between the global search ability and the local search ability of krill herd. Finally， through simulation， the proposed algorithm was compared with KH algorithm， Particle Swarm Optimization （PSO） algorithm， Artificial Bee Colony （ABC） algorithm and Flower Pollination Algorithm （FPA）. Experimental results show that the PRKH algorithm can find better QoS composite services faster.

Key words: Service Oriented Architecture (SOA), service composition, Quality of Service (QoS), service composition optimization, Krill Herd (KH) algorithm

摘要：

面向服务的架构（SOA）下，针对服务组合优化过程中易陷入局部最优、时间开销大的问题，提出一种加入自适应交叉算子和随机扰动算子的改进磷虾群算法PRKH。首先基于服务质量（QoS）建立了服务组合优化模型，并给出不同结构下QoS的计算公式和归一化处理方法。然后在磷虾群（KH）算法的基础上加入自适应的交叉概率和基于实际偏移量的随机扰动，从而在磷虾群的全局搜索能力和局部搜索能力之间达到良好平衡。最后通过仿真，把所提算法与KH算法、粒子群优化（PSO）算法、人工蜂群（ABC）算法和花朵授粉算法（FPA）进行对比，实验结果表明，PRKH算法能够更快找到QoS更优的复合服务。

关键词: 面向服务的架构, 服务组合, 服务质量, 服务组合优化, 磷虾群算法

CLC Number:

TP391.3

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.

廖水聪, 孙鹏, 刘星辰, 钟贇. 基于改进磷虾群算法的服务组合优化[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3652-3657.

Figures/Tables 14

Fig. 1 Schematic diagram of service composition optimization

Fig. 2 Service composition structures

Tab. 1 Calculation formulas of composite service QoS under different structures

QoS属性	顺序	并行	选择	循环
响应时间t	$∑ j = 1 n t j$	$m a x (t j)$	$∑ j = 1 n p j t j$	$k ⋅ t j$
服务费用c	$∑ j = 1 n c j$	$∑ j = 1 n c j$	$∑ j = 1 n p j c j$	$k ⋅ c j$
可用性ava	$∏ j = 1 n a j$	$∏ j = 1 n a j$	$∑ j = 1 n p j a j$	$(a j) k$
可靠性rel	$∏ j = 1 n r j$	$∏ j = 1 n r j$	$∑ j = 1 n p j r j$	$(r j) k$

Tab. 1 Calculation formulas of composite service QoS under different structures

QoS属性	顺序	并行	选择	循环
响应时间t	$∑ j = 1 n t j$	$m a x (t j)$	$∑ j = 1 n p j t j$	$k ⋅ t j$
服务费用c	$∑ j = 1 n c j$	$∑ j = 1 n c j$	$∑ j = 1 n p j c j$	$k ⋅ c j$
可用性ava	$∏ j = 1 n a j$	$∏ j = 1 n a j$	$∑ j = 1 n p j a j$	$(a j) k$
可靠性rel	$∏ j = 1 n r j$	$∏ j = 1 n r j$	$∑ j = 1 n p j r j$	$(r j) k$

Fig. 3 PRKH algorithm flowchart

Tab. 2 Parameter setting of each algorithm

算法	参数设置
PRKH	磷虾数=25， $I m a x = 500$ ， $V f o o d = 0.02$ ， $D m a x = 0.005, N m a x = 0.01$
KH
RKH
PKH
PSO	粒子规模 $N = 500$ ， $I m a x = 500$ ，惯性权重 $w = 0.72$ ，自学习因子 $c 1 = 2.05$ ，全局学习因子 $c 2 = 2.05$
ABC	种群规模 $N = 500$ ， $I m a x = 500$ ，蜜源停留次数限制 $L 1 = 10$ ，加速系数上限 $L 2 = 1$
FPA	种群规模 $N = 500$ ，最大迭代次数 $I = 500$ ，转换概率 $p = 0.8$

Tab. 2 Parameter setting of each algorithm

算法	参数设置
PRKH	磷虾数=25， $I m a x = 500$ ， $V f o o d = 0.02$ ， $D m a x = 0.005, N m a x = 0.01$
KH
RKH
PKH
PSO	粒子规模 $N = 500$ ， $I m a x = 500$ ，惯性权重 $w = 0.72$ ，自学习因子 $c 1 = 2.05$ ，全局学习因子 $c 2 = 2.05$
ABC	种群规模 $N = 500$ ， $I m a x = 500$ ，蜜源停留次数限制 $L 1 = 10$ ，加速系数上限 $L 2 = 1$
FPA	种群规模 $N = 500$ ，最大迭代次数 $I = 500$ ，转换概率 $p = 0.8$

Fig. 4 Results of the sixth iteration

Fig. 5 Best fitness comparison of PRKH， RKH， PKH and KH

Fig. 6 Best fitness data box plot of PRKH， RKH， PKH and KH algorithms

Tab. 3 Standard deviations of best fitness values of PRKH， RKH， PKH and KH

算法	标准差	算法	标准差
PRKH	0.006 74	PKH	0.007 85
RKH	0.008 11	KH	0.007 70

Fig. 7 Time cost box plot of PRKH， RKH， PKH and KH algorithms

Fig. 8 Best fitness comparison of PRKH， PSO， ABC and FPA

Fig. 9 Best fitness data box plot of PRKH， PSO， ABC and FPA

Tab. 4 Standard deviation of best fitness values of PRKH， PSO， ABC and FPA

算法	标准差	算法	标准差
PRKH	0.007 38	ABC	0.004 37
PSO	0.004 54	FPA	0.002 78

Fig. 10 Time cost comparison of PRKH， PSO， ABC and FPA

References 17

1	BOUZARY H， CHEN F F. A classification-based approach for integrated service matching and composition in cloud manufacturing［J］. Robotics and Computer-Integrated Manufacturing， 2020， 66： No.101989. 10.1016/j.rcim.2020.101989
2	YAGHOUBI M， MAROOSI A. Simulation and modeling of an improved multi-verse optimization algorithm for QoS-aware web service composition with service level agreements in the cloud environments［J］. Simulation Modelling Practice and Theory， 2020， 103： No.102090. 10.1016/j.simpat.2020.102090
3	张苑蕾，邵清，李刘静，等. 融合遗传聚类的可靠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
4	DU M M. An improved genetic algorithm for Web service composition optimization［J］. World Scientific Research Journal， 2020， 6（10）：369-379.
5	夏亚梅，程渤，陈俊亮，等. 基于改进蚁群算法的服务组合优化［J］. 计算机学报， 2012， 35（2）：2270-2281. 10.3724/SP.J.1016.2012.00270
	XIA Y M， CHENG B， CHEN J L， et al. Optimizing services composition based on improved ant colony algorithm［J］. Chinese Journal of Computers， 2012， 35（2）：270-281. 10.3724/SP.J.1016.2012.00270
6	YANG Y F， YANG B， WANG S L， et al. A dynamic ant-colony genetic algorithm for cloud service composition optimization［J］. The International Journal of Advanced Manufacturing Technology， 2019， 102（1/2/3/4）：355-368. 10.1007/s00170-018-03215-7
7	温涛，盛国军，郭权，等. 基于改进粒子群算法的Web服务组合［J］. 计算机学报， 2013， 36（5）：1031-1046. 10.3724/SP.J.1016.2013.01031
	WEN T， SHENG G J， GUO Q， et al. Web service composition based on modified particle swarm optimization［J］. Chinese Journal of Computers， 2013， 36（5）：1031-1046. 10.3724/SP.J.1016.2013.01031
8	郭星，陈姗姗，张以文，等. 烟花粒子群优化算法在Web服务组合上的应用［J］. 小型微型计算机系统， 2018， 39（6）：1312-1316. 10.3969/j.issn.1000-1220.2018.06.035
	GUO X， CHEN S S， ZHANG Y W， et al. Application of fireworks particle swarm optimization algorithm in Web service composition［J］. Journal of Chinese Computer Systems， 2018， 39（6）：1312-1316. 10.3969/j.issn.1000-1220.2018.06.035
9	宋航，王亚丽，刘国奇，等. 基于改进多目标蜂群算法的Web服务组合优化方法［J］. 东北大学学报（自然科学版）， 2019， 40（6）：777-782. 10.12068/j.issn.1005-3026.2019.06.004
	SONG H， WANG Y L， LIU G Q， et al. Web service composition optimization method based on improved multi-objective artificial bee colony algorithm［J］. Journal of Northeastern University （Natural Science）， 2019， 40（6）：777-782. 10.12068/j.issn.1005-3026.2019.06.004
10	SEGHIR F， KHABABA A， SEMCHEDINE F. An interval-based multi-objective artificial bee colony algorithm for solving the web service composition under uncertain QoS［J］. The Journal of Supercomputing， 2019， 75（9）：5622-5666. 10.1007/s11227-019-02814-9
11	GANDOMI A H， ALAVI A H. Krill herd： a new bio-inspired optimization algorithm［J］. Communications in Nonlinear Science and Numerical Simulation， 2012， 17（12）：4831-4845. 10.1016/j.cnsns.2012.05.010
12	沈莹，黄樟灿，谈庆，等. 基于动态压力控制算子的磷虾群算法［J］. 计算机应用， 2019， 39（3）：663-667. 10.11772/j.issn.1001-9081.2018081661
	SHEN Y， HUANG Z C， TAN Q， et al. Krill herd algorithm based on dynamic pressure control operator［J］. Journal of Computer Applications， 2019， 39（3）：663-667. 10.11772/j.issn.1001-9081.2018081661
13	WANG G G， GUO L H， GANDOMI A H， et al. Simulated annealing-based krill herd algorithm for global optimization［J］. Abstract and Applied Analysis， 2013， 2013： No.213853. 10.1155/2013/213853
14	WANG G G， GUO L H， WANG H Q， et al. Incorporating mutation scheme into krill herd algorithm for global numerical optimization［J］. Neural Computing and Applications， 2014， 24（3/4）：853-871. 10.1007/s00521-012-1304-8
15	LI L L， ZHOU Y Q， XIE J. A free search krill herd algorithm for functions optimization［J］. Mathematical Problems in Engineering， 2014， 2014： No.936374. 10.1155/2014/936374
16	丁成，王秋萍，王晓峰. 基于广义反向学习的磷虾群算法及其在数据聚类中的应用［J］. 计算机应用， 2019， 39（2）：336-342. 10.11772/j.issn.1001-9081.2018061437
	DING C， WANG Q P， WANG X F. Krill herd algorithm based on generalized opposition-based learning and its application in data clustering［J］. Journal of Computer Applications， 2019， 39（2）：336-342. 10.11772/j.issn.1001-9081.2018061437
17	任子武，伞冶. 自适应遗传算法的改进及在系统辨识中应用研究［J］.系统仿真学报， 2006， 18（1）：41-43， 66. 10.3969/j.issn.1004-731X.2006.01.011
	REN Z W， SAN Y. Improved adaptive genetic algorithm and its application research in parameter identification［J］. Journal of System Simulation， 2006， 18（1）：41-43， 66. 10.3969/j.issn.1004-731X.2006.01.011

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[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]	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.
[8]	GUO Shujie, LI Zhihua, LIN Kaiqing. Fuzzy membership degree based virtual machine placement algorithmin cloud environment [J]. Journal of Computer Applications, 2020, 40(5): 1374-1381.
[9]	LUO Chiwei, QU Tao, DENG Dexiang. Rate adaption algorithm for embedded multi-channel wireless video transmission [J]. Journal of Computer Applications, 2020, 40(4): 1119-1126.
[10]	LIU Huijian, LIU Junsong, WANG Jiawei, XUE Gang. Service composition partitioning method based on process partitioning technology [J]. Journal of Computer Applications, 2020, 40(3): 799-805.
[11]	MAO Xinyi, NIU Jun, DING Xueer, ZHANG Kaile. QoS verification of microservice composition platform based on model checking [J]. Journal of Computer Applications, 2020, 40(11): 3267-3272.
[12]	SUN Tianqi, HU Jianpeng, HUANG Juan, FAN Ying. Bandwidth resource prediction and management of Web applications hosted on cloud [J]. Journal of Computer Applications, 2020, 40(1): 181-187.
[13]	MEI Guang, ZOU Henghua, ZHANG Tian, XU Weisheng. SOA based education informatization driven by master data management [J]. Journal of Computer Applications, 2019, 39(9): 2675-2682.
[14]	WANG Yan, MA Xiurong, SHAN Yunlong. Downlink resource scheduling based on weighted average delay in long term evolution system [J]. Journal of Computer Applications, 2019, 39(5): 1429-1433.
[15]	SHEN Ying, HUANG Zhangcan, TAN Qing, LIU Ning. Krill herd algorithm based on dynamic pressure control operator [J]. Journal of Computer Applications, 2019, 39(3): 663-667.