Multiple Population Genetic Algorithm And Its Application In Complex Network Community Classification Research

The problem of the community division in complex network is a hotspot in recent years, How to detect and divide the community structure of complex network is of great significance to understand the structure and properties of the entire network. So far, people have proposed many community partition algorithms, although most of the algorithms still have some defects, such as some algorithms need to know the number of nodes in the community or the number of the communities in advance, and part of the algorithms still need to know other threshold, more importantly, most of the algorithms are not suitable for the analysis to large complex network due to the high time complexity. Based on the conclusion above, this paper forward a new method of community division in complex network, which is based on multi-population genetic algorithm, namely IMPGA algorithm. The experiments show the superiority of the IMPGA algorithm.The major work and innovation points in this paper are as follows:(1) An improved structure form of the multi-population genetic algorithm is proposed. The traditional genetic algorithm using serial idea to solve the problem of the community division in complex network, IMPGA algorithm use three child populations parallel evolutionary structure form, one of the populations is elite population, and the other two are common populations, then use the multi-thread technology to achieve multi-population parallel operation, making three population evolve parallelly, eventually get the global optimal solution. The improvement of the structure form makes the algorithm be significantly enhanced in efficiency.(2) An improved adaptive crossover probability and mutation probability is proposed. Traditional multi-population genetic algorithms use the fixed crossover probability and mutation probability, In IMPGA algorithm, the crossover probability is judged by the difference of the chromosomal, if the difference is small then the crossover probability is big, otherwise, the crossover probability is small, it is advantageous to the separation of individual characters, and increase the diversity of the population; The mutation probability is judged by the fitness value of the chromosomal, if the fitness value is large then the mutation probability is small, otherwise, the mutation probability is big. It protects the excellent individual with large fitness value, making its good gene are not destroyed, at the same time, the individual with small fitness value execute mutation operation, making its inferior genes are improved. The improved adaptive crossover probability and mutation probability reduce the destruction of the traditional crossover operation and mutation operation, and enhance the capacity of parameters allocation, making the algorithm achieve a great improvement both in the optimal quality and the convergence efficiency.(3) An improved migration operator is proposed. The elite migration strategy is used after every generation of evolution in the traditional multi-population genetic algorithms. It is not only to bring the burden on the efficiency of the algorithm, but also is not good for the evolution of the population when ignoring the bad individual. In IMPGA algorithm, the improved migration operator is used after a set generation number. Two common populations generate the best individuals, and migrate them to the elite population. At the same time, two common populations exchange their worst individual and the best individual with each other. It can keep the good gene in the inferior individuals, even improve the bad gene through the changed environment. The improved migration operator promoted the information interaction among populations and enhance the diversity of population.(4) A new method named IMPGA algorithm is proposed to solve the problem of the community division in complex networks, which is based on multi-population genetic algorithm. IMPGA can overcome the disadvantage of traditional community division algorithm, such as prior information restrictions and high time complexity and network scale limit. IMPGA only requires less priori information, and the efficiency of the algorithm is high, so it is suitable for the community division in large complex network.