Do Search and Selection Operators Play Important Roles in Multi-Objective Evolutionary Algorithms:A Case Study  

作　　者：Yan Zhen-yu, Kang Li-shan, Lin Guang-ming ,He MeiState Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, Hubei, ChinaSchool of Computer Science, UC, UNSW Australian Defence Force Academy, Northcott Drive, Canberra, ACT 2600 AustraliaCapital Bridge Securities Co. ,Ltd, Floor 42, Jinmao Tower, Shanghai 200030, China 

出　　处：《Wuhan University Journal of Natural Sciences》2003年第S1期195-201,共7页武汉大学学报（自然科学英文版）

基　　金：Supported by the National Natural Science Foundation of China(60133010,70071042,60073043)

摘　　要：Multi-objective Evolutionary Algorithm (MOEA) is becoming a hot research area and quite a few aspects of MOEAs have been studied and discussed. However there are still few literatures discussing the roles of search and selection operators in MOEAs. This paper studied their roles by solving a case of discrete Multi-objective Optimization Problem (MOP): Multi-objective TSP with a new MOEA. In the new MOEA, We adopt an efficient search operator, which has the properties of both crossover and mutation, to generate the new individuals and chose two selection operators: Family Competition and Population Competition with probabilities to realize selection. The simulation experiments showed that this new MOEA could get good uniform solutions representing the Pareto Front and outperformed SPEA in almost every simulation run on this problem. Furthermore, we analyzed its convergence property using finite Markov chain and proved that it could converge to Pareto Front with probability 1. We also find that the convergence property of MOEAs has much relationship with search and selection operators.Multi-objective Evolutionary Algorithm (MOEA) is becoming a hot research area and quite a few aspects of MOEAs have been studied and discussed. However there are still few literatures discussing the roles of search and selection operators in MOEAs. This paper studied their roles by solving a case of discrete Multi-objective Optimization Problem (MOP): Multi-objective TSP with a new MOEA. In the new MOEA, We adopt an efficient search operator, which has the properties of both crossover and mutation, to generate the new individuals and chose two selection operators: Family Competition and Population Competition with probabilities to realize selection. The simulation experiments showed that this new MOEA could get good uniform solutions representing the Pareto Front and outperformed SPEA in almost every simulation run on this problem. Furthermore, we analyzed its convergence property using finite Markov chain and proved that it could converge to Pareto Front with probability 1. We also find that the convergence property of MOEAs has much relationship with search and selection operators.

关 键 词：multi-objective evolutionary algorithm convergence property analysis search operator selection operator Markov chain 

分 类 号：O224[理学—运筹学与控制论]