Variable solution structure can be helpful in evolutionary optimization

doi:10.1007/s11432-015-5382-y

Variable solution structure can be helpful in evolutionary optimization

2015-09-21

14

PRE

AI

DOI：10.1007/s11432-015-5382-y

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

evolutionary algorithms

genetic programming

maximum matching

minimum spanning tree

running time

computational complexity

Variable solution structure can be helpful in evolutionary optimization

Abstract

AI Summary

Journal

Organization