Review - Optimization by Simmulated Annealing.

Yannis E. Ioannidis: Review - Optimization by Simmulated Annealing. ACM SIGMOD Digital Review 1: (1999) BibTeX

Review

This is probably the paper that opened the gates for several generic computer optimization techniques that were inspired by optimization processes found in nature. This one introduced Simulated Annealing, which is a probabilistic hill-climbing algorithm simulating the crystalization of material when they are first heated to high temperature and then cooled down slowly. Other such examples are Genetic Algorithms, which is a family of algorithms simulating the survival of the most fit members of a population as the strongest genes are passed from generation to generation, Tabu Search, etc. The paper gives the details of the Simulated Annealing algorithm and its application to some VLSI problems, but leaves many issues of correctness, convergence, and performance open, which have been later addressed by other authors elsewhere. More importantly, however, it offers a very clear abstraction of so many optimization problems: the space of alternative solutions are the nodes of the graph, labeled by the corresponding "cost" or "benefit" of the solution ("cost" for minimization problem, "benefit" for maximization problems); similar solutions that can be transformed into each other based on certain rules have their corresponding nodes connected through edges of the graph; optimization is transformed into a search for the node with the global minimum or maximum. Thus, Simulated Annealing becomes just one of the algorithms that can be applied to search the graph. Moreover, the whole approach is generic and can be applied to so many different problems, as has been the case with several ones that are close to the heart of the database community, i.e., all sorts of query optimization (regular single relational query optimization, multiple query optimization, parametric query optimization, etc.), physical database design (data placement) in distributed systems, and others. But the paper's greatest contribution in my mind is showing the potential and beauty of "technology transfer" in its most imaginative form, from nature itself, and demonstrating these with such an intricate and effective example as Simulated Annealing.

References

[1]: Scott Kirkpatrick, D. Gelatt Jr., Mario P. Vecchi: Optimization by Simmulated Annealing. Science 220(4598): 671-680(1983) BibTeX

BibTeX

Digital Review - DBLP: [Home | Search: Author, Title | Conferences | Journals]