Simulated Annealing: paradigma Clássico da Mecânica Estatística Para Problemas de Otimização Combinatória

Abstract

In nature, and on practical daily basis situations, problems that requires the extremization of some quantity are considerably common, and forms the base of what applied science and technology are today. However, several optimization situations that arises frequently in engineering and operational research contexts are of great theoretical interest due to the high computational cost necessary to obtain their solutions. These kind of problems, intrisically discrete, are called non convex combinatorial optimization problems and do not admit, at the current state, algorithms with polinomial time complexity that assures global minimum solutions. Because that, the construction of practical approximative methods to handle these classes of problems is necessary. Thus, under the context of theoretical physics, the Simulated Annealing method represents one of the most traditional classical paradigms of how the statistical physics can provide concepts and efficient techniques for the solution and analysis of several optimization problems. Given this perspective, in this work we present an introduction to statistical mechanics and its natural connection with complex optimization problems, in a way to build consistent analogies between fundamental concepts and definitions of each field of study. By that, we choose for discuss in detail the classical method of Simulated Annealing with the goal of exemplify the theoretical physics paradigm, more specifically the statistical mechanics one, to provide theoretical models of extreme importance for the resolution and understanding of practical optimization situations. Furthermore, we build, from general and heuristic arguments, the classical method algorithm, so to accomplish the appropriate applications for two traditional examples of combinatorial optimization in graph theory: graph partitioning and the calculation of the chromatic number in graph coloring. Lastly, we present a point of view about the theoretical generalizations of the method, with the goal to point the limitations and perspectives for the improvements, in a fundamental level, of the efficiency of the method for continuous problems and, mainly, for intrisically discrete problems.