Research On Symbolic Regression Based On Mathematical Formula Space Representation Mechanism

Evolutionary algorithm,as a heuristic search method,is one of the commonly used methods for solving symbolic regression problems.However,evolutionary algorithm often falls into a local optimum because the individuals in the population tend to be similar as the evolution process progresses.In addition,as a random search method,evolutionary algorithm is non-directional,and blind search leads to its performance degradation.To overcome these two shortcomings of evolutionary algorithm in solving symbolic regression problem,according to the characteristics of mathematical formula space,this thesis proposes space partition methods AB-GEP and GVAE-ABGEP based on symbolic similarity and fitness distance respectively.AB-GEP partitions the whole mathematical formula space into multiple mutually exclusive subspaces according to the symbolic similarity.On this basis,AB-GEP constructs a modified adversarial bandit strategy Avg Exp3 to dynamically evaluate the reward of subspaces,and makes the evolution process occurs in the subspace with better reward,so that AB-GEP ensures the directionality and guidance of the search;In addition,according to the evaluation results of subspaces’ reward by Avg Exp3,AB-GEP guides the population to jump between the subspaces to maintain the population diversity,so as to avoid the algorithm from falling into local optimum.This thesis proves that the estimation method of Avg Exp3 for the subspace average reward is an unbiased estimate,and has a smaller variance than the original adversarial bandit algorithm Exp3.Experimental results show that AB-GEP makes search directional while maintaining population diversity;and compared with the baseline algorithms GEP,SL-GEP and SPJ-GEP,AB-GEP can obtain symbolic expressions with smaller error.AB-GEP partitions the mathematical formula space according to the symbolic similarity,which cannot meet the requirements of similar individual fitness in the same subspace,resulting in the efficiency reduction of the algorithm due to the frequent search of individuals with poor fitness when exploring the subspace.In order to solve this problem,GVAE-ABGEP partitions the mathematical formula space based on fitness distance,thus ensuring that the fitness of symbolic expressions is similar in the same subspace.On this basis,GVAE-ABGEP uses Avg Exp3 to evaluate the subspace reward,and according to the evaluation results,uses the grammar variational auto-encoder(GVAE)to generate individuals in the selected subspace for the purpose of exploration.The experimental results show that,compared with AB-GEP,GVAE-ABGEP enables evolutionary search to occur in areas with better fitness and can obtain more accurate symbolic expressions.