Evolving dynamic fitness measures for genetic programming.

Abstract

This research proposes dynamic fitness measure genetic programming (DFMGP). DFMGP modifies the conventional genetic programming (GP) approach: rather than applying a single fitness measure individually throughout GP, a different fitness measure (or combination of fitness measures) is applied on each GP generation. A detailed review of the fitness measures used in GP is presented. The review demonstrates that different fitness measures were introduced to overcome different shortcomings, e.g. escaping local optima, reducing bloat, thereby improving on the performance of the GP algorithm. A subsequent analysis of the fitness measures shows that there is no universal “best” fitness measure; rather, different fitness measures are appropriate for different problems. The literature also anticipates that applying different fitness measures at different points of the GP problem solving process should be more effective then applying a single fitness measure throughout the algorithm. Hence the case for DFMGP. Selecting the fitness measures to apply on each GP generation is in itself a combinatorial optimization problem: the study investigates two approaches to serve this purpose, namely, a genetic algorithm and genetic programming. The genetic algorithm (GA) derives a sequence of fitness measures to be applied, while GP produces an arithmetic function combining the fitness measures. The performance of DFMGP applying the evolved fitness measure sequences and DFMGP applying the evolved fitness measure combinations is compared to the conventional GP approach on a number of benchmark and complex, real-world problems. DFMGP is found to be more effective than standard GP. The study also reveals that both the sequences and arithmetic combinations of the fitness measures are effective when applied to problem instances different from those used to derive them. Hence, the sequences and arithmetic combinations are reusable, whereby simpler problems are used for derivation, and DFMGP applying the derived fitness measures is then used to solve more complex problems. Therefore the time necessary for the derivations is reduced. An analysis of the evolved sequences and arithmetic combinations of the fitness measures shows that fitness measures applied in the preliminary DFMGP generations support exploration while those applied in later DFMGP generations support exploitation. GP search is a constant balance between exploration and exploitation, with the former being more suited to the preliminary generations, and the latter, later generations. DFMGP’s performance advantage over standard GP is therefore justified by the premise that the fitness measure used on each generation supports the more suitable search in the on-going phase of GP. DFMGP applying the fitness measure combinations derived by GP is also found to perform better than DFMGP applying the fitness measure sequences derived by the GA. The former approach facilitates combining explorative and exploitative fitness measures on some of the DFMGP generations, whereby rather than simply switching between exploration and exploitation, the fitness measure can drive the two processes to occur simultaneously when required. Hence it follows that GP searching the space of fitness measure combinations is the preferred approach to generating dynamic fitness measures for DFMGP. Overall, the study reveals the effectiveness of DFMGP when applied to benchmark and real-world problems. Future work will look at a priori detecting the properties of complex problems, such that simpler problems with similar properties can be used to derive better dynamic fitness measures for DFMGP.