The encoding or representation scheme in evolutionary algorithms is very important because it can greatly affect their performance. Most previous evolutionary algorithms for solving graph problems have traditionally used a vertex-based encoding in which each gene corresponds to a vertex. In this paper, addressing the well-known maximum cut problem, we introduce an edge-set encoding based on the spanning tree – a kind of edge-based encoding. In our encoding scheme, each gene corresponds to an edge subset derived from a spanning tree.
In contrast to a traditional edge-based encoding in which each gene corresponds to only one edge, our encoding scheme has the advantage of representing only feasible solutions, so there is no need to apply a repair step. We present a genetic algorithm based on this new encoding. We have conducted various experiments on a large set of test graphs including commonly used benchmark graphs and have obtained performance improvement on sparse graphs, which frequently appear in real-world applications such as social networks and systems biology, in comparison with a scheme using a vertex-based encoding.