面向交通出行服务的多目标优化选择方法

杨万春 张晨曦

(山东交通学院理学院 山东 济南 250357) 2(同济大学软件学院 上海 201804)

0 引 言

随着交通行业信息化的发展和出行方式的多元化,现有研究在交通服务选择[1]和交通流预测[2]等方面开展了大量工作,其中在功能相似的海量服务资源中挑选交通出行服务成为智能交通系统的关键。为此,如何将功能单一的服务按需定制、重新组装来满足用户需求成为当下的研究重点。如出行者要去参加国际会议,并在参加国际会议的空闲之余游览旅游景点,需要用到信息搜索、规划线路、选择交通方式、预订酒店与景点、支付费用、地图显示等服务。服务质量(Quality of Service,QoS)包含多个指标,用户在选择出行服务的时候,会考虑速度、花费、满意度等非功能属性。现有的交通服务选择研究大多将各个目标聚合为一个单目标函数,然后采用数学规划方法或者启发进化算法对单目标问题进行求解。文献[3]采用蚁群算法进行交通出行服务的选择。文献[4]将烟花爆炸算法和变异算子相结合以应用于服务选择模型。文献[5]提出一种混合混沌机制与Levy变异的改进烟花算法,但上述方法无法满足用户多目标的需求。由于各个指标维度之间可能存在矛盾,某个指标的改善会引起其他指标的恶化,例如可用性高的服务,其价格花费就会相应提高,这就需要在不同维度指标之间进行平衡,从而能够满足用户多方位的出行需求。多目标优化问题不存在使得所有目标都达到最优解,其是由Pareto最优解或非劣最优解构成的解集。

现阶段已有相关研究将启发式进化算法应用于服务的多目标选择问题中,从而达到Pareto前沿。文献[6]针对有数据依赖的组合服务构建了依赖图,基于依赖图设计了基于集束搜索(beam search)和非支配排序遗传算法(NSGA-II)的改进启发式进化算法。文献[7]采用分布估计算法进行局部搜索以提高NSGA-II的性能。文献[8]采用多目标遗传算法来确定一个Pareto最优多维边界,并能够权衡相互冲突的目标。文献[9]针对服务选择问题,给出了改进的多目标粒子群算法,在算法中加入了近似距离方法和外部存档机制。文献[10]先对候选服务进行排序优化筛选,在此基础上给出了基于多目标粒子群优化的云服务选择排序系统。文献[11]提出了ε支配的多目标遗传算法来解决服务组合优化问题。它支持用户在当前服务失败时做出灵活的决策或选择替代方案。文献[12]给出了混合多目标进化算法,其将NSGA-II和差分进化算法相结合,其中的差分进化算法采用了自适应变异算子和交叉算子。文献[13]给出了基于多目标进化算法与决策支持的组合优化方法。该方法首先应用决策支持方法来计算用户偏好的权重,然后将计算出来的权重应用于拥挤距离的求解中。以上多目标服务选择方法采用不同的算法解决了多目标服务选择问题,但它们都没有考虑服务的事务属性问题。

针对网络环境的不稳定、信息传输的不可靠等因素,采用事务处理技术来保证组合服务的可靠性和一致性。文献[14]给出了服务的事务属性定义和规则。文献[15]针对事务性服务的组合问题,给出了改进的遗传算法。文献[16]给出了SLA感知的事务型组合服务容错方法。

综上所述,针对交通出行服务选择,现有的研究都是基于服务的QoS属性构建了多目标选择模型,没有考虑服务的事务属性。基于服务选择模型的多目标优化算法在解集的收敛性、均匀性、广泛性方面还存在性能不足。本文从QoS和事务两个维度建立了服务优化选择模型,在该模型基础上,设计了烟花爆炸算法与启发式的差分进化算法相结合的混合优化方法,对组合服务进行优化选择,利用外部存档中的解作为Pareto最优解集。该多目标优化算法将烟花爆炸算法的局部搜索能力以及差分进化算法的种群多样性结合起来,重新定义了爆炸半径、交叉与变异算子,具有较好的搜索性能。

1 服务优化选择模型

服务选择问题是首先根据用户的需求构建抽象服务流程,然后在候选服务中选择具体服务,将选择出的具体服务和抽象服务进行绑定。这些候选服务具有不同的属性参数值,因此可形成海量的服务组合方案。

1.1 QoS属性

交通信息服务的QoS属性包括花费(cost)、及时性(time)、可用性(availability)、可靠性(reliability)、满意度(satisfaction)等。由于每种QoS属性的单位或取值范围不一样,因此需要在统一的标准下计算QoS属性。QoS属性可以分为积极属性和消极属性两类。积极属性考虑QoS的最大化,如可用性、可靠性、满意度等,其归一化公式为式(1)。消极属性考虑QoS的最小化,如花费、及时性等,其归一化公式为式(2)。

(1)

(2)

式中:q表示QoS属性;q′表示归一化后的结果;qmin表示QoS属性中的最小值;qmax表示QoS属性中的最大值。若qmax=qmin,则q′=1。

1.2 组合函数

虽然服务的组合类型不同,但都可将其分解为顺序类型的组合函数。顺序类型的组合服务由n个组件顺序构成,其花费和及时性具有累加特点,而可用性、可靠性和满意度则具有累乘特点,如表1所示。

表1 组合函数

1.3 事务属性

由于网络的动态性和不稳定性,组合服务在运行过程中可能存在服务失效或异常情况,这会降低组合服务的可靠性。事务性组合服务就是利用事务处理的方法来保证组合服务的可靠性和一致性。在文献[14]中,服务的事务属性包含如下几类:可补偿的事务属性(c)、可重试的事务属性(r)、枢纽事务属性(p),及它们的组合cr(可补偿+可重试)。组合服务的事务属性由其组成部分的事务属性来决定[14]。若该组合服务的事务属性是{p,c,r,cr}之一,则这个组合服务满足事务属性的要求。为了保证组合服务的事务属性,设置了事务优先级,cr的优先级为L3,c和r的优先级都为L2,p的优先级为L1,其中L3>L2>L1,并约定c和r不可比较。

1.4 多目标服务优化选择模型

本文将及时性、可用性和满意度作为三个目标准则,希望组合服务CS的响应时间短,可用性与满意度高。设置五个QoS约束条件和一个事务约束条件,A0表示组合服务的最低可用性,T0表示组合服务的最大反应时间,C0表示组合服务的最高花费,R0表示组合服务的最低可靠性,S0表示组合服务的最低信誉度,TP(CS)表示组合服务的事务属性。对于QoS属性来说,有些是越大越好,有些是越小越好,因此我们统一求Maximum,即在及时性的计算公式前面加负号。带约束条件的多目标优化模型如下:

Maximum(-T(CS),A(CS),S(CS))

s.t.

(1)A(CS)≥A0

(2)T(CS)≤T0

(3)C(CS)≤C0

(4)R(CS)≥R0

(5)S(CS)≥S0

(6)TP(CS)∈{p,c,r,cr}

2 多目标服务优化选择方法

本文提出的改进多目标算法采用的是混合优化选择方法,将烟花爆炸算法[17]与差分进化算法[18]相结合,利用外部存档中的解作为Pareto最优解集。

2.1 编码策略

采用一个整数数组进行编码,数组的长度为个体所包含的服务数,数组中每个元素的值为对应抽象服务绑定的具体服务实例的标识。图1中是6个服务构成的组合服务,其中S[1]3表示第1个抽象服务选择了其第3个候选服务实例,依此类推。

S[1]3S[2]6S[3]8S[4]10S[5]20S[6]2

2.2 烟花爆炸算法

烟花弹在空中爆炸会释放出许多火星,且火星分布在以烟花弹为中心的一定区域范围内。对于烟花xi,其产生的火星数目si计算公式为:

(3)

式中:fmin表示种群中最小的适应度值;α和m是常数,m用来控制火星个数。烟花xi爆炸产生的半径Ai的计算公式如下:

(4)

式中:fmax是种群中适应度的最大值;A是常数,用来调整爆炸半径的大小。针对组合服务问题,我们通过变异率来替换半径大小,即好的烟花爆炸后产生的半径小,其对应组合服务的变异率就小,差的烟花爆炸后产生的半径大,其对应组合服务的变异率就大。假设候选个体集合大小为K,烟花种群的大小为N,要在候选个体集合中选择N-1个个体进入到下一代,对于候选者xi,其被选择的概率计算公式如下:

(5)

式中:R(xi)为xi到候选个体集合中的其他个体的距离之和。

(6)

式中:d(xi,xj)表示个体xi和xj的距离。在种群集合中,若个体的密度高,则选中该个体的概率就小。

2.3 启发式的差分进化算法

差分进化算法(DE)由变异、交叉和选择操作构成。对于第t代种群中的每一个目标个体向量Xi(t),其相应的变异操作如下:

Vi(t+1)=Xbest(t)+F×(Xr1(t)-Xr2(t))

(7)

式中:r1、r2为随机选择的整数,且与个体i不相同,表示父代种群中两个不同的个体;Xbest(t)是基向量;F为常数,称为缩放因子,用来控制差分向量的缩放程度。结合组合服务的特点,我们设置变异操作公式中的F=1。假设有两个个体Xr1(t)=(S[1]3,S[2]5,S[3]6,S[4]3),Xr2(t)=(S[1]6,S[2]5,S[3]9,S[4]2),将Xr1(t)与Xr2(t)比较,只有第2个服务相同,所以Xr1(t)-Xr2(t)=(1,0,1,1)。在Xbest(t)+(Xr1(t)-Xr2(t))的计算过程中,对Xbest(t)的第1、3、4个服务进行变异,从而产生变异个体向量Vi(t+1)。

为了增强种群的多样性,差分进化算法将目标向量个体Xi(t)与其相应的变异个体Vi(t+1)进行启发式的交叉操作,得到试验个体,即目标个体的候选个体Ui(t+1)。

(8)

式中:xij(t)表示父代种群中目标个体向量Xi(t)中的第j维分量;vij(t+1)为变异个体Vi(t+1)中的第j维分量;tp(xij(t))表示Xi(t)的第j维分量的事务属性。

差分进化算法利用优胜劣汰的方法来引导算法向全局最优解逼近。在选择操作中,算法首先对试验个体Ui(t+1)和目标个体Xi(t)的适应度值进行计算,然后将二者进行比较,并按照式(9)来选择适应度值较优的个体进入下一代。

(9)

经过以上的变异、启发式的交叉和选择操作,种群将进化到下一代,该过程反复循环,直到算法达到预定的最大迭代次数时算法结束。

2.4 适应度计算

本文采用了一种可行解优先的法则来处理约束条件,具体内容如下:(1) 如果i是可行解,j是不可行解,则i优于j;(2) 如果i和j都是可行解,则目标函数适应值大的个体较好;(3) 如果i和j都是不可行解,则违反约束力最少的个体较好。可行解的适应度值由支配度(Domination Value)与密度(Density)两个方面共同决定[19]。若i和j的支配度不同,则支配度值大的适应度值大;若i和j的支配度相同,则考虑解的密度。可行解i的适应度函数计算公式如下:

Fitness(i)=Domination-Value(i)×Density(i)

(10)

个体i的支配度由其支配其他个体的个数来决定。个体i拥挤距离的计算方法是:首先针对一个目标,计算围绕个体i的最近两个体的目标函数值差的绝对值,然后用该绝对值除以该目标的最大值与最小值的差,得到个体i的一个目标距离值,其次计算出个体i所有目标的目标距离值,最后将i的所有目标距离值进行平均即得密度,计算公式如下:

(11)

针对不可行解,我们设置了不可行度阈值α,计算公式如式(12)所示。该阈值能够在种群中保留一部分目标值较好的不可行解,从而达到由不可行解向可行解演变的目的,防止算法的未成熟收敛。

(12)

式中:T表示迭代次数;v(i)表示个体i违反约束的程度;n为群体规模。如果i的约束违反度小于给定的阈值,则i的适应度值按照式(10)计算,否则按照式(13)计算。

Fitness(i)=-∑vk/Domination-Value(i)

(13)

式中:vk表示个体i违反第k个约束的程度。

2.5 外部存档

算法采用外部存档来存储进化优良个体加入外部存档[20]。算法开始时外部存档为空,随着迭代次数的增加,那些不被父代个体所支配的试验个体将与外部存档中的个体依次比较,若试验个体被外部存档中的个体所支配,则拒绝该试验个体加入到外部存档中;若试验个体支配外部存档中的某些个体,则被支配的个体将从外部存档中剔除;若试验个体与外部存档中的个体之间互不占优,则试验个体是一个Pareto解从而加入到外部存档中。当外部存档的容量达到最大时,我们采用文献[20]中基于紧邻个体间距离值和最小的剔除方法来进行处理。该方法首先将新的非支配解加入到外部存档中,然后求取所有个体与其紧邻个体之间的距离值,其次求取任一个体左右紧邻的两个距离值和,最后剔除距离值和最小的个体。

2.6 改进的多目标优化算法

改进的多目标优化算法通过烟花爆炸与变异算子实现了局部搜索,同时利用差分进化算法使种群具备较好的分布性和扩展性,进而向Pareto前沿面搜索。

步骤1在解空间内随机生成满足事务属性要求的n个体来构成种群P,创建空的外部存档NP。

步骤2计算P中每个个体的适应度值,从种群P中选出非支配个体来更新NP,t=1。

步骤3若终止条件不满足,则执行步骤4到步骤7,否则转至步骤8。

步骤4利用式(3)和式(4)生成新的种群P1,利用式(10)和式(13)计算新产生个体的适应度值,用新个体更新外部存档NP。

步骤5在种群P1中选择n个个体构成种群P2,个体的选择概率与其适应度值成正比。

步骤6对种群P2中的每个个体利用式(7)、式(8)和式(9)所示的变异及交叉操作生成子代个体,计算新产生个体的适应度值,用新个体更新外部存档NP。

步骤7利用式(5)和式(6)中基于距离的选择方法选择n个个体构成新的种群,迭代次数t=t+1,返回步骤3。

步骤8输出非支配解集NP,并终止算法。

3 实验与结果分析

以下通过仿真实验分析算法的可行性和有效性。实验环境为Windows 10,内存为8 GB,开发语言为Python。在交通出行应用场景中提取8个抽象服务构成全体抽象服务集合,并假定流程为顺序结构,考虑了五种QoS属性:花费、及时性、可用性、可靠性和满意度。文献[21]给出了仿真QoS数据在取值范围内的生成规则,文献[22]中给出的QWS2.0数据集收集了网络上实际存在的Web服务集,这些属性提供者都是通过标准的测量工具测得的真实数据。百度地图中针对服务给出了真实的评分和满意度数据。本文参考文献[21-22]与百度地图中的服务数据,得到相应的实验指标数据。服务的事务属性从{p,c,r,cr}中随机选择。本文从问题规模、约束强度、迭代次数三个方面进行比较,采用Hypervolume[23]评价指标来分析各算法的优劣。Hypervolume指标能够对解集的收敛性、均匀性、广泛性进行评估,从而给出解集的综合评估结果。图2中虚线所围的部分即是集合w={w1,w2,w3,w4}的Hypervolume指标值HV(w),而个体w5则被集合{w1,w2,w3,w4}所支配。

图2 Hypervolume指标

Hypervolume指标值越大表明集合的质量越高。为了比较不同的多目标优化算法的性能,我们融合多个优化算法的Hypervolume指标值,得到最大的集合wmax,然后利用式(14)计算集合w的HV ratio的值:

HVratio=HV(w)/HV(wmax)

(14)

θ用来表示全局约束的强度。对于积极属性与消极属性,分别用式(15)与式(16)计算θ。

(15)

(16)

3.1 问题规模方面的性能比较

设定约束强度为0.2,候选服务数量从40增加到120。如表2所示,随着问题规模的增长,混合算法始终保持了较高的HV ratio值,优于其他算法。当候选服务数量为120时,混合算法的HV ratio为91.4%,NSGA-II-DE的值为89.3%,MOPSO的值为87.5%,NSGA-II的值为87.1%,GDE的值为78.4%。实验结果表明,本文算法在不同的问题规模情况下均能够得到较好的解,由此可以验证本文算法在解决大规模服务选择问题上具有可行性和有效性。

表2 候选服务数量方面的性能比较

3.2 约束强度方面的性能比较

设置候选服务数量为100,约束强度从0.2增长到0.6。随着约束强度的增大,满足约束的个体数量降低。表3所示混合算法的HV ratio值始终保持在90%以上。当约束强度为0.6时,混合算法的HV ratio值为91%,NSGA-II-DE的值为88.1%,MOPSO的值为86.2%,NSGA-II的值为85.1%,GDE的值为66.3%。由此可见,混合算法能够有效地解决强约束情况下的多目标服务选择问题。

表3 约束强度方面的性能比较

3.3 迭代次数方面的性能比较

设置候选服务数量为100,约束强度为0.2,迭代次数从0到400。随着迭代次数的增大,算法的HV ratio值都逐渐增大。在图3中,当迭代400次时,混合算法的HV ratio值达到93.1%,NSGA-II-DE的值为91.5%,MOPSO的值为90.6%,NSGA-II的值为87.3%,GDE的值为80.2%。经过比较,混合算法能够收敛到较高值,这说明混合算法求得的Pareto最优解能够很好地逼近理论Pareto最优解。相对于其他算法,混合算法在解集的分布和范围上具有明显优势,从而验证了其在多目标优化选择问题上的有效性,能够满足用户对算法求解精度的要求。

图3 迭代次数方面的性能比较

4 结 语

本文分析了交通出行服务的QoS和事务维度属性,建立了多目标服务优化选择模型。基于该模型,给出基于烟花爆炸与启发式差分进化的混合优化算法。实验结果表明,混合优化算法有较好的搜索性能,保证种群在进化过程中保持良好的分布性和扩展性,收敛性好,能够有效地解决多目标服务优化选择问题。下一步将研究面向交通领域的数据密集型服务的多目标选择问题,并进一步改进算法的性能。