基于多策略离散差分进化的移动互联网个性化服务组合

2016-11-30许斌亓晋印溪王野常瑞云

电信科学 2016年2期

关键词：适应度差分矢量

许斌，亓晋，印溪，王野，常瑞云

（南京邮电大学物联网学院，江苏南京210003）

研究与开发

基于多策略离散差分进化的移动互联网个性化服务组合

许斌，亓晋，印溪，王野，常瑞云

（南京邮电大学物联网学院，江苏南京210003）

移动互联网技术的普及使人们不再满足于单一功能的服务，而更倾向于按需定制的个性化服务或服务组合。提出了一种应用于Web服务组合的多策略离散差分进化（multi-strategy discrete differential evolution，MDDE）算法。该算法采用随机选择框架，调用具有不同特性的变异策略，是一种搜索能力和收敛速度均衡的离散差分进化算法。实验结果表明，MDDE算法在求解Web服务组合优化问题中比原始DE算法的收敛精度更高，稳定性更好。

Web服务组合；差分进化；多策略变异

1 引言

移动互联网、云计算、网络融合等技术的飞速发展促进了多种类业务环境的快速融合［1］。智能移动终端除了基本网页浏览、定位等基本数据业务能力外，还需要混合支付、旅游规划等相对复杂的混合服务能力［2］，以使用户更好地享用信息化服务。近年来，随着云计算技术的飞速发展和广泛应用，资源的使用方式发生了根本性变化，即通过网络就可使用处于不同空间的任意软件和硬件资源。所以人们不再强烈关注各类设备和应用本身，转而对处于云上的一系列资源能够提供的服务类型、服务质量以及服务体验和个性化更为感兴趣［3］。同时，移动互联网技术的普及，使人们不再满足于单一功能的服务，或仅仅是在数量上的服务集成，而更倾向于按需定制的个性化服务或服务组合［4-6］。满足该需求的一种策略是，将当前互联网环境中存在的功能相对单一的服务进行有机选择并有序组合，依据服务质量指标给出最佳的个性服务组合。由于一个服务的成功实施涉及服务器、网络、软件等各类资源的整体协调使用［7］，实际资源代价相当高。因此，通过采用上述策略，重复利用现有互联网各种服务，避免资源过度开发和浪费，是发展绿色节能移动互联网的有效手段。

当前服务组合的研究多集中于Web服务组合［8-11］。在Web服务组合的研究中，一般采用服务的QoS指标来评价和区分服务。QoS指标主要包括服务执行时间、代价、可用性、可靠性以及信誉度等。基于QoS的Web服务组合问题，是从若干个服务候选集中分别选择出候选服务进行组合，使得组合后的服务既能满足用户的需求，又具有良好的QoS。Web组合服务的QoS计算模型和服务组合优选算法是目前研究的热点问题［12，13］。

［14］从用户需求角度出发，提出了Web服务QoS主要应满足可用性（availability）、可达性（accessibility）、完整性（integrity）、性能（performance）、可靠性（reliability）、规范性（regulatory）、正确性（accuracy）、顽健性（robustness）、安全性（security）等方面的需求。参考文献［15］研究了带QoS约束的Web服务选择问题，提出了一个新的QoS模型来更灵活地选择服务，并引入Top k的排名策略来反映用户的个人需求，保证了新模型的有效性和实用性。参考文献［16］用服务价格、响应时间、可用性、可靠性和信誉度等属性来描述QoS，并提出了基于整数线性规划的服务选择算法，实现了在满足约束条件的前提下，计算服务组合的QoS。参考文献［17］提出了一种通过用户协作来预测Web服务的QoS方法。该方法通过研究用户以往Web服务使用经验来收集QoS数据，在此基础上采用邻域综合矩阵分解的方法来获得个性化的QoS预测值。

由于Web服务组合问题实质为NP难的组合优化问题，当前针对Web服务组合优选采用的算法主要是智能优化算法。参考文献［18］将启发式的模拟退火以及和声搜索作为遗传算法的智能变异算子，获得了更快的收敛速度以及更高的平均适应度值。参考文献［19］提出一种改进的遗传算法用于QoS感知的Web服务组合，采用两种不同的算法进行服务选择，避免了随机生成初始种群带来的负面影响，并将路径模板化以减少服务组合的工作量，用染色体可变长的编码方式来解决组合服务的多路径选择问题。利用PSO算法作为Web服务选择算法，体现了PSO算法并行计算的优势，全局搜索能力也得到很大提升。参考文献［20］提出了基于PSO的多目标优化策略，用于解决Web服务组合中基于QoS的服务选择全局优化问题，将服务组合全局最优问题转化为一个带QoS约束的多目标服务组合优化问题，然后利用多目标粒子群算法同时优化多个QoS，最终得到一组较优的服务组合方案。参考文献［21］改进了PSO算法，并应用于Web服务组合之中。该算法使用基于粒子圆周轨道和零惯性权重，基于三角函数的动态学习因子，控制粒子群的行为，使粒子的局部认知和全局搜索能力达到较好的平衡。参考文献［22］改进了人工蜂群算法，通过引入混沌策略产生新的解来代替面临丢弃的解使得算法跳出局部最优解，引入禁忌搜索策略避免跟随蜂的重复搜索，提高了算法的成功率以及搜索效率。

本文提出了一种多策略离散差分进化（multi-strategy discrete differential evolution，MDDE）算法，并将MDDE算法应用于基于QoS的Web服务组合优化问题。MDDE算法采用随机选择框架，调用具有不同特性的变异策略，是一种搜索能力和收敛速度均衡的离散差分进化算法。仿真实验表明，MDDE算法在求解Web服务组合优化问题中比原始DE算法的收敛精度更高，证实了多种变异策略的混合会增加种群中个体的多样性，避免了过早收敛及陷入局部最优。

2 问题建模

2.1 Web服务的QoS属性

为了区分和评价Web服务，现有的研究一般采用QoS指标。在QoS指标中，有些参数值由服务生产者提供，有些则由用户（服务使用者）决定。本文选取响应时间、可用性和执行代价这3个具有代表性的QoS属性来评估Web服务［15］。

因此，单个服务的QoS可用一个向量表示：Q=（T，A，C）。

（1）响应时间T

表示用户请求服务后到接受服务响应所经过的总时间。

其中，Ttrans表示请求消息和响应消息在网络上的传输时间，容易受到网络状况影响；Tproc表示处理服务请求所使用的时间。

（2）可用性A

表示服务可访问的概率。

其中，∑tsucess表示在调用一定次数的服务后，服务被成功调用的总时间；∑t表示所用的总时间。实际环境中，服务的可用性受到网络环境、服务器状态、客户端状态等因素影响，具有随机不确定性。

（3）执行代价C

表示用户执行一个Web服务所需的代价。

上述各个QoS属性中，执行代价和执行时间的属性值越大，表明Web服务质量越差，称为成本型指标，属于负指标；可用性越大，则表明Web服务质量越好，称为效益型指标，属于正指标。

2.2 基于QoS的Web服务组合模型

Web服务组合是将现有的小粒度的Web服务按照一定的逻辑组合起来使得获得的整体服务功能更强。Web服务组合的模式可以分为顺序结构、选择结构、并行结构和循环结构这4种结构模式，在实际应用中大部分组合服务都可以由这4种基本结构复合而成。由参考文献［23］的研究结果可知，4种结构模式可以转换为串联结构（如图1所示），因此本文仅考虑串联结构下的Web服务组合问题。

图1 Web服务的串联结构

图1中WSi表示组合中使用的各服务。

相应地，Web服务组合的QoS计算模型［21］见表1。

表1 Web服务组合QoS计算模型

在表1中，Ti、Ai、Ci分别表示在组合服务中第i个服务的响应时间、可用性和执行代价这3个QoS属性值，n表示服务的总数目。

基于QoS的Web服务组合模型定义如下：

其中，ωi表示各个属性的权值，应取其归一化值。

3 离散差分进化算法

DE算法是一种原理简单、实现有效的基于群体进化的算法。DE采用与遗传算法相似的进化步骤，包括变异、交叉、选择3种操作。与传统遗传算法不同的是，DE算法在当前代随机选择不同的个体，使其生成一个或几个比例差分矢量，再利用差分矢量对当前代种群的个体进行扰动，从而进行变异。

在DE算法中，有不同特性的变异操作能够用于为当前种群的目标矢量创建变异矢量。以DE/best/1为例：

其中，r1、r2为从集合｛1，2，…，NP}中随机选取的两个整数，且r1≠r2。为当前种群中适应度值最好的个体，该种策略以当前代全局最优值引导目标矢量的变异，收敛速度快，但极易陷入局部最优。

为了挖掘出种群潜在的多样性，DE算法将目标矢量Xit与相应的变异矢量Vit进行交叉操作生成一个试验矢量U。DE算法中通常使用的是二项式交叉方式。该交叉策略如下：

其中，υit为第i个变异矢量的第t个元素，uit为交叉之后产生的第i个试验矢量的第t个元素。randit为第i个矢量对应的t维随机数。该式决定了试验矢量中的元素是由变异矢量还是由目标矢量提供，t=trand确保了至少一个元素由变异矢量提供。

在执行二项式交叉时，对于D个变量中的每一个变量，均生成［0，10］的随机数，若随机数小于或等于预先给定的交叉概率CR时，该变量进行交叉操作。因其变异矢量贡献给试验矢量的参数个数近似二项式分布而称之为二项式交叉。由式（5）可知，当CR越大，则对V的贡献越大，此时有利于局部搜索和加速收敛。反之，当CR越小，此时DE算法更侧重于保持群体多样性和全局搜索能力。本文CR取0.5。

在进行交叉操作后，先对试验矢量进行取值范围的检查，确保其取值在给定范围中。为了保持后代种群的规模不变，将经过变异和交叉的试验矢量Uit与目标矢量Xit进行竞争，以确定更优的矢量进入下一代。本文将试验矢量Uit与目标矢量Xit混合排序，选取最优秀的NP个进入下一代。据此，重复变异、交叉、选择操作，直至达到停止条件。

DE有多种不同的变化形式，演化出具有不同特性的变异策略，有的策略侧重全局搜索能力，有的策略则强调收敛速度。本文结合多种DE变异策略，提出一种离散多策略DE，并将其应用于Web服务组合问题。

3.1 离散解编码

将DE算法应用到Web服务组合问题中，首要解决的是该问题中子任务子服务到DE算法个体的映射。本文对服务组合编码的方法如下，假定服务组合问题包含n个子任务，且每个子任务待选Web服务的个数均为m，那么每个待选服务可用WSij（T，A，R）表示，i为子任务的编号，j为完成该子任务的子服务的编号。设定DE算法的每个个体代表一条服务组合路径，个体的维度与服务组合问题的子任务数一致。举例来说，服务组合路径WS12→WS21→WS32→…→WSn5和WS15→WS24→WS39→…→WSn3可以分别用和来表示。

3.2 多策略随机选择框架

根据变异过程的不同，DE算法演化出了多种不同的变异策略。本文为求解Web服务组合问题，以DE/rand/2、DE/current_to_rand/1和DE/best/2 3种变异策略构建变异策略选择池。

（1）DE/rand/2

DE/rand/2变异策略中，将两个差分矢量和一个基矢量相加，表现出类高斯扰动，使得个体变异具有更好的全局搜索能力，不易出现过早收敛的现象，但收敛速度相对较慢。其变异策略公式为：

其中，Vit代表经过变异之后的新矢量（下文同），r1、r2、r3、r4、r5是从｛1，2，…，NP}（NP为解种群规模）中随机选取的整数，且其值互不相同，分别是r1、r2、r3、r4、r5对应的个体的第t维差分矢量缩放因子，F控制着变异矢量对基矢量的影响，本文中F取0.5。

（2）DE/current_to_rand/1

DE/current_to_rand/1变异策略中，两个差分矢量的规模因子分别为［0，1］、［0.6，1］区间均匀分布的随机变量，使得该变异策略保持了种群多样性，同时也具备了一定的局部搜索能力。其变异策略公式为：

其中r1、r2、r3、r4是从｛1，2，…，NP}（NP为解种群规模）中随机选取的整数，且其值互不相同分别是r1、r2、r3、r4对应的个体的第t维。Xit是基矢量，该策略中以等待变异的原个体的矢量作为基矢量。差分矢量缩放因子F控制着变异矢量对基矢量的影响，本文中F取［0.6，1］。rand是均匀分布的随机变量，范围为［0，1］。

（3）DE/best/2

DE/best/2变异策略中，以两个差分矢量对当前代全局最优解进行扰动，具有很强的局部搜索能力，收敛速度快，但极易陷入局部最优。其变异策略公式为：

其中，r1、r2、r3、r4是从｛1，2，…，NP}（NP为解种群规模）中随机选取的整数，且其值互不相同，分别是r1、r2、r3、r4对应的个体的第t维。是基矢量，该策略中以当代适应度值最优的个体的矢量作为基矢量。差分矢量缩放因子F控制着变异矢量对基矢量的影响，本文中F取［0.6，1］。rand是均匀分布的随机变量，范围为［0，1］。

基于上述3种策略，本文引入多策略随机选择框架，每次进化随机选择策略池中的策略，即设定｛1，2，3}中每个整数对应一个变异策略，每次进行变异操作前，随机生成｛1，2，3}中任意一个整数，调用相应的变异策略。

变异策略池中，DE/rand/2有较强的全局搜索能力，不易陷入局部最优；DE/current_to_rand/1保持了种群多样性；而DE/best/2具有很强的局部搜索能力，收敛速度快，本文算法引入多策略随机选择框架，调用具有不同特性的变异策略，以随机的方式进行搜索能力和收敛速度的均衡，增加了种群中个体的多样性，避免了过早收敛及陷入局部最优。同时，增加多策略随机选择框架的改进DE算法与原始DE算法的时间复杂度相同O（NP·D），与原始DE算法一样简单，便于实现。MDDE算法流程具体如下。

步骤1初始化

置进化代数计数器g=1，并在搜索空间中随机初始化种群。

步骤2依据式（3），计算初始化种群的目标矢量的适应度值。

步骤3While终止条件不满足Do

Fori=1：NP

步骤3.1变异操作

随机产生｛1，2，3}中任意一个整数x，调用相应的变异策略生成变异矢量Vit，进行越界修正。

步骤3.2交叉操作

变异矢量Vit与目标矢量Xit进行二项交叉操作，根据式（5）生成试验矢量Uit=（ui1t，…，uiDt），进行越界修正。

步骤3.3选择操作

计算目标矢量和试验矢量的适应度值，将其混合排序比较，取最优的NP个矢量。

End For

g=g+1

End While

4 实验和分析

由于目前尚未有标准的实验平台以及测试数据，因此本文在实验的时候采取随机产生QoS数据来仿真验证算法的性能。实验中使用的Web服务数据具有如下特性：一个功能相对复杂的个性化服务由10个功能相对单一的服务WS1～WS10组合而成，每个服务的候选服务数为100，各候选服务的3维QoS指标数据（响应时间、可用性、执行代价）随机产生取值范围均是，各维对应权重分别设置为1/3、1/3、1/3。

实验中选取原始DE算法作为比较对象。设置原始DE算法以DE/best/1为变异策略，差分矢量缩放因子取0.5，MDDE算法中的差分矢量缩放因子以及一些参数均在第4.2节给出，MDDE算法和原始DE算法的交叉概率均取0.5，且使用相同的选择策略，最大迭代次数同为100，种群规模均为100。鉴于智能算法的随机性，每次试验运行100次，记录算法求解的最大值、最小值、平均值。

图2表示的是原始DE算法以及MDDE算法求得的解的平均适应度值随着迭代次数增加的收敛过程。原始的DE算法虽然具有很强的局部搜索能力，收敛速度快，但容易陷入局部最优，体现在折线图上是，在迭代60次以后，原始DE算法求解得平均适应度值已不再变化。MDDE算法在算法初期收敛相对缓慢，在60代之前其平均适应度值不大于原始DE算法，经过60次迭代以后，与原始DE算法陷入局部最优解不同，MDDE算法仍然能够继续提升求解精度直至到达算法终止条件。出现这种情况的原因在于：MDDE算法中采用了多策略和随机选择机制，意味着算法具备多种演化能力，可以有效避免单一进化机制导致的局部收敛，具备全局探索能力，维持了解种群的多样性，避免了过早收敛。

图2 算法平均适应度值演变趋势

图3描述了两种算法运行100次，所得解适应度的最大值、最小值、平均值的对比情况。对比柱状图，能够发现，同样的运行次数100，同样的最大迭代次数100，MDDE算法在适应度最大值、最小值、平均值都全面优于原始算法。更优的最大值、最小值表明MDDE算法拥有更好的全局以及局部寻优能力；更优的平均值说明MDDE算法的稳定性更好。

图3 算法运行100次数据统计

5 结束语

移动互联网技术的普及，使人们不再满足于单一功能的服务，或仅仅是在数量上的服务集成，而更倾向于按需定制的个性化服务或服务组合。本文首先提出了一种多策略离散差分进化算法，MDDE算法采用随机选择框架，调用具有不同特性的变异策略，具备较好全局探索能力，能维持解种群的多样性，避免过早收敛。然后将MDDE算法应用于基于QoS的Web服务组合优化问题。仿真实验表明，MDDE算法是一种搜索能力和收敛速度均衡的离散差分进化算法，在求解Web服务组合优化问题中比原始DE算法的收敛精度和稳定性更高。

参考文献：

［1］张平.移动泛在融合的通信业务发展趋势［J］.电信工程技术与标准化，2008（1）：1-5.ZHANG P.Towards mobile and ubiquitous convergent communication service［J］.Telecom Engineering Technics and Standardiziation，2008（1）：1-5.

［2］QIU X F，LIU J W，ZHAO P C.Secure cloud computing architecture on mobile internet［C］/The 2nd International Conference on Artificial Intelligence，Management Science and Electronic Commerce（AIMSEC），August 8-11，2011，Dengfeng，China.New Jersey：IEEE Press，2011：619-622.

［3］BENYAMINA D，HAFID A，GENDREAU M.Wireless mesh networks design-a survey［J］.Communications Surveysamp;Tutorials，2012，14（2）：299-310.

［4］沈晶歆.移动互联网关键技术及典型业务产品研究［J］.电信科学，2010（10）：5-12.SHEN J X.Research of key technique and typical applications in mobile internet［J］.Telecommunications Science，2010（10）：5-12.

［5］FRANGOUDIS P A，POLUZOS G C，KEMERLIS V P.Wireless community networks：an alternative approach for nomadic broadband network access［J］.Communications Magazine，2011，49（5）：206-213.

［6］曾桂根，韩小燕，陈伏州，等.基于模式感知的无线异构网络融合方案［J］.南京邮电大学学报：自然科学版，2011，31（3）：14-20.ZENG G G，HAN X Y，CHEN F Z，et al.Wireless heterogeneous network convergence scheme based on mode awareness［J］.Journal of Nanjing University of Posts and Telecommunications：Natural Science，2011，31（3）：14-20.

［7］KIM W，KIM K S.Trial of communication services based on wireless ubiquitous network［C］/The 40th International Conference on Computers and Industrial Engineering（CIE），July 25-28，2010，Hyogo，Japan.New Jersey：IEEE Press，2010：1-5.

［8］岳昆，王晓玲，周傲英.Web服务核心支撑技术：研究综述［J］.软件学报，2004，15（3）：428-442.YUE K，WANG X L，ZHOU A Y.Underlying techniques for Web services：A survey［J］.Journal of Software，2004，15（3）：428-442.

［9］肖芳雄，黄志球，曹子宁，等.Web服务组合功能与QoS的形式化统一建模和分析［J］.软件学报，2011，22（11）：2698-2715.XIAO F X，HUANG Z Q，CAO Z N，et al.Unified formal modeling and analyzing both functionality and QoS of Web services composition［J］.Journal of Software，2011，22（11）：2698-2715.

［10］DUSTDAR S，SCHREINER W.A survey on web services composition［J］.International Journal of Web and Grid Services，2005，1（1）：1-30.

［11］SHENG Q Z，QIAO X，VASILAKOS A V，et al.Web services composition：A decade’s overview［J］.Information Sciences，2014（280）：218-238.

［12］DUAN Q.Network service description and discovery in ubiquitous and pervasive grids［C］/2008 IEEE GLOBECOM Workshops，November 30-December 4，2008，New Orleans，Louisiana，USA.New Jersey：IEEE Press，2008：1-5.

［13］PENG K，BAO F.A design of secure ubiquitous network service［C］/The 4th International Conference on Ubiquitous Information Technologiesamp;Applications，December 20-22，2009，HongKong，China.New Jersey：IEEE Press，2009：327-331.

［14］LEE K，JEON J，LEE W，et al.Qos for web services：requirements and possible approaches［J］.W3C Working Group Note，2003，25（3）：1-9.

［15］HAO Y，ZHANG Y，CAO J.A novel QoS model and computation framework in web service selection［J］.World Wide Web，2012，15（5-6）：663-684.

［16］ZENG L Z，BENATALLAH B，NGU A H H，et al.QoS-aware middleware for Web services composition［J］.IEEE Transactions on Software Engineering，2004，30（5）：311-327.

［17］ZHENG Z，MA H，LYU MR，et al.Collaborative web service QoS prediction via neighborhood integrated matrix factorization［J］.IEEE Transactions on Services Computing，2013，6（3）：289-299.

［18］YILMAZ A E，KARAGOZ P.Improved genetic algorithm based approach for QoS aware web service composition［C］/2014 IEEE 21st International Conference on Web Services（ICWS 2014），June 27- July 2，2014，Anchorage，Alaska，USA.New Jersey：IEEE Press，2014：463-470.

［19］张成文，苏森，陈俊亮.基于遗传算法的QoS感知的Web服务选择［J］.计算机学报，2006，29（7）：1029-1037.ZHANG C W，SU S，CHEN J L.Genetic algorithm on Web services selection supporting QoS［J］.Chinese Journal of Computers，2006，29（7）：1029-1037.

［20］XU T，WANG X H.Web service composition based on multi-objective particle swarm optimization algorithm［J］.Computer Engineering and Design，2010，31（18）：4076-4081.

［21］温涛，盛国军，郭权，等.基于改进粒子群算法的Web服务组合［J］.计算机学报，2013，36（5）：1031-1046.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.

［22］HE J，CHEN L，WANG X，et al.Web service composition optimization based on improved artificial bee colony algorithm［J］.Journal of Networks，2013，8（9）：2143-2149.

［23］WANG P.QoS-aware web services selection with intuitionistic fuzzy set under consumer’s vague perception［J］.Expert Systems with Applications，2009，36（3）：4460-4466.

Personalized service com position based on multi-strategy discrete differential evolution in mobile internet

XU Bin，QI Jin，YIN Xi，WANG Ye，CHANG Ruiyun
School of Internet of Things，Nanjing University of Posts and Telecommunications，Nanjing 210003，China

With the popularity of mobile internet technology，people are not satisfied with the service that provides a single function and hope to gain the personalized or composition service according to their needs.A muti-strategy discrete differential evolution（MDDE）algorithm applied in Web service composition was put forward.The algorithm，which adopts a random selection framework and multi-mutation strategies with different properties，was the balance of search ability and convergence speed.The results indicate that the proposed algorithm is better than traditional differential evolution algorithm in solving Web service combination optimization problems in terms of the solution quality and stability.

Web service composition，differential evolution，multi-strategy mutation

s：China Postdoctoral Science Foundation Funded Project（No.2015M571790），NUPTSF（No.NY213047，No.NY213050，No.NY214102）

TP18

10.11959/j.issn.1000-0801.2016042

2015-09-01；

2015-12-21

中国博士后科学基金资助项目（No.2015M571790）；南京邮电大学引进人才科研启动基金和校级科研基金资助项目（No.NY213047，No.NY213050，No.NY214102）