TY - GEN
T1 - Generic hardness estimation using fitness and parameter landscapes applied to Robust Taboo Search and the quadratic assignment problem
AU - Pitzer, Erik
AU - Beham, Andreas
AU - Affenzeller, Michael
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - Fitness landscape analysis methods have become an increasingly popular topic for research. The future application of these methods to metaheuristics can yield advanced self-adaptive metaheuristics and knowledge bases that can take the role of expert systems in the field of optimization. One important feature of such an expert system would be the prediction of algorithm effort on a certain instance. Estimating whether a certain algorithm is able to tackle the problem adequately or not is a valuable piece of information that currently only an experienced human expert can give. The ability to generate such an advice automatically is, therefore, an important milestone. While fitness landscape analysis methods have been developed for exactly this purpose, it has been shown in the past that single-value analyses have limited applicability. Here, a general method for extracting fitness landscape features will be shown in combination with regression models that indicate a strong correlation between the actual and the predicted effort. Significant potential to increase the prediction quality arises when combining several measures each derived from several different sampling trajectories.
AB - Fitness landscape analysis methods have become an increasingly popular topic for research. The future application of these methods to metaheuristics can yield advanced self-adaptive metaheuristics and knowledge bases that can take the role of expert systems in the field of optimization. One important feature of such an expert system would be the prediction of algorithm effort on a certain instance. Estimating whether a certain algorithm is able to tackle the problem adequately or not is a valuable piece of information that currently only an experienced human expert can give. The ability to generate such an advice automatically is, therefore, an important milestone. While fitness landscape analysis methods have been developed for exactly this purpose, it has been shown in the past that single-value analyses have limited applicability. Here, a general method for extracting fitness landscape features will be shown in combination with regression models that indicate a strong correlation between the actual and the predicted effort. Significant potential to increase the prediction quality arises when combining several measures each derived from several different sampling trajectories.
KW - Fitness landscapes
KW - HeuristicLab
KW - Neutrality
KW - Parameter landscapes
KW - Quadratic assignment problem
KW - Robust Taboo Search
KW - Sampling trajectories
KW - Tabu search
UR - http://www.scopus.com/inward/record.url?scp=84865044387&partnerID=8YFLogxK
U2 - 10.1145/2330784.2330845
DO - 10.1145/2330784.2330845
M3 - Conference contribution
SN - 9781450311786
T3 - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation Companion
SP - 393
EP - 400
BT - GECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation Companion
PB - ACM Sigevo
T2 - 14th International Conference on Genetic and Evolutionary Computation, GECCO'12
Y2 - 7 July 2012 through 11 July 2012
ER -