关键词: 服务组合, Petri网, 遗传算法, 多路径, 变长染色体, Web服务

Abstract: Combined with Petri net, a variable length chromosome Genetic Algorithm (GA) was proposed to handle QoS-aware service composition among multiple composite structures (paths) problem. Petri net was used to express kinds of Web Service composite structures. It listed all the execution sequences of Web Service to fulfill the user's functional requirements. Subsequently, parallel service execution structures were found out and added into execution sequence so as to modify execution sequence to represent the unique path. Based on paths from Petri net, the variable length chromosome GA represented composited services in multiple paths by variable length chromosomes and conducted the gene crossover operation by service parameters matching to implement the optimum Quality of Service (QoS) composition service search in multi-path. Based on the proposed algorithm, two improvements were put forward to enhance the stability of the algorithm. One was used to choose better initial generation and the other was to optimize the stage generations. Scalability of the algorithm was analyzed theoretically and experimental results demonstrated its effectiveness by comparing to traditional GA.

Key words: service composition, Petri nets, genetic algorithms, multi-path, variable length chromosome, Web Service