Ergodic Annealing: Intelligent Optimization Under Uncertainty

NP-hard decision problems in which the cost function is a priori unknown to the Decision Maker arise naturally in many applications. We present a novel algorithm, inspired by Simulated Annealing, that exploits the structural randomness of Metropolis exploration in order to simultaneously find the optimal solution and learn its cost. As benchmark cases, we test our algorithm on the Directed Steiner Tree and Traveling Salesman problems. Our results suggest that problems for which Simulated Annealing works with known costs can be efficiently attacked with our algorithm when costs are unknown.