预防局部极优的高质量网络服务组合方法

本发明涉及一种高质量网络服务组合方法，特别涉及一种预防局部极优的高质量网络服务组合方法，属于网络服务组合方法技术领域。

网络服务是一种运行在互联网上的自包含、自描述、模块化的应用程序，根据一定的开放标准在网络上发布、查和调用。网络服务的概念和网络服务体系结构的提出可以将不同层次的软件或资源作为一个网络服务以统一的形式提供给用户，服务提供者就可以将自己所开发的软件作为一种网络服务提供给用户，而网络服务用户便可以根据自身需要选取该网络服务并加以利用，或是选取该网络服务与其它服务提供者提供的网络服务组合利用，这种软件开发方式已经成为一种新的范式。

随着面向服务技术的广泛应用，网络上的服务提供者向用户提供了越来越多功能相同的网络服务，使得用户在需要某种功能的网络服务时需要花费大量的时间和精力去搜索自己满意的网络服务，因此，在匹配功能需求的前提下，如何从众多功能相同的网络服务中快速准确发现服务质量良好的网络服务已成为网络服务组合技术的关键，网络服务组合方法是影响网络服务组合服务质量高低的关键因素。

根据网络服务组合自动化程度，可将网络服务组合分为静态组合、半自动组合和自动组合三种组合方式。目前，现有技术最常用的是静态组合方式，但静态组合方式缺点也十分明显，它需要事先了解所需的网络服务组合中各个原子网络服务之间的控制流和数据流的情况，这对于现实中不断变化的业务需求非常不利，因为很难将静态组合方式运用到实际中。现有技术的半自动组合方式则是根据网络服务组合所处领域建立相应的模型，然后在此模型的基础上结合实际需求动态构成网络服务组合。而自动组合方式由于过程过于复杂、开销很大，所以对自动组合方式的研究和应用很少，当前对网络服务组合的研究主要以半自动组合方式为主。

网络服务组合模型是由多个网络服务链接而成的结点串，各个结点可以有多个功能相同但非功能属性或服务质量不同的原子网络服务可供选取，结合实际服务质量需求，如何从各个结点的备选网络服务中选取合适的网络服务构成一个满足业务需求的网络服务组合，成为服务组合中的关键问题，现有技术服务质量优选的网络服务组合方法大致可归纳为以下两类。

一是用穷举法求解网络服务组合问题，将服务组合问题转换成一个数学问题，利用递归回溯的方法进行处理。穷举法列举出所有的网络服务组合方案，然后计算比较它们的服务质量性能并从中出服务质量性能最优的网络服务组合方案，采用穷举法能出最佳的网络服务组合方案，但随着问题规模的增大，穷举法所需占用的资源也就越多，当问题规模达到一定程度时，就很可能出现计算机内存溢出、计算时间过长等问题。所以，采用穷举法解决服务质量优选的网络服务组合问题有很大的局限性。

二是利用演化算法求解网络服务组合问题，现有技术将一些演化算法应用到求解基于服务质量网络服务组合问题中，这些演化算法包括人工神经网络、蚁算法、粒子算法以及遗传算法等，遗传算法主要的应用领域是最优化问题，在高维度组合优化问题中，组合方案随维度的增加而呈几何倍数增加，如果按照现有技术的穷举法，需要将所有可能组合方案一一列出后，再将这些组合方案两两对比，这个过程需要的计算资源非常大，对于这类高维组合问题，专注于寻求全局最优组合方案的做法是不可取的，应该专注于在众多组合方案中寻满足自己需求的组合方案。

现有技术依然没有从根本上解决网络服务组合的难题，现有技术的难点和本发明解决的问题主要集中在以下方面：

第一，网络服务组合是一个组合优化问题，现有技术典型的服务质量优选的网络服务组合方法主要采用穷举法，由于求最优解的穷举法复杂度太高，需寻求有效的近似解法以求最接近全局最优解的近似解，作为一种新的全局优化算法，遗传算法已在众多领域中取得令人鼓舞的成绩，但遗传算法在解决本发明所提出问题过程中收敛速度很慢，而且容易发生局部收敛现象，为克服这种缺陷，现有技术以一个较小的概率进行变异操作，以便跳出局部极小，但变异所起的作用有限，变异太小对解改进不大，变异太大会导致算法跳动；

第二，网络服务技术得到了广泛应用，许多企业或者个人将自己开发的程序作为一个网络服务发布到互联网上供他人使用，但这些发布在互联网上的网络服务大多功能简单，无法满足实际业务需求；对于组合优化问题，现有技术往往采用枚举或动态规划求解精确解，但这只适合规模不大的情况，但网络服务组合问题往往都是大规模、复杂的，所以解决实际问题大多采用模拟退火、蚁算法近似求解，但这些算法通常都存在陷入局部极优的缺点；

第三，现有技术最常用的服务组合是静态组合方式，但静态组合方式缺点也十分明显，它需要事先了解所需的网络服务组合中各个原子网络服务之间的控制流和数据流的情况，这对于现实中不断变化的网络服务组合业务需求非常不利，因为很难将静态组合方式运用到实际中，现有技术的半自动组合方式则是根据网络服务组合所处领域建立相应的模型，然后在此模型的基础上结合实际需求动态构成网络服务组合。而自动组合方式由于过程过于复杂、开销很大，所以对这方面的研究和应用很少；

第四，现有技术的穷举法求解网络服务组合问题，列举出所有的网络服务组合方案，然后计算比较它们的服务质量性能并从中出服务质量性能最优的网络服务组合方案，但随着问题规模的增大，穷举法所需占用的资源也就越多，当问题规模达到一定程度时，就很可能出现计算机内存溢出、计算时间过长等问题，采用穷举法解决服务质量优选的网络服务组合问题有很大的局限性；

第五，现有技术利用演化算法求解网络服务组合问题，包括人工神经网络、蚁算法、粒子算法以及遗传算法等，遗传算法主要的应用领域是最优化问题，在高维度组合优化问题中，组合方案随维度的增加而呈几何倍数增加，如果按照现有技术的穷举法，需要将所有可能组合方案一一列出后，再将这些组合方案两两对比，这个过程需要的计算资源非常大，对于这类高维组合问题，专注于寻求全局最优组合方案的做法是不可取的，应该专注于在众多组合方案中寻满足自己需求的组合方案。

针对现有技术的不足，本发明定义了基于公共数据集的服务质量优选的网络服务组合优化问题，遗传算法在求解该问题过程中易陷入局部极优，即局部收敛现象的不足，提出一种体局部收敛预防体系，并将其引入到遗传算法中得到建立体局部极优状况预防体系的改进遗传算法，为验证本发明在解决服务质量优选网络服务组合问题性能较之于之前的遗传算法的性能有所改进，用Java语言实现了本发明方法，处理基于同一个公共数据集的服务质量优选的网络服务组合问题，另外，本发明提出利用体中个体的平均适应度函数值来衡量各种算法的性能，得出本发明能有效避免遗传算法中易陷入局部极优的情况，同时该改进算法能更加高效的解决服务质量优选的网络服务组合问题，网络服务组合推荐准确率和效率有较大提高。

为达到以上技术效果，本发明所采用的技术方案如下：

预防局部极优的高质量网络服务组合方法，基于遗传算法进行改进，提出一种体局部收敛状态预防体系，通过在算法中使用预防体系来判断当前体是否有可能会进入局部收敛状态，继而判断是否该对当前体施以混沌扰动，混沌扰动过程是体中的个体利用抛物线混沌映射生成子个体的过程，将预防局部极优的高质量网络服务组合方法运用到本发明的网络服务组合问题中，避免出现遗传算法可能出现的局部收敛状态，同时能更快的收敛到一个很好的适应度函数值，本发明包括以下几个方面：

第一，定义基于公共数据集的服务质量优选的网络服务组合优化问题；

第二，提出一种体局部收敛预防体系，并将其引入到遗传算法中得到建立体局部极优状况预防体系的改进遗传算法，如果依据体局部收敛预防体系判断当前体有陷入局部极优的可能，则调用混沌扰动处理使当前体跳出现阶段所处状态；

第三，采用Java语言实现本发明方法，提出利用体中个体的平均适应度函数值来衡量算法的性能；

本发明基于遗传算法在处理网络服务组合问题时有可能出现陷入局部最优的情况，提出利用混沌的遍历性使得遗传算法跳出局部极优状况，同时，还提出一种体局部收敛状态监测机制，在监测机制没有检测到发生局部收敛趋势时，仍然按照遗传算法的一般流程进行，一旦预防体系检测到系统有可能会发生局部收敛时，开始利用一维抛物线混沌映射改变系统状态，将一维抛物线混沌映射和局部收敛检测机制引入遗传算法得到一种改进算法，然后将这种改进算法用于解决本发明所提出的网络服务组合问题，并记录所生成的网络服务组合方案的平均适应度函数值。

预防局部极优的高质量网络服务组合方法，进一步的，基于网络服务组合问题，以公共数据集中功能相同而服务质量各异的多个网络服务集合作为网络服务组合中各网络服务的备选集合，构建能使服务质量达到最大化的网络服务组合，分别从各个不同的网络服务备选集合中选取出合适的网络服务，提出一种体局部收敛状态监测机制，并将预防体系和混沌扰动引入遗传算法中，并对遗传算法进行适应性改进，然后将改进算法运用到解决本发明所定义的网络服务组合问题中。

预防局部极优的高质量网络服务组合方法，进一步的，网络服务组合框架模型：从互联网上众多已注册的功能相同而服务质量不同的网络服务中选取合适的网络服务，并将选取出来的网络服务组合成一个满足用户应用需求的网络服务组合，采用一种网络服务组合框架模型，描述基于网络服务的服务质量指标获得满足用户需求的网络服务组合方案的过程；

网络服务组合框架模型中，通过注册中心，网络服务开发者将自己开发的网络服务发布到互联网中供用户使用，用户依据自身需求向网络服务组合引擎提交网络服务请求，在接收到用户所提交的请求之后，网络服务搜索引擎依据该服务请求从注册中心选取多个网络服务，并将其构建成一个满足用户服务请求的网络服务组合推荐给用户，整个网络服务组合的构建过程分为组合规划阶段和优化选取阶段，在组合规划阶段，网络服务组合引擎依据用户服务请求的功能属性将所需的网络服务组合拆分成若干个功能简单的组件网络服务，对于每一个组件网络服务，网络服务组合引擎从注册中心出实现该功能的网络服务构成该组件网络服务的备选集合，在优化选取阶段，网络服务组合引擎基于组合规划，依据各个组件网络服务的服务质量，运用组合优化算法从各组件网络服务备选集合中选取合适的网络服务，并将选中的网络服务构建成网络服务组合推荐给用户，网络服务组合引擎在组合规划阶段将所需网络服务组合拆分成若干个组件网络服务，组合优化阶段中的网络服务组合方法直接影响网络服务组合服务质量性能高低。

预防局部极优的高质量网络服务组合方法，进一步的，混沌扰动重新构建体个体：混沌是非线性动力系统固有的性质，组合优化是在满足一定约束条件的可行解集中到，使目标函数达到最大或最小的解，组合优化问题包含较多的局部极值点，混沌在解决网络服务组合优化问题时有独特的特性，它的随机性促进使网络服务组合优化问题的解跳出局部极优，同时，它的遍历性促进所得到的对网络服务组合优化问题的解到达全局最优解附近。

预防局部极优的高质量网络服务组合方法，进一步的，本发明混沌优化解决网络服务组合问题的基本方法是：首先，依据网络服务组合优化问题解空间的特征生成初始解，然后对初始解施以小幅度的扰动，得到新解或利用混沌变量产生新的解，对得到的解集计算其中各个解的适应值，选取当前最优解，迭代该过程若干次，得到全局最优解。

预防局部极优的高质量网络服务组合方法，进一步的，基于遗传算法的网络服务组合方法应用的具体流程为：

步骤1，编码，本发明使用公共数据集，数据集中的一行表示一个网络服务，一行中的一列代表该网络服务的一个服务质量属性，以Point类表示数据集中的一行，即用Point类表示一个网络服务；

步骤2，初始化体，初始种中的个体个数由种规模的大小决定，为保证体中个体的多样性，取600作为种规模，同时，初始种中600个初始个体是随机产生的；

步骤3，计算网络服务组合的服务质量属性，一个网络服务组合由多个组件网络服务组合而成的，将构成该网络服务组合的各个组件网络服务组合的服务质量属性按服务质量聚合函数计算，得到该网络服务组合的服务质量属性；

步骤4，网络服务组合的适应度函数，适应度函数值反映算法执行过程中所生成的个体的性能，适应度函数值较高代表这个个体的性能越好，反之则差，一个网络服务组合的适应度函数值为该网络服务组合服务质量属性的目标函数值；

步骤5，单点交叉，交叉算子极为关键，交叉处理促进遗传算法跳出局部范围的搜索，进而具备全局搜索的能力；本发明取交叉概率为0.1，从作为父代的体中随机选出若干个个体，个体的数目为体个体总数乘以选定的交叉概率，将这些个体作为一个临时体，然后将这个临时体的个体随机两两进行单点交叉操作，最后将得到新的临时体合并到初始体中作为下一次迭代操作的起点；

步骤6，变异处理，在本发明遗传算法中，取变异概率为0.01，从初始体中随机选取若干个个体，个体数目为体个体总数乘以选定的变异概率，将选中的个体基因序列的中的一个基因进行变异操作，得到新的个体并加入到初始体中；

步骤7，选取，将体中个体按照其适应度函数值从大到小进行排序，选取前600名个体作为下一次迭代过程的体；

步骤8，检查遗传算法是否满足算法结束条件，即算法是否迭代了指定的次数，如果遗传算法结束条件满足，则退出运算，所得到的体便是到遗传算法所求得的最接近最优解的解集；如果遗传算法结束条件不满足，则算法跳转到步骤5继续执行。

预防局部极优的高质量网络服务组合方法，进一步的，一种系统局部收敛预防体系：基于一维抛物线混沌映射的遍历性，在遗传算法陷入局部最优时，利用抛物线混沌映射混沌序列的遍历性使算法跳出局部极优，同时，本发明还提出一种机制来判断当前体是否会陷入局部极优状况，即通过一种局部收敛预防监测系统检测是否会发生局部收敛。

预防局部极优的高质量网络服务组合方法，进一步的，一种系统局部收敛预防体系主要包括：

第一，在整个系统演化过程中，算法都维持着三个参数变量：A-系统当前所处等级，A’-系统在上一轮演化过程中所处等级，T-系统扰动参数；

第二，设置系统当前所处等级A的初始值为3，系统扰动参数T的初始值为1，然后，为不同等级的体设置不同的权重值，等级为3的体权重值为1，等级为2的体权重值为0.99，等级为1的体权重值为0.9；

第三，在本轮迭代过程开始之前，将上一轮迭代过程最终生成的所有网络服务组合按照这些服务组合的适应度函数值大小分成3个等级，假设这些网络服务组合中最大的适应度函数值为Gmax，最小的适应度函数值为Gmin，统计网络服务组合的适应度函数值在[Gmin，Gmax]范围前三分之一的网络服务组合个数，中间三分之一的个数和后三分之一的个数，依据[Gmin，Gmax]三个子范围中网络服务组合个数最多的那个子范围确定当前系统所处等级A’的值，若前三分之一范围内个数最多，则A’取1，若中间前三分之一范围内个数最多，则A’取2，若后前三分之一范围内个数最多，则A’取3，A’值越高，表示当前系统的等级也就越高；

第四，将本轮系统的等级A’与上一轮系统的等级A进行比较，当A’取3，则无论A为何值，都将系统扰动参数T设置为1，当A’取2，A取2或3时，将系统扰动参数T乘以当前系统的权重值0.99，若A取1时，系统扰动参数T为1，当A’取1，无论A取何值，将系统扰动参数T乘以当前系统的权重值0.9；

第五，系统随机产生在[0,1]范围内的一个随机数N，将该随机数N与系统扰动参数T进行比较，如果N大于T，则需要对体进行混沌扰动操作，否则，不需要对体进行混沌扰动，而只需要进行一般遗传算法处理即可。

预防局部极优的高质量网络服务组合方法，进一步的，混沌扰动跳出局部极优的具体方法为：

步骤一，生成混沌序列的初始值，在改进之后的遗传算法中，将一维抛物线混沌映射与遗传算法相结合，一维抛物线混沌映射定义如式下所示：

bi(e+1)＝ei·bi(e)·(1-bi(e))

其中，i为混沌变量的序号，e为体序号，bi为混沌变量且bi∈[0,1]，将一维抛物线混沌映射运用到组成网络服务组合的原子网络服务的下标编码中，原子网络服务的下标的取值范围都不在[0,1]范围内，因而先进行一次映射操作将原子网络服务的编码映射到[0,1]范围内，映射公式如式下所示：

其中，CSe(C)[w]表示e体中网络服务组合C的第w个基因的编码值，min(CSe(C)[w])表示e体中网络服务组合C的第w个基因的最小值，max(CSe(C))[w]表示e体中网络服务组合C的第w个基因的最大值，在改进的遗传算法中，一个服务组合的第w个基因的取值范围为[200w-200,200w-1]；

步骤二，产生下一代的混沌序列，经过步骤一处理后，体中的个体基因变量均被转换到[0,1]范围内，如此便可以采用一维抛物线混沌映射生成混沌子序列，即生成新的个体，这个过程避免遗传算法中对初始体的过分依赖，使用一维抛物线混沌映射生成子代，运用混沌的遍历性保证所生成的子代不会在局部解范围内浮动，而是在整个问题解集范围内变动，保证对给定问题解的全局性；

步骤三，还原混沌序列，在利用一维抛物线混沌映射生成子代混沌序列之后，将初始混沌序列与其所生成的子代混沌序列都放入同一个体中，为执行之后的选取算子，将这些混沌序列重新还原成个体的基因编码，将混沌序列中的[0,1]范围内的值重新反向映射到基因编码对应的取值范围中，这种反向映射如下式：

CSe(C)[w]＝[max(CSe(C)[w])-min(CSe(C)[w])]*CSe(C)[w]′+min(CSe(C)[w])

其中CSe(C)[w]′表示e体中网络服务组合C的第w个基因的混沌序列值，min(CSe(C)[w])表示e体中网络服务组合C的第w个基因的最小值，max(CSe(C))[w]表示e体中网络服务组合C的第w个基因的最大值，将混沌序列重新反向映射到初始范围内的同时，对还原之后的网络服务组合个体计算其服务质量属性值和适应度函数值，并保存在该网络服务组合对象中。

预防局部极优的高质量网络服务组合方法，进一步的，基于改进遗传算法解决网络服务服务组合问题的具体步骤如下：

第一步，编码，改进之后的遗传算法与改进前的遗传算法的编码方式相同，都是将个体在数据集合中的行号作为一个服务组合基因序列中一个基因的编码；

第二步，初始化体，以遗传算法所生成的初始体作为起始体，体大小仍然设置为600；

第三步，计算网络服务组合的服务质量值，依据网络服务组合的各个服务质量指标意义的不同，采用不同的计算方式将构成此网络服务组合的原子网络服务相应服务质量指标进行计算；

第四步，计算适应度函数，以体中所有网络服务组合的平均加权切比雪夫距离值作为当前体的适应度函数值；

第五步，设置体等级初始值为3，并为各个等级设置不同的权重值，第一等级权重值为0.9，第二等级权重值为0.99，第三等级权重值为1；

第六步，计算当前体的等级，并与体在上一轮所处的等级进行比较，进而判断算法是否需要对体进行混沌扰动，如果需要，则算法跳转到第九步执行，否则，算法执行第七步；

第七步，单点交叉处理，按照交叉概率从当前体中随机选取出若干个个体，选中的个体数目是交叉概率与该体现阶段的个体数量的乘积，实施例中取交叉概率为0.1，将选取出来的网络服务组合方案两两随机进行单点交叉处理，并得到的新网络服务加入到初始体中；

第八步，变异处理，取变异概率为0.01，从初始体中随机选取若干个个体，个体数目为体个体总数乘以选定的变异概率，将选中的个体基因序列的中的一个基因进行变异处理，得到新的个体并加入到初始体中；

第九步，混沌扰动，将体中后300个个体进行混沌扰动；

第十步，选取，将体中个体按照其适应度函数值从大到小进行排序，选取前600名个体作为下一次迭代过程的体；

第十一步，判断改进算法结束条件是否满足，如果算法结束条件满足，则退出迭代过程并得到一个对问题到目前为止最优解集合，否则，算法跳转到第六步继续迭代过程。

与现有技术相比，本发明的贡献和创新点在于：

第一，本发明提出的预防局部极优的高质量网络服务组合方法，将功能简单的网络服务集合成一个功能多样的网络服务组合，随着互联网上网络服务越来越多，这些网络服务中包含很多功能相同而服务质量不同的网络服务，基于匹配功能需求，本发明从众多功能相同的网络服务中根据用户的服务质量需求发掘合适的网络服务，通过网络服务组合方法大幅提高网络服务组合服务质量性能，在实际应用中可行性很强，是一种简洁高效、实用性强的预防局部极优的高质量网络服务组合方法；

第二，本发明基于遗传算法进行改进，提出一种体局部极优状况预防体系，在算法执行过程中，如果预防体系监测到当前体有可能陷入局部极优，便调用混沌扰动操作重新构建当前体中部分个体以跳出可能陷入的局部极优，本发明的改进算法能很好的处理遗传算法在处理服务质量优选的网络服务组合问题中所出现的缺陷和不足，能很好解决遗传算法易陷入局部收敛状态的不足，并能很好的解决基于服务质量的网络服务组合问题。

第三，本发明提出服务质量的网络服务组合问题，构建出能使服务质量达到最大化的网络服务组合，分别从各个不同的网络服务备选集合中选取出合适的网络服务，遗传算法在解决该问题时容易陷入局部收敛状态，而且不易收敛，针对遗传算法的这一不足，本发明首先引入一种体局部收敛状态预防体系，通过在算法中使用预防体系来判断当前体是否有可能会进入局部收敛状态，继而判断是否该对当前体施以混沌扰动，而混沌扰动过程则是体中的个体利用抛物线混沌映射生成子个体的过程，将预防局部极优的高质量网络服务组合方法运用到本发明的网络服务组合问题中，能有效避免出现遗传算法可能出现的局部收敛状态，同时能更快地收敛到一个很好的适应度函数值；

第四，本发明定义了一个基于公共数据集的服务质量优选的网络服务组合优化问题，遗传算法在求解该问题过程中易陷入局部极优，即局部收敛现象的不足，提出一种体局部收敛预防体系，并将其引入到遗传算法中得到建立体局部极优状况预防体系的改进遗传算法，为验证本发明在解决服务质量优选网络服务组合问题性能较之于之前的遗传算法的性能有所改进，本发明用Java语言实现了本发明方法，处理基于同一个公共数据集的服务质量优选的网络服务组合问题，另外，本发明提出利用体中个体的平均适应度函数值来衡量各种算法的性能，并将记录不同的迭代次数算法所生成的体的适应度函数值以图标的形式展现，得出本发明能有效避免遗传算法中易陷入局部极优的情况，同时该改进算法能更加高效的解决服务质量优选的网络服务组合问题，网络服务组合推荐准确率和效率有较大提高，充分体现本发明的必要性和先进性。

图1是本发明的网络服务组合框架模型图。

图2是本发明基于遗传算法的网络服务组合方法应用示意图。

图3是本发明基于改进遗传算法解决网络服务服务组合问题的流程图。

下面结合附图，对本发明提供的预防局部极优的高质量网络服务组合方法的技术方案进行进一步的描述，使本领域的技术人员能够更好的理解本发明并能予以实施。

网络服务技术得到了广泛应用，许多企业或者个人将自己开发的程序作为一个网络服务发布到互联网上供他人使用，但这些发布在互联网上的网络服务大多功能简单，无法满足实际业务需求，因此，有必要将功能简单的网络服务集合成一个功能多样的网络服务组合。但随着互联网上网络服务越来越多，这些网络服务中包含很多功能相同而服务质量不同的网络服务，基于匹配功能需求，从众多功能相同的网络服务中根据用户的服务质量需求发掘合适的网络服务是网络服务组合技术的热点，网络服务组合方法是影响网络服务组合服务质量性能高低的关键。

高质量网络服务组合是一个组合优化问题，属于NP-hard问题，现有技术典型的服务质量优选的网络服务组合方法主要采用穷举法，由于求最优解的穷举法复杂度太高，需寻求有效的近似解法以求最接近全局最优解的近似解，作为一种新的全局优化算法，遗传算法已在众多领域中取得令人鼓舞的成绩，为了验证遗传算法在解决服务质量优选的网络服务组合问题时是否同样有效，本发明以公共数据集中功能相同而服务质量各异的多个网络服务集合作为网络服务组合中各网络服务的备选集合，然后将遗传算法、微粒算法和差分进化算法从各个网络服务备选集合中选取网络服务并组成一个服务质量最大化的网络服务组合，通过分析对比，得出遗传算法在解决本发明所提出问题过程中收敛速度很慢，而且容易发生局部收敛现象，为克服这种缺陷，现有技术以一个较小的概率进行变异操作，以便跳出局部极小，但变异所起的作用有限，变异太小对解改进不大，变异太大会导致算法跳动。

为此，本发明基于遗传算法进行改进，提出一种体局部极优状况预防体系，在算法执行过程中，如果预防体系监测到当前体有可能陷入局部极优，便调用混沌扰动操作重新构建当前体中部分个体以跳出可能陷入的局部极优，为验证本发明改进算法解决服务质量优选的网络服务组合问题的有效性，将该算法运用到从公共数据集中选取网络服务构建网络服务组合的问题中，结果表明本发明的改进算法能很好的处理遗传算法在处理服务质量优选的网络服务组合问题中所出现的缺陷和不足。

本发明基于网络服务组合问题，以公共数据集中功能相同而服务质量各异的多个网络服务集合作为网络服务组合中各网络服务的备选集合，为构建能使服务质量达到最大化的网络服务组合，分别从各个不同的网络服务备选集合中选取出合适的网络服务，将遗传算法、差分进化算法和微粒算法运用到本发明所定义的网络服务组合问题的求解中，并对比这三种算法的结果，提出一种体局部收敛状态监测机制，并将预防体系和混沌扰动引入遗传算法中，并对遗传算法进行适应性改进，然后将改进算法运用到解决本发明所定义的网络服务组合问题中。

提出一种建立体局部极优状况预防体系的改进遗传算法，将本发明所提出的一种局部收敛状态预防体系和混沌扰动引入遗传算法中，将该改进算法对本发明所定义的基于服务质量网络服务组合问题进行处理，能很好解决遗传算法易陷入局部收敛状态的不足，并能很好的解决基于服务质量的网络服务组合问题。

一、网络服务组合框架模型

本发明从互联网上众多已注册的功能相同而服务质量不同的网络服务中选取合适的网络服务，并将选取出来的网络服务组合成一个满足用户应用需求的网络服务组合，采用一种网络服务组合框架模型，描述基于网络服务的服务质量指标获得满足用户需求的网络服务组合方案的过程，网络服务组合框架模型如图1所示。

网络服务组合框架模型中，通过注册中心，网络服务开发者将自己开发的网络服务发布到互联网中供用户使用，用户依据自身需求向网络服务组合引擎提交网络服务请求，在接收到用户所提交的请求之后，网络服务搜索引擎依据该服务请求从注册中心选取多个网络服务，并将其构建成一个满足用户服务请求的网络服务组合推荐给用户，整个网络服务组合的构建过程分为组合规划阶段和优化选取阶段，在组合规划阶段，网络服务组合引擎依据用户服务请求的功能属性将所需的网络服务组合拆分成若干个功能简单的组件网络服务，对于每一个组件网络服务，网络服务组合引擎从注册中心出实现该功能的网络服务构成该组件网络服务的备选集合，在优化选取阶段，网络服务组合引擎基于组合规划，依据各个组件网络服务的服务质量，运用组合优化算法从各组件网络服务备选集合中选取合适的网络服务，并将选中的网络服务构建成网络服务组合推荐给用户。

本发明网络服务组合引擎在组合规划阶段将所需网络服务组合拆分成若干个组件网络服务，组合优化阶段中的网络服务组合方法是影响网络服务组合服务质量性能高低的关键因素，本发明重点研究网络服务搜索引擎中基于服务质量的网络服务组合方法。

二、建立体局部极优状况预防体系的改进遗传算法

(一)混沌扰动重新构建体个体

混沌是非线性动力系统固有的性质，组合优化是在满足一定约束条件的可行解集中到，使目标函数达到最大或最小的解，组合优化问题可能包含较多的局部极值点，对于组合优化问题，现有技术往往采用枚举或动态规划求解精确解，但这只适合规模不大的情况，但网络服务组合问题往往都是大规模、复杂的，所以解决实际问题大多采用模拟退火、蚁算法近似求解，但这些算法通常都存在陷入局部极优的缺点。

混沌在解决网络服务组合优化问题时有独特的特性，它的随机性可以使网络服务组合优化问题的解跳出局部极优，同时，它的遍历性可以使所得到的对网络服务组合优化问题的解到达全局最优解附近。

本发明网络服务组合优化的混沌特征包括：

第一，遍历性，混沌运动按照自身规律，在混沌吸引子范围内不重复、不紊乱的遍历该范围内所有的状态；

第二，对初始值优选，当处于混沌状态中时，若给予初始值一个极其细小的变化，其运动行为也会产生很大的差异，即使初始值相当接近的初值，在经过一段时间的迭代之后，其轨道会发生指数分离；

第三，非周期性，如果无限精确的追踪一条混沌运动轨道所经过的相点，这条轨道所经历的点都不会是在该轨道上已经出现过的点，在整条混沌运动轨迹中可能存在一段轨迹跟某一周期性运动的轨迹无限接近的情况，但整条混沌运动轨迹最终还是会与这一周期性运动的轨迹发生偏离，只能通过跟踪整个混沌运动轨道来确定该轨道上已存在的某个相点出现在该轨道上的位置，不能利用周期性去预测该相点未来可能出现在该轨道上的位置。

本发明混沌优化解决网络服务组合问题的基本方法是：首先，依据网络服务组合优化问题解空间的特征生成初始解，然后对初始解施以小幅度的扰动，得到新解或利用混沌变量产生新的解，对得到的解集计算其中各个解的适应值，选取当前最优解。迭代该过程若干次，得到全局最优解。

(二)基于遗传算法的网络服务组合方法

1.遗传算法的方法流程

遗传算法代表对问题解的集合作为一个体，这个体中的各个个体便是对该问题的一个解，在遗传算法开始执行时，随机产生一个初始种，初始种产生之后，按照适者生存的类自然选取法则逐代演化产生出越来越多好的近似解。在每一代进化过程中，依据问题域中的各个个体适应度函数值选取若干个个体，然后将选取出的个体进行两两交叉以及变异操作，产生出代表对该问题的新解集的体，将这个新的体作为下一次演化过程的父代，重复上述过程直至满足算法的结束条件，算法结束后所得到的体便是对该问题直至当前阶段最优解的集合。遗传算法的流程为：

第1步，依据不同的问题选取不同的编码方式表示体中的一个个体，即该问题解集中的一个解，随机选取若干个个体作为遗传算法的起始体；

第2步，依据适者生存的自然法则，从第1步的体中选取合适的个体，依据体中各个个体的适应度函数值的大小排序选取排在前面的若干个个体，然后将选取出来的个体作为父代繁殖下一代个体；

第3步，按照交叉概率将第2步所选取出的作为父代的体中所有个体中任意二个进行交叉处理，从而产生两个新的个体；

第4步，将经过交叉处理的体按照一定的策略出若干个个体，对这些个体按照一定的变异概率进行变异处理；检查是否满足停止遗传算法的条件，如果不满足则跳转到第2步继续执行遗传算法，若果满足则跳出遗传算法，整个算法结束；

在上述演化过程中，每一次演化就会产生一个新的体，体中的个体表示到目前为止所到的对于问题的近似最优解。

2.基于遗传算法的网络服务组合方法应用

基于遗传算法的网络服务组合方法应用如图2所示，具体流程为：

步骤1，编码，本发明使用公共数据集，数据集中的一行表示一个网络服务，一行中的一列代表该网络服务的一个服务质量属性，以Point类表示数据集中的一行，即用Point类表示一个网络服务。

步骤2，初始化体，初始种中的个体个数由种规模的大小决定，为保证体中个体的多样性，取600作为种规模，同时，初始种中600个初始个体是随机产生的；

步骤3，计算网络服务组合的服务质量属性，一个网络服务组合由多个组件网络服务组合而成的，将构成该网络服务组合的各个组件网络服务组合的服务质量属性按服务质量聚合函数计算，得到该网络服务组合的服务质量属性；

步骤4，网络服务组合的适应度函数，适应度函数值反映算法执行过程中所生成的个体的性能，适应度函数值较高代表这个个体的性能越好，反之则差，一个网络服务组合的适应度函数值为该网络服务组合服务质量属性的目标函数值；

步骤5，单点交叉，交叉算子极为关键，交叉处理促进遗传算法跳出局部范围的搜索，进而具备全局搜索的能力；本发明取交叉概率为0.1，从作为父代的体中随机选出若干个个体，个体的数目为体个体总数乘以选定的交叉概率，将这些个体作为一个临时体，然后将这个临时体的个体随机两两进行单点交叉操作，最后将得到新的临时体合并到初始体中作为下一次迭代操作的起点；

步骤6，变异处理，在本发明遗传算法中，取变异概率为0.01，从初始体中随机选取若干个个体，个体数目为体个体总数乘以选定的变异概率，将选中的个体基因序列的中的一个基因进行变异操作，得到新的个体并加入到初始体中；

步骤7，选取，将体中个体按照其适应度函数值从大到小进行排序，选取前600名个体作为下一次迭代过程的体；

步骤8，检查遗传算法是否满足算法结束条件，即算法是否迭代了指定的次数，如果遗传算法结束条件满足，则退出运算，所得到的体便是到遗传算法所求得的最接近最优解的解集；如果遗传算法结束条件不满足，则算法跳转到步骤5继续执行。

(三)一种系统局部收敛预防体系

基于一维抛物线混沌映射的遍历性，本发明在遗传算法陷入局部最优时，利用抛物线混沌映射混沌序列的遍历性使算法跳出局部极优，同时，本发明还提出一种机制来判断当前体是否会陷入局部极优状况，即通过一种局部收敛预防监测系统检测是否会发生局部收敛。本发明提供的一种系统局部收敛预防体系，主要包括：

第一，在整个系统演化过程中，算法都维持着三个参数变量：A-系统当前所处等级，A’-系统在上一轮演化过程中所处等级，T-系统扰动参数；

第二，设置系统当前所处等级A的初始值为3，系统扰动参数T的初始值为1，然后，为不同等级的体设置不同的权重值，等级为3的体权重值为1，等级为2的体权重值为0.99，等级为1的体权重值为0.9；

第三，在本轮迭代过程开始之前，将上一轮迭代过程最终生成的所有网络服务组合按照这些服务组合的适应度函数值大小分成3个等级，假设这些网络服务组合中最大的适应度函数值为Gmax，最小的适应度函数值为Gmin，统计网络服务组合的适应度函数值在[Gmin，Gmax]范围前三分之一的网络服务组合个数，中间三分之一的个数和后三分之一的个数，依据[Gmin，Gmax]三个子范围中网络服务组合个数最多的那个子范围确定当前系统所处等级A’的值，若前三分之一范围内个数最多，则A’取1，若中间前三分之一范围内个数最多，则A’取2，若后前三分之一范围内个数最多，则A’取3，A’值越高，表示当前系统的等级也就越高；

第四，将本轮系统的等级A’与上一轮系统的等级A进行比较，当A’取3，则无论A为何值，都将系统扰动参数T设置为1，当A’取2，A取2或3时，将系统扰动参数T乘以当前系统的权重值0.99，若A取1时，系统扰动参数T为1，当A’取1，无论A取何值，将系统扰动参数T乘以当前系统的权重值0.9；

第五，系统随机产生在[0,1]范围内的一个随机数N，将该随机数N与系统扰动参数T进行比较，如果N大于T，则需要对体进行混沌扰动操作，否则，不需要对体进行混沌扰动，而只需要进行一般遗传算法处理即可。

(四)混沌扰动跳出局部极优

本发明混沌扰动跳出局部极优的具体方法为：

步骤一，生成混沌序列的初始值，在改进之后的遗传算法中，将一维抛物线混沌映射与遗传算法相结合，一维抛物线混沌映射定义如式下所示：

bi(e+1)＝ei·bi(e)·(1-bi(e))

其中，i为混沌变量的序号，e为体序号，bi为混沌变量且bi∈[0,1]，将一维抛物线混沌映射运用到组成网络服务组合的原子网络服务的下标编码中，原子网络服务的下标的取值范围都不在[0,1]范围内，因而先进行一次映射操作将原子网络服务的编码映射到[0,1]范围内，映射公式如式下所示：

其中，CSe(C)[w]表示e体中网络服务组合C的第w个基因的编码值，min(CSe(C)[w])表示e体中网络服务组合C的第w个基因的最小值，max(CSe(C))[w]表示e体中网络服务组合C的第w个基因的最大值，在改进的遗传算法中，一个服务组合的第w个基因的取值范围为[200w-200,200w-1]；

步骤二，产生下一代的混沌序列，经过步骤一处理后，体中的个体基因变量均被转换到[0,1]范围内，如此便可以采用一维抛物线混沌映射生成混沌子序列，即生成新的个体，这个过程避免遗传算法中对初始体的过分依赖，在现有技术遗传算法中，由于是在初始体的基础上进行的迭代操作，即使在进化过程中也会产生一些新的个体，但这些个体的产生与初始体仍然有很大的相关性，本发明改进之后的遗传算法中使用一维抛物线混沌映射生成子代，运用混沌的遍历性保证所生成的子代不会在局部解范围内浮动，而是在整个问题解集范围内变动，保证对给定问题解的全局性；

步骤三，还原混沌序列，在利用一维抛物线混沌映射生成子代混沌序列之后，将初始混沌序列与其所生成的子代混沌序列都放入同一个体中，为执行之后的选取算子，将这些混沌序列重新还原成个体的基因编码，将混沌序列中的[0,1]范围内的值重新反向映射到基因编码对应的取值范围中，这种反向映射如下式：

CSe(C)[w]＝[max(CSe(C)[w])-min(CSe(C)[w])]*CSe(C)[w]′+min(CSe(C)[w])

其中CSe(C)[w]′表示e体中网络服务组合C的第w个基因的混沌序列值，min(CSe(C)[w])表示e体中网络服务组合C的第w个基因的最小值，max(CSe(C))[w]表示e体中网络服务组合C的第w个基因的最大值，将混沌序列重新反向映射到初始范围内的同时，对还原之后的网络服务组合个体计算其服务质量属性值和适应度函数值，并保存在该网络服务组合对象中。

三、基于改进遗传算法解决网络服务服务组合问题

基于改进遗传算法解决网络服务服务组合问题的流程图如图3所示，具体步骤如下，

第一步，编码，改进之后的遗传算法与改进前的遗传算法的编码方式相同，都是将个体在数据集合中的行号作为一个服务组合基因序列中一个基因的编码；

第二步，初始化体，以遗传算法所生成的初始体作为起始体，体大小仍然设置为600；

第三步，计算网络服务组合的服务质量值，依据网络服务组合的各个服务质量指标意义的不同，采用不同的计算方式将构成此网络服务组合的原子网络服务相应服务质量指标进行计算；

第四步，计算适应度函数，以体中所有网络服务组合的平均加权切比雪夫距离值作为当前体的适应度函数值；

第五步，设置体等级初始值为3，并为各个等级设置不同的权重值，第一等级权重值为0.9，第二等级权重值为0.99，第三等级权重值为1；

第六步，计算当前体的等级，并与体在上一轮所处的等级进行比较，进而判断算法是否需要对体进行混沌扰动，如果需要，则算法跳转到第九步执行，否则，算法执行第七步；

第七步，单点交叉处理，按照交叉概率从当前体中随机选取出若干个个体，选中的个体数目是交叉概率与该体现阶段的个体数量的乘积，实施例中取交叉概率为0.1，将选取出来的网络服务组合方案两两随机进行单点交叉处理，并得到的新网络服务加入到初始体中；

第八步，变异处理，取变异概率为0.01，从初始体中随机选取若干个个体，个体数目为体个体总数乘以选定的变异概率，将选中的个体基因序列的中的一个基因进行变异处理，得到新的个体并加入到初始体中；

第九步，混沌扰动，将体中后300个个体进行混沌扰动；

第十步，选取，将体中个体按照其适应度函数值从大到小进行排序，选取前600名个体作为下一次迭代过程的体；

第十一步，判断改进算法结束条件是否满足，如果算法结束条件满足，则退出迭代过程并得到一个对问题到目前为止最优解集合，否则，算法跳转到第六步继续迭代过程。

本发明提出服务质量的网络服务组合问题，为了构建出能使服务质量达到最大化的网络服务组合，需要分别从各个不同的网络服务备选集合中选取出合适的网络服务。遗传算法在解决该问题时容易陷入局部收敛状态，而且不易收敛，针对遗传算法的这一不足，本发明基于遗传算法进行改进，首先引入一种体局部收敛状态预防体系，通过在算法中使用预防体系来判断当前体是否有可能会进入局部收敛状态，继而判断是否该对当前体施以混沌扰动，而混沌扰动过程则是体中的个体利用抛物线混沌映射生成子个体的过程。最后，将预防局部极优的高质量网络服务组合方法运用到本发明的网络服务组合问题中，能有效避免出现遗传算法可能出现的局部收敛状态，同时能更快地收敛到一个很好的适应度函数值。本发明的主要工作包括以下几个方面：

第一，本发明定义了一个基于公共数据集的服务质量优选的网络服务组合优化问题，遗传算法在求解该问题过程中易陷入局部极优的不足；

第二，针对遗传算法中易陷入局部极优，即局部收敛现象的不足，本发明提出一种体局部收敛预防体系，并将其引入到遗传算法中得到建立体局部极优状况预防体系的改进遗传算法，如果依据体局部收敛预防体系判断当前体有陷入局部极优的可能，则调用混沌扰动处理使当前体跳出现阶段所处状态；

第三，为验证本发明在解决服务质量优选网络服务组合问题性能较之于之前的遗传算法的性能是否有所改进，本发明用Java语言实现了本发明方法，处理基于同一个公共数据集的服务质量优选的网络服务组合问题，另外，本发明提出利用体中个体的平均适应度函数值来衡量各种算法的性能，并将记录不同的迭代次数算法所生成的体的适应度函数值以图标的形式展现，得出本发明能有效避免遗传算法中易陷入局部极优的情况，同时该改进算法能更加高效的解决服务质量优选的网络服务组合问题。