利用猫群优化算法增强Web服务发现的研究

王继魁

(吉林师范大学 计算机学院，吉林 四平 136000)

Web服务是一种基于客户端和服务器端的使用标准的网络通信协议HTTP或HTTPS进行通信的应用程序.Web服务架构的组件有服务提供者、服务消费者和服务代理规范标准(如通用描述、发现与集成UDDI[1](Universal Description Discovery and Integration).在UDDI机制的规范下，特定行为的Web服务可用Web服务描述语言(WSDL)描述其功能和用途.传统的针对需求查找相关Web服务的方法都是基于服务名称或自然语言描述的，可遗憾的是绝大多数的Web服务不能够被自然语言清晰准确的表述.为了克服上述限制，在WSDL语言中应用文本挖掘技术可以识别出描述所需Web服务功能的组件.使用这些功能获取相关信息后，可以对WSDL进行聚类，以便在服务发现和选择过程中缩小搜索空间，提高搜索效率.

对于文档的聚类，聚类算法的选择是至关重要的.传统的算法是K-means、Hierarchical Agglomerative、Suffix Tree等.目前流行的基于群体智能的聚类算法：蚁群优化算法(ACO)，粒子群优化算法(PSO)、遗传算法(GA)等.本文采用一种新颖的猫群优化算法[2]来进行Web服务的聚类.猫群优化算法是模拟自然界中猫的社会习性和觅食形为的一种算法.本文采用自适应的猫群优化算法来对Web服务集合进行聚类分组，然后将此算法的聚类精度与传统的K-means[3]聚类算法的精度做比较，给出实验结果.

1 自然语言处理

解决本文问题的关键在于如何提取Web服务的功能性信息，并使用这些信息对指定的需求的Web服务进行分类.首先，使用自然语言处理NLP技术对WSDL文档进行预处理，比如去除stop-word等，用来获取自然语言中的主干作为分析的属性.然后，使用NLP中的TF-IDF[4](Term Frequency-Inverse Document Frequency)技术，使用欧几里德距离计算出WSDL文档之间相近性和差异度.

本文使用的WSDL文档数据集来自于OWLS-TC4[5]，选取其中的虹膜、眼镜、大豆、红酒数据作为测试对象.对文档内容聚类计算出相似度的值后，为分别应用K-means算法和猫群优化算法，对得出的结果进行比较.

2 K-means聚类

K-means算法[6,7]中，要形成的簇的数量由k值给出.随机选择k个文档作为聚类中心，通过计算中心和文档之间的欧几里德距离[8]，将所有文档分配到最近的中心.找到每个簇中所有文档的均值，将值最小的文档作为新簇的中心.最终，根据公式(1)计算的欧几里德距离重新分配文档，并且继续该过程直到不再能重新分配，即已经达到稳定的聚类.

(1)

3 猫群聚类

虽然猫的大多数时间在休息，但它对所在环境和移动的物体有着高度的警觉性和好奇心.这样的形行特征能帮助猫发现猎物并捕捉猎物.相对于休息时间，猫花费较少的时间去追逐猎物以节省体能.受这种狩猎模式的启发，猫群优化算法(CSO)可分为两种模式：猫在休息时的“搜索模式”和在追逐猎物时的“追踪模式”.在CSO中，创建一群猫并另它们随机分布于M维度的解空间中，每只猫代表一个解决方案.猫群根据状态自然的被分为两组，第一组的猫正在休息并密切关注周围环境，即搜索模式；第二组的猫处于移动状态并追逐猎物，即追踪模式.这两种模式的融合有助于CSO算法在M维度的解空间中得出最佳的解决方案.由于猫在追踪模式中花费的时间较少，在追踪模式组中的猫的数量应该较少.在把猫分类为两种模式后，将提供新的位置和适应度函数，将最佳解决方案的猫筛选出来，重复以上步骤直到满足终止条件.

CSO算法过程可分为以下5步：

1．创建群体中猫的总数并把它们分散到M维的解空间Xi,d中，同时为每只猫随机分配一个在最大速度区间内的一个初速度vi,d.

2．根据两种模式的混合比MR，为每只猫设置一个标志，将它们分类为搜索模式或跟踪模式.

3．使用最佳适应度函数保存每只猫的适应度的值，并对其进行评估.位置最好的猫(Xbest)代表目前最佳的解决方案.

4．根据猫的标志，让猫在搜索模式和跟踪模式间切换.

5．若终止条件被满足，则算法结束，否则重复2至5步.

3.1 搜索模式

要描述猫的搜索行为，需要使用4个参数：搜索存储池(SMP)、相应维度搜索范围(SRD)、可变维度总数(CDC)、自身位置考量(SPC).SMP表示进入搜索模式的猫的总数；SDR记录了猫所在维度的旧值与新值的变化范围；CDC表示有多少个维度发生了变化；SPC是布尔变量，它表示猫的当前位置是否可作为移动的候选位置.SPC的值不能影响SMP的值.

搜索过挰如下：

1．遍历每一只猫确定SMP数量.如果当前猫的SPC值为true，则SMP值减1，并记录当前猫的位置信息.

2．针对上一步记录的猫，根据CDC的值使用以下公式(2)计算其新位置.

xcn=(1±SRD×R)×XC

(2)

其中XC为猫的当前位置，XCN为猫的新位置，R为0-1间的随机数

3．计算猫的新位置适应度值FS.若所有适应度值FS都相等，将所有侯选点的备选概率设置为1，否则使用公式(3)来计算每一个侯选点的备选概率.

(3)

其中，Pi是第i只侯选猫的概率，FSi第i只侯选猫的适应度值，FSmax和FSmin适应度的最大值和最小值.

3.2 跟踪模式

跟踪模式激发猫去捕捉猎物.当猫在搜索模式中发现猎物后，猫可以根据猎物的位置及其速度决定自身的移动速度和方向.在CSO中，猫k在维度d上的速度由公式(4)计算：

Vk,d=Vk,d+r1×c1(Xbest,d-Xk,d)

(4)

其中，vk,d为猫在维度d上的速度，Xbest,d为最优解的猫的位置，Xk,d为猫k的位置，c1为常量，r1为0～1间的随机数.

猫k的最新位置可由公式(5)计算：

Xk,d,new=Xk,d,old+Vk,d

(5)

其中，Xk,d,new为猫k在维度d上的新位置，Xk,d,old为猫k在维度d上的当前位置.

4 实验结果分析

本文实验使用一些常用标准数据集，同时也采了WSDL数据集，WSDL文档数据集源自于OWLS-TC4.聚类的精确度使用公式(6)来计算：

(6)

其中，k表示聚类的个数，j表示分类的个数.在WSDL数据集中，为提高运算精度，采用了一些特定的领域，如通信、经济、教育、食品、地理、医药、模拟、旅行及武器.实验结果及对比分析如表1.可以看到相对于K-means算法，CSO算法在各个数据集上的计算精度都有所提高.

表1 k-means算法和CSO算法在各数据集的聚类精度

5 结 论

本文提出一种分类Web服务以增强服务发现的方法.为对Web服务进行聚类，应用了K-means算法和猫群优化算法CSO，并比较了两种算法在标准数据集和WSDL数据集上性能.结果表明，CSO明显优于K-means，在CSO的跟踪模式下，聚类中心随机变化可以检测出更好的聚类中心.我们将进一步扩展所提出的聚类算法，优化Web服务的实时搜索精度，增强Web服务发现的时间和精度等性能.