Avaliação de mecanismo probabilístico de cooling schedule para o algoritmo simulated annealing.

Abstract

Desde da sua concepção na década de 40, os algoritmos de Monte Carlo são utilizados para resolver diversos tipos de problemas, tais como problemas de amostragem e estimação, encontrando aplicações na Física, Biologia e Engenharia. Dentre suas muitas variações, algoritmos de Monte Carlo acoplados a cadeias de Markov (MCMC) estão entre os mais poderosos, tais como Metropolis-Hastings e simulated annealing. Com a crescente quantidade de dados e demanda por eficiência computacional, tais algoritmos vem são como base de técnicas emergentes em Ciências dos Dados e Inteligência Artificial. Algoritmo de Metropolis para Monte Carlo foi nomeado pela revista IEEE Computing in Science & Engineering como um dos 10 algoritmos que mais influenciaram o desenvolvimento e a prática da ciência e engenharia no século 20! O clássico algoritmo Simulated Annealing é uma vertente desse algoritmo com eficácia e vasta aplicabilidade em problemas de otimização de interesse prático. Este estudo busca apresentar estas constatações e avaliar a estrutura específica do algoritmo através de testes de adaptabilidade por meio do conhecido problema do caixeiro viajante.