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

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

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

１ 引言

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

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

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

２．１ 基本蚁群算法描述

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

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