Cloud computing as a widely used computing platform can provide a number of services for customers in a pay-as-you-go fashion. Enabling further growing and complex needs of users, service of different independent cloud provider should be composed to deliver uniform Quality of Service (QoS) as a single request. An open and valid question is how to select services as a partner chain and optimize the service compositions in order to satisfy both functional and non-functional requirements across multiple Cloud services. It is a NP-hard problem and faces trade-off among various QoS criteria. In this paper, a service composition model is presented considering the geo-distributed Multi-Cloud environment. Furthermore a Genetic Algorithm (GA) with improved crossover and mutation operator is proposed for QoS-aware service composition which allows users to select the optimized composition solution according to their preference. Experiment results show that this algorithm can improve the solution optimality and accelerate convergence speed.