用遗传算法模拟复杂最优网络的自然涌现过程

为了模拟复杂最优网络从树演化到完备图的整个过程，解决现有邻接节点编码方法只适用于低密度网络，而传统的交叉变异方法又有大量不可行解的问题，提出了基于三角阵的变长基因编码方法和段间交叉、段内变异平衡的交叉变异方法．该编码方法只记录对称邻接矩阵中三角阵的信息，反映了无向网络的所有可能变化，因而编码串长度适中，网络边数不需限制，可以模拟网络从树到完备图的整个演化过程．段间交叉只交换节点一级近邻的连接方式，段内变异平衡对边进行重绕，这既符合遗传算法的要求，又保证了网络的连通性．模拟结果表明，与邻接节点编码和传统交叉变异方法相比，所提方法适用范围更广，收敛速度较快．

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.