Research On Improvement And Application Of Genetic Programming

Genetic programming(GP),one of the representatives of evolutionary algorithms.It uses a tree structure to represent individuals and simulates the idea of Darwin's theory of evolution to complete optimization tasks.The GP is able to automatically generate programs or structures to solve problems without explicit programming.Cartesian Genetic Programming(CGP)is an important improvement for the bloat problem of GP.In the standard CGP,individuals are represented by two-dimensional directed graphs,which can encode many computational structures flexibly.Each CGP individual has fixed-length genotype,and only point mutation operators are used to generate offspring,which can avoid the bloat problem well.But there are also defects in the standard CGP,it is easy to fall into local optimum because of the low population diversity,fixed-length genes cannot adapt to the unknown scale problem,etc.To address these problems,this paper adds the frameshift mutation as a new operation operator to the CGP algorithm which is inspired by the DNA mutation in biology.The proposed algorithm is called Frameshift Mutation Cartesian Genetic Programming(FMCGP).Around FMCGP,this paper develops the following three studies.(1)Introduce the frameshift mutation in DNA into the standard CGP,and design specific algorithms of the frameshift mutation for CGP individuals with one-dimensional topology.The proposed frameshift mutations in this paper can be caused by two operations: insertion and deletion of nodes in the individual network.In FMCGP,point mutation and frameshift mutation coexist,and offspring individuals have a certain probability that generated by frameshift mutation on parenets.The Individual selected for frameshift mutation insert nodes or delete nodes from the individual network randomly,therefore the FMCGP individuals have variable length genotype.The standard CGP,the Advanced Phenotypic Mutations in Cartesian Genetic Programming(TAPMCGP)which is set as control group algorithms and the proposed FMCGP with one-dimensional topological individuals are tested on these two sets of experiments,which are symbolic regression and even parity.The experimental results show that the proposed FMCGP has a higher evolutionary efficiency than the standard CGP and a time advantage over the TAPMCGP.In addition,the computational comparison of the length of genotype and phenotype of traditional GP,standard CGP,and FMCGP on Koza-3 and Even-8-Parity proves that FMCGP still keeps the non-bloat property of CGP.(2)In order to improve the usability of the algorithm,the frameshift mutation for onedimensional topology is introduced to two-dimensional topology,and the Two-dimensional Frameshift Mutation Cartesian Genetic Programming(2-dim-FMCGP)is proposed.In the individual network of 2-dim-FMCGP,three new genes,Colunm ID,Minimum connectable ID and Maximum connectable ID,are added to the node genes to accommodate the frameshift code mutations.In the 2-dim-FMCGP evolution strategy,the priority of the individuals generated by point mutation is higher than that by frameshift mutation.The upper limit ratio and lower limit ratio are set for individual genotype length to narrow the search range appropriately.The experimental reuslts on symbolic regression and even parity shows that the2-dim-FMCGP is able to obtain higher evolutionary efficiency than the standard 2-dim-CGP with the same topology.In order to quantitatively analyze the population diversity of graphical individuals,the calculation of individual edit distance in GP is introduced to 1-dimensional and2-dimensional CGP and FMCGP on different problems to calculate and compare the population diversity changes.The analysis result proves that the addition of frameshift mutation improves the population diversity and enhances the group search ability.(3)After clarifying the algorithm of the frameshift mutation operation on individuals with2-dimensional topology,the frameshift mutation is further introduced into the Neural Architecture Search(NAS)problem to investigate the method of automatic design Convolutional Neural Network(CNN)based on FMCGP.The FMCGP-CNN is proposed based on CGP-CNN,the performance of FMCGP-CNN is verified on CIFAR-10 and CIFAR-100 by two sets of modules,Convset and Res Set.In FMCGP-CNN,the individual uses the sames coding method as the individual in 2-dim-FMCGP,and the offspring individuals are generated by point mutation or frameshift mutation randomly.According to the experience of constructing CNN,special allele constraints are set in FMCGP-CNN.During initialization,only Conv Block or Res Block is used as the function gene within the first level-back length of the individual network.During the evolution process,the output node gene can only point to the node which in the last column of the network.Part of the training set of CIFAR-10 or CIFAR-100 is used to evaluate individual fitness.The experimental results show that FMCGP-CNN can both obtain better results than CGP-CNN by using Convset and Res Set respectively.In this paper,focusing on frameshift mutation,frameshift mutation algorithms for individuals with 1-dimensional topology and 2-dimensional topology are designed,and the performance are verified on the benchmark function.And then it is introduced into the NAS problem to complete the application of FMCGP-CNN to search CNN structure.The introduction of frameshift mutation improves the evolutionary efficiency of the standard CGP population,reduce the local optimal problem which is common in the CGP.And the frameshift mutation makes the individuals have variable-length genotype,which can better adapted to problems of different scales.Besides,the application of FMCGP in NAS problem also proves that it has certain practical value.