Versatile Semantic Linear Genetic Programming For Program Synthesis Problems

Program synthesis is an optimization problem searching a sequence of program to satisfy user demand based on the domain specific language.It has been applied in a wide range of scenes such as software development and maintaining,industrial procedure design,and knowledge discovery.Existing program synthesis methods still suffer from the high dependence on expertise knowledge,or the low success rate,or the less interpretable solutions.Thus,this paper proposed a semantics linear genetic programming to relief these drawbacks.The contributions of this paper are listed as follows.Firstly,the paper designed a generalized linear genetic programming chromosome representation to decode programs.The main innovation of the generalized linear genetic programming chromosome representation is decoding instructions into deeper parsing trees,instead of 3-register machine language.This linear chromosome representation method also combines the procedural semantic outputs as the semantic context of the program.Secondly,to further improve the performance,this paper also proposed a versatile semantic evolution mechanism(including the frequency switch,semantic perceptron,insertand-divide propagation,and evolutionary library maintaining)to understand and utilize the semantics,and have an insight into instructions.By this means,the proposed method improves the searching efficiency and interpretability while reduces the dependence on the expertise knowledge.Thirdly,to validate the performance of the proposed method,a benchmark of program synthesis problems is also designed.The proposed benchmark covers four types of program synthesis problems to validate the generalization of the proposed method.Based on the proposed benchmark,the paper performed a series of experiments including success rate comparison,learning rate comparison,and interpretability analysis.The experiment results show that the proposed method successfully overcomes those drawbacks and has a high success rate in various applications.The solutions produced by the proposed method also have better interpretability.