Improved Evolvability in Genetic Programming with Polyandry

Abstract

This paper proposes Polyandry, a new nature-inspired modification to canonical Genetic Programming (GP). Polyandry aims to improve evolvability in GP. Evolvability is a critically important GP trait, the maintenance of which determines the arrival of the GP at the global optimum solution. Specifically evolvability is defined as the ability of the genetic operators employed in GP to produce offspring that are fitter than their parents. When GP fails to exhibit evolvability, further adaptation of the GP individuals towards the global optimum solution becomes impossible. Polyandry improves evolvability by improving the typically disruptive standard GP crossover operator. The algorithm employs a dual strategy towards this goal. The chief part of this strategy is an incorporation of genetic material from multiple mating partners into broods of offspring. Given such a brood, the offspring in the brood then compete according to a culling function, which we make equivalent to the main GP fitness function. Polyandry’s incorporation of genetic material from multiple GP individuals into broods of offspring represents a more aggressive search for building block information. This characteristic of the algorithm leads to an advanced explorative capability in both GP structural space and fitness space. The second component of the Polyandry strategy is an attempt at multiple crossover points, in order to find crossover points that minimize building block disruption from parents to offspring. This strategy is employed by a similar algorithm, Brood Recombination. We conduct experiments to compare Polyandry with the canonical GP. Our experiments demonstrate that Polyandry consistently exhibits better evolvability than the canonical GP. As a consequence, Polyandry achieves higher success rates and finds solutions faster than the latter. The result of these observations is that given certain brood size settings, Polyandry requires less computational effort to arrive at global optimum solution than the canonical GP. We also conduct experiments to compare Polyandry with the analogous nature-inspired modification to canonical GP, Brood Recombination. The adoption of Brood Recombination in order to improve evolvability is ubiquitous in GP literature. Our results demonstrate that Polyandry consistently exhibits better evolvability than Brood Recombination, due to a more explorative nature of the algorithm in both structural and fitness space. As a result, although the two algorithms exhibit similar success rates, the former consistently discovers global optimum GP solutions significantly faster than the latter. The key advantage of Polyandry over Brood Recombination is therefore faster solution discovery. As a consequence Polyandry consistently requires less computational effort to arrive at the global optimum solution compared to Brood Recombination. Further, we establish that the computational effort exerted by Polyandry is competitively low, relative to other Evolutionary Algorithm (EA) methodologies in literature. We conclude that Polyandry is a better alternative to both the canonical GP as well as Brood Recombination with regards to the achievement and maintenance of evolvability.