Diversity Maintenance in Genetic Programming

This paper is motivated by an experimental result that better performing genetic programming runs tend to have higher phenotypic diversity. To maintain phenotypic diversity, we apply implicit fitness sharing and its variant, called unfitness multiplying. To apply these methods to problems in which individuals have infinite kinds of possible behaviours, we classify posible behaviours into 50 achievement levels, and assign a reward or a penalty to each level. In implicit fitness sharing a reward is shared out among individuals with the same achievement level, and in unfitness multiplying a penalty is multiplied by the number of individuals with the same level and is distributed to related individuals. Five benchmark problems (11-multiplexer, sextic polynomial, four-sine, intertwined spiral, and artificial ant problems) are used to illustrate the effect of the methods. The results show that our methods clearly promote diversity and lead population to a smooth frequency distribution of achievement levels, and that our methods usually perform better than the original implicit fitness sharing on success rate and the best (raw) fitness. We also observe that the unfitness multiplying makes a quite different ranking over individuals than the one by the implicit fitness sharing