The Optimization Ability of Evolved Strategies



Hyper-Heuristics (HH) is a field of research that aims to au- tomatically discover effective and robust algorithmic strategies by com- bining low-level components of existing methods and by defining the appropriate settings. Standard HH frameworks usually comprise two se- quential stages: Learning is where promising strategies are discovered; and Validation is the subsequent phase that consists in the application of the best learned strategies to unseen optimization scenarios, thus as- sessing its generalization ability. Evolutionary Algorithms are commonly employed by the HH learning step to evolve a set of candidate strategies. In this stage, the algorithm relies on simple fitness criteria to estimate the optimization ability of the evolved strategies. However, the adoption of such basic conditions might compromise the accuracy of the evaluation and it raises the question whether the HH framework is able to accurately identify the most promising strategies learned by the evolutionary algorithm. We present a detailed study to gain insight into the correla- tion between the optimization behavior exhibited in the learning phase and the corresponding performance in the validation step. In concrete, we investigate if the most promising strategies identified during learn- ing keep the good performance when generalizing to unseen optimization scenarios. The analysis of the results reveals that simple fitness criteria are accurate predictors of the optimization ability of evolved strategies


17th Portuguese Conference on Artificial Intelligence (EPIA 2015), September 2015

PDF File

Cited by

Year 2017 : 1 citations

 Soria-Alcaraz, J. A., Espinal, A., and Sotelo-Figueroa, M. A. (2017). Evolvability metric estimation by a parallel perceptron for on-line selection hyper-heuristics. IEEE Access, 5, 7055-7063.

Year 2016 : 3 citations

 Mariani, Thainá, Giovani Guizzo, Silvia R. Vergilio, and Aurora TR Pozo. "A grammatical evolution hyper-heuristic for the integration and test order problem." In GECCO. ACM, 2016.

 Mariani, Thainá, Giovani Guizzo, Silvia R. Vergilio, and Aurora TR Pozo. "Grammatical Evolution for the Multi-Objective Integration and Test Order Problem." In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, pp. 1069-1076. ACM, 2016.

 Mariani, Thainá, Giovani Guizzo, Silvia R. Vergilio, and Aurora TR Pozo. "Automatic Design of Algorithms Applied to the Multi-Objective TSP Problem."