Efficient simulated annealing on fractal energy landscapes (Q805499): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3947020 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Geometric bounds for eigenvalues of Markov chains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images / rank
 
Normal rank
Property / cites work
 
Property / cites work: Cooling Schedules for Optimal Annealing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3795602 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimization by Simulated Annealing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convergence of an annealing algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Convergence and finite-time behavior of simulated annealing / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximate counting, uniform generation and rapidly mixing Markov chains / rank
 
Normal rank
Property / cites work
 
Property / cites work: Configuration Space Analysis for Optimization Problems / rank
 
Normal rank

Revision as of 16:32, 21 June 2024

scientific article
Language Label Description Also known as
English
Efficient simulated annealing on fractal energy landscapes
scientific article

    Statements

    Efficient simulated annealing on fractal energy landscapes (English)
    0 references
    0 references
    0 references
    1991
    0 references
    A new theoretical framework for analyzing simulated annealing is presented. The behavior of simulated annealing depends crucially on the ``energy landscape'' associated with the optimization problem: the landscape must have special properties if annealing is to be efficient. For a class of deterministic fractal landscapes, and for ``linearly separable'' functions, annealing is proved to be efficient, running in time polynomial or quasi-polynomial in the solution quality. The cooling schedule employed is the familiar geometric schedule of annealing practice, rather than the logarithmic schedule of previous theory. While random sampling and descent algorithms may be more efficient than annealing in some cases, their run times increase exponentially with the number of dimensions, while annealing's increases only linearly. A number of circuit placement problems are found to have energy landscapes with weaker, random fractal properties, giving for the first time a reasonable explanation of the successful application of simulated annealing to problems in the VLSI domain. The analysis models annealing as a random walk on a graph, and uses recent theorems relating the ``conductance'' of a graph to the mixing rate of its associated Markov chain. This enables both a new conceptual approach and new quantitative methods. Another foundation of the analysis is a proof that the expected energy cannot increase during annealing with decreasing temperatures; a surprising ``probability pump'' counterexample exists if the hypotheses are weakened slightly. This article is extracted from the author's doctoral thesis. Additional material there includes the construction of a more efficient ``hypergeometric'' cooling schedule for annealing on the deterministic fractals, and numerical experiments on a ``real-world'' circuit partitioning problem instance. The experiments confirm the predicted dependence of solution quality on the initial temperature and run time. Contradicting the theoretical predictions, however, the effect of the temperature reduction factor is found to be almost nonexistent.
    0 references
    rapidly-mixing Markov chains
    0 references
    simulated annealing
    0 references
    fractal landscapes
    0 references
    random walk on a graph
    0 references

    Identifiers