A Spanning Tree-Based Encoding of the MAX CUT Problem for Evolutionary Search

Kisung Seo¹, Soohwan Hyun¹, and Yong-Hyuk Kim²

¹Dept. of Electronic Engineering, Seokyeong University, Seoul, Korea
ksseo@skuniv.ac.kr
xjavalov@shhyun.com

²Dept. of Computer Science and Engineering, Kwangwoon University, Seoul, Korea
yhdfly@kw.ac.kr

Abstract. Most of previous genetic algorithms for solving graph problems have used vertex-based encoding. In this paper, we introduce spanning tree-based encoding instead of vertex-based encoding for the well-known MAX CUT problem. We propose a new genetic algorithm based on this new type of encoding. We conducted experiments on benchmark graphs and could obtain performance improvement on sparse graphs, which appear in real-world applications such as social networks and systems biology, when the proposed methods are compared with ones using vertex-based encoding.

Keywords: Basis change, encoding, representation, genetic algorithm, MAX CUT, spanning tree, graph

LNCS 7491, p. 510 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012