From simulated annealing to stochastic continuation: a new trend in combinatorial optimization

Marc Robini () and Pierre-Jean Reissman ()

Journal of Global Optimization, 2013, vol. 56, issue 1, 185-215

Abstract: Simulated annealing (SA) is a generic optimization method that is quite popular because of its ease of implementation and its global convergence properties. However, SA is widely reported to converge very slowly, and it is common practice to allow extra freedom in its design at the expense of losing global convergence guarantees. A natural way to increase the flexibility of SA is to allow the objective function and the communication mechanism to be temperature-dependent, the idea being to gradually reveal the complexity of the optimization problem and to increase the mixing rate at low temperatures. We call this general class of annealing processes stochastic continuation (SC). In the first part of this paper, we introduce SC starting from SA, and we derive simple sufficient conditions for the global convergence of SC. Our main result is interesting in two respects: first, the conditions for global convergence are surprisingly weak—in particular, they do not involve the variations of the objective function with temperature—and second, exponential cooling makes it possible to be arbitrarily close to the best possible convergence speed exponent of SA. The second part is devoted to the application of SC to the problem of producing aesthetically pleasing drawings of undirected graphs. We consider the objective function defined by Kamada and Kawai (Inf Process Lett 31(1):7–15, 1989 ), which measures the quality of a drawing as a weighted sum of squared differences between Euclidean and graph-theoretic inter-vertex distances. Our experiments show that SC outperforms SA with optimal communication setting both in terms of minimizing the objective function and in terms of standard aesthetic criteria. Copyright Springer Science+Business Media, LLC. 2013

Keywords: Combinatorial optimization; Simulated annealing; Stochastic continuation; Markov chains; Monte-Carlo methods; Graph drawing (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10898-012-9860-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:56:y:2013:i:1:p:185-215

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-012-9860-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().