Master-Slave Parallel Gene Expression Programming With Constrained Description

Evolutionary algorithm is a branch of artificial intelligence algorithm.After decades of development,it has been widely used in many aspects related to computer.Gene Expression Programming(GEP),as a kind of evolutionary algorithm,has been widely recognized by researchers because of its simple coding ability but the ability to solve complex problems.It has achieved great achievements in many fields,such as time series prediction,big data analysis,multi-objective optimization etc.However,the classical GEP algorithm also has some shortcomings: genotypes are mostly randomly generated,which leads to a large number of invalid individuals in the population and reduces the quality of the population;Single population design can easily lead to convergence and precocity,which makes the population fall into local optimum and affects the search of solution.Evaluation is in a sense a serial behavior in a sense,can not make good use of the computer performance,affecting the speed of its evolution.To address above problems,this paper mainly improves the classical GEP from two aspects of representation structure and parallel design:1.To solve the problem that there are a large number of invalid individuals in the population,this paper improves the representation structure level and proposes a depth-first decoding GEP with embedded constraint description function.On the one hand,the domain knowledge is introduced into GEP,and a description matrix(constraint table)is used to constrain and guide the generation of genes and the evolution of population,thus improving the convergence speed and the precision of the solution of GEP.On the other hand,the depthfirst principle is used to implement gene decoding and construct expression tree to make the relationship between genes closer,so as to effectively guide the generation and search process of solutions.In addition,for the absence of domain knowledge,this paper also proposes a depth-first GEP of constraint table co-evolution,that is,starting from the GEP without domain knowledge,the constraint table is continuously evolved to find relevant domain knowledge for practical problems,so as to guide the convergence evolution of GEP.2.To solve the problem that the precocious population is trapped in local optimal and serial GEP,which cannot make good use of computer performance,this paper proposes a parallel GEP with master-slave population co-evolution based on the parallel design level.On the one hand,the coarse-grained master-slave population co-evolution strategy is adopted to enlarge the population diversity of GEP and prevent the evolution from falling into local optimum too quickly,so as to improve the precision of the GEP solution.On the other hand,the serial GEP is improved in global parallel to speed up its solving speed.In addition,this paper proposes a master-slave parallel GEP with constraint description based on the above two kinds of GEP improvements,which combines structural constraints and parallel design improvements.The experimental verification and analysis show that these improved methods can speed up the GEP solution,accelerate the convergence process and improve the quality of the solution,which is a new attempt to explore the performance improvement of GEP.