Heurística para sintonização de metaheurísticas aplicada ao Problema de FlowShop Permutacional.

Abstract

Many combinatorial optimization problems are considered NP-Hard and therefore require a high computational cost to be solved by exact algorithms. A promising alternative is the use of metaheuristics, generic algorithmic models capable of finding great solutions to complex optimization problems in a reasonable time. However, for metaheuristics to obtain quality solutions, parameters of various types must be calibrated. The problem of finding the best setting for these parameters is called Tuning. Usually, the process of finding optimal settings in a parameter search space has difficulty equal to or greater than the search for optimal solutions in the solution space of the problem, such an obstacle makes the study of tuning unattractive to researchers, who prefer cheaper approaches based in trial and error or expert experience. As there is no standard in the tuning, researchers use to set parameters by following their own approaches that influence in different ways the effectiveness of their algorithms, making it difficult to compare and improve them due to aspects that are not very measurable. This work presents a cross-validated Racing (CVR) heuristic tuning method that adds crossvalidation to the tuning process by racing to achieve a generalization perspective by Machine Learning, thus obtaining quality solutions for unknown instances . For CVR validation, a hybrid biased random-key genetic algorithm (BRKeCS) was designed and applied to solve Permutational FlowShop Problems with random and realistic instances. The computational results demonstrated that the CVR is robust to find an effective parameter configuration with an average residual error of less than 2:3% when compared to other metaheuristics specially developed for the problem since it requires training process in only half of the set total number of instances. We also verified the stability of the quality of CVR solutions when the search space topology is modified by changing from random to realistic instances.