Study On The Optimization Of The Topology Structure Of Networks Based On Genetic Algorithm

The complex network phenomenon is very widespread in the daily life. In other words, people are living in a network of the society. With the fast development of network theory and computer technology, there has been increasing interest in studying complex network as relevant to many areas of science in recent years. Especially, the proposal of small-world network and scale-free network create a new ear of studying on the complex network.The minimum spanning tree (MST) problem is the optimal topology structure of communications network. In the real world, many problems of network optimization can be described as various constrained minimum spanning tree problems. Considering the concrete model is a better method for study of the topology structure of complex network. Therefore, in virtue of the thought of mathematics model, various constrained minimum spanning tree problems can be abstracted to relevant models. Then the optimization of complex network is converted into solving the mathematics model. How to solve this model is the most important work in this paper. Up to the present, there are few effective algorithms to solve these problems because of its NP-hard complexity. As an optimization method, genetic algorithm (GA) has been widely applied. GA is excellent to many tradition search algorithms, and it provides a valid approach for the optimization of complex network system.Take degree-constrained minimum spanning tree (DCMST) problem as an example, this paper discusses how to solve this problem by means of genetic algorithms. It is presented by using C and MATLAB programs. On the one hand, according to encoding, genetic operations and running stages, this paper uses prüfer number GA (PGA), two-stage GA (TSGA) and degree-based permutation GA (DGA) respectively, and realizes the optimization of the topology structure of complex network. On the other hand, for proving the feasibility and validity of GA, edge exchange heuristic algorithm is adopted for solving this problem. Compared with this heuristic algorithm, the different scale numerical examples demonstrate the effectiveness of GA. Therefore, GA is of high practical importance in many optimization of topology structure of network.In a word, not only for study on GA but also for optimizing the allocation of resources of complex network, as logistics network, information network and traffic network etc, this study is of great research value and meaningful in practice.