Wave: Incremental Erosion of Residual Error

Typically, Genetic Programming (GP) attempts to solve a problem by evolving solutions over a large, and usually pre-determined number of generations. However, overwhelming evidence shows that not only does the rate of performance improvement drop considerably after a few early generations, but that further improvement also comes at a considerable cost (bloat). Furthermore, each simulation (a GP run), is typically independent yet homogeneous: it does not re-use solutions from a previous run and retains the same experimental settings. Some recent research on symbolic regression divides work across GP runs where the subsequent runs optimise the residuals from a previous run and thus produce a cumulative solution; however, all such subsequent runs (or iterations) still remain homogeneous thus using a pre-set, large number of generations (50 or more). This work introduces Wave, a divide and conquer approach to GP whereby a sequence of short but sharp, and dependent yet potentially heterogeneous GP runs provides a collective solution; the sequence is akin to a wave such that each member of the sequence (that is, a short GP run) is a period of the wave. Heterogeneity across periods results from varying settings of system parameters, such as population size or number of generations, and also by alternating use of the popular GP technique known as linear scaling. The results show that Wave trains faster and better than both standard GP and multiple linear regression, can prolong discovery through constant restarts (which as a side effect also reduces bloat), can innovatively leverage a learning aid, that is, linear scaling at various stages instead of using it constantly regardless of whether it helps and performs reasonably even with a tiny population size (25) which bodes well for real time or data intensive training