刘 彬，张仁津

（贵州师范大学 数学与计算机科学学院，贵州 贵阳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］。……