Hyper-heuristic Model Based on Neural Networks for Solving the Metaheuristic Composition Optimisation Problem in Continuous Domains

Abstract

Metaheuristics (MHs) have been proven to be powerful algorithms for solving highly non-linear and intricate optimisation problems over discrete, continuous, or mixed domains, with applications ranging from basic sciences to applied technologies. Nowadays, the literature is prolific with MHs based on outstanding ideas, but the researchers often recombine elements from other methods. To avoid the frenetic tendency of proposing methods more focused on metaphors than operations, a standard model has been proposed to customise population-based MHs, which uses simple heuristics or search operators extracted from well-known metaheuristics. The framework corresponding to this model can be found as Customising Optimising Metaheuristic via Hyper-heuristic Search (CUSTOMHyS), which facilitates implementing models that explore a heuristic space. Still, they are limited by the nature of the metaheuristics used in such models, as such algorithms does not consider the information gained from previous explorations to enhance the tailoring process.

A field of action and improvement that has not been explored is the model implementation to take advantage of previous results and learns from them to boost the performance of the tailoring process. For that reason, we propose a hyper-heuristic model based on neural networks, which is trained with processed sequences of heuristics to identify patterns that one can use for generating modified metaheuristics. Being more specific, the task assigned to the neural network is to predict the simple heuristic from the collection or heuristic space to apply next, considering a sequence of heuristics already applied to the low-level problem. Using the neural networks, the challenge is to define how to generate metaheuristics with a high performance for tackling a family of optimisation problems. This research work propose a novel methodology that decomposes the metaheuristics into several subsequences of heuristics to train the neural network models.

To prove the feasibility of the proposed model and training methodology, it is compared against generic well-known basic metaheuristics and other heuristic-based approaches, such as the unfolded MHs. The results evidence that the proposed model outperform an average of 86% of all scenarios; in particular, 91% of basic and 81% of unfolded approaches. Plus, it is worth to highlight the configurable capability of the proposed model: several experiments are carried out to explore a few control variables and show their effects in the model. It proves to be exceptionally versatile regarding the computational budget. After exploring and finding a suitable configuration, we perform an extended analysis of the training computational cost, and a study of the metaheuristics generated by the model. Moreover, we analyse the usage of previously generated metaheuristics on an unseen problem via a few strategies. The proposed model and its metaheuristics show their adaptation capabilities to unseen problems, proving to be a good alternative for real-world application problems.