Variable solution structure can be helpful in evolutionary optimization
Variable solution structure can be helpful in evolutionary optimization作者机构：National Key Laboratory for Novel Software Technology Nanjing University Collaborative Innovation Center of Novel Software Technology and Industrialization
出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))
年 卷 期：2015年第58卷第11期
页 面：145-161页
核心收录：
学科分类：0810[工学-信息与通信工程] 12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0808[工学-电气工程] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：supported by National Natural Science Foundation of China(Grant Nos.61375061,61333014) Jiangsu Science Foundation(Grant No.BK2012303)
主 题：evolutionary algorithms genetic programming maximum matching minimum spanning tree running time computational complexity
摘 要：Evolutionary algorithms are a family of powerful heuristic optimization algorithms where various representations have been used for solutions. Previous empirical studies have shown that for achieving a better efficiency of evolutionary optimization, it is often helpful to adopt rich representations(e.g., trees and graphs)rather than ordinary representations(e.g., binary coding). Such a recognition, however, has little theoretical justifications. In this paper, we present a running time analysis on genetic programming. In contrast to previous theoretical efforts focused on simple synthetic problems, we study two classical combinatorial problems, the maximum matching and the minimum spanning tree problems. Our theoretical analysis shows that evolving tree-structured solutions is much more efficient than evolving binary vector encoded solutions, which is also verified by experiments. The analysis discloses that variable solution structure might be helpful in evolutionary optimization when the solution complexity can be well controlled.
同方期刊数据库