ST Encoding: An Efficient Scheme for Encoding Trees in Genetic Algorithms

Abstract

Graph optimization problems are usually difficult and time-consuming NP problems. Genetic algorithms have been proven to be an efficient technique for solving these problems. Well-designed chromosomes and appropriate operators are key factors that determine the performance of such genetic algorithms. This study proposes a novel scheme, sequence and topology encoding, for encoding trees and three associated operators. Experiments on different scales of minimum spanning tree problems are conducted to compare the performance of the proposed encoding scheme with that of the Prüfer number, which is the best encoding scheme so far. The results indicate that the proposed encoding scheme is an efficient scheme for encoding trees in genetic algorithms.