Adaptive Search Algorithms and Fitness-Distance Correlation
J. Christopher Beck, Jean‐Paul Watson · 2003
Several constructive heuristic search algorithms dynamically adapt their search strategy during execution by learning the relative importance or weight of solution components. We hypothesize that the performance of such techniques depends on the strength of the tness-distanc e correlation (FDC) in the space of solutions. FDC is the correlation between the quality of a solution and its distance to an optimal solution. In problems with strong FDC, components in good solutions are likely to occur in optimal solutions. Thus, the learned weights will tend to bias the search toward optimal solutions. In problems with no FDC, the learned weights are essentially random, as there is no correlation between the presence of a particular solution component and its occurrence in an optimal solution. In a problem with negative FDC, good solutions share little with optimal solutions, causing adaptive search algorithms to learn weights that bias search away from optimal solutions. In this paper, we test our hypothesis in two problem domains: an idealized problem domain that allows complete control over the tness-distance correlation and the job shop scheduling problem. Researchers have hypothesized that Fitness-Distance Correlation (FDC)[BKM94] is correlated with problem dicult y for local search algorithms. To compute the FDC for a problem instance, a simple local search algorithm (e.g., steepest-descent) is used to generate N random local optima. The quality of a local optima i is denoted by F (i) and the distance between i and the nearest globally optimal solution is denoted by disti. FDC for the instance is then dened as the Pearson’s correlation between disti and F (i) in the N samples. We consider the impact of FDC on the performance of two constructive, adaptive search algorithms: Ant Colony Optimization (ACO) and Adaptive Probing (AP). Consider a problem whose solution requires a value be assigned to each of N attributes ai. Both ACO and AP