Modelo hiper-heurístico baseado em redes de autômatos estocásticos com aprendizado

Abstract

In the last decade, there has been a substantial increase in works about metaheuristics based on metaphors. Although these works have produced effective solutions within their proposals, the scientific community criticizes the validity of metaphorical bases, such as simple camouflage processes. In this sense, the research investigated the process of moving through the search space performed by heuristic mechanisms, free of abstractions employed in techniques. Or, in the conceptual terms proposed by the thesis, we developed a hyper-heuristic model based on stochastic learning automata networks, for choice and parametrization of low-level heuristics. To this end, the research started from an epistemic review finding model perspectives, with a catch on concepts and characteristics. After that, we evaluated eight metaheuristics in favor of the identification of heuristic mechanisms, that is, the processes leading to the search. This identification allied to the theory of stochastic learning automata networks guided the construction of their representations. These representations are consolidated in the figure of the meta-space, a part of the architecture of the Hyper-heuristic proposed in the work, named H2-SLAN model. Therefore, we present the process of experimentation and validation of the proposed model. The validation technique was based on solving instances of the traveling salesman problem, through the application of the canonical metaheuristic models. This process served to construct a comparative basis of results, considering the Computational Grain as a unit of measure of quantitative and qualitative performance. Having established the target patterns of execution, we apply the hyper-heuristic under the same context, aiming to obtain better performances. The results obtained by the H2-SLAN model were 3 % better than those obtained by the canonical algorithms and carried out on average 45% less objective function assessments. This experimentation showed that computational grain is an alternative for measuring the quality of the heuristic search. Thus, we can state that the results obtained by the model reached expectations, going to meet the goal of the research. As a result of this work, we obtained a system capable of selecting the parametrization of low-level heuristics, with the ability to learn the heuristics movements employed by the model.