Research On The Algorithms Of Constructing Graphs With Given Girths Based On Evolutionary Computation

With the rapid development of evolutionary computation,it is becoming more and more widely used in solving large-scale sophisticated problems such as multi-objective function optimization,engineering design and nonlinear multi-objective optimization.Extreme graph theory is an important branch of graph theory,and it mainly studies the extremal graph problem satisfying the maximum graph or minimum graph under a given condition.Studying the algorithms for constructing extremal graphs is an important research content of extremal graph theory,and is concerned by more and more researchers.However,it is very difficult to construct the extremal graphs by using the computer programs,especially when the number of vertices is increasing constantly.Therefore,it is of great theoretical and practical value to study the application of evolutionary algorithms for constructing extremal graphs.Firstly,the programming model of the extremal graph problem is given according to its definition,which is used to construct the corresponding extremal graphs.By adding adaptive mechanism and fast evolutionary operation base on the traditional genetic evolutionary algorithm,the algorithm named ConstructEG_GA is proposed to construct graphs with given girths.A discrete mapping mechanism is also proposed to solve the discrete optimization problem.Based on this,the algorithm named ConstructEG_PSO is proposed to construct graphs with given girths.Then,an adaptive method for adjusting rotation angle step is proposed to solve the problem of single rotation step of the traditional quantum evolutionary algorithm.Based on the adaptive adjusting method,the algorithm named ConstructEG_QEA is proposed to construct graphs with given girths.In order to speed up the convergence rate of the algorithm,the perturbation operation and selecting the symmetry graphs into the next generation are added in the evolutionary process.Finally,the compared experiments of the three algorithms ConstructEG_GA,ConstructEG_PSO and ConstructEG_QEA are carried out by constructing graphs with n vertices(44 ? n ? 48)and girth 10.The experimental results show that ConstructEG_QEA is superior to ConstructEG_PSO and ConstructEG_GA in solving the suboptimal solution and the optimal solution of the problem.The convergence rate of the algorithm ConstructEG_QEA is also analyzed by constructing a graph with n vertices(21?n?30)and girth 11.The results show that ConstructEG_QEA can reach the optimal solution in a short time.In the end,the graphs with n vertices(31 ?n?89)and girth 11 are constructed by ConstructEG_QEA,and the lower bounds of ex(n;11)are obtained.