Órbita Perpétua e outras técnicas de otimização global robusta para os algoritmos Simulated Annealing Acoplado e Nelder-Mead

Abstract

Metaheuristics are algorithms whose strategy is to reduce the computational load to the detriment of the optimal quality of solutions. They are widely used to approximate solutions of computationally intractable optimization problems. Although typically simple to implement, some metaheuristics suffer because of lack of robustness for tuning some initialization parameters, which requires a very expensive tuning process due to its empirical nature. In this paper, we present some solutions to this problem by proposing three new metaheuristics based on free-parameter, less is more (LIMA) and parallel approaches, aiming to make some metaheuristics robust. As results, the algorithms Simplified Nelder-Mead algorithm (SNM), Syncrhonous (SCSA) and Asynchronous Coupled Simulated Annealing (ACSA), and Perpetual Orbit Coupled Simulated Annealing (PO-CSA) were proposed. The SNM is the result of the LIMA approach and the Nelder-Mead (NM) method. While its implementation has far fewer points than the original algorithm, its ability to perform several simple steps makes it able to find better results than the original NM even for non-convex functions. The SCSA and the ACSA are parallel implementations of Simulated Annealing Coupled (CSA) that allow the user to efficiently choose one or another version based on the size of the problem and the number of optimizer cores. The Perpetual Orbit (PO) technique was developed to control the generation temperature of the CSA to make it parameter free. The algorithm PO-CSA takes advantage of the PO technique combined to the CSA’s automatic quasi-optimal scheduling of the acceptance temperature to make optimization of the CSA more robust with respect to the initialization parameters. While the PO-CSA performed better than the reference algorithms for the majority of the objective functions, both in quality of solution and execution time, its control of the generation temperature also proved to be more effective than the original CSA with an exhaustively tuned initialization parameters.