The Research And Practice On Symbol Regression Based Space Division

Gene Expression Programming(GEP)is the most commonly used algorithm for handling symbolic regression(SR)problems.However,it is a random search algorithm without direction and memory.In the search process,the individual structures of the population tends to be the same,thus the algorithm loses the search function,and it is easy to fall into the local optimal.In order to overcome these shortcomings,this thesis proposes an evolutionary search algorithm based on the idea of space division(SP-GEP-UCB),using the Upper Confidence Bound(UCB)combined with ? greedy method as a selection strategy and an improved search algorithm based on extreme value theory(SP-GEP-EV).In order to maintain the population diversity and prevent GEP from falling into the local optimal space,SP-GEP-UCB uses a space division strategy to divide the entire search space into k different subspaces.In the evolution of each generation,based on the search information of the population in each subspace,SP-UCB-EV firstly uses the subspace selection strategy combined with UCB and ? greed to select one of subspaces.Then,individuals use crossover and mutation operations to search in the selected subspace.Through the subspace selection strategy,individuals search in different subspaces.Moreover,the population diversity is maintained.Through algorithm analysis,this thesis gives the algorithm complexity and reasonable range of subspace.Experimental results show that SP-GEP-UCB can overcome classical GEPs' shortcomings,such as the decline of population structure diversity and unguided.The algorithm can also speed up the convergence speed and obtain more accurate results at the same time.In SP-GEP-UCB algorithm,in order to make up for the defect that the UCB will lose effect after the search number increases to a certain number.To overcome the fault of UCB,?-greedy is used in the late stage of the algorithm.However,?-greedy is completely random,and impossible to select valuable subspaces based on individual access to information.In order to overcome the shortcomings of this algorithm,the SP-GEP-EV algorithm is proposed.This algorithm uses extreme value theory to select the subspace after the UCB loses its effect.In addition,in order to reduce the time complexity of the algorithm,a new L-moment parameter estimation method is also constructed to achieve on-line online calculation.Experiments show that SP-GEP-EV has better accuracy.