基于改进蚁群算法的Ｗｅｂ 服务组合优化

摘 要：为解决基础蚁群算法存在的前期搜索速度慢、后期容易陷入局部最优解的问题，针对服务组合的动态性、不稳定性以及非功能属性限制等情况，提出基于改进蚁群算法的 Web 服务组合优化方法首先分别介绍基本蚁群算法和 L-I-ACO 改进蚁群算法，再将其应用到 Web 服务组合优化建模中，最后通过对比实验测试两种算法的性能。实验结果表明，L-I-ACO 改进蚁群算法性能较好，它弥补了基础蚁群算法的不足，提高了动态组合优化过程中的准确率和效率，更利于选取符合客户要求的服务

关键词：改进蚁群算法;Web 服务组合优化;动态服务组合;L-IACO 算法

中图法分类号：TP393文献标识码：A

１ 引言

动态服务组合技术是当前的研究热点，在动态服务组合的整个流程中，需要选取符合用户要求的服务，这涉及选取相同属性的多个服务和组合服务。随着提供的服务不断增多，选取服务问题的范围快速扩大，因此解决动态服务组合中的服务选取问题变得尤为重要［１～２］ 。这种解决服务选取问题被称为服务组合优化，是一个ＮＰ 难问题。由于Ｗｅｂ 服务或许存在状态不稳定、服务非功能属性经常变化等情况，因此动态服务组合中的服务选取问题需要一种能够动态适应各种服务状态变化的最优算法［３］ 。

目前，研究的一些主要方法包括贪心算法、遗传算法、神经网算法等。其中，贪心算法简单易用，但往往不能得到全局最优解；遗传算法可以较好地处理复杂的组合优化问题，但计算量较大；神经网络算法可以快速实现并具有适应性，但对服务的不确定性和动态性处理效果有限；传统的蚁群算法有收敛速度慢和易于停滞等缺点，无法很好地解决组合服务优化中存在的多种非功能属性约束的问题［４～６］ 。因此，为解决上述问题，本文使用改进蚁群算法进行服务组合优化，其不仅性能良好，而且能应付Ｗｅｂ 服务的动态特性。其特点是能适应动态服务优化，在非功能属性值计算过程中可及时调整计算方式，而且需设参数少，操作简单，优化速度快，结果准确性高。

２ 基于改进蚁群算法的Ｗｅｂ 服务组合优化

２．１ 基本蚁群算法描述

蚁群算法（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ） 是由Ｄｏｒｉｇｏ 等在１９９１ 年的第一屆欧洲人工生命会议上提出的一种随机搜索算法，该算法是通过模拟大自然中蚂蚁寻找食物的过程而得出的［７］ 。蚁群算法是仿生优化算法的一种，其特点有鲁棒性强、并行分布式计算，以及易与其他方法结合等。经过蚂蚁之间互相配合、协调工作，在多个目标优化问题中找到最好的解决方式。该方法在动态组合规划问题、车辆路径问题和旅行商问题等方面已得到广泛的应用［８］ 。

采用蚁群算法处理Ｗｅｂ 服务组合优化问题的主要方式是蚂蚁的位移过程，用此算法计算Ｗｅｂ 服务组合优化模型时，每当蚂蚁路过一个抽象服务下的ＣＳ时都需要计算候选ＣＳ 的转移概率，候选ＣＳ 指蚂蚁所在位置的ＣＳ 和下一个ＡＳ 中间含有的全部ＣＳ。公式所示为该转移概率计算方法：

２．２ Ｌ?Ｉ?ＡＣＯ 算法的设计与实现

２．２．１ Ｌ?Ｉ?ＡＣＯ 算法状态转移概率

当Ｗｅｂ 服务组合需要解决多个非功能性属性约束的问题时，随着循环次数不断增加，基本蚁群算法因其具有收敛速度慢、易于停滞的缺点，容易导致信息素在局限的少量路径上停留，易出现循环停滞现象。这样得到的处理结果只能算是局部优化，所以基本蚁群算法无法很好地解决这个问题［９］ 。因此，本文研究了Ｌ?Ｉ?ＡＣＯ 改进蚁群算法来解决Ｗｅｂ 服务组合优化问题。

２．２．２ Ｌ?Ｉ?ＡＣＯ 改进蚁群算法

一个抽象服务含有多个候选服务实例，如图１ 所示，多个候选服务存在于２ 个节点中间。若优化处理每一个路径，则是一个十分大的计算工程，大幅增加了组合优化问题的难度。但是，若努力缩小优化问题的范围，将大范围分解成小范围，则可降低算法的寻优难度。

Ｌ?Ｉ?ＡＣＯ 算法从预计算部分和随机选取寻优部分两个方面展开计算，预计算部分把近似同类属性的服务分到一起，成为一个节点并增加限定要求，去掉属性不相近的服务，以缩小搜索范围。

给同类属性分类时，可采用近似值匹配的方法。若把含有ｎ 个非功能性属性Ｑ 的服务设为ｓ，将代表这些属性的量化值转换成函数Ｑ１（ｓ），Ｑ２（ｓ），…，Ｑｎ（ｓ），把含有ｍ 个非功能性属性Ｑ 的服务设为ｓ′，将代表这些属性的量化值转换成函数Ｑ′１（ｓ′），Ｑ′２（ｓ′），…Ｑ′ｍ（ｓ′），若ｓ 和ｓ′服务属性相似，则ｎ≈ｍ，Ｑ１（ｓ）≈Ｑ′１（ｓ′）…，因此可以计算这２ 个服务的指标，如公式（６）所示：

Ｃ（ｓ，ｓ′）＝ Σ ｍｉｎ（ｎ，ｍ）ｒ ＝１ （Ｑｒ（ｓ）－Ｑ′ｒ（ｓ′））２ （６）

可以看出，若ｓ 和ｓ′相似，则Ｃ（ｓ，ｓ′）接近于０，因此可以判断２ 个服务的近似度。但此方法并不完善，若ｓ 和ｓ′的匹配度接近０，同时ｓ′和ｓ″的匹配度也接近０，则此时很难自动把该３ 个服务规分为一类。这种状况下，需考虑先把ｓ′和ｓ″分到一类，之后继续分配其他服务，待计算好所有服务近似匹配分类后，若发现ｓ″与某一类的大部分服务匹配度接近０，则可把ｓ″分到这一类。

由于动态服务组合以及服务质量的诸多因素具有不确定性，因此对状态转移概率的路径选取进行了改变，具体做法如下：首先，采用改变计算概率值或随机的方式选取服务；其次，筛选出不满足条件的服务，这时就可采用状态转移概率的方式，这一操作可缩小服务选择范围，降低计算难度，提高计算速度，详细算法如下。

假如最大循环次数可用Ｎｃｍａｘ 表示；蚂蚁个数用Ｍ 表示；最优服务列表用Ｌｉｊ表示，其中ｉ 和ｊ 代表需要服务选择分类的服务组合中的抽象服务，即Ｓｉｊ 中设ｔ＝０ 代表初始化时间、Ｎｃ ＝０代表循环控制变量、ｋ ＝０ 代表蚂蚁循环变量。

为解决服务组合优化问题，则需使式（１９）中的５个目标函数都达到最小，服务组合优化后的解集便是得到的Ｐａｒｅｔｏ 最优解集。

３ 实验

本实验在两种情况下分别测试基本蚁群算法和Ｌ?Ｉ?ＡＣＯ 改进蚁群算法的Ｗｅｂ 服务组合优化的成功率，情况１ 是任务节点数是２０，服务数是４８；情况２ 是任务节点数是３５，服务数是１１０。每种情况测试８ 次。结果如图２、图３ 所示。

通过分析图２ 和图３ 曲线可得：基本蚁群算法在服务数是４８ 时，随着迭代次数的增加，成功率呈波动状态，不稳定，且总体成功率都在０．７ 以下。当服务数是１１０ 时，曲线波动减少，但是成功率较低且一直没有超过０．６，说明基本蚁群算法收敛速度慢，容易陷入局部最优解，无法高成功率地实现最终服务组合优化。Ｌ?Ｉ?ＡＣＯ 改进蚁群算法性能相对较好，在服务数是４８ 和服务数是１１０ 时，都能达到平均成功率９０％以上，虽在迭代初期曲线稍有波动，但最后都达到平稳高度，证明本文研究的Ｌ?Ｉ?ＡＣＯ 改进蚁群算法既弥补了基本蚁群算法的不足，又能大幅提高了Ｗｅｂ 服务组合优化的成功率。

４ 结束语

随着互联网技术的发展，网络上涌现了大量种类繁多的Ｗｅｂ 服务，但其中很大一部分Ｗｅｂ 服务提供的功能是相互重叠的，并且这些服务的功能多数是小粒度的，难以充分满足用户需求。为解决这些问题，Ｗｅｂ 服務组合技术应运而生。Ｗｅｂ 服务组合将具有相同功能的Ｗｅｂ 服务合并为集合，并根据用户需求选择组合多个简单的Ｗｅｂ 服务，以形成新的功能更强大的Ｗｅｂ 服务。本文旨在提出一种高效方法，从众多的Ｗｅｂ 服务数据库中，选择出满足用户需求且满足ＱｏＳ 限制的Ｗｅｂ 服务，进而组合成更优的Ｗｅｂ 服务。本文通过对基本蚁群算法进行改进，提出了Ｌ?Ｉ?ＡＣＯ 改进蚁群算法，既弥补了普通蚁群算法的不足，又能高效率、高准确率地选取满足客户需求的Ｗｅｂ 服务组合。

参考文献：

［１］ 倪志伟，方清华，李蓉蓉，等．改进蚁群算法在基于服务质量的ＷＥＢ 服务组合优化中的应用［Ｊ］．计算机应用，２０１５，３５（８）：２２３８?２２４３＋２２７９．

［２］ 颉斌，杨扬，王洁莹．基于ＭＡＰＲＥＤＵＣＥ 改进蚁群算法的ＷＥＢ 服务组合优化［Ｊ］．微型机与应用，２０１６，３５（８）：６１?６４．

［３］ 陈宇锋．改进蚁群算法在ＷＥＢ 服务中应用与实现［Ｄ］．长沙：湖南大学，２０１９．

［４］ 曹腾飞，符云清，钟明洋．融合遗传蚁群算法的ＷＥＢ 服务组合研究［Ｊ］．计算机系统应用，２０１２，２１（６）：８１?８５．

［５］ 承松，周井泉，常瑞云．混沌蚁群算法的ＷＥＢ 服务组合优化研究［Ｊ］．计算机技术与发展，２０１７，２７（２）：１７８?１８１＋１８６．

［６］ 夏亚梅，程渤，陈俊亮，等．基于改进蚁群算法的服务组合优化［Ｊ］．计算机学报，２０１２，３５（２）：２２７０?２２８１．

［７］ 谢琴．蚁群算法在ＷＥＢ 日志挖掘中的研究与应用［Ｄ］．重庆：重庆大学，２００６．

［８］ 马文龙，王铮，赵燕伟．基于改进蚁群算法的制造云服务组合优化［Ｊ］．计算机集成制造系统，２０１６，２２（１）：１１３?１２１．

［９］ 承松．云计算环境下基于蚁群算法的ＷＥＢ 服务组合研究［Ｄ］．南京：南京邮电大学，２０１７．

［１０］ 李东星，陈喆，钱双洋，等．改进蚁群算法及其在云服务组合优化中的应用研究［Ｊ］．计算机应用与软件，２０１７，３４（３）：１３?２０＋２６．

作者简介：

裴毓（ １９８９—）， 硕士， 助理工程师， 研究方向： 计算机网络。