A dominance tree and its application in evolutionary multi-objective optimization |
| |
Authors: | Chuan Shi Zhenyu Yan |
| |
Affiliation: | a Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, China b Department of Systems and Information Engineering, University of Virginia, USA c Brunel University, Uxbridge, UB8 3PH, UK d Institute of Computing Technology, Chinese Academy of Sciences, China |
| |
Abstract: | Most contemporary multi-objective evolutionary algorithms (MOEAs) store and handle a population with a linear list, and this may impose high computational complexities on the comparisons of solutions and the fitness assignment processes. This paper presents a data structure for storing the whole population and their dominating information in MOEAs. This structure, called a Dominance Tree (DT), is a binary tree that can effectively and efficiently store three-valued relations (namely dominating, dominated or non-dominated) among vector values. This paper further demonstrates DT’s potential applications in evolutionary multi-objective optimization with two cases. The first case utilizes the DT to improve NSGA-II as a fitness assignment strategy. The second case demonstrates a DT-based MOEA (called a DTEA), which is designed by leveraging the favorable properties of the DT. The simulation results show that the DT-improved NSGA-II is significantly faster than NSGA-II. Meanwhile, DTEA is much faster than SPEA2, NSGA-II and an improved version of NSGA-II. On the other hand, in regard to converging to the Pareto optimal front and maintaining the diversity of solutions, DT-improved NSGA-II and DTEA are found to be competitive with NSGA-II and SPEA2. |
| |
Keywords: | Evolutionary multi-objective optimization Evolutionary computation Pareto dominance Fitness assignment Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|