1 Population Measures: Entropy and Edit Distance Diversity

To better understand the distribution of fitness values that a selection method is presented with, and the ability of the population to represent solutions for each problem instance, we use the measure of entropy based on fitness, described in detail in Chapter 4. Again, the entropy measure represents the chaos of the system with respect to the distribution of fitness values amongst the population [Rosca, 1995a]. An increase in entropy reflects the system (population's fitness values) moving into a state of more chaos (more different fitness values). This measure also gives us a sense of how the fitness values are distributed over the fitness classes, from a uniform distribution over all fitness classes to the other extreme of the entire population belonging to only one fitness class.

Measuring the genetic diversity of populations is difficult, as there are many aspects of tree shapes and contents that could be measured. In this study, a measure is used based on the edit distance between two trees, introduced and used in Chapter 4 as edit distance One, and in Chapter 5 as the non-weighted edit distance. This measure is used to understand how structurally similar populations become and to give insight into the search process.

Figure 6.1: The Binomial-3 problem and the generated polynomial functions of degree 3 (upper right), 7 (bottom left) and 11 (bottom right). The inset for degree 7 and 11 shows the same x-range and smaller y-range between [-0.005:0.005], where it is relatively easy for genetic programming to find a close fit, but difficult to fine-tune the approximation.