A dominance tree and its application in evolutionary multi-objective optimization

doi:10.1016/j.ins.2009.06.035

	A dominance tree and its application in evolutionary multi-objective optimization
	Shi, Chuan 1; Yan, Zhenyu 2; Lue, Kevin 3; Shi, Zhongzhi 4; Wang, Bai 1
	2009-09-29
发表期刊	INFORMATION SCIENCES
ISSN	0020-0255
卷号	179 期号:20 页码:3540-3560
摘要	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 DTs 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. (C) 2009 Elsevier Inc. All rights reserved.
关键词	Evolutionary multi-objective optimization Evolutionary computation Pareto dominance Fitness assignment Computational complexity
DOI	10.1016/j.ins.2009.06.035
收录类别	SCI
语种	英语
资助项目	National Science Foundation of China[60402011] ; National Science Foundation of China[60775035] ; National Science Foundation of China[60805041] ; 863 National High-Tech Program[2007AA01Z132] ; National Basic Research Priorities Programme[2003CB317004] ; National Basic Research Priorities Programme[2007CB311004] ; National Science and Technology[2006BAC081306] ; National Science and Technology[2006BAH031305]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000269429100006
出版者	ELSEVIER SCIENCE INC
引用统计	被引频次：13[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11858
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shi, Chuan
作者单位	1.Beijing Univ Posts & Telecommun, Beijing Key Lab Intelligent Telecommun Software, Beijing, Peoples R China 2.Univ Virginia, Dept Syst & Informat Engn, Charlottesville, VA 22903 USA 3.Brunel Univ, Uxbridge UB8 3PH, Middx, England 4.Chinese Acad Sci, Inst Comp Technol, Beijing 100864, Peoples R China
推荐引用方式 GB/T 7714	Shi, Chuan,Yan, Zhenyu,Lue, Kevin,et al. A dominance tree and its application in evolutionary multi-objective optimization[J]. INFORMATION SCIENCES,2009,179(20):3540-3560.
APA	Shi, Chuan,Yan, Zhenyu,Lue, Kevin,Shi, Zhongzhi,&Wang, Bai.(2009).A dominance tree and its application in evolutionary multi-objective optimization.INFORMATION SCIENCES,179(20),3540-3560.
MLA	Shi, Chuan,et al."A dominance tree and its application in evolutionary multi-objective optimization".INFORMATION SCIENCES 179.20(2009):3540-3560.