Abstract: Optimal service selection satisfying Service Level Agreement (SLA) is a NP hard problem. In order to solve the dimension and granularity problems, a comprehensive service selection model was proposed which considered semantic link degree, Quality of Service (QoS) and transactional properties. A coding strategy was adopted to solve the multi-granularity problem. In order to reduce the computation cost, a hybrid optimization algorithm based on clonal selection and Genetic Algorithm (GA) was proposed. Firstly, the dynamic fitness function was adopted to drive the evolution toward constraint satisfaction. Secondly, the knowledge-oriented crossover and mutation operators based on priority were designed to ensure the transactional property of composite service. Finally, the clonal selection was combined into the GA to improve the search ability. In the simulation experiments, the proposed algorithm had better performance in accuracy and successful rate compared to GA; the time cost of the proposed algorithm was a little higher than that of GA but much lower than that of exhaustive search algorithm. The experimental results show that the proposed algorithm can guarantee QoS of service selection with low time cost.

Key words: semantic link degree, Quality of Service (QoS), transactional property, clonal selection, Genetic Algorithm (GA), service selection

摘要： 服务级别协议（SLA）等级感知的服务选择是NP难题。针对服务选择中维度与粒度方面的问题，提出结合语义与事务属性的服务质量（QoS）感知的服务优化选择模型。该模型从语义链接匹配度、QoS与事务三个维度对服务进行优化选择，并设计了支持多粒度的编码策略。针对服务选择中时间复杂度高的问题，提出了克隆选择与遗传算法相结合的混合优化算法。该算法首先采用动态适应度函数，逐代淘汰不满足约束的个体；其次给出了事务属性的优先级，并根据优先级设计了知识启发式的交叉与变异算子，以保证个体满足事务属性要求；最后在遗传算法中对优秀个体进行克隆选择，以增强对最优解的搜索能力。仿真实验中，该算法在服务选择的精确度和成功率方面均优于遗传算法；在时间花费上稍高于遗传算法但远低于穷举法。实验结果表明，所提算法能在较少时间花费的基础上保证服务选择的质量。

关键词: 语义链接匹配度, 服务质量, 事务属性, 克隆选择, 遗传算法, 服务选择