Research On Binary Space Partition Tree Based On Efficient Search Genetic Algorithm

The optimization problem exists widely in the field of scientific research and practical engineering applications.At present,many experts and scholars have proposed a lot of methods for this kind of problem,such as gradient descent method,Newton method,Lagrange multiplier method and intelligent optimization algorithm based on evolutionary computation.Among them,the intelligent optimization algorithm based on evolutionary computation has the characteristics of self-organization,self-learning and self-adaptation.Its good global search ability and parallel processing ability have attracted wide attention of scholars.The performance of the evolutionary algorithm is affected by various factors such as the distribution of the population,the setting of algorithm parameters and the selection of genetic operators.Among them,the good population distribution,as well as the search history information of the algorithm,can guide the search direction of the population,speed up the convergence speed of the algorithm,and improve the accuracy of the algorithm.Based on this,two genetic algorithms based on binary space partition tree are proposed,and the individual distribution in the population is adjusted by using the binary space partition tree,and the evolution of the population is guided by the recorded historical information from the point of view of single region and multi-region respectively,so as to improve the search ability of the algorithm to a certain extent.The research content of this thesis is as follows:(1)This thesis proposes a single region guided search genetic algorithm based on binary space partition tree(BSPSGA).The main idea of the BSPSGA algorithm is to use the binary space partition tree as an archive,record the historical information of the genetic algorithm search,adjust the population distribution.The BSPSGA algorithm redefines the construction rules of the binary space partition tree,and uses the binary space partition tree to record the search information generated by the genetic algorithm in the process of exploring the optimal solution,and adjusts the individuals with relatively close distribution in the space to make the population distribution more uniform,thus ensuring a good diversity of the population.Based on the historical information recorded by the binary space partition tree,a local search strategy is proposed,which strengthens the search intensity of the subspace where the current optimal solution is located and guides the evolution direction of the population.The proposed strategy not only accelerates the convergence speed of the algorithm,but also improves the accuracy of the algorithm.In order to verify the validity of the proposed algorithm,three groups of experiments are designed in this thesis,which are simulated experiments on the problem of reference function testing,fault diagnosis of power system and molecular feature selection of cancer,and the experimental results verify the effectiveness of the proposed algorithm.(2)This thesis proposes a multi-region guided search genetic algorithm based on binary space partition tree(BSPMGA).Intelligent optimization algorithm based on evolutionary computation with the increase of the size of the optimization problem,the search ability of the algorithm needs to be improved.The main idea of the BSPMGA algorithm is to use the binary space partition tree to divide the search space of the problem,and bind each individual to the spatial sub-area,and use the individual fitness.The value is used as a measure of the search value of each sub-region.Select multiple sub-regions with search value,expand the search range of the algorithm,and strengthen the search strength through the local search strategy.Based on this the extended population is introduced,and the population size of the participating environment selection is expanded,which improves the performance of the algorithm to some extent.In order to verify the effectiveness of the proposed algorithm,the experimental verification is carried out on the large-scale benchmark function test problem,and a series of simulation experiments are carried out on the large-scale backpack problem.The results show that the proposed algorithm can effectively deal with large-scale optimization problems.