Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/44013
Tipo: TCC
Título: Simulated Annealing: paradigma Clássico da Mecânica Estatística Para Problemas de Otimização Combinatória
Autor(es): Monteiro, Higor da Silva
Orientador: Reis, Saulo Davi Soares e
Palavras-chave: Otimização combinatória;Mecânica estatística;Simulated annealing (Mathematics)
Data do documento: 2019
Citação: MONTEIRO, H. da S. Simulated annealing: paradigma clássico da mecânica estatística para problemas de otimização combinatória. 2019. 94 f. Monografia (Bacharelado em Física) - Universidade Federal do Ceará, Fortaleza, 2019.
Resumo: Na natureza, e em situações práticas cotidianas, problemas que requerem a extremização de alguma quantidade são consideravelmente comuns, e formam a base do que hoje é a tecnologia e ciência aplicada. Contudo, diversas situações de otimização que surgem com frequência em contextos de engenharia e pesquisa operacional são de grande interesse teórico devido ao elevado custo computacional necessário para a obtenção de suas soluções. Esses tipos de problemas, intrisicamente discretos, são denominados de problemas de otimização combinatória não convexa e não admitem, até então, algoritmos de complexidade de tempo polinomial que assegurem a obtenção de soluções ótimas globais. Por conta disso, a construção de métodos aproximativos práticos para o tratamento dessas classes de problemas é necessária. Assim, sob o contexto da física teórica, o método de Simulated Annealing representa um dos paradigmas clássicos mais tradicionais de como a física estatística pode fornecer conceitos e técnicas eficientes para a solução e análise dos mais diversos problemas de otimização. Diante tal perspectiva, neste trabalho apresentamos uma introdução à mecânica estatística e sua conexão natural com problemas complexos de otimização, de modo a construir analogias consistentes entre conceitos e definições fundamentais de cada grande área de estudo. A partir disso, escolhemos por discutirmos detalhadamente o método clássico de Simulated Annealing com o objetivo de exemplificarmos o paradigma da física teórica, mais especificamente da mecânica estatística, para fornecer modelos teóricos de extrema importância para a resolução e entendimento de situações práticas de otimização. Ainda mais, construimos, a partir tanto de argumentos gerais como heurísticos, o algoritmo clássico do método, de modo a realizarmos as devidas aplicações para dois exemplos tradicionais de otimização combinatória em teoria de grafos: o particionamento de grafos e o problema de número cromático em coloração de grafos. Por fim, apresentamos uma visão acerca das generalizações teóricas do método, a fim de apontar limitações e perspectivas para o aperfeiçoamento, em nível fundamental, da eficiência do método tanto para problemas contínuos quanto principalmente para problemas intrisicamente discretos.
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.
URI: http://www.repositorio.ufc.br/handle/riufc/44013
Aparece nas coleções:FÍSICA-BACHARELADO - Monografias

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2019_tcc_hsmonteiro.pdf6,8 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.