Network coding can greatly improve throughput and bandwidth utilization of optical networks, but it may bring additional coding cost. Besides, excessive transmission links for network coding may increase transmission distances and routing costs. In order to achieve the maximum multicast rate as much as possible for finding an efficient trade-off between the routing cost and coding cost, an improved Minimizing Coding-Link Cost Non-dominated Sorting Genetic Algorithm NSGA-II (MCLC-NSGA-II) is proposed in this paper. To reduce the complexity of coding cost optimization and link cost optimization, a modified non-dominated classification method is designed in the MCLC-NSGA-II. In the MCLC-NSGA-II, for speeding up the convergence and finding more Pareto-optimal solutions, a modified crowded-sorting method based on crowding distance and Hamming distance is put forward. And a crossover operator based on mutual learning is introduced to improve the evolutionary process. To increase the diversity of the population, a deleting–reserving strategy is applied to those individuals having the same coding cost schemes and routing cost schemes. Simulation results show that the proposed MCLC-NSGA-II can obtain more trade-offs than other multi-objective optimization algorithms with faster speed.