Abstract: The service deployment with multi-service level agreement is a basic problem to be solved for the service based software system. To overcome the shortcomings of the existing algorithms, a multi-objective model for this problem is built and a Simulation-based Multi-Objective Genetic Optimization Algorithm (SMOGA) is proposed. According to the characteristics of this problem, the genetic operations are redefined, including the introduction of individual domination strength into the environment selection, and the redefinition of crossover strategy and individual mutation strategy incorporated with local search. The performance of the proposed SMOGA was analyzed and compared with that of recently proposed algorithms E3-MOGA and NSGA-II for this problem on different scale test cases. Experiment results show that the proposed SMOGA can solve this problem more effectively.