Using determinant and cycle basis schemes in genetic algorithms for graph and network applications
Faris N. Abuali · 1996
Two new schemes for representing spanning trees are developed. The first scheme is the determinant encoding, and is based on the factorization of the in-degree matrix of the original graph. This scheme is compared to the Prufer encoding for representing spanning trees on complete graphs. The second encoding is the cycle basis encoding and is based on the cycle basis of the original graph. The cycle basis encoding is designed to work with incomplete graphs. The cycle basis encoding is compared to the determinant encoding for incomplete graphs. The determinant encoding and cycle basis encoding schemes are used to find optimal or near optimal solutions to the probabilistic minimum spanning tree problem (PMST). My new encoding schemes and other newly developed schemes are applied to the PMST problem to determine empirically the best encoding. The results of the research indicate that the determinant encoding is better than the Prufer encoding for representing spanning trees on the PMST problem. Also the cycle basis encoding is better than the determinant encoding on incomplete graphs with small (less than 0.3) edge connectivity probability. A Markov chain is used to model a simple Genetic Algorithm using the determinant and Prufer codes. The steady state distribution for the determinant codes identifies the isomorphism classes. Detailed theoretical analysis of the search space is also presented.