Long path problems have been introduced into GA literature as problems that are hard for hill-climbers but empirical results suggest they can easily be solved by GAs. However, no formal analysis has been carried out which would explain this apparent success. The paper shows that the Root2path problem resembles a Royal Road function which allows the GA to exploit short cuts in the crossover landscape. To fully understand the GA behaviour the original problem as introduced by Horn et.al. has been decomposed into its components: the Root2path and the slope function. Although both functions may be classified as GA-easy, they impose different requirements on the constitution of the population. These requirements are shown to be incompatible, so that the combination of Root2path and slope function results in a problem that is hard for a GA.
展开▼
