A Solution of Real-world OCST Problems through Genetic Algorithm with a New Tree Encoding Method

摘要

For implementing the ubiquitous computing environments, the recent increasing attraction on communication systems has been driving the theory and technology of the related fields. Among these related problems, the minimum spanning tree (MST) problems, which are one of the basic combinatorial optimization problems, have many applications in the communication systems. Especially, the optimal communication spanning tree (OCST) problem is the famous application of MST problem. The OCST problem is defined by finding a spanning tree that connects all nodes and satisfies their communication requirements for connecting all nodes. This OCST problem can be applied in the many network optimization problems, such as network topology design problems, multicast tree configuration problems, and ad-hoc network or ubiquitous sensor network routing problems, and so forth. This paper presents a genetic algorithm with a new encoding method, which is based on the Prufer number (PN) and a clustering string, for solving the OCST problems. Finally, we will see clearly that the efficiency and effectiveness of our proposed method, employed as the solution method of the OCST problems, can be shown by several experimental results.