A comparative study of tree encodings on spanning tree problems

Spanning tree is one of classical combinatorial optimization problem. Recently, more attention has been paid to this problem by using genetic algorithm. Several tree encodings have been suggested to code the solution of the problem, such as Prufer number and so on. But all of them are focused on dealing with the MST problems on a complete graph. Actually, it is not always the case in practice because most practical network structures are not a complete graph. In this paper, we propose a matrix-based tree encoding to cope with the MST problem on a sparse graph. Each chromosome consists of a matrix whose gene (element) is an integer. If there is no connection between a pair of vertices, its corresponding gene is a larger positive number M (M/spl Gt/0), otherwise, an integer arranging from 1 to 256. Actually, this encoding occupies more memory, but it is more efficient to deal with the MST problem on a sparse graph. Numerical examples show that this new encoding is effective to get the optimal or near-optimal solution of the MST problem on a sparse graph.