Black-Box Search By Elimination Of Fitness Functions

In black-box optimization an algorithm must solve one of many possible functions, though the precise instance is unknown. In practice, it is reasonable to assume that an algorithm designer has some basic knowledge of the problem class in order to choose appropriate methods. In traditional approaches, one focuses on how to select samples and direct search to minimize the number of function evaluations to find an optima. As an alternative view, we consider search processes as determining which function in the problem class is the unknown target function by using samples to eliminate candidate functions from the set. We focus on the efficiency of this elimination process and construct an idealized method for optimal elimination of fitness functions. From this, we place our technique in context by relating performances of our idealized method to common search heuristics (e.g., (1+1) EA), and showing how our ideas relate to No Free Lunch theory. In our discussion, we address some of the practicalities of our method. Though in its early stages, we believe that there is utility in search methods based on ideas from our elimination of functions method, and that our viewpoint provides promise and new insight about black-box optimization. Copyright 2009 ACM