Deterministic Annealing: Fast Physical Heuristics for Real-Time Optimization of Large Systems

Abstract

This paper systematically investigates the heuristical optimization technique known as deterministic annealing. This method is applicable to a large class of assignment and partitioning problems. Moreover, the established theoretical results, as well as the general algorithmic solution scheme, are largely independent of the objective functions under consideration. Deterministic annealing is derived from strict minimization principles, including a rigorous convergence analysis. We stress the close relation to homotopy methods, and discuss some of the most important strengths and weaknesses in this framework. Optimization results for unsupervised texture segmentation are presented for an autonomous robotics application. INTRODUCTION Physically inspired heuristics like Simulated Annealing (SA) are generally applicable stochastic optimization methods, which have been successfully applied to a broad range of combinatorial problems. Their basic strength is their flexibility and the ease of...