Individual sensors in wireless mobile sensor networks (MSNs) can move in search of coverage region for the sensing accuracy and for reaching the most efficient topology. Besides, sensors' clustering is crucial for achieving an efficient network performance. Although MSNs have been an area of many research efforts in recent years, integrating the coverage problem of MSNs with the efficient routing requirement that will maximize the network lifetime is still missing. In this paper, we consider the coverage optimization problem where the location of a given number of mobile sensors needs to be re-decided such that the sensed data from the detected targets can be routed more efficiently to the sink and thus increasing the network lifetime. We formulate this NP-complete problem as a multi-objective optimization (MOO) problem, with two conflicting and correlated objectives; aiming at high coverage as well as longevity of network lifetime. The Non-Dominated Sorting Genetic Algorithm-II (NSGA-II) is utilized as a cluster-based routing protocol to tackle this MOO problem. Each round of the proposed NSGA-II based routing protocol creates a set of near-Pareto-optimal solutions containing a number of non-dominated solutions, in which the sink can pick up and distribute the one with high coverage to form the clustered routes. Heuristic operators are also proposed to enhance the quality of the solutions. Simulation results are provided to illustrate the effectiveness and performance of the proposed evolutionary algorithm.