The property analysis of evolutionary algorithms applied to spanning tree problems

Abstract

The search behavior of an evolutionary algorithm depends on the interactions between the encoding that represents candidate solutions to the target problem and the operators that act on that encoding. In this paper, we focus on analyzing some properties such as locality, heritability, population diversity and searching behavior of various decoder-based evolutionary algorithm (EA) frameworks using different encodings, decoders and genetic operators for spanning tree based optimization problems. Although debate still continues on how and why EAs work well, many researchers have observed that EAs perform well when its encoding and operators exhibit good locality, heritability and diversity properties. We analyze these properties of various EA frameworks with two types of analytical ways on different spanning tree problems; static analysis and dynamic analysis, and then visualize them. We also show through this analysis that EA using the Edge Set encoding (ES) and the Edge Window Decoder encoding (EWD) indicate very good locality and heritability as well as very good diversity property. These are put forward as a potential explanation for the recent finding that they can outperform other recent high-performance encodings on the constrained spanning tree problems.