Genetic Algorithm for Dynamic Capacitated Minimum Spanning Tree
Tanu Gupta, Anil Kumar · 2012
Many of the network topology design problems include CMST, which means to find a minimum cost tree that connects all the nodes of the network to the central node with some capacity constraint. The links of edges have associated costs that could be based on their distance, capacity, quality of line etc, and the nodes have their associated demand. Usually most of the network obtained from CMST are static in nature, but there are situations where the network is subjected to change by addition (or deletion) of nodes, such a network is known as dynamic network and identifying CMST in this case is known as Dynamic CMST or DCMST. The Genetic Algorithm is an approach in finding better solution to DCMST problem. The GA is used with two encodings Prufer and Netkey for CMST to provide always optimal solution. Genetic algorithm are the part of evolutionary computing, which is a rapidly growing area of artificial intelligence. Genetic algorithms are computer programs, which create an environment where populations of data can compete, and only the fittest survive. Genetic algorithms are a search method that can be used for both solving problems and modeling evolutionary systems. Keyword: Spanning tree, genetic, CMST, prufer, Netkey, Edge notation, crossover.