Abstract: A binarytreecoding genetic algorithm (BTGA) was proposed for optimizing services selection during ServiceOriented Architecture (SOA) composition. The services composition plan was transferred into an AOV graph equivalently, and then was transformed into a binary tree further. The binary tree was traversed in postorder, and then encoded. The encoding scheme was based on binarytree. Since Nonleaf nodes of the tree keep the QoS information of its subtree, its calculation load was decreased. It also can represent branch architecture, and overcome the limits of One Dimension coding Genetic Algorithm (ODGA). Simulation results show that BTGA works more efficiently than ODGA.

摘要： 为解决SOA 服务组合中服务选择问题，提出了一种基于二叉树编码的遗传算法。首先将一个服务的组合方案等效成AOV图，并将其转换成二叉树，然后进行后续遍历并编码。该编码基于二叉树结构，树的非叶子节点保存了其子树的QoS计算结果，可有效降低遗传算法的计算量；同时可表示分支结构的组合方案，克服了一维编码的局限性。通过实例分析和仿真实验验证了其有效性及比一维编码遗传算法更高的执行效率。

关键词: 面向服务体系结构, 服务选择, 遗传算法, 二叉树编码, 服务质量, Service-Oriented Architecture (SOA), services selection, genetic algorithm, binary-tree coding, Quality of Service (QoS)