Long path problems

Horn, Jeffrey ; Goldberg, David E. ; Deb, Kalyanmoy (1994) Long path problems Lecture Notes in Computer Science, 866/19 . pp. 149-158. ISSN 0302-9743

PDF - Author Version

Official URL: http://www.springerlink.com/content/7738173012k578...

Related URL: http://dx.doi.org/10.1007/3-540-58484-6_259


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.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:83524
Deposited On:21 Feb 2012 07:08
Last Modified:19 May 2016 00:20

Repository Staff Only: item control page