On a similar note, recently a lot of research has looked at the extent to which utility functions fail to explore a space, and how the introduction of novelty is a crucial new strategy:
"Novelty search is a recent algorithm geared toward exploring search spaces without regard to objectives. When the presence of constraints divides a search space into feasible space and infeasible space, interesting implications arise regarding how novelty search explores such spaces. "