A Adaptive Partition Strategy Of Nondominated Individuals For Evolutionary Multi-objective Optimization And Application

Evolutionary Algorithm provides a new direction to complex optimization problems. Because of its intelligence, university, robustness, global search ability and parallelism, it has been widely used in many fields. After 20 years'development, multi-objective evolutionary algorithm (MOEA), whose main task is to deal with multi-objective optimization problems (MOP) by evolutionary computation, has become one of the hot issues in evolutionary computation community gradually. Evolutionary multi-objective optimization algorithms proposed before 1999, are based on selection scheme by Pareto ranks and diversity maintain by fitness sharing respectively. Towards the ends of the 1990s, emphasis on algorithmic efficiency which is the main characteristic of EMO and several algorithms based on elitism has been proposed later. More recently, current research in EMO reveals new traits. On one hand, more new evolutionary paradigms have been introduced in EMO community, such as particle swarm optimization, artificial immune system, estimation distribution algorithm, and several novel multi-objective optimization algorithms inspired by natural system have been proposed. On the other hand, in order to deal with multi-objective optimization problems, several new dominance schemes different from traditional Pareto dominance come forth.The distribution of MOP's solution mainly manifests in two aspects: breadth and uniformity. This article has analyzed two traditional ways which were used to maintenance the diversity of individual in MOEAs, then give a novel selection strategy based on adaptive partition of nondominated individuals for Multi-objective optimization. By the different level of the individual's similarity in object space, the Pareto front which consists of nondominated individuals is partitioned adaptively with this strategy. Then some typical individuals are selected to prune the nondominated individuals.When applied in two typical MOEAs: NSGA-II and PESA-II, the simulation results based on thirteen benchmark problems show that the new strategy performs better upon two others in terms of population diversity and convergence in solving most of the test problems. Then, based on the antibody clonal selection theory of immunology, by introducing adaptive partition of nondominated individuals, we propose a novel immune algorithm to deal with complex multi-objective optimization problems. The new algorithm can make the most of the structure information of antibodies, perform better in terms of population diversity and convergence, and also accelerate the convergence and obtain the global optimization quickly.Finally, a practical case, QoS multicast routing, is adopted to validate the efficiency of ADP Clonal Selection Strategy. And the results demonstrate that the new algorithm can solve the problem successfully.This work was supported by the National Natural Science Foundation of China (Grant No. 60703107), the National High Technology Research and Development Program (863 Program) of China (Grant No. 2009AA12Z210).