基于改进蚁群优化算法的服务组合与优化方法

沈记全,罗常委,侯占伟,刘志中

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

0 概述

云计算[1]的概念是在原本已存在的并行处理(parallel computing)、效用计算(utility computing)以及网格计算(grid computing)等科学计算领域的基础上发展起来的一种基于互联网的商业模式。

随着电子商务以及大数据时代的到来,用户提交了大量功能复杂的服务请求,对服务质量的需求越来越高,细粒度原子服务几乎难以达到用户复杂多样的需求标准。此时,需要复合多种云服务,即对云平台上已有的服务按照一定的业务逻辑构造粒度更粗的服务,即云服务组合[2]。

由于互联网环境的复杂性、开放性以及动态性、用户任务请求与反馈的随意性、云服务负载的波动性等各种不确定因素的干扰,云平台上出现了大量具有功能性等价特征的云服务。而它们的服务质量(Quality of Service,QoS)多数处于参差不齐的状态,能达到用户需求的较少。

到目前为止,众多学者为了方便高效地处理QoS感知的云服务组合问题,分别提出了诸如模拟现实蚂蚁群体协作寻找优化路径的蚁群优化(Ant Colony Optimization,ACO)系统、模仿生物遗传进化的遗传算法(Genetic Algorithm,GA)、基于飞鸟集群觅食活动模型的粒子群优化(Particle Swarm Optimization,PSO)算法等为代表的群集协作智能算法。文献[3]提出以3个相异的、适应度高的个体为进化核心的双精英协同进化算法,通过采取不同的进化策略来提高算法的搜索能力。文献[4]通过优化蚁群系统的信息素更新机制,提出一种多信息素动态更新的全局优化算法,相比于原始蚁群算法和遗传算法,在求解服务组合优化问题时有着更优的性能。文献[5]借鉴多目标遗传算法的理论,提出一种基于全局QoS约束的多目标服务动态选择优化算法GODSS,通过对多个目标函数进行优化,可以得出符合用户需求的最优非劣解集合。文献[6]提出一种基于频率分配的蜂群优化算法,在求解旅行商问题的实验中具有58.42%的改进。文献[7]提出一种混合蚁群遗传算法,通过对数值报告的分析,证明了该算法在处理全局复杂优化问题的可行性。上述的研究方法虽然在一定程度上可以求解服务组合问题,但都存在着各自的不足。例如:遗传算法局部搜索能力不强,求解结果不稳定;蚁群算法初期信息素积累时间长、易陷入局部最优等。

文献[8]提出一种新的群体智能算法——社会认知优化(Social Cognitive Optimization,SCO)算法,SCO虽然可以用来处理复杂连续函数的优化问题,但是该算法不能用来求解离散型的服务组合问题。

基于上述问题,本文对最大最小蚂蚁系统进行改进,提出一种新的基于蚁群系统的云服务组合算法。该算法借鉴遗传算法、社会认知优化算法的思想,求得最优云服务组合,并通过实验来验证该算法的可行性及精确性。

1 问题描述与模型建立

1.1 云服务组合问题描述

云服务组合通常被分为任务规划、服务推荐、服务组合与优化3个步骤,本文的侧重点在于云服务组合的第3个阶段。多数云服务组合路径的工作流控制模型都可分解为并行模型、选择模型、循环模型以及顺序模型。为方便研究服务组合问题,本文根据文献[9]的方法处理并行的服务聚合流程,将其转化为串行的顺序模型。

尽管Internet中分布着海量不确定的云服务,但是功能单一的云服务往往不存在实用意义,要实现云服务的真正价值,关键在于将多个服务按照某种业务需求交互集成。设一条完整的云服务组合链如图1所示,S1,S2,…,Sn是构成云服务组合链的服务节点,它们对应的候选服务簇分别为CS1,CS2,…,CSn,其中CSj(1≤j≤n)在m个功能上等价,但QoS状态不同的服务CSji(1≤i≤m),即CSj={CSj1,CSj2,…,CSjm}。

图1 云服务组合

1.2 数学模型

目前不同标准下建立的QoS参数体系总会有些出入,通常云服务的QoS参数是由一些诸如服务价格、执行时间、可靠性、可用性等不仅能够体现服务本身固有的质量属性,而且能够体现用户需求的非功能属性构成[10]。根据顺序结构的QoS聚合方法[9],可以计算出CSji的任何一个QoS属性向量。一般而言,可定义服务CSji的QoS属性向量为:

QoSji= {q1(CSji),q2(CSji),…,qk(CSji),…,

qr(CSji)}

其中,qk(CSji)(1≤k≤r)表示候选服务CSji的第k个属性。根据用户对服务综合性能的不同需求定义了全局QoS约束条件如下:

Conji= {c1(CSji),c2(CSji),…,ck(CSji),…,

cr(CSji)}

每个候选云服务CSji都具有各种各样的QoS属性qk(CSji),大体上可以分成2种:一种是QoS属性值越大越好的积极属性(positive attribute),比如服务可用性、可靠性;另一种是考虑QoS属性值最小化的消极属性(negative attribute),比如服务价格、反应时间。显而易见,qk(CSji)的度量单位及取值区间也不尽相同。通过采用简单加权法(Simple Additive Weighting,SAW),按式(1)对多个QoS属性值进行标准化处理。

(1)

(2)

云服务组合关于全局QoS约束的数学模型如式(3)所示。

(3)

云服务全局QoS需要满足的约束条件如式(4)所示。

(4)

2 改进的蚁群优化算法

2.1 蚁群优化算法

最大最小蚂蚁系统(MMAS)是文献[11]基于蚂蚁系统提出的仿生优化算法,并且在众多的应用领域中得到了大力推广和广泛应用,是目前蚁群优化系统中性能最好的算法之一。蚂蚁在寻优时以选择概率为启发式规则,会在不同的服务CSjk之间向着选择概率最大的节点进行转移,直到遍历完所有的服务节点。本文采用了轮盘赌的方式增加算法搜索的随机性来选择候选云服务。

(5)

式(5)为蚂蚁c在t时刻由当前云服务节点Sj的第k个候选服务CSjk,向下一个服务节点Sj+1的第i个候选服务CSj+1,l转移的选择概率。其中,α为信息启发式因子,反映了蚂蚁在遍历过程中积累的信息素对后来蚂蚁所起到的作用,β为期望启发式因子,表示蚂蚁在遍历过程中的启发信息对于蚂蚁选择路径时的相对重要程度,allowdc={C-tabuc}表示蚂蚁c下一步允许选择的服务CSj+1,l,即还未曾被访问到的候选服务,τkl(t)表示t时刻候选服务CSjk与CSj+1,l之间的信息素强度,ηkl(t)表示t时刻从候选云服务CSjk转移到CSj+1,l的启发函数,本文将目标函数设置为启发函数:

(6)

2.2 信息素更新策略

考虑到信息启发式因子α和期望启发式因子β在算法运行中是保持相对稳定的,那么信息素的更新机制就成为了影响状态转移概率Pkl(t)的决定性因素。最大最小蚁群算法的信息素更新机制在原始的蚁群算法上进行了优化,选择蚂蚁迭代过程中的最优路径增长信息素,这条路径可能是当前循环中得到最佳路径,也可能是第一次循环以来得到最佳路径。然而一旦有大多数蚂蚁都经过同一条路径的情况发生,那么就大大降低了算法的随机搜索能力。这样可能会引起局部较优路径上残留信息素过多,从而导致启发信息被淹没,算法过早收敛于局部最优解。为了使算法搜索效率更高,本文设计的全局信息素更新公式如式(7)～式(9)所示。

τkl(t+1)=ρτkl(t)+Δτklg(t)

(7)

(8)

τkl(t+1)=(1-ρ)τkl(t)

(9)

当所有蚂蚁都经历过一次遍历路径寻优后,按照式(7)增长评价值处于前x位的蚂蚁路径的信息素,按照式(9)衰减评价值最差的x位蚂蚁路径上的信息素,用来影响蚂蚁种群下一次循环遍历的寻优过程。为了避免信息素连续不断的积累,ρ的取值范围取为ρ⊂[0,1),其中,ρ为全局信息素保留因子,(1-ρ)表示信息素挥发因子,Δτklg(t)代表第g只蚂蚁在候选服务CSjk与CSj+1,l路径上的信息素增量,f(CSg)代表处于第g只蚂蚁经过路径的评价值,el代表蚂蚁寻优经过的第l条边,Lg代表蚂蚁经过的整条路径。为了避免搜索停滞,陷入局部最优,对于各条路径上的信息素τkl(t)都有τkl(t)∈[τmin,τmax]。最大最小信息素量如式(10)、式(11)[12]所示。

(10)

(11)

其中,Sbest是到目前为止具有最优评价值的蚂蚁路径,如果信息素τkl(t)出现∃τkl(t)∉[τmin,τmax]的情况,当τkl(t)≥τmax时,将τkl(t)的大小设定为τkl(t)=τmax,当τkl(t)≤τmin时,则将τkl(t)赋值为τkl(t)=τmin。

2.3 遗传算法

由于蚁群算法具有正反馈、分布并行能力,能够借助信息素的保留和更新而收敛于最优路径,因此非常适合用来求解较为困难的组合优化问题。然而,因为蚁群算法在搜索初期时信息素极度匮乏,需要耗费大量时间积累信息素,导致了蚁群算法经常会出现搜索速度慢、易于停滞等问题,蚁群算法中至少有60%的时间都被用来形成初期信息素值[13]。借鉴生物进化过程中存在的自然选择、优胜劣汰的铁律以及基因的遗传变异原理,美国密歇根大学的John Holland教授于1975年首先提出了遗传算法,它具有随机性、鲁棒性和全局解空间搜索的特性,适合用来求解群体性全局优化问题[14]。但是当用遗传算法来求解更精确的服务组合问题时,往往会出现不能充分利用系统中反馈信息的情况,而且当运行到某个阶段时常常会产生许多没有价值的冗余迭代,从而导致收敛能力较低。

为了集成2种算法的优点,达到扬长避短的目的。在采取蚁群的并行性、正反馈以及启发式搜索等优势求解服务路径之前,首先借助遗传算法的快速性、随机性和全局搜索的能力初始化服务节点路径上的信息素。

由于在云环境中不同用户对于服务的要求往往差距较大,而且云服务簇中包含大量参差不齐的候选服务,因此不仅要参考服务质量的好坏,更要注重用户个人的需求倾向。在遗传算法中,一条完整的服务路径CSGi代表染色体长度,采用十进制整数编码,每一个基因对应于服务CSji。适应度函数的选取同样关系到算法的收敛速度与最终解的优劣,本文选取式(3)作为遗传算法的适应度函数。

交叉操作:在保证云服务路径节点组合方式不变的前提下,随机选择节点服务CSji和CSj+d,i+d进行双点交叉操作,如图2所示。交叉概率和变异概率分别为常数PC和Pm,在算法运行中利用random生成r∈[0,1],如果r

图2 双点交叉操作示意图

变异操作:遍历服务组合路径CSGi,由变异概率Pm决定该组合路径上的服务节点CSji是否用候选服务CSjk进行替换,从而形成一个新的路径组合。如果需要变异,则使用轮盘赌策略对路径中的节点CSji进行变异,否则不采取任何行为。依靠这种操作,比较重新生成的服务路径适应度评价值,除了评价值有所优化的服务组合之外,不接受其余的情况。当遗传算法运行到最大迭代次数之后,选择服务组合中居于前10%的适应值f10%better(CSi),并以式(12)生成改进蚁群算法中的初始信息素分布。

(12)

其中,τC是一个常数,相当于MMAS算法中的τmax,τG是遗传算法求解出的最优路径所转换的信息素,KG为常数。

2.4 社会认知算法

很多研究群居性生物的科学家通过模拟昆虫群落的集体行为,相继研发出多种仿生优化算法,如GA、ACO、ABC等群集智能算法。然而,从现实中的生物群落来看,群居性昆虫的合作终究较为简单,人类社会比昆虫群落具有更完整的社会形态与更高级的智慧层次。人类的学习过程是在利用观察学习的同时,思考其他人因为不同选择而引发的结果,并且将这个过程进一步转化为符号的活动。类似这种采取观察以及模仿其他人的言行举止,从而不断积累知识量的学习过程被定义为观察学习,由于这样的观察学习是要求在人类社会的环境中才能发生的,因此也将观察学习形象地称之为社会学习。

社会认知算法的概念中包括了对模仿选择的定义,从根本上来看,也就是利用不同知识点之间存在的优劣好坏,然后通过简单的对比选择出较好的知识点,没有可能涉及到现实社会中人类群体之间彼此互通有无、共同成长的背后意义。鉴于此,为了达到让SCO能够处理离散型云服务组合优化问题的目的,本文结合文献[15]提出的协作学习(collaborative learing)理念,改进了蚂蚁群体间的模仿选择。当蚂蚁群体在每一次循环遍历寻找最优路径的过程中,参照蚂蚁路径评价值的优劣进行排序,直到选择出x条较优的蚂蚁路径CSSi(1≤i≤x)作为模板,然后分别和剩余的m-1条蚂蚁路径一起分成相等的子路径,对应的子路径之间再进行模仿选择,模仿学习示意图如图3所示。这样就可以将m条蚂蚁路径CSRi(1≤i≤m)的局部优点集成到一起,进而得到x条优于其他路径的新路径CSTi(1≤i≤x)。

图3 模仿学习示意图

由SCO定义的学习代理是一个能够在知识库中进行搜索知识点的行为个体。凭借位于不同水准层次的知识点,行为个体能够采取领域搜索的手段重新定位到一个水准更高的知识点,然而这种学习规则只能用来解决满足解集合连续这一要求的学术研究。为了更好地处理离散型云服务组合路径的优化问题,在SCO观察学习规则的基础上执行变异操作:当蚂蚁群体完成协作学习的程序,为了搜索新的蚂蚁路径,对每一条经过协作学习程序的蚂蚁路径采取基于多点变异的操作,并且蚂蚁路径每进行过一次变异,就挑选出原路径与变异之后路径的较优者作为新路径。经过多次变异的观察学习操作,能够得到更广泛、更优秀的蚂蚁路径,还可以防止算法过早收敛于非全局最优值。其中蚂蚁路径变异的节点个数设为o,变异次数设为y。

2.5 算法基本步骤

在基于改进蚁群算法的云服务组合优化研究中,蚂蚁经过的路径CSRi代表服务组合方式,利用目标函数求解云服务组合路径的聚合QoS评价值。初始时刻,输入用户QoS约束及偏好。具体步骤如下:

步骤1初始化云服务CSji以及QoS属性值qk(CSji),按照式(4)的全局QoS约束条件初步筛选服务,设置遗传算法的最大迭代次数NGA-max。

步骤2依次从节点Sj的候选服务簇CSji中选出具体服务组成染色体,形成规模为N的初始种群,并利用式(3)得到评价值排在前m条的染色体CSGi。

步骤3先根据交叉概率Pc选择染色体进行双点交叉操作,再由变异概率Pm决定基因是否需要采取变异操作,产生新的染色体。

步骤4判断是否达到最大迭代次数NGA-max,若满足条件,则停止遗传算法,进入步骤5,否则返回步骤3。

步骤5初始化参数,设置蚂蚁个数m,蚂蚁循环变量Mc=1,改进蚁群算法的最大迭代次数NACO-max,禁忌表矩阵tabum×n,代表优秀蚂蚁路径的记录表L,较差蚂蚁路径的记录表R。

步骤6根据式(12)生成改进蚁群算法的初始信息素分布,其中KG=1。

步骤7按照式(5)计算出每只蚂蚁移动到下一个服务节点的选择概率Pkl(t),采用轮盘赌的方式增加改进蚁群算法搜索的随机性。

步骤8更新禁忌表tabum×n,当蚂蚁经过最后一个节点,计算路径CSRi的聚合QoS评价值并排序。

步骤9通过公式Mc=Mc+1,判断是否满足循环条件Mc=m,如果满足则继续下一步,否则转回步骤7。

步骤10选择前x条蚂蚁路径CSSi放入记录表L,选择最差的x条路径放入记录表R。

步骤11对记录表L中的CSSi,采用改进的模仿和观察学习方法,得到x条新路径CSTi,最后从CSSi和CSTi中选出优秀的x条路径用来更新记录表L。

步骤12采用上文提到的全局信息素更新策略,分别按照式(7)、式(9)对记录表L和记录表R中路径的信息素进行增加和衰减。

步骤13重置禁忌表tabum×n,如果改进蚁群算法达到最大迭代次数NACO-max,那么输出具有最优评价值的服务组合路径,否则转回步骤5。

2.6 算法复杂度分析

假设遗传算法种群规模为N,迭代次数为NGA,则算法复杂度为O(NGA·N2)。蚁群算法复杂度为O(M+AN2+NACO×M2),M为蚁群规模大小,AN为初始解,NACO为进化代数。文中的蚁群优化算法的时间复杂度主要包括2个部分,分别为初始信息素生成和蚂蚁遍历寻优过程。信息素由遗传算法生成,其复杂度为O((a+b)NGA×N×Nbetter),a表示目标函数的规模,b表示约束条件的个数,Nbetter表示遗传算法进化过程中的精英种群。蚂蚁寻优过程的时间复杂度为O(NACO·M·Mbetter),Mbetter表示蚁群算法迭代过程中的精英种群,那么蚁群优化算法的时间复杂度为O((a+b)NGA×N×Nbetter+NACO×M×Mbetter)。

3 实验结果与分析

3.1 实验设计

为了验证上述改进蚁群算法在求解云服务组合优化问题上的有效性,本文实验借鉴文献[16]的方法,在一定的取值区间内随机生成模拟云服务的QoS属性值。测试案例中的云服务节点数一共有9个,且这些服务节点分别对应的候选云服务数目为50个。模拟实验所采用的QoS属性包括服务价格、执行时间2种消极属性以及可靠性和可用性2种积极属性。其中费用、反应时间的取值区间分别是[0,100]和[0,30],可靠性以及可用性的取值区间都设定为[0.80,1],它们对应的向量偏好比重被设定为{0.35,0.3,0.25,0.1}。在遗传算法中的主要参数如下:初始种群N=100,最大迭代次数NGA-max=50,交叉率Pc=0.75,变异率Pm=0.15;在改进蚁群优化算法中,m=50,β=5,α=1,ρ=0.6,τmax=2,τmin=0.1,x=10。在社会认知优化算法中,蚂蚁路径被分成以下的子路径,o=5,y=10。

改进蚁群优化算法实现工具为Microsoft Visual Studio 2012,运行环境PC的具体配置为Windows7操作系统,RAM为2.00 GB,处理器为Intel(R)Core(TM)2 Duo CPU E7500 @ 2.93 GHz。

3.2 结果分析

为了验证改进蚁群算法处理云服务组合与优化问题的优越性,本文同时还采用最大最小蚁群算法、遗传蚁群算法进行求解,它们都是在相同的实验环境下通过C++编程语言实现。

3种算法求解云服务问题的性能如图4所示。由图4可见,最大最小蚁群算法经过30次迭代收敛,求得的评价值最低,与之相比,遗传蚁群算法的求解结果有明显提高,但是却需要80次迭代才求得稳定结果。最终的改进蚁群算法拥有协作学习的能力,其25次迭代后所求得的服务组合方案已经收敛于最优解。

图4 3种算法的性能比较

随机从3种算法中选择的服务组合方案评价值以及相应运行时间如表1所示。最大最小蚁群算法收敛于0.488,耗费26.988 s,所需时间最长;遗传蚁群算法在32.84 s之后稳定在0.654 s,但是比最大最小蚁群算法耗时更久;本文的改进蚁群算法在求解云服务组合方案上,其在运行11.309 s时收敛于0.697 s,综合性能明显优于另外2种算法。

表1 算法评价值与相应时间

4 结束语

服务组合是目前服务计算领域研究的热点,面对网络上功能等价、服务质量却参差不齐的海量云服务,用户得到高质量服务组合的难度不断增加。目前遗传算法和蚁群算法等模拟进化算法在处理云服务组合与优化问题中的局限性越来越突出,社会认知算法的应用范围又局限于连续性的组合优化研究。基于此,本文考虑了上述3种算法各自的优缺点,利用遗传算法生成蚁群算法初始信息素分布,在寻优过程中引入社会认知优化算法的学习操作。实验结果表明,改进后的蚁群算法在求解云服务组合与优化的问题中具有更高的求解效率,能够得到精确度更高的最优解。