An Improved NSGA-II Algorithm with Markov Networks

NSGA-II algorithm is one of the most representative multi-objective Evolutionary Algorithms. With the help of elite preserving strategy and fast non-dominated sorting method, NSGA-II can effectively maintain the diversity of population and reduce the computational complexity. It has been widely used to solve different problems. However, traditional crossover and mutation operators in NSGA-II have poor linkage learning ability, so it is not easy for NSGAII to identify and exploit the interaction between variables. To make matters worse, it will inevitably damage randomly good building blocks in solution and make the process of searching the optimal Pareto front extremely difficult. In this paper, we propose an improved NSGA-II based on Markov network that replaces crossover and mutation operators by building Markov networks of promising solutions and sampling the built model to generate new solutions. Markov network can describe, identify and maintain the interaction at the variable level abstractly and accurately, which can identify and protect the good building blocks. At the same time, reduction of the manual parameter setting such as crossover probability will direct the MN-NSGA-II intelligently search for Pareto optimal front. The experimental results also show that the MNNSGA-II is effective and has better global convergence than NSGA-II.