融合SOM和多目标寻优的Web 服务组合优化方法

1 引 言

得益于互联网技术的日益发展与软件工程学科的不断进步，Web的服务组合技术在网络技术研究领域发挥着愈加重要的作用.但是随着用户需求的日益增多，单一的Web服务往往难以满足用户日益复杂的需求，越来越多的企业倾向于采用多样的Web服务组合来完成对业务的构建[1].随着服务提供者发布的服务个数激增，出现许多功能相类似但是服务质量(Quality of Service，QoS)并不相同的服务，在满足用户对于服务质量要求的前提下，如何选择最优的服务组合，是Web服务组合优化研究领域中的一个重要的研究问题.该问题是一个典型的多目标下的NP-hard问题[2].

目前大多数的解决方法是从QoS角度出发使用元启发式算法求解优化模型.如文献[3]从服务水平协议(SLA)的角度提出一种全新的多元优化算法IMVO，其设计的算法在数据集较小的情况下具有良好的优化能力，但随着数据集增大，其寻优能力明显下降;文献[4]提出一种基于柯西变异的烟花算法，但是在算法种群更新过程中完全放弃适应度较差的变异个体，增大了陷入局部最优的可能;文献[5]则运用了一些传统的多目标算法如NSGA-II、SPEA2等来解决基于QoS的云服务组合优化问题，但算法的有效性和速率仍有待改进.

此外，由于Web服务的动态性，不少学者开始关注针对服务集的聚类研究.对服务进行聚类的目的在于将同一服务集合中的候选服务按每种规律聚集为不同的类别.如文献[6]使用K-means算法根据候选服务的QoS属性进行聚类操作，但是K-means算法需要给出预测的类个数K，该值通常较难把握.文献[7]使用AGNES层次聚类和K-means算法对初始服务集合进行两次筛选从而提高组合的可靠性，但两次聚类操作极大地增加了算法计算时间.文献[8]提出一种基于逻辑关系的Web服务聚类方法，通过分析服务的OWL-S(Web ontology Language for Services)语义描述完成聚类，但此类方法对初始的数据要求较高，需要较为完整的OWL-S描述才能较好地完成聚类操作.服务聚类主要有两个目的，首先对于相类似的服务，他们可在大多数情况下进行相互替换，故其并不需要全部都参与到服务组合的流程中，这样可以缩小服务选择中候选服务的规模;其次，对于部分不符合用户要求的服务，在聚类过程中可能被归于同类服务，故在组合过程中可以避免调用该类服务从而提高服务表现.

基于以上思路，本文提出一种基于聚类分析和QoS感知相结合的Web服务组合优化方法模型(SO-AFSA).首先基于SOM神经网络对单个服务集合进行聚类操作，有效减少单个子服务集合的候选服务数量并降低服务间的相似程度;其次使用第一阶段的聚类结果构造初始种群，提出一种改进的多目标鱼群算法，以解决多目标优化算法中的效率和有效性问题，实验结果表明，相较于传统方法，本文提出的算法模型在多个指标上均具有更好的表现.

2 结构与问题描述

2.1 Web服务组合问题描述

定义1(服务质量).服务质量指Web服务的非功能属性，比如可用性，安全性，可行度等等.本文采用一个四元组表示服务质量：QoS={RT，AV，TH，L}，其中RT表示服务响应时间(Response Time)，AV表示服务可用性(Availability)，TH表示表示吞吐量(Throughput)，L表示时延(Latency).

由于不同QoS属性的单位并不一致，所以在对QoS属性进行度量计算的时候，一般需要对数据进行预处理，使得不同的QoS属性有相同的度量单位[9].本文将不同单位的QoS属性进行归一化，将不同单位的属性都转换为[0，1]的数值.QoS属性分为“正向QoS”和“逆向QoS”，正向QoS属性其指标越大越能满足需求，比如可用性和吞吐量;而逆向 QoS属性其指标值越小越能满足用户需求，比如服务时延和服务响应时间.针对两种不同的QoS类型，本文将按照公式(1)进行归一化：

(1)

定义2(Web服务组合).Web 服务组合指根据用户提交的信息将任务划分为细粒度的抽象任务，同时将每个抽象任务对应的候选服务快速组合起来形成完整的服务以满足不同用户的需求.设一个Web服务组合Wsc={T1，T2，T3,…,Ti}由i个抽象任务组成，其中Ti表示任务拆分后第i个子任务.Csi={Csi1，Csi2，Csi3,…,Csin} 表示每一个Ti对应的n个候选服务集合，对于每个候选服务Csin有QoS={qos1，qos2，qos3,…,qosm}，表示该候选服务对应共m项QoS属性值，最后W={w1，w2，w3,…,wm} 表示各QoS指标所占权重.

在基于工作流方法的Web服务组合中，对于子任务的执行关系工作流管理联盟(WFMC)定义了4种基本模型，即顺序(Sequence)，并行(Parallel)、选择(Selective)和循环(Circular)[10].在不同的结构下，组合服务的QoS的计算方式是不同的，4种基本模型的QoS的计算方式如表1所示，其中n为子任务个数，pi表示第i个子服务集被选中的概率且满足以上4种模型结构均可转化为顺序结构，为方便描述，本文采用顺序结构展开研究.

表1 组合服务QoS计算方法

Table 1 QoS calculation method of composite services

2.2 QoS多目标优化模型描述

Web服务QoS优化是一个典型的多目标优化问题，且这些目标往往难以同时达到最优.很多学者采取优化模型的方法，将不同的QoS属性根据其相应的权值向量整合，将多目标问题转换为单目标问题进行优化.但这种方法并没有考虑到QoS之间的冲突性，并且计算的结果为QoS聚合值，具有片面性且极易丢失大量的决策信息.文本采用上文提到的4元模型建立多目标优化模型.取在Web服务中相互对立且较为重要的两个属性响应时间和时延作为目标函数f1、f2，以服务组合可用性和吞吐量作为约束来构建多目标模型.

(2)

3 SO-AFSA服务组合模型

3.1 QoS服务聚类

3.1.1 自组织映射网络

综合考虑上述提到的多种 Web服务聚类方法的优缺点，在此我们引入SOM(Self-organizing Maps)神经网络来完成对候选服务的聚类.SOM是一种无监督的高维聚类方法，用于描述从高维输入空间到低维竞争空间的映射，从而实现自动聚类[11].二维的 SOM拓扑结构如图1所示，其由竞争层和输入层组成.对于一个任意维度的输入向量Xi(t)，根据初始的权值计算其与各个神经元之间的欧式距离，距离最小的即为获胜神经元，同时在每次训练中按照公式(3)调整获胜神经元和相邻神经元的权值.

图1 SOM拓扑结构

Fig.1 SOM two-dimensional topology

wi(t+1)=wi(t)+η(t)×[Xi(t)-wi(t)]

(3)

其中η(t)是一个值域在0到1 之间随时间而减小的增益函数，wi(t)表示第i个输出层节点在第t代的权值向量.修改权值将使获胜的神经元及其相邻权值更加靠近输入样本，从而使同类的神经元具有相近的权值系数.在学习过程结束之后，同类神经元相对集中，异类神经元逐步发散，从而达到聚类的效果.文献[12]首次将SOM运用到基于QoS的聚类操作中，但是其对QoS数值的格式有一定的要求，并且没有给出在聚类之后的具体操作，本文将给出基于一般QoS属性值的SOM聚类过程.

在聚类操作中我们将使用QoS属性值对一个候选服务Csi进行描述.对于同一个子任务的候选服务集合Cs，将每一个Csi作为输入向量训练SOM网络从而完成服务聚类.对于服务聚类结果的操作详见3.3.5

算法1.SOM聚类的实现步骤

输入：服务集合矩阵Cs

输出：QoS聚类结果

Step 1.初始化每个节点的权重，其被设置为一个较小的随机值，同时设定获胜神经元的初始邻域，学习率，最大迭代次数Tmax

Step 2.将Cs的一个具体服务Csi输入SOM网络，并根据欧式距离找到获胜节点

Step 3.更新获胜神经元及其邻域神经元的连接权重

Step 4.重复Step 3，直到达到最大迭代次数Tmax

3.2 基本人工鱼群算法

人工鱼群算法(AFSA)是李晓磊在2002年提出的一种元启发式算法 [13].人工鱼群算法具有鲁棒性强，实现简单，寻优速度较快以及全局寻优能力强等优点，极其适合解决Web组合优化问题.

设在一个D维空间中有N条人工鱼，每条人工鱼状态表示为Xi=(x1，x2，…，xn)，其中i=1，2，…，N.Yi=f(Xi)表示在Xi位置的目标函数值.Visual表示人工鱼感知范围，Step表示人工鱼最大移动步长，δ表示拥挤度因子;try_number表示最大试探次数;delta表示鱼群拥挤度因子.以下将具体介绍人工鱼群算法的4种行为.

3.2.1 觅食行为

觅食行为是人工鱼最基本的一种行为，具体可表述为处于Xi位置的人工鱼在视野范围内随机确定一个新的位置Xj，Xj可用以下公式(4)确定.Yi、Yj表示在Xi、Xj位置的食物浓度.如果满足Yj> Yi，则人工鱼按照公式(5)向Xj移动一步.若在尝试try_number次后没有找到满足条件的Yj，则执行随机行为.

Xj=Xi+Visual×rand()

(4)

(5)

其中rand()表示一个在0-1之间的随机数，‖Xj-Xi‖表示两条人工鱼之间的欧式距离.

3.2.2 聚群行为

聚群行为指鱼群聚集成群以集体进食及躲避敌害.鱼群的中心位置由公式(6)进行定义，其中Xc表示鱼群的中心位置.定义人工鱼在Xi状态时的视野范围内所有的人工鱼数量为nf_swarm，Yc为人工鱼在Xc位置的食物浓度，若满足Yc/nf_swarm>delta×Y并且Yc>Yi，则Xi按照公式(7)向Xc的方向移动一步.若无满足条件的Xc则执行觅食行为.

(6)

(7)

3.2.3 追尾行为

追尾行为是指当鱼群中的人工鱼发现食物的时候，它们附近的鱼会尾随其方向游动.设人工鱼在Xi状态时视野范围内的人工鱼条数为nf_follow，拥有最大食物浓度的人工鱼为Xmax，其食物浓度为Ymax，如果同时满足Ymax/nf_follow>delta×Yi则向按照公式(8)向Xmax方向前进一步.反之则执行觅食行为.

(8)

3.2.4 随机行为

随机行为也是鱼群的一种基本行为，对于处在Xi状态的人工鱼按照公式(9)在视野范围内随机选择一个状态，然后向该方向移动.

Xi|next=Xi+Visual×rand()

(9)

鱼群在执行不同行为后，算法将会执行一个评估函数evaluate()对人工鱼当前的位置作出评价，然后选择一种行为执行.评估函数依照具体的问题设定，常用的评估函数函数即选择各个行为中使人工鱼向最优方向上前进最大的行为.

3.3 改进的多目标人工鱼群算法

基本的人工鱼群算法只适用于单目标的问题，而在多目标优化的问题环境下，则需要对人工鱼的4种行为以及算法流程进行修改.本文将从多个方面将基本人工鱼群算法改进为多目标的人工鱼群算法.

3.3.1 自适应视野及步长

在基本的人工鱼群算法中，视野决定了搜索范围，步长决定了搜索的速度和精度.视野越小，人工鱼更有可能执行觅食行为和随机行为，有利于探寻局部最优解和数据精度的提升，而视野越大，聚群和追尾行为将会更加频繁，更有益与全局最优解的发现，故对于算法整体过程，需要视野的变化趋势由大到小，变化速率由快到慢.令视野最大最小值分别为Vismax和Vismin.本文引入logistic模型对人工鱼视野进行动态调整，具体变化设定为公式(10)，其中Iteration为当前迭代次数，Max_Iteration为最大迭代次数，α为动态因子，用以调节视野下降速度.

(10)

g(x)=e-πx2

(11)

(12)

而为平衡迭代速度和解的精度，本文基于文献[14]引入一个变形的正态分布函数来控制步长的变化，具体步长如公式(11)、公式(12)所示.在算法初期步长的减少较为缓慢，有利于迭代速度，算法后期步长迅速减少，有利于算法的收敛.图2绘制了公式(10)和公式(12)的曲线，我们可以看到两条曲线的整体下降趋势均符合预期且始终满足视野大于步长.

图2 视野与步长曲线

Fig.2 Curve of view and step

3.3.2 人工鱼群4种行为更新

拓展的多目标人工鱼群算法无疑需要基于Pareto支配来判断所得解的优劣，以下将给出相关定义.

定义3(Pareto支配).对于任意两个在解空间中的D维向量u和v，当且仅当u和v的任意分量上满足ui≥vi，且至少存在一项满足ui>vi，则称u支配v，记做uv.

定义4(Pareto非支配解).对于u∈S，当且仅当不存在w∈S，使得wu，则称u为Pareto非支配解.

定义5(Pareto非支配解集).所有Pareto非支配解组成的集合称为Pareto非支配解集.

过往对多目标人工鱼群算法的研究存在将支配关系直接套用在基本的人工鱼群算法中的情况，如在文献[15]中，只是简单将适应度值的大小比较替换为支配关系的判断，然而对多目标人工鱼群算法中鱼群中心位置拥挤判断、多条人工鱼互不支配情况下的行为选择等问题均没有给出明确的解答.基于上文给出的Pareto关系的定义，本文将给出多目标人工鱼群算法的4种鱼群行为及行为选择策略：

1)觅食行为：对于人工鱼Xi，按照公式(4)选择其视野范围内的另一条人工鱼Xj，如果F(Xj)F(Xi)，则Xi向Xj移动，如果在尝试try_number次后都没有满足条件的Xj，则执行随机行为.

2)聚群行为：对于人工鱼Xi，计算视野范围内所有人工鱼数目nf_swarm和并按公式(6)求得鱼群的中心位置Xc.如果F(Xc)F(Xi)，并且满足nf_swarm/N<delta，则Xi按照公式(7)向Xc位置移动一步，反之则执行觅食行为.

3)追尾行为：对于人工鱼Xi，先求得视野范围内的最优人工鱼Xbest，即对于Xi视野范围内的任意X*，有XbestX*，同时求得Xi视野范围内人工鱼数目nf_follow，如果满足F(Xbest)F(Xi)并且nf_follow/N<delta，则人工鱼Xi按照公式(8)向Xbest方向前进一步，反之则执行觅食行为.

4)随机行为：多目标人工鱼群算法总的随机行为和基本的人工鱼群算法保持不变.

对于多目标人工鱼群算法的行为选择，大体思路依旧是选择使人工鱼向最优方向上前进最大的行为.本文默认执行聚群和追尾行为，觅食和随机行为在前两种行为中有概率执行.对两种行为得到的解进行支配关系判断，其中的非支配解将加入非支配解集.

若出现互不支配的情况，因为人工鱼每次只能向一个方向前进，所以只能选择其中的一个解加入非支配解集并执行对应行为，在此使用聚合函数Aggregation来进行选择.Xi=(x1，x2，…，xn)共有n个分量，则给定权重向量w=(w1，w2，…，wn)，按照公式(13)将Xi的各分量相加，针对最小化问题将聚合函数值较小的解加入非支配解集.

(13)

3.3.3 外部档案维护策略

外部档案的维护是多目标优化算法中非常重要的一个问题.在多目标鱼群算法中，我们将维护一个外部档案集P以保存得到的非支配解.每次迭代后，对于每条人工鱼将依照其食物浓度判断其支配关系，将本次迭代后获得的的非支配解保存在集合Q中，随后将集合P和集合Q合并删去其中的支配解.参考已有的研究基础[16]，本文引入拥挤距离的概念，在每次所有人工鱼完成一次移动行为后每条人工鱼按照当前的食物浓度来计算拥挤距离.当外部档案中非支配解的个数超过档案集的最大数量Pmax的时候按照拥挤距离删除部分集合P中的部分非支配解，计算拥挤度过程如下：

算法2.计算人工鱼拥挤距离

输入：人工鱼群AFpop，鱼群大小N，目标个数object_num

输出：每条人工鱼的拥挤度

Step 1.初始化AFpop中每一条人工鱼的拥挤距离CrowdDis=0，当前计算的目标数为j

Step 2.对第j个目标的函数值进行降序排列，设第i条人工鱼的在排序后的顺序为i′，同时将排序后的第1条和最后一条人工鱼的拥挤距离值为无穷大，令i=2(从第2条人工鱼开始计算)

Step 3.对于第i条人工鱼按照以下公式(14)进行计算，同时令i=i+1

(14)

Step 4.判断i是否小于N，若是则返回Step 3，否则转到Step 5

Step 5.令j=j+1，判断j是否小于object_num，若是则结束结束计算，反之则转到Step 2

3.3.4 变异算子的添加

如前文所述，人工鱼群算法具有较快的收敛速度和良好的并行性，但在多目标环境下，过快的收敛有可能导致算法收敛于局部最优或目标空间边界值而获得错误的Pareto前沿，本文将参考多目标粒子群算法(MOPSO)[17]的变异过程并加以改进，在每次迭代中有概率选择部分人工鱼执行变异操作，变异概率Mu随迭代次数逐渐减小，具体如公式(15)所示，其中γ为变异率因子，用以控制变异操作的比例.

(15)

同时，在MOPSO中基于位置的变异方法并不能很好从全局角度寻优，由于差分算子非常有利于种群之间的信息交换并改善收敛精度，本文提出一种基于差分变异算子的变异策略.基本的差分变异算子包含5种变异策略，本文将基于“current-to-best/1”策略实施变异操作.“current-to-best/1”在通常情况下被用于在全局范围内探索更大的可行解区域，具体如公式(16)所示.

(16)

其中表示在第t代种群中的一个个体，表示全局的最优解，表示从种群中任意选的两个解，F为一个在(0，1)之间的控制参数.在多目标鱼群算法中，我们希望差分变异操作能够实现人工鱼群和外部档案集之间的信息交换，从而跳出局部最优，本文变异算子的设定参照公式(17)：

(17)

图3显示了该变异算子的变异机制，其中表示一个从外部档案集中的一个随机解，表示从外部档案集P和当前主种群的混合种群U中随机选择的一个解.其中携带支配解集的信息，促进当前解向量向支配解方向收敛，同时携带主种群和支配解集的信息，一定概率上将会参考全局位置进行移动，从而避免变异操作过多参考当前世代最优解而陷入局部最优.

图3 差分变异算子变异策略

Fig.3 Differential mutation operator mutation strategy

3.3.5 人工鱼编码及种群初始化

在进行组合服务的选择时我们将每条人工鱼看做是一个组合服务的解决方案，本文采用实数编码对人工鱼进行编码，假设一个服务组合Wsc={T1，T2，T3,…,Ti}包含i个子服务，每个子服务Ti对应的候选服务共有n个候选服务，则具体的编码方式如图4所示.

图4 组合服务的编码

Fig.4 Encoding of composite services

对于算法初始种群的构建，一般的做法是采用随机生成的方式产生初始种群.但在SO-AFSA中，我们将基于SOM的聚类结果来构建初始种群.因为对于同一个候选服务的相同簇中的服务，其往往具有相类似的QoS属性，从组合优化的角度完全可以选择簇中的一个服务来代表整个簇参与初始化流程.因此同一簇的服务，我们将选择其聚类中心来代表其整个类.设单一原子服务Ti经过SOM聚类后共有n个簇，则包含该服务的服务组合的第i位将从n个聚类中心中随机选择一个代表Ti.

3.3.6 模型整体流程

综上，结合SOM聚类和多目标人工鱼群算法的Web 服务组合优化模型(SO-AFSA)具体实现步骤如下：

Step 1.设置算法参数：初始化算法参数，包括种群规模N，最大迭代次数Max_Iteration，最大最小视野Vismax、Vismin和步长Step等，同时初始化Qos属性.

Step 2.利用SOM筛选服务，并利用SOM的聚类结果构建初始种群.

Step 3.每一条人工鱼Xi分别执行聚群和追尾行为，当不满足聚群和追尾条件时则执行觅食行为，若觅食行为条件亦不满足则执行随机行为，取两次行为最后的位置记为Xnext1和Xnext2.

Step 4.分别计算人工鱼Xnext1和Xnext2的食物浓度Ynext1和Ynext2并判断支配关系，人工鱼向非支配解位置移动.若Ynext1和Ynext2互不支配，则按公式(13)计算聚合函数值，人工鱼向聚合函数值较小的位置移动.

Step 5.根据当前迭代次数计算变异概率并选择部分人工鱼按照差分变异策略进行变异操作.

Step 6.在每一条人工鱼进行移动后，构建本次迭代获得的Pareto解集并计算拥挤度.将新的Pareto解集加入外部档案P并对P进行维护.

Step 7.重复Step 3-Step 6直至达到最大迭代次数Max_Iteration.

4 实验分析

为验证本文所提出的SO-AFSA模型的有效性，本节将进行一系列实验.首先对基于SOM过滤服务及种群初始化进行有效性验证.其次，针对Web服务QoS度量模型，采用SO-AFSA模型和其他几种经典的多目标优化算法进行对比，实验程序使用Matlab2019b编写，运行环境为Mac Os，Intel®Core I5，1.8GHz CPU，8G内存.

4.1 实验数据

本文实验将采用真实数据集QWS，该数据集包含2507条真实Web服务的QoS属性记录，关于QWS的详细介绍详见文献[18].在实验中，为模拟真实环境下的服务组合问题，该实验为工作流设置了不同的任务数，并将QWS数据集中的服务数据分配到这些原子任务的候选服务集，每个候选服务包含4个QoS属性对应前文提出的QoS四元组.同时，由于在人工鱼的行为选择时需要使用权重，对于响应时间和时延的权重分别设置为0.6和0.4.

4.2 SOM聚类评价验证

为验证采用SOM聚类操作对于算法模型具有可行性与有效性，以下将基于不同的候选服务个数来验证SOM聚类对于服务的过滤和选择两方面的效果，同时与K-means聚类算法进行对比.对于服务过滤效果，文献[19]给出了单独两个服务之间QoS相似度的计算方式，本文将不同服务间的相似度相加后与服务个数的比值作为整个服务集合的相似度，来衡量经过聚类操作后候选服务集的相似差异.QoS相似度越小，则表明候选服务具有更大的差异性，从而更有可能找到较好的服务组合;对于服务选择效果，我们设立一个新的评价指标组合错误率(Fault Rate)，该评价指标计算在一次服务组合中使用了不满足用户需求的服务的比例.本文将在原数据基础上添加一定量不符合可用性和吞吐量约束的服务(具体为候选服务数的30%)，并计算该候选服务集合在经过聚类操作后构建的服务组合的错误率.

该部分实验的参数如下：取候选服务个数为50，100，150，200，SOM的输出层大小为默认的8×8，初始邻近距离为3.同时为保证两种算法在聚类后有相近的候选服务个数，选取候选服务个数乘0.4作为K-means的K值.所有实验结果取30次实验的平均值，实验结果如图5、图6所示.

图5 不同服务个数下的QoS相似度

Fig.5 QoS similarity under different number of services

图6 不同服务个数下的组合错误率

Fig.6 Fault rate under different number of services

从图5可以观察到，在经过聚类过滤后，原服务集合相似度出现明显的下降，并随服务个数的增多而愈发明显.在不同候选服务个数下，由于SOM并没有聚类中心个数的限制，服务个数呈动态变化，故SOM聚类的候选服务其相似度始终小于使用K-means聚类的候选服务.由图6可见，在不同候选服务个数下，服务组合的错误率始终在0.2-0.3之间，但是经过SOM聚类的候选服务的错误率始终小于其他两种情况，并且随着候选服务个数上升逐渐下降.综上，可见SOM聚类能有效降低候选服务的数量和调用错误服务的可能，并且候选服务个数越大，过滤效果愈发明显.

4.3 服务组合QoS优化对比

为验证SO-AFSA在求解基于QoS的服务组合问题的有效性，本文将分两部分进行试验.首先，本文将基于随机的初始种群测试多目标人工鱼群算法在Web服务组合优化问题上的表现，其次，将基于SO-AFSA使用SOM聚类结果作为初始种群依据，从而评价模型整体的优劣.两部分实验都将与经典的多目标算法MOPSO[17]、NSGA-II[20]、SPEA-II[21]和PESA-II[22]进行对比，各算法的具体参数详见表2.

表2 参数设置

Table 2 Parameter setting

4.3.1 多目标鱼群算法评价

本文将从收敛性和分布性来评价算法表现，在此引入引入MOP中常用的两个评价指标GD[23]和Spacing[23]，前者计算算法得到的近似解与Pareto前沿的平均距离，从而体现算法的收敛性，后者计算解集中每个解到其他解的最小距离的标准差，从而衡量解集是否分布均匀，两评价指标均为越小则结果越好.因为GD的计算需要使用到Pareto前沿，但是对于实际问题没有确定的Pareto前沿可供参考，本实验参考文献[24]的实验方法，将5种算法各迭代1000代，取30次结果的并集，去掉其中被支配和重复的解，将获得的最后的解集作为Pareto前沿(见图7(a)).5种算法将基于相同的候选服务，同样依照上述方法在不同迭代次数下构建解集进行计算评价指标，实验结果如图7(b)-图7(c)所示.

可以看到随着迭代次数的增加，5种算法的GD值均呈现下降趋势并逐渐趋向于0，首先该结果充分说明图7(a)中求得的近似Pareto前沿能够充分代表最优解集.在GD值方面，随着迭代次数递增，虽然PESA-II和MOPSO在部分迭代次数下(前者取200-300，后者取600)能够逼近多目标人工鱼群算法取得的GD值，但是从整体情况看来，多目标人工鱼群算法的GD值在任何代数下始终小于其他4种算法.在Spacing值方面，多目标人工鱼群算法的表现较为优秀，在不同迭代次数下均优于其余4种算法.综上，相比其他4种算法，多目标人工鱼群算法具有更好的收敛性和均匀性.在图7(d)可视化显示了5种算法在运行200代时的结果.可观察到，SPEA-II和PESA-II两种算法所取得的最优解明显被多目标人工鱼群算法取得的最优解所支配，同时虽然NSGA-II和MOPSO的部分解优于多目标人工鱼群算法，但后者在解数量和分布情况上均优于前者.综上，对于Web组合优化模型，多目标人工鱼群算法相较于上述其他算法能取得更优的Pareto解集.

图7 多目标鱼群算法与其余4种算法的对比

Fig.7 Comparison of multi-objective fish swarm algorithm and other four algorithms

4.3.2 SO-AFSA评价

为验证SO-AFSA在求解基于QoS服务组合问题的有效性，以下同样使用上述4种算法作为对比.实验参考文献[25]引入响应时间和ANE(Average Normalized Error)两个评价指标，其中响应时间指算法求得Pareto最优解的时间，用于衡量算法的运行效率，ANE指标衡量求得的服务组合对于各目标的满足情况，具体表现为优化效果，其值越大表示结果越能满足各目标函数.所有方法均取200的迭代次数，每个子服务的候选服务数均为50，实验在不同服务个数下取20次实验结果均值作为最后结果，如表3、表4所示.

表3 各算法的ANE(%)

Table 3 ANE of each algorithm

从表3可以观察到，SO-AFSA在服务个数较小(Number of Service=5)时的优化效果略逊于NSGA-II，这是由于受到较小服务个数的限制，SOM聚类对于服务的过滤效果并不显著.但当服务个数逐渐增加时，SO-AFSA的ANE值逐渐增大，并且始终高于其他4种算法，这是由于聚类操作过滤相类似的候选服务使得SO-AFSA拥有更优的初始种群及服务搜索空间，从而通过差分变异等一系列机制寻得最优解.

同时，通过表4并不难发现，随着服务个数的增大，各算法的响应时间均随之增大，NSGA-II的响应时间最长，MOPSO则最短，PESA-II在部分服务个数下的响应时间小于SO-AFSA，即SO-AFSA的优势并不明显，这是因为SOM的聚类操作和算法中拥挤距离的计算耗费了大量时间，但整体的响应时间与MOPSO、PESA-II的差距并不大.同时当服务个数上升到20以后，PESA-II的响应时间已没有明显的优势.并且在实验中我们发现，随着服务个数的增加，MOPSO中粒子维数的上升使得基于网格密度的维护策略占用更多的时间，使得SO-AFSA和MOPSO在响应时间上的 差距进一步缩小.当故综合来看，SO-AFSA 能有效处理 Web 服务组合优化问题，并且相较于其余4种算法，更加适应服务个数较多的情况.

表4 各算法响应时间(s)

Table 4 Response time of each algorithm

5 结 论

本文研究了SOM神经网络在Web服务组合优化问题上的应用，并提出了多目标人工鱼群算法，两者构成SO-AFSA模型，解决了传统的多目标算法在服务组合优化领域内的一些问题.实验证明，本文提出的模型能有效提升组合服务的综合表现.

未来需要进行的工作主要包含两部分：首先SO-AFSA并没有考虑 Web服务具有一定的动态性和不确定性，但实际上服务的QoS值是在不断发生变化的，因此我们需要进一步考虑QoS数据的可靠性.其次，在SO-AFSA中，SOM的聚类操作耗费了组合优化过程的大部分时间，对聚类过程加以改进将会极大改进SO-AFSA在计算时间上的表现.