Long path problems

Abstract

We demonstrate the interesting, counter-intuitive result that simple paths to the global optimum can be so long that climbing the path is intractable. This means that a unimodal search space, which consists of a single hill and in which each point in the space is on a simple path to the global optimum, can be difficult for a hillclimber to optimize. Various types of hillclimbing algorithms will make constant progress toward the global optimum on such long path problems. They will continuously improve their best found solutions, and be guaranteed to reach the global optimum. Yet we cannot wait for them to arrive. Early experimental results indicate that a genetic algorithm (GA) with crossover alone outperforms hillclimbers on one such long path problem. This suggests that GAs can climb hills faster than hillclimbers by exploiting building blocks when they are present. Although these problems are artificial, they introduce a new dimension of problem difficulty for evolutionary computation. Path length can be added to the ranks of multimodality, deception/misleadingness, noise, variance, etc., as a measure of fitness landscapes and their amenability to evolutionary optimization.