Abstract: In this study, we proposed to adopt a variable length chromosome Genetic Algorithm (GA) for handling QoS-aware service composition among multiple paths (multi-path) problem. Our approach uses variable length chromosomes to represent composited services in multiple paths and conducts the gene crossover operation based on service parameters matching. The scalability of the algorithm is analyzed theoretically and its effectiveness is demonstrated by experimental results.