A têmpera controlada pela entropia : uma caracterização formal

Abstract

Nesta dissertação é proposto um modelo para a Têmpera Simulada, como abordagem metaheurística para a resolução de problemas de Optimização Combinatória. O modelo é construído tendo por base o conceito de Entropia entendido no contexto da Teoria da Informação. Para este modelo é feita uma caracterização formal e são estabelecidas propriedades a partir das quais se demonstram diversos resultados. A partir deste modelo são deduzidos algoritmos adaptáveis e gerados automaticamente em tempo real. São apresentados testes computacionais da aplicação de um algoritmo assim construído ao Problema do Caixeiro Viajante.

In this dissertation a new model for Simulated Annealing is presented, as a meta-heuristic approach to Combinatorial Optimisation problems. The model is built upon the concept of Entropy, in the sense of Information Theory. A formal characterisation is established and several results, such as the asymptotic convergence of the method, are proved. A class of algorithms is them derived from the model, which are adaptable and automatically generated in running time. Computational results of the application of a simple algorithm of that class, where applied to the Travelling Salesman Problem, are also reported.