一种基于改进型遗传算法的Web服务选择

严良达

摘要：随着Web服务技术的快速发展和广泛应用，单个Web服务的功能已经无法满足复杂应用的需求，因而需要将原子服务进行组合，从而形成功能强大的组合服务以完成复杂事务。该文提出了改进的遗传算法，来解决基于QoS感知的Web服务组合问题，算法从编码方式、初始化种群、适应度函数、进化选择策略等方面对进行改进，使得服务选择算法具有更好的收敛速度和搜索寻优能力。

关键词：Web服务；遗传算法；QoS

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）35-8574-02

1 Web服务的定义

Web服务是一个独立于平台、自包含、松耦合、基于可编程的Web应用程序，可以使用开放的XML标准描述、发布、协调和配置这些应用程序，用于开发分布式的互操作的应用程序。通俗的来讲，对于Web服务访问者而言，Web服务就是一种部署在Web上的对象或组件，具备对象的良好封装性，用户只能通过服务接口对服务进行访问；Web服务基于标准的协议和规范被发布、部署和调用；当一个Web服务接口不发生变化，对于该服务的调用就不会发生变化，实现了调用的透明化；由于Web服务采用简单易于理解的标准协议作为组件界面描述，完全屏蔽了不同平台的差异，实现了当前环境下的高度集成性。

2 遗传算法概述

遗传算法是一种借鉴达尔文生物进化论和遗传学机理的生物进化计算模型，它通过模拟自然进化过程搜索最优解的算法。1975年，遗传算法由美国Michigan大学J.Holland教授所提出，他提出的为最初的遗传算法，即简单遗传算法。现在遗传算法广泛应用在很多学科中，应用领域主要有函数优化、生产调度、自动控制、机器人智能控制、组合优化、图像处理好热模式识别以及机器学习等，并且在工程技术和社会经济中的大量的应用。

在遗传算法中，主要使用的术语有以下几种：

组合路径：组合路径由一组抽象服务根据一定逻辑关系组合而成。

组合计划：组合计划是指组合路径中抽象服务被其对应的具体服务替换后形成的服务序列。

个体：在本文中，个体是指能完成用户请求的单个组合计划，也即问题可能潜在的解。

基因：在遗传算法的Web服务组合中，基因指的是Web服务组合中每个抽象服务。

基因位：Web服务组合中抽象服务在组合服务中的位置。

染色体：在遗传算法的Web服务组合中，染色体对应的是不同组合路径上的组合计划。

种群：在本文中，种群是代表问题一个可能潜在的解的集合，它具有一定数量组合计划，而且这些组合计划符合用户需求。

3 遗传算法的特点和运行过程

3.1遗传算法的特点

遗传算法作为一种有别于传统算法的搜索和优化方法，主要区别有下面几点：

1）遗传算法与传统算法最大的区别在于它行问题解的串集开始搜索，而不是从单个解开始。遗传算法从串集开始搜索，覆盖范围广，利于全局选优。传统的优化算法是从单个初始值迭代求最优解，容易陷入局部最优解。

2）遗传算法强调概率转换规则，而不是采用确定的转换规则来指引它的搜索方向。

3）遗传算法不必求导和其它方面的知识，仅仅使用一个适应度函数来评估个体，在此基础上进行遗传操作。

4）遗传算法可以同时处理群体中的多个个体，即对搜索空间中多个解进行评估，从而降低了陷入局部最优解的几率，同时遗传算法易于实现并行。许多搜索算法都是单点搜索，易陷入局部的最优解。

5）遗传算法还具有自组织性、自学习和自适应性。遗传算法在确定了染色体编码方式、遗传算子和适应度函数之后，就会利用演化过程中的信息进行组织搜索。由于采用基于达尔文生物进化论的选择策略，所以存活几率取决于个体适应度的大小。适应度越大的染色体个体将拥有更加适应所处环境的基因，进而通过基因重组、突变这些操作，可能会产生对环境有更加适应特性的个体。

3.2遗传算法的运行过程

遗传算法运算对象为M个个体组成一个种群，其与生物自然进化过程相似，算法运算过程也是一个不断循环迭代的过程。记第n代为P（n），经过一代的遗传演化后得到n+l代，记为P（n+1）。然后种群通过不断地遗传和进化，按照生物进化论的法则适应度高的染色体个体将遗传到下一代中，最后进化后得到的种群接近或者达到问题的最优解。遗传算法中，父代P（n）产生下一代，P（n+1）主要通过选择、交叉和编译操作来实现。选择操作是根据个体适应度进行选择进入下一代的个体。交叉操作是随机选择种群中个体以一定概率交换染色体个体上的部分基因，以得到新个体。变异操作是对种群个体以一定概率改变其基因位上的基因来产生新个体。

遗传算法的具体流程：

1）初始化种群：遗传算法中基本的个体为染色体，初始化时，每一个染色体的基因的值是随机产生的。随机产生是为了希望种群能够均匀的分布在整个解空间中。

2）计算适应度函数：透过计算每一个染色体的适应度值作为其在种群适应程度的指标，适应度大的染色体就有较高的几率进入下一代继续得以进化，而适应值低者则有较高几率被淘汰。

3）选择：依据母代中染色体之适应值来决定哪些染色体得以进入下一代或者被淘汰。即选择几率的大小取决于染色体适应值的好坏。适应值较差的染色体对于子代的贡献度较小，被淘汰的几率较大。与之相反，适应值较大的染色体可以产生优秀的子代，故有较高的几率进入下一代进化，如此一来进化的过程中，可以搜索的参数收敛至整体最优解的几率得到提高。

4）交配：通过选择，可以使母代染色体中较优秀的染色体在下一代中生存，但并未创造出新的个体，因此要通过交配和突变产生新的个体，以创造出更好的个体，基本做法为随机选择两个母代染色体，并随机获取一个或者多个交配点吗、，将染色体基因信息切割成多个片段，再通过两个母代染色体交换其染色体基因信息片段来产生新的个体。

5）突变：通过选择交配虽然能够有效的在已有的种群中搜寻，但其缺点是无法产生新的染色体，毕竟交配仍是交换原有的染色体基因，因此，必须利用突变来防止进化的过程过早收敛至区域最佳解，为此用随机选取一个母代染色体以及获取突变位置，并置换该位置的基因代码。过高的突变几率将造成整个进化的过程完全随机化，导致无法收敛至整体最佳解。

6）终止：进化过程是最后一步就是设置终止条件，否则进化过程将如同死循环不断运行，而对于能否顺利的收敛至最优解，设置合适的终止条件也是相当重要的一个环节。

4 改进的遗传算法流程

有了前面的理论基础，该文在应用遗传算法基础上进行改进，解决了基于QoS的服务组合中的关键问题。利用改进的一维染色体的编码，同时也使用优化的初始化种群生成策。在算法运行整个过程里，该文设计了带有动态惩罚机制的适应度函数对种群中的个体进行选择，相对传统遗传算法本文利用可动态变化的选择概率和交叉概率。算法流程图如图1所示。

算法具体流程描述如下：

1）染色体编码。采用染色体树型编码方式进行编码。

2） 初始化操作。根据文中提出的初始化策略进行种群初始化。

3） 个体评价。对种群中的所有个体进行个体适应度进行评价操作。

4）最优个体保存。找出种群中最优的个体，并对其进行保存。

5） 个体选择操作。基于种群中每个个体的适应度大小进行选择操作，个体选择的几率与适应度大小成正比例关系。

6） 交叉操作。对种群中的配对个体进行自适应的交叉操作。

7）变异操作。对种群中的个体进行自适应的变异操作。

8） 个体评价。对种群中的所有个体进行个体适应度进行评价。

9） 如果当前种群最优个体的适应度比历史最优个体的适应度高，则用当前种群最优个体替换历史最优个体；否则，用历史最优的个体替换当前群体中最差个体。

10）结束条件判断。判断条件是否达到终止条件，若达到则继续下一步骤，否则转到步骤（5）。

11）染色体解码。将得到的染色体序列转化为实际问题的解，即可执行的复合Web服务。

5 结束语

本文首先介绍了Web服务和遗传算法的基本概念，详细的阐述了遗传算法的特点和运行过程，针对Web服务组合中应用遗传算法的不足，从编码方式、初始化种群、进化策略等方面对服务选择遗传算法提出改进，使算法满足基于Qos感知的服务组合问题。基于QoS感知的Web服务选择是一个复杂的研究问题，下一步要做的工作是结合服务语义，构建更全面的QoS评价模型，使得服务选择不仅具有通用性，而且还具有支持服务的领域特性。

参考文献：

[1] 帕派佐格罗.Web服务原理和技术[M].龚玲，张云涛，译.北京：机械工业出版社，2010：169-202.

[2] 王阳阳，李俊.一种基于QoS全局最优的服务选择算法[J].计算机应用研究，2010，27（5）：1659-1661.

[3] 张文博，史维峰.基于BPEL和QoS的动态Web服务组合框架研究[J].计算机技术与发展，2009，19（11）：72-75.

[4] 程永上.Web服务组合建模与验证[M].北京：中国物资出版社，2011.