Simulation of spontaneous emergence process of complex optimal networks by genetic algorithm

In order to simulate the whole process of the network evolution from the tree to complete graph and to solve the problem that existing adjacency nodes encoding was only suitable for the network with low density, and the traditional crossover and mutation would give rise to a lot of infeasible solution, a variable length gene encoding based on triangle matrix and operators including crossover between gene segments, mutation and balance among gene segments is proposed. Because only the triangle matrix information is encoded in the symmetric matrix that describes all possible changes of the undirected network, the length of coding string is moderate and there is no limitation of edges for modeling the whole evolution from the tree to complete graph. Crossover between gene segments only exchanges the adjacent connection at node level and the mutation balance within gene segment rewires old edge. Hence, this kind of crossover and mutation not only satisfies the demands of genetic algorithm, but also ensures the connectivity of evolving networks. Compared with the adjacency node encoding and the traditional crossover and mutation, this method has wider application range and faster convergent speed.