Analysis And Design Of Genetic Algorithms Based On Complex Network Theory

There are various optimization problems in every field of real life.Genetic algorithm simulating biological evolution process has been widely used in production scheduling,image processing,machine learning and other fields because of its high robustness,versatility and simplicity.However,the standard genetic algorithm has some shortcomings,such as easy to fall into local optimum,low solution accuracy and slow convergence speed.As a bionic algorithm,the relationship between individuals of genetic algorithm can be regarded as a complex network,so the population structure of genetic algorithm can be designed from the perspective of complex network.Population topology can adjust the transmission of information among individuals,so it has an important impact on the population diversity and convergence performance of genetic algorithm.Therefore,this paper focuses on the analysis and design of genetic algorithm based on complex network theory.Firstly,the evolutionary process of genetic algorithm can be modeled as a complex network model,which is called information flow network.In this paper,information flow network modeling is improved and a more accurate and simple method of network nonuniformity analysis is proposed.In the process of information flow network modeling,the selected individuals without crossover and mutation are edged.The information flow network model can describe the transmission process of dominant gene information in genetic algorithm more completely.In addition,the network structure entropy of complex network theory is used to characterize the heterogeneity of information flow network.The network structure entropy reflects the orderliness of the information flow network,i.e.the non-uniformity of the network.Compared with the scaling index fitted in the power law degree distribution curve,the network structure entropy calculated directly according to the number and connectivity of nodes in the network can measure the non-uniformity of information flow network more accurately and concisely.Secondly,in order to improve the population diversity and convergence performance of genetic algorithm,this paper designs a genetic algorithm based on self-organizing dynamic network.In order to evaluate the importance of nodes effectively,a new definition of exponential network node fitness is proposed by considering the ranking of the objective function value of nodes in neighboring nodes and the number of neighboring nodes,which can avoid invalid evaluation caused by zero node fitness.In addition,three topology updating rules,namely,double-new,single-new and selection-deletion,are proposed to make the population structure of genetic algorithm evolve dynamically with the evolution of genetic algorithm,which effectively improves the performance of genetic algorithm in convergence performance.Finally,the genetic algorithm based on self-organizing dynamic network is compared with standard genetic algorithm and small-world genetic algorithm.The test results of typical optimization functions show that the genetic algorithm based on self-organizing dynamic network has excellent performance in maintaining population diversity and convergence performance.