基于文化遗传算法的QoS感知的服务组合

柳正利，李兵，强保华，王静

基于文化遗传算法的QoS感知的服务组合

柳正利1，李兵1，强保华2，王静3

(1. 武汉大学 计算机学院，湖北 武汉，430079；2. 桂林电子科技大学 广西可信软件重点实验室，广西 桂林，541004； 3. 中国电子技术标准化研究院，北京，100007)

为了提高服务组合的效率，提出1种改进的基于文化遗传算法的QoS感知的服务组合方法。首先构建社会种群和信仰双层空间，然后利用接收函数从社会种群中提取种群进化学习到的知识并更新信仰空间，进而利用信仰空间来引导社会种群进化，加快算法的收敛性，提高组合效率。研究结果表明：与传统的文化遗传算法和经典的遗传算法相比，本文提出的算法收敛所需的迭代次数明显降低，执行效率和收敛速度均有所提高。

服务组合；QoS感知；文化遗传算法；服务选择

随着Web服务技术的成熟，软件系统的架构模式逐渐从传统的面向组件演变为面向服务的计算模式。凭借强大的可扩展性和良好的异构资源整合能力，Web服务为企业之间进行的无缝业务集成提供了可能。随着大量具有相同功能的开放Web服务的不断汇聚，服务合成的关键问题不再是找到所需服务，如何从海量Web服务中快速挑选出满足用户需求、可信度高、具有良好质量保障的Web服务，成为服务组合领域的新课题[1]。现代商业生态系统变得日益庞大与复杂，企业业务环境复杂多变，这对组合服务的功能需求和非功能需求都提出了越来越高的要求。对于业务系统下的每个工作流节点，都存在众多功能类似但服务质量不同的服务可供选择。从服务质量的角度出发，对这些候选服务集进行筛选与组合，在服务数量庞大的情况下，可能会出现“组合爆炸”，这是一个典型的NP难问题。遗传算法通过借鉴生物进化原理，运用选择、交叉、变异等自然进化过程对个体执行遗传操作，并借助适应度函数对种群个体实行“优胜劣汰”评价，这样经过不断地迭代，最终适应度最高的个体胜出。由于遗传算法具备良好的可扩展性和较强的全域搜索能力，适合用于解决像服务组合这样的NP难问题[2]。但是，由于遗传算法采用随机进化策略，迭代过程缺乏知识指导，导致算法搜索方向呈现一定的盲目性。而文化算法是一种基于知识的双层进化系统，能够从进化的种群中抽取待解决问题的知识，并反馈这些知识以指导搜索过程，从而加快算法收敛，防止算法出现“早熟”现象。将文化算法和遗传算法相结合来处理组合优化问题，已成为众多研究者的选择。KO等[3]从服务组合方案的角度出发，将基于QoS(quality of service)感知的Web服务组合分为基于工作流、基于QoS语义和基于QoS属性计算这3类。基于工作流的服务组合方式，一般是将工作流和QoS结合，利用动态服务组合技术，在流程运行过程中动态绑定Web服务[4−5]；或者是利用Web语义技术和工作流结构，完成Web服务组合任务[6]；或者是将绿色计算和工作流有机结合，考虑服务组合过程中的能耗感知，求得能耗优化的组合服务[7]。基于工作流的服务组合方式，实质上是一种静态绑定机制：当流程模板确定以后，从节点功能出发，为每个流程节点绑定可满足其功能需求的具体服务，而不考虑服务的全局QoS信息；即使考虑了QoS信息，也多是局部服务选择。基于语义的服务组合方式，一般是将Web语义技术[8−9]和其他机制(如智能算法[10]、智能体[11]、描述逻辑[12]和本体[13]等)相结合，实现服务匹配，或者是借助人工智能规划来实现Web服务组合[14]。基于QoS语义的服务组合，大多是根据服务的QoS语义信息，从候选服务集中查找与用户功能要求相匹配的服务，其本质仍旧是一种基于功能的服务组合，虽然其支持考虑服务质量的单一服务选择，但无法根据用户对服务质量的需求处理具有全局QoS约束的服务组合问题。基于QoS属性计算的方式从QoS约束的角度可分为局部优化目标下的服务组合和全局优化目标下的服务组合。局部优化方法主要是采用层次分析方法[15]和多属性决策[16]来实现局部服务选择。相对于全局QoS约束的服务组合方法，局部优化方法计算量较小，但是求得的解仅为局部最优解，无法有效处理全局约束问题。而全局优化的方法通常是借助效用函数将组合服务的QoS属性归一化，通过反复迭代运算，最后求得全局最优解。全局优化方法主要采用遗传算法[1]、粒子群算法[17−18]、蚁群算法[19]、模拟退火算法[20]、整数规划[21]和人工智能[22]等方法。除了上述提到的方法外，其他诸如最佳路径算法、剪枝法等也常被用于处理服务组合问题。本文作者将遗传算法和文化算法相结合，用遗传算法来实现文化算法的社会种群空间进化，运用信仰空间提取的知识来指导社会种群空间的进化，以期提高算法的收敛速度和服务组合效率。

1 问题描述

2 基于文化遗传算法的服务组合

2.1 算法总体框架

文化遗传算法框架如图1所示。其中，社会种群空间由遗传算法的个体来构造；更新函数主要用来更新信仰空间的知识；接收函数用于从社会群体空间接收一定数量的个体进入信仰空间以形成知识；影响函数主要通过信仰空间的知识来影响社会群体空间的进化方向；生成函数主要用于生成种群；选择函数主要用于遗传操作中选择交叉的个体；评价函数用于评价当前种群的适应度。

图1 文化遗传算法框架

2.2 编码

结合服务组合的特点，采用矩阵编码方式来表示染色体的结构。矩阵的每1列表示同一类抽象服务，每1行表示1个组合路径，每个组合路径包含多个具体服务，每个具体服务对应着其QoS属性记录。染色体编码结构如图2所示。其中，为组合路径中的所有具体服务数，每1个具体服务的QoS信息包括价格(cost)、响应时间(time)、信誉度(reputation)、可用性(availability)共4种属性；w，h，l和s分别为某一类抽象服务(,=1, 2, …,)。

图2 染色体编码结构

2.3 遗传算子

1) 选择算子。

每次从上一代种群选择2个染色体进行交叉，这里采用轮盘赌算法选择2条染色体。具体选择过程描述如下。

①=(1,2,3,…,f)，表示上1代种群中每个个体的适应度，其中为种群数量。

②分别计算每个个体x被选中并进入下一代遗传的概率。

③计算累计概率。

④每次产生1个随机数，若在[(x),(x1))区间内，则第个个体被选中。

2) 相似染色体排斥交叉策略。

同源染色体在交叉之后对种群多样性的影响有限，为了避免不必要的交叉操作，提高交叉效率，本文作者提出1种相似染色体排斥机制。设1=(1,1,1,1)，2=(2,2,2,2)，分别表示被选中的2条染色体，2条染色体的相似度用欧几里得距离来表征。

情形1：若2条染色体的相似度≤0.5，则认为2条染色体相似度过高，不进行交叉，采取变异策略，通过引入外部基因以扩大种群多样性。

情形2：若2条染色体的相似度＞0.5，则认为2条染色体极不相似，可以进行交叉操作。

3) 变异算子。

在变异操作过程中，主要采用随机变异策略。1=Rand(1,)，选择要变异的染色体，其中为种群数量；2=Rand(1,)，其中为抽象服务种类。

生成随机数(0.01≤≤1.00)，将其作为该染色体的变异概率，给定种群变异概率mu(0.01＜mu＜1.00)。若＜mu，则在第代种群里随机选取1个基因位P[1][2]，然后将该基因位替换掉+1代种群对应染色体的等位基因，即P1[1][2]=P[1][2]；若＞mu，则不进行变异操作。

4) 精英个体保留。

在遗传算法执行过程中，每进化1代，就将当前种群的最优个体与历史最优个体比较，若当前代的最优个体比历史最优个体的适应度高，则用当前代的最优个体替换掉历史最优个体，并将当前代的最优个体复制到下一代种群的第0个位置，并且该最优个体不参与交叉、变异操作，同时用历史适应度最大的个体替换当前代适应度最小的个体。

上述过程具体描述如下。

算法1：精英个体保留机制。

输入：当前代服务个体组成的种群c，历史最优个体C()，当前代最优个体C(+1)。

输出：新一代种群c+1。

算法流程如下。

步骤1：比较当前代最优个体的适应度值fit(C(+1))与历史最优个体的适应度(C())的大小；

步骤2：若(C(+1))＞(C())，则用当前代最优个体C(+1)替换掉历史最优个体C()，用历史最优个体C()替换掉当前代种群最差个体b(+1)。

步骤3：若(C(+1))＜(C())，则用历史最优个体C()替换掉当前代最优个体C(+1)，用当前代适应度最优个体C(+1)替换掉当前代适应度最差个体b(+1)。

步骤4：将历史最优个体复制到新种群。

2.4 信仰空间

1) 信仰空间的设计。

在文化框架中，信仰空间主要用来保存进化过程中种群形成的知识。基于QoS感知的服务组合问题是1个离散优化问题，因此，采用环境知识来表示文化算法的信仰空间。信仰空间定义为二元组<,[]>，其中为最优个体集合，[]为第最优个体对应的适应度。

2) 信仰空间的更新。

算法2：信仰空间更新算法。

输出：新的信仰空间。

算法流程如下。

步骤1：对当前代种群c执行进化操作，记录进化代数。

步骤2：用进化代数对进行求模运算，若计算结果为0，则计算当前代种群c的每个个体的适应度(c(I))，并对适应度进行排序。

步骤4：更新信仰空间。

2.5 适应度函数设计

为评估当前种群的适应度，构建效用函数如下：

(4)

若QoS属性为正属性(如信誉度和可用性)，则

若QoS属性为负属性(如价格和响应时间)，则

2.6 算法执行流程

利用改进的文化遗传算法求解服务组合问题的基本步骤如下。

步骤1：构造初始社会种群，进而利用适应度函数评价种群空间的所有个体的适应度。

步骤2：对所有个体的适应度进行排序，利用接收函数从初始种群中选择若干适应度较高的个体，产生和初始化信仰空间。

步骤3：对社会种群个体执行遗传进化操作。

步骤4：每到1个进化周期，借助影响函数引导社会种群空间个体的交叉、变异等遗传操作，使种群向适应度高的方向进化，并生成相应个数的下一代个体。

步骤5：对当前代社会种群空间个体进行评估，并利用接收函数将较优个体输送到信仰空间，更新信仰空间的知识。

步骤6：若不满足停止条件，则重复步骤3至步骤5，直到满足最大进化代数或达到算法终止条件 为止。

3 实验

3.1 实验介绍

3.2 实验结果及分析

1) 适应度对比。

本组实验中共有4类抽象服务，每类抽象服务数为50，进化代数在500~5 000之间，适应度对比结果分别如图3和图4所示。

1—TCGA；2—ICGA；3—IGA。

1—TCGA；2—ICGA；3—IGA。

从图3和图4可以看出：在不同进化代数和不同候选服务数量的情况下，本文提出的ICGA所求的最优服务的适应度均比TCGA和IGA的高，这说明ICGA比TCGA和IGA具有更好强搜索能力。从图3还可以看出：本文提出的ICGA算法相较于TCGA算法和IGA算法具有更好的收敛性。这是因为本文提出的改进文化遗传算法在进化过程中，采用了最优个体保留的精英主义策略与相似染色体排斥机制，既能避免同源染色体之间的无效交叉，又能利用信仰空间的知识引导社会种群向最优解方向靠近，使得社会种群空间的进化呈现一定的方向性。由此可见，与其他2种方法相比，采用本文提出的ICGA方法求得的种群的适应度更高，而且收敛性更好。

2) 执行时间对比。

图5所示为不同服务数量下3种算法执行时间的比较。本组实验共有4类抽象服务，每类抽象服务对应的具体服务数量范围为100~500，进化代数均为500。

1—ICGA；2—TCGA；3—IGA。

从图5可以看出：ICGA的执行时间比TCGA以及IGA的略多。这是因为ICGA增加了染色体相似度计算和精英个体保留机制，需要花费额外的计算时间。

4 结论

1) 提出1种改进的文化遗传算法(ICGA)用于Web服务组合，并采用信仰空间和种群空间的双层进化机制。

2) 在进化过程中，采用精英保留策略和相似染色体排斥策略来控制种群的交叉，有效地防止近亲染色体的无效交叉；通过在当前种群外部引入基因片段的方式，扩大了种群染色体的多样性。

3) ICGA算法能够有效地实现服务组合，并具有较强的搜索能力和较高的收敛速度。

[1] CHEN Wuhui, PAIK I. Toward better quality of service composition based on a globe social service network[J]. IEEE Transaction on Service Computing, 2015, 26(5):1466−1476.

[2] ALRIFAI M, SKOUTAS D, RISSE T. Selecting skyline services for QoS-based web service composition[C]// Proceedings of 19th International Conference on World Wide Web. North Carolina, USA: ACM, 2010: 11−20.

[3] KO J M, KIM C O, KWON I H. Quality-of-service oriented web service composition algorithm and planning architecture[J]. Journal of System and Software, 2008, 81(11): 2079−2090.

[4] 苑迎春, 王克俭, 韩宪忠, 等. 基于工作流的Web服务组合多视图模型[J].计算机集成制造系统, 2010, 16(1): 30−36. YUAN Yingchun, WANG Kejian, HAN Xianzhong, et al. Multi-view model for web service composition based on workflow[J]. Computer Integrated Manufacturing Systems, 2010, 16(1):30−36.

[5] YU Genong, ZHAO Peisheng, DI Liping, et al. BPELPower-a BPEL execution engine for geospatial web service[J]. Computers and Geosciences, 2012, 47: 87−101.

[6] 赵松, 王红, 阎嫕. Web服务组合工作流中扩展UDDI的设计与实现[J]. 计算机工程与设计, 2009, 30(1): 217−221. ZHAO Song, WANG Hong, YAN Yi. Design and implementation of extending UDDI in workflow composed of web services[J]. Computer Engineering and Design, 2009, 30(1): 217−221.

[7] 朱勇, 罗军舟, 李伟.一种工作流环境下能耗感知的多路径服务组合方法[J].计算机学报, 2012,35(3): 627−638. ZHU Yong, LUO Junzhou, LI Wei. An approach for energy aware multipath service composition based on workflow[J]. Chinese Journal of Computers, 2012, 35(3): 627−638.

[8] MIER P R, PEDRINACI C, LAMA M, et al. An integrated semantic web service discovery and composition framework[J]. IEEE Transaction on Service Computing, 2016, 9(4):537−550.

[9] JEMIMA D D, KARPAGAM G R. Conceptual framework for semantic web service composition[C]//2016 Fifth International Conference on Recent Trends in Information Technologies. New York,USA: IEEE, 2016: 1−6.

[10] 张佩云, 黄波, 孙亚民.一种基于语义与QoS感知的Web服务匹配机制[J]. 计算机研究与发展, 2010, 47(5): 780−787. ZHANG Peiyun, HUANG Bo, SUN Yamin. A web services matching mechanism based on semantics and QoS-aware aspect[J]. Journal of Computer Research and Development, 2010,47(5):780−787.

[11] 刘华鹏, 刘胜全, 刘艳, 等.基于主体和QoS的语义Web服务组合方法[J].计算机工程, 2013, 39(10): 227−232. LIU Huapeng, LIU Shengquan, LIU Yan, et al. Semantic web service composition method based on agent and QoS[J]. Computer Engineering, 2013, 39(10): 227−232.

[12] 彭晖, 陈立民, 常亮, 等.基于动态描述逻辑的语义Web服务匹配研究[J].计算机研究与发展, 2008, 45(12): 2102−2109. PENG Hui, CHEN Limin, CHANG Liang, et al. Semantic web service matching based on dynamic description logic[J]. Journal of Computer Research and Development, 2008, 45(12): 2102−2109.

[13] 李曼, 王大治, 杜小勇, 等. 基于领域本体的Web服务动态组合[J]. 计算机学报, 2005, 28(4): 644−650. LI Man, WANG Dazhi, DU Xiaoyong, et al. Dynamic composition of web service based on domain ontology[J]. Chinese Journal of Computers, 2005, 28(4):644−650.

[14] RAFIEE A, EMADI S. An integrated method for semantic web service composition using planning based on qualitative parameters[C]//2016Second International Conference on Web Research. New York,USA:IEEE,2016: 84−89.

[15] 李玲,刘敏,成国庆.一种基于FAHP的多维QoS局部最优服务选择模型[J].计算机学报, 2015, 38(10): 1997−2010. LI Ling, LIU Min, CHENG Guoqing. A local optimal model of service selection of Multi-QoS based on FAHP[J]. Chinese Journal of Computers, 2015, 38(10): 1997−2010.

[16] 冯艳, 陈富赞. 基于QoS多属性决策的Web服务组合优化方法[J].计算机工程, 2015, 41(6):33−38. FENG Yan, CHEN Fuzan. Web service composition optimization method based on QoS multi-attribute decision making[J]. Computer Engineering, 2015, 41(6):33−38.

[17] 温涛, 盛国军, 郭权, 等. 基于改进粒子群算法的Web服务组合[J]. 计算机学报, 2013, 36(5): 1031−1046. WEN Tao, SHENG Guojun, GUO Quan, et al. Web service composition based on modified particle swarm optimization[J]. Chinese Journal of Computers, 2013, 36(5): 1031−1046.

[18] 夏亚梅, 程渤, 陈俊亮, 等.基于改进蚁群算法的服务组合优化[J]. 计算机学报, 2012, 35(2): 270−281. XIA Yamei, CHENG Bo, CHEN Junliang, et al. Optimizing service composition based on improved ant colony algorithm[J]. Chinese Journal of Computers, 2012, 35(2): 270−281.

[19] WU Quanwang, ZHU Qingsheng. Transactional and QoS-aware dynamic service composition based on ant colony optimization[J]. Future Generation Computer Systems, 2013, 29(5): 1112−1119.

[20] 曹云健, 董晶. 基于模拟退火遗传算法的服务选择[J].计算机工程与设计, 2011, 32(10): 3507−3511. CAO Yunjian, DONG Jing. Services selection based on simulated annealing genetic algorithm[J]. Computer Engineering and Design, 2011, 32(10): 3507−3511.

[21] PAGANELLI F, AMBRA T, PARLANTI D, et al. A semantic-driven integer programming approach for QoS-aware dynamic services composition[C]//2011 50th FITCE Congress.New York, USA: IEEE, 2011: 1−6.

[22] ZOU Guobing, GAN Yanglan, CHEN Yixin, et al. Dynamic composition of web services using efficient planners in large-scale service repository[J]. Knowledge-Based Systems, 2014, 62: 98−112.

[23] ZHANG Miao, LIU Li, LIU Songtao. Genetic algorithm based QoS-aware service composition in multi-cloud[C]//2015 IEEE Conference on Collaboration and Internet Computing. New York, USA: IEEE, 2015:113−118.

(编辑 伍锦花)

QoS-aware service composition based on culture genetic algorithm

LIU Zhengli1, LI Bing1, QIANG Baohua2, WANG Jing3

(1. School of Computer Science, Wuhan University, Wuhan 430079, China; 2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China 3. China Electronics Standardization Institute, Beijing 100007, China)

To improve the efficiency of service composition, an improved QoS-aware service composition approach was proposed based on cultural genetic algorithm. A double space include social population and belief was constructed. The reception function was used to extract knowledge from the social population and to update the belief space. Then the belief space of cultural algorithm was utilized to guide the evolution of social population, accelerate the convergence and improve the efficiency of combination. The results show that compared with traditional culture genetic algorithm and improved genetic algorithm, the number of iterations required for convergence of the proposed algorithm can be significantly reduced, and the execution efficiency and convergence speed are improved.

service composition; QoS-aware; culture genetic algorithm; service selection

10.11817/j.issn.1672-7207.2018.11.013

TP311

A

1672−7207(2018)11−2731−07

2017−12−11；

2018−01−28

国家重点研发计划项目(2016YFB0800401，2017YFB1400602)；国家重点基础研究发展规划(973计划)项目(2014CB340401)；国家自然科学基金资助项目(61572371)；国家博士后科学基金资助项目(2015M582272)；中央高校基本科研业务费专项资金资助项目(2042016kf0033)；湖北省自然科学基金资助项目(2016CFB158)；武汉市黄鹤英才(专项)计划项目(2017) (Projects (2016YFB0800401, 2017YFB1400602) supported by the National Key Research and Development Program of China; Project(2014CB340401) supported by the National Basic Research Development Program(973 Program) of China; Project(61572371) supported by the National Natural Science Foundation of China; Project(2015M582272) supported by the National Science Foundation for Postdoctoral Scientists of China; Project(2042016kf0033) supported by the Fundamental Research Funds for the Central Universities; Project(2016CFB158) supported by the Natural Science Foundation of Hubei Province; Project(2017) supported by the Wuhan Yellow Crane Special Talents Program)

李兵，博士，教授，博士生导师，从事服务计算、人工智能、软件工程研究；E-mail: bingli@whu.edu.cn