2 Problem Difficulty

Another issue in genetic programming is how to identify important properties of problems or problem instances. Specifically, what makes a problem difficult with respect to genetic programming? Daida et al. (2001) investigated a tunable problem, the binomial-3 function with varying ephemeral random constant ranges, to show that difficulty can be increased without changing the combinatorial search space. In this case, genetic programming difficulty increases with the increased range of ERC values. The authors suggested that the conflict between content and context is largely responsible for increased difficulty. O'Reilly and Goldberg [O'Reilly, 1998,Goldberg and O'Reilly, 1998] used constructed problems to highlight the content and context dependencies in genetic programming solutions. The authors investigated how partial solutions contribute toward fitness and how they make solving the problem more difficult [O'Reilly and Goldberg, 1998]. Recent research has also investigated possible structural mechanisms that make search more difficult [Daida, 2002,Daida et al., 2003b]. Population diversity, among other things, could be a way to reduce problem difficulty by filtering misleading or deceptive solutions from the population and search.