刘 彬，张仁津

（贵州师范大学 数学与计算机科学学院，贵州 贵阳550001）

0 引 言

Web服务作为面向服务的体系结构 （service oriented architecture，SOA）软件的一种重要形式，已广泛得到工业界和学术界的认可并应用于金融、电子商务、电子政务、物联网等多个领域。通常，单个Web服务的功能比较有限，很难满足复杂的业务需求，所以需要依据业务需求将这些单个服务根据功能和服务质量 （quality of service，QoS）集成为组合服务［1－3］，完成复杂的业务。随着公共网络上web服务的种类和数量日益增多，虽然这为Web服务组合提供了广泛的资源，但也为Web服务组合带来了新的问题，从大量的组合方案中找出满足用户要求的最优方案并不是一件容易的事，这是一个NP难问题。例如在一个业务包括10子任务，每个子任务通过调用具体Web服务来实现的，若每个子任务有10个候选服务，则该业务的组合方案就有1010种。如何对候选服务进行选择，得到最优的服务组合方案，成为亟待解决的问题。文献 ［4］提出一种基于事件的服务组合方法，以简单服务事件语言为基础，通过模块化方法构造组合服务方案。文献 ［5］以Bayes方法对Web服务的信任模型，以遗传算法进行服务组合，但没有考虑Web服务中的各种QoS属性的冲突问题，这可能会导致对Web服务的要求过高等问题，间接增加了使用者的成本。更多研究者是以QoS属性为基础实现Web服务组合，采用的算法包括量子贪心算法［6］、量子遗传算法［7］、免疫遗传算法［8］、蚁群算法［9］、禁忌搜索和模拟退火相结合的混合算法［10］、禁忌搜索算法［11］、蚁群算法［12］。这些研究工作虽然采用了不同的算法实现Web服务组合，但都是采用某种方法把多种不同的QoS属性要求人为转换成为一个目标函数，这种转换都可能导致与用户的实际关注要求有偏差，容易导致用户得不到最合适的服务。普通用户通常只能给出组合服务QoS属性 （如服务价格，服务时间，可用性等）的最低要求，而这些要求很难同时达到最优，有时这些属性还有可能是对立的，如服务时间短的服务通常服务价格会比较高，所以Web服务组合优化问题是一个典型的多目标优化问题。在我们的研究工作中，是把Web服务组合作为多目标优化问题进行处理，即针对服务的多个QoS属性进行优化，更符合使用者的要求。

1 多目标优化问题的数学描述

不失一般性，一个多目标优化问题可以定义为一个三元组：（X，C，F）。其中X是n维决策空间，即x＝ （x1，x2，…，xn）X；C是一组决策变量必须同时满足的约束集合；F是含有m≥2个目标函数的矢量，可表示为：F＝（f1（x），f2（x），…，fm（x））。多目标优化就是让些不同的目标函数最小化。

定义1（可行解） 如果xX且满足C中的所有约束条件，则称x为可行解。

定义2（可行解集合） 所有可行解的集合称为可行解集合，记为Xf，显然XfX。

定义3（Pareto占优） 假设xA，xBXf，则xA对xB是Pareto占优的充要条件是：i＝1，2，…，m，fi（xA）≤fi（xB）且j＝1，2，…，m，fj（xA）＜fj（xB），记为：xAxB，也称为xA支配xB。

定义4（Pareto最优解） 如果一个可行解x＊满足条件：xXf使xx＊，则x＊被称为Pareto最优解（或非支配解）。

定义5（Pareto最优解集） 所有Pareto最优解的集合称为Pareto最优解集。

多目标优化的目标就是找出非支配解的Pareto最优解集。但在实际工作中，由于Pareto最优解集可能会有太多的元素甚至是无限集合，导致计算机效率很低甚至无法完成，因此在实际工作中更倾向于搜索出一个分布均衡的Pareto最优解集的子集。

2 Web服务组合模型

一个复杂的业务可以分成m个子任务，每个子任务都有一个或多个Web服务可以完成所需的功能，实现这个业务的Web服务组合如图1所示，S为任务起点，E为任务终点，WSi（i＝1，2，…，m）为能够完成第i个子任务的候选Web服务集合，从S到E的任何一条路径所包含的Web服务即为可以完成此业务的组合服务 （只考虑了功能）。Web服务可以表示为Wij＝ ｛Fij，Qij｝，其中Fij为功能属性集合；Qij为服务质量属性集合。显然候选Web服务集合WSi中Web服务实体的F都能完成第i个子任务的功能。每个Web服务的Q都包含n个QoS属性，即Qij＝｛，，…，｝。

图1 Web服务组合模型

3 基于QoS的多目标蚁群优化

蚁群优化最初是用于解决旅行商这一经典组合优化问题，很快应用于顺序排序、广义分配、多重背包、网络路由等各种各样的问题。现在许多研究者开始研究多目标蚁群优化［13－14］，并已成功用于资源分配［15］、旅行问题［16－17］、

网格计算［18］、流水作业调度［19］、开放工厂安排［20］等。

3.1 QoS属性的预处理

根据第1节的描述，多目标优化中采用的标准是：目标函数数值越小，则性能越优。但对于Web服务的QoS属性来说，并不是全部满足这种要求。QoS属性可以分为两类，一类是负属性，这类属性取值越大，性能越低，如执行时间、服务价格等；另一类是正属性，这类属性取值越大，性能越高，如服务评价、可用性等。而且各种不同属性的数值属性差别很大，例如价格是货币单位，而可用性是百分比。我们为了把这种存在着巨大差异的各种属性用于多目标蚁群优化的单一启发式信息中 （因为在我们的方案中是采用各种QoS属性启发式信息之和作为启发式信息），必须要让它们的数值不能相差太大，否则会导致数值过大的启发式信息淹没数值很小的启发式信息。同时还要满足目标函数规定的数值越小性能越好的要求，所以需要对Web服务的QoS属性进行预处理。

如图1所示结构中的任一Web服务Wij，设它有n个QoS属性，即Qij＝ ｛，，…，｝。若第r个属性为负属性，其处理后的属性vrij如式 （1）所示。若第r个属性为正属性，其处理后的属性如式 （2）所示，其中是图1中全部Web服务中第r个属性中的最大值，分子中加1是为了保证分子不为0（为了用于启发式信息）。式（1）、式 （2）中的表示图1中全部 Web服务的第r个属性之和。通过式 （1）、式 （2）就能把 Web服务的所有QoS属性值都转换到具有这样的特征：

（1）数值越小表示相应性能越好；

（2）每个属性都是与同类属性数值之和的一个比例值，不同属性数值之间比原始数值更具有可比较性；

（3）因为各种QoS属性转换后的数值差别不会特别大，不会出现大数值掩盖小数值的问题，可以方便用于蚁群优化中的启发式信息

由于服务使用者在请求服务时要求的是组合服务的QoS属性，为了确保数值的一致性，也必须做类似处理，设服务使用者要求的QoS属性Q＝ ｛q1，q2，…，qn｝，则QoS属性qr如果是负属性，按式 （3）处理，如果为正属性则按式 （4）处理，式 （3）、式 （4）分母与式 （1）、式（2）中的分母为相同的值，式 （4）中的qrmax和式 （2）中的qrmax相同

根据图1所示的模型，组合服务的QoS属性与其组合成员的QoS属性的关系与具体的属性有关，如组合服务价格是由成员服务价格之和确定，组合服务可用性是由成员服务可用性最低的决定。因为我们这里采用的是经预处理后的QoS属性，与未经处理的有所不同。如未处理的组合服务可用性是由成员服务可用性最低的确定，而经预处理后数值越小代表可用性越高，因此在经过我们这种方法预处理后，组合服务可用性是由成员服务可用性最高的确定。如图1所示，假设一个组合服务中需要m个成员服务，几种常用的组合QoS属性与成员QoS属性的关系如表1所示。

表1 组合服务QoS属性值

3.2 多信息素表的蚁群优化算法

要针对Web服务组合中的多个QoS属性进行优化，在蚁群优化中就是要把多个QoS属性转换为启发式信息和信息素进行处理，在我们算法中对每一个QoS属性 （对应一个目标函数）都分别用一个变量保存信息素和启发式信息。如服务实体Wij的第k个QoS属性的信息素表示为τki（j），第k个QoS属性的启发式信息表示为ηki（j）。蚂蚁在如图1所示Web组合图中选择下一个Web实体时按式 （5）的概率进行选择 （包括起始点和前m－1个候选服务集合），α和β参数分别决定了信息素和启发式信息的相对影响力。在式 （5）中采用的启发式信息并不是单个QoS属性的启发式信息，而是用户关注的所有QoS属性的启发式信息之和［17］，由式 （6）求出 （假设需要优化的QoS属性个数为n）。因为最终要优化的是用户关注的多个QoS属性，如果在此公式中采用单个属性的启发式信息，那么构建的解只会是对单个QoS属性的优化。因此我们在此采用全部用户关注的QoS属性的启发式信息之和作为蚂蚁选择路径的启发式信息，蚂蚁在选择路径时受到多个QoS属性启发式信息的影响，故所产生的结果就会同时对多个QoS属性对应的目标函数进行优化

信息素是蚁群系统中搜索解空间的基础，如果局部衰减得过小会导致探索的空间缩小到很小，如果局部信息素增长到过高会导致停滞现象，因此通常把信息素限制在一个区间 ［τmin，τmax］。用于 Web服务组合的多信息素蚁群算法求解的构建算法如下算法1所示。

算法1：多信息素蚁群优化算法

（1）所有信息素初始化为τmax；

（2）蚁群中每只蚂蚁从1～n（n为目标函数的个数）中随机选取一个值i，然后以第i个信息素表中的信息素

构建一个解 （详见算法2）；

（3）更新第i个信息素表中的所有信息素值 （详见3.3节）；

（4）如果达到最大循环次数就结束，否则跳转到 （2）。

算法2：解的构建算法

（1）初始化解为空；

（2）按式 （5）的概率选择下一个服务，并把选中的服务加入解中；

（3）如果无后续服务则返回，否则转到 （2）。

3.3 信息素更新

信息素是蚁群优化算法中引导蚂蚁行为的一个至关重要的因素，因此信息素的更新是蚁群优化的一个核心问题。为了让信息素能有效地引导蚂蚁构建出良好的解，我们采取的措施是在每一个循环周期内所有蚂蚁都随机地选择一个信息素表，并依据此信息素表构建解后按以下方法更新信息素：首先，为模拟信息素的蒸发，信息素表中的所有信息素都要减少一部分，如式 （7）所示，其中ρ∈ （0，1）为蒸发因子；其次，在当前循环内可以得到n个与目标函数 （对应n个QoS属性）对应的最优解，设Si为当前循环中使第i个目标函数fi最小的解，为从第一个循环开始到当前循环 （包括当前循环）中得到使第i个目标函数fi最小的解，在第i个信息素表中Sibest包含的Web服务的信息素增加一个量△τk，如式 （8）所示。△τk由式 （9）求出，即当前循环中如果Si优于，则△τk＞1，且Si越好，△τk的值越大；否则△τk≤1，且Si越差，△τk的值越小。如果当前循环中如果Si优于Sibest，信息素更新后，＝Si。因此，经过信息素更新后，没有被选择的候选服务的每个信息素的值都会减少一部分 （除非已经降低至τmin），具体算法见算法3。

算法3：信息素更新算法

（1）初始化i＝1；

（2）按式 （7）更新第i个信息素表中的信息素值，如果某个信息素的值小于最小值τmin则设置为τmin，如果某个信息素的值大于最大值τmax则设置为τmax；；

（3）把所有解分别代入fi求出Si，依据式 （9）求出△τk，把当前循环最优解Si中包含的所有Web服务在第i个信息素表中对应的信息素的值增加△τk。如果某个信息素的值小于最小值τmin则设置为τmin，如果某个信息素的值大于最大值τmax则设置为τmax；

（4）如果Si优于Sibest，Sibest＝Si；

（5）如果还有未更新的信息素表，i增加1，跳转到（3）；否则返回。

4 仿真实验及分析

假设一个业务可以由10个子任务组合而成，每个子任务都有10个候选Web服务。需要优化如表1所示的4个QoS属性，故可定义如式 （10）所示的4个目标函数

其它参数取值：τmin＝10，τmax＝100，ρ＝0.01，蚂蚁数取100，循环次数取1000，启发式信息ηi（j）按式 （6）取值，服务实体Wij的第k个QoS属性的信息素因为篇幅的原因，只针对α＝2，β＝2和α＝1，β＝4两组参数进行比较，测试情况分别如图2和图3所示。●代表f1的平均值，■代表f2的平均值，▲代表f3的平均值，★代表f4的平均值。从图中可以看出，这4个目标函数随着循环次数的增加，全部都得到了优化，后一组参数目标函数收敛要明显快于前一组。其原因在于：蚂蚁在优化任何一种QoS质量属性时都要受到启发式信息的影响，而我们采用的启发式信息包含了全部需要优化的QoS质量属性的启发式信息，所以能同时对多个目标函数进行优化；后一组数据由于启发式信息对蚂蚁路径选择起到的作用更大，所以目标函数收敛更快。

通过仿真实验可知，我们能把Web服务组合问题作为多目标优化问题进行处理，将多种差别很大QoS属性经过预处理后用多信息素单启发式信息的蚁群优化能有效地实现多目标函数的优化，实验结果稳定，具有较好的鲁棒性，达到了预期的目标。

5 结束语

Web服务的组合是面向服务体系结构软件中的一个十分重要的问题，它极大地影响着Web服务应用的推广。以QoS属性为基础的Web服务组合涉及到QoS的多个属性，目前常用的方法是通过某种方法把多个QoS属性转化为一个量后再进行优化，但这种方法对权重很敏感，可能会导致与用户的实际关注要求有偏差。在我们的组合方法中把服务组合建模为多目标优化问题，对每个用户关注的QoS属性建立一个目标函数，采用多个信息素表和一个启发式信息表的蚁群优化对QoS多个属性同时进行优化，最终产生一组Pareto最优解。虽然多目标优化要比单目标优化要复杂得多，但这种多目标优化模型可以灵活地对用户感兴趣的QoS属性进行优化，搜索出的结果能更好地满足用户要求，因此有很好的用应前景。

［1］Farhan Hassan Khan，Younus Javed M，Saba Bashir，et al.QoS based dynamic web services composition ＆execution ［J］.International Journal of Computer Science and Information Security，2010，7 （2）：147－152.

［2］Piergiorgio Bertoli，Marco Pistore，Paolo Traverso.Automated composition of web services via planning in asynchronous domains［J］.Artificial Intelligence，2010，174 （3－4）：316－361.

［3］Esra Kirci Ozorhan，Esat Kaan Kuban，Nihan Kesim Cicekli.Automated web services composition with the event calculus［J］.Information Sciences，2010，180 （19）：3589－3613.

［4］LI Xin，CHENG Bo，YANG Guowei，et al.Method of web services composition based on events ［J］.Journal of Software，2009，20 （12）：3101－3116 （in Chinese）.［李鑫，程渤，杨国纬，等.一种基于事件的Web服务组合方法 ［J］.软件学报，2009，20 （12）：3101－3116.］

［5］YUN Ben－sheng，YAN Junwei，LIU Min.Method to optimize web service composition based on Bayes trust model［J］.Computer Integrated Manufacturing Systems，2010，16 （5）：1103－1110 （in Chinese）. ［云本胜，严隽薇，刘敏.基于Bayes信任模型的Web服务组合优化方法 ［J］.计算机集成制造系统，2010，16 （5）：1103－1110.］

［6］XU Bin，LUO Sen，YAN Yixin.Efficient composition of semantic web services with end－to－end QoS optimization ［J］.Tsinghua Science ＆ Technology，2010，15 （6）：678－686.

［7］LIU Feng，LEI Zhenming.Research on user－aware QoS based web services composition ［J］.The Journal of China Universities of Posts and Telecommunications，2009，16 （6）：125－130.

［8］CHEN Liang，SUN Min.Web services composition method based on immune genetic algorithm ［J］.Computer Engineering，2010，36 （10）：226－228 （in Chinese）.［陈亮，孙敏.基于免疫遗传算法的 Web服务组合方法 ［J］.计算机工程，2010，36 （10）：226－228.］

［9］WANG Chuangwei，QIAN Xuezhong.Application of ant colony algorithm in web services composition problem ［J］.Computer Engineering and Design，2007，28 （24）：5912－5915 （in Chinese）. ［王创伟，钱雪忠.蚁群算法在Web服务组合问题中的应用研究［J］.计算机工程与设计，2007，28 （24）：5912－5915.］

［10］Jong Myoung Ko，Chang Ouk Kim，Ick－Hyun Kwon.Qualityof－service oriented web service composition algorithm and planning architecture ［J］.The Journal of Systems and Software，2008，81 （11）：2079－2090.

［11］DONG Zongran，LI Yingqiu，CHEN Ming－hua.Web services composition optimization based on tabu search algorithm ［J］.Computer Engineering and Design，2010，31 （5）：942－945（in Chinese）.［董宗然，李迎秋，陈明华.基于禁忌搜索算法的Web服务组合优化 ［J］.计算机工程与设计，2010，31（5）：942－945.］

［12］SHEN Ji－quan，ZHENG Xuefeng，TU Xuyan.An approach to service composition based on ant colony algorithm ［J］.Journal of Wuhan University of Technology：Transportation Science ＆ Engineering，2009，33 （6）：1179－1182 （in Chinese）.［沈记全，郑雪峰，涂序彦.一种基于蚁群算法的服务组合方法 ［J］.武汉理工大学学报：交通科学与工程版，2009，33 （6）：1179－1182.］

［13］Daniel Angus，Clinton Woodward.Multiple objective ant colony optimization ［J］.Swarm Intelligence，2009，3 （1）：69－85.

［14］Christine Solnon，Khaled Ghédira.Ant colony optimization for multi－objective optimization problems ［C］.Proceedings of 19th IEEE International Conference on Tools with Artificial Intelligence. Patras： IEEE Computer Society， 2007：450－457.

［15］Chaharsooghi S K，Amir H Meimand Kermani.An effective ant colony optimization algorithm （ACO）for multi－objective resource allocation problem （MORAP） ［J］.Applied Mathematics and Computation，2008，100 （1）：167－177.

［16］Daniel Angus.Crowding population－based ant colony optimisation for the multi－objective travelling salesman problem ［C］.Proceedings of the IEEE Symposium on Computational Intelligence in Multicriteria Decision Making.Honolulu：IEEE Computer Society，2007：333－340.

［17］García－Martínez C，Cordón O，Herrera F.A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi－criteria TSP ［J］.European Journal of Operational Research，2007，180 （1）：116－148.

［18］YANG Yahong，WU Guiling，CHEN Jianping，et al.Multiobjective optimization based on ant colony optimization in grid over optical burst switching networks ［J］.Experts Systems with Applications，2010，37 （2）：1769－1775.

［19］Betul Yagmahan，Mehmet Mutlu Yenisey.Ant colony optimization for multi－objective flow shop scheduling problem ［J］.Computers ＆Industrial Engineering，2008，54 （3）：411－420.

［20］Hadi Panahi，Reza Tavakkoli－Moghaddam.Solving a multiobjective open shop scheduling problem by a novel hybrid ant colony optimization ［J］.Expert Systems with Applications，2011，38 （3）：2817－2822.