Dynamic grammar pruning for program size reduction in symbolic  regression

Grammar is a key input in grammar-based genetic programming. Grammar design not only infuences performance, but also program size. However, grammar design and the choice of productions often require expert input as no automatic approach exists. This research work discusses our approach to automatically reduce a bloated grammar. By utilizing a simple Production Ranking mechanism, we identify productions which are less useful and dynamically prune those to channel evolutionary search towards better (smaller) solutions. Our objective in this work was program size reduction without compromising generalization performance. We tested our approach on 13 standard symbolic regression datasets with Grammatical Evolution. Using a grammar embodying a well-defned function set as a baseline, we compare efective genome length and test performance with our approach. Dynamic grammar pruning achieved signifcantly better genome lengths for all datasets, while signifcantly improving generalization performance on three datasets, although it worsened in fve datasets. When we utilized linear scaling during the production ranking stages (the frst 20 generations) the results dramatically improved. Not only were the programs smaller in all datasets, but generalization scores were also signifcantly better than the baseline in 6 out of 13 datasets, and comparable in the rest. When the baseline was also linearly scaled as well, the program size was still smaller with the Production Ranking approach, while generalization scores dropped in only three datasets without any signifcant compromise in the rest.