基于改进磷虾群算法的服务组合优化

doi:10.11772/j.issn.1001-9081.2021040699

《计算机应用》唯一官方网站 ›› 2021, Vol. 41 ›› Issue (12): 3652-3657.DOI: 10.11772/j.issn.1001-9081.2021040699

• 先进计算 • 上一篇

基于改进磷虾群算法的服务组合优化

廖水聪¹(), 孙鹏¹, 刘星辰², 钟贇³

^1.空军工程大学信息与导航学院，西安 710077
^2.93182部队，沈阳 110015
^3.空军工程大学装备管理与无人机工程学院，西安 710051

收稿日期:2021-05-06 修回日期:2021-06-16 接受日期:2021-06-18 发布日期:2021-12-28 出版日期:2021-12-10
通讯作者: 廖水聪
作者简介:孙鹏（1972—），男，河北安平人，教授，博士，主要研究方向：指挥信息系统、指挥决策与分析
刘星辰（1982—），男，辽宁沈阳人，工程师，主要研究方向：军用通信
钟贇（1990—），男，江苏金坛人，博士，主要研究方向：指挥信息系统、指挥决策与分析。

Service composition optimization based on improved krill herd algorithm

Shuicong LIAO¹(), Peng SUN¹, Xingchen LIU², Yun ZHONG³

^1.College of Information and Navigation，Air Force Engineering University，Xi’an Shaanxi 710077，China
^2.93182 Troop，Shenyang Liaoning 110015，China
^3.College of Equipment Management and UAV Engineering，Air Force Engineering University，Xi’an Shaanxi 710051，China

Received:2021-05-06 Revised:2021-06-16 Accepted:2021-06-18 Online:2021-12-28 Published:2021-12-10
Contact: Shuicong LIAO
About author:SUN Peng， born in 1972， Ph. D.， professor. His research interests include command information system， command decision and analysis.
LIU Xingchen， born in 1982， engineer. His research interests include military communication.
ZHONG Yun， born in 1990， Ph. D. His research interests include command information system， command decision and analysis.

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP391.3

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

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.

图/表 14

图1 服务组合优化示意图

Fig. 1 Schematic diagram of service composition optimization

图2 服务组合结构

Fig. 2 Service composition structures

表1 不同结构下复合服务QoS计算公式

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$

表1 不同结构下复合服务QoS计算公式

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$

图3 PRKH算法流程

Fig. 3 PRKH algorithm flowchart

表2 各算法参数设置

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$

表2 各算法参数设置

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$

图4 第6轮迭代结果

Fig. 4 Results of the sixth iteration

图5 PRKH、RKH、PKH和KH算法最佳适应度值对比

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

图6 PRKH、RKH、PKH和KH算法最佳适应度数据箱线图

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

表3 PRKH、RKH、PKH和KH算法最佳适应度值标准差

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

图7 PRKH、RKH、PKH和KH算法时间开销箱线图

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

图8 PRKH、PSO、ABC和FPA最佳适应度对比

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

图9 PRKH、PSO、ABC和FPA最佳适应度数据箱线图

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

表4 PRKH、PSO、ABC和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

图10 PRKH、PSO、ABC和FPA的时间开销对比

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

参考文献 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]	周烁, 仇润鹤, 唐旻俊. 基于禁忌搜索和Q-learning的CR-NOMA系统的功率分配算法[J]. 计算机应用, 2021, 41(7): 2026-2032.
[2]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[3]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[4]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[5]	徐金荣, 郭彩萍, 童恩栋. 面向服务遥感图像处理平台中时间感知的服务质量预测[J]. 计算机应用, 2020, 40(6): 1714-1721.
[6]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[7]	罗际炜, 瞿涛, 邓徳祥. 嵌入式多通道无线视频传输的码率自适应算法[J]. 计算机应用, 2020, 40(4): 1119-1126.
[8]	刘惠剑, 刘峻松, 王佳伟, 薛岗. 基于过程划分技术的服务组合拆分方法[J]. 计算机应用, 2020, 40(3): 799-805.
[9]	毛昕怡, 钮俊, 丁雪儿, 张开乐. 基于模型检测的微服务组合平台QoS验证[J]. 计算机应用, 2020, 40(11): 3267-3272.
[10]	孙天齐, 胡建鹏, 黄娟, 樊莹. 云环境下Web应用带宽资源预测与管理[J]. 计算机应用, 2020, 40(1): 181-187.
[11]	梅广, 邹恒华, 张甜, 许维胜. 主数据管理驱动的高校信息化SOA建设[J]. 计算机应用, 2019, 39(9): 2675-2682.
[12]	王妍, 马秀荣, 单云龙. 长期演进系统基于加权平均时延的下行资源调度[J]. 计算机应用, 2019, 39(5): 1429-1433.
[13]	沈莹, 黄樟灿, 谈庆, 刘宁. 基于动态压力控制算子的磷虾群算法[J]. 计算机应用, 2019, 39(3): 663-667.
[14]	丁成, 王秋萍, 王晓峰. 基于广义反向学习的磷虾群算法及其在数据聚类中的应用[J]. 计算机应用, 2019, 39(2): 336-342.
[15]	李磊, 薛洋, 吕念玲, 冯敏. 基于李雅普诺夫优化的容器云队列在线任务和资源调度设计[J]. 计算机应用, 2019, 39(2): 494-500.

基于改进磷虾群算法的服务组合优化

Service composition optimization based on improved krill herd algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 17

相关文章 15

编辑推荐

Metrics