苏佰川，张国义，许胤龙

（中国科学技术大学 计算机科学学院，安徽 合肥230026）

随着面向服务计算技术的深入发展，通过组合Web服务建立分布式应用系统逐渐成为基于Web应用开发的主流技术。在众多可获得的Web服务资源中，如何选择合适的服务实例进行组合，使之既能满足应用的功能需求，又能满足用户提出的QoS需求，是一个备受关注的问题，并已得到了广泛的研究。

QoS约束的Web服务选择与组合是一类组合优化问题。到目前为止，求解该问题比较典型的方法有线性规划算法[1-2]和遗传算法[3-6]。线性规划算法在候选服务集规模较小时是非常有效的，但是随着规模的加大，计算耗时增长速度明显加快，可扩展性变差。遗传算法被用于QoS的全局组合优化已有许多成功的案例，但是，由于在诸多的研究中一般采用随机交叉和变异操作，没有考虑候选服务实例之间实际存在的连接偏好，组合服务的可靠性难以得到有效的保证。连接频率反映了服务之间的连接偏好，频率越高，下一次连接的可能性就越大，在一定程度上可增强组合服务的可靠性。如何利用候选服务实例之间的连接偏好优化服务的随机选择，提高服务组合的效率与成功率是本文主要关注的问题。

根据软件工程的一般常识可知，一个复杂的组合服务包含平行、分支、选择、循环等结构，可以利用数据流聚合方法形成颗粒较大的结构块。而对于一个大规模的候选服务集合，应用社会网络社区形成机制[7]，也可以形成与服务流程聚合块功能相一致的服务子集，即所谓的服务社区。……