Simulated Annealing for Graph Bisection
namely that equilibrium typically takes much longer to attain at low temperatures than at high ones. In simulated annealing proper, the temperature parameter is varied with time in an attempt to exploit this tension. The temperature starts high and is gradually reduced with time according to a speci ed\cooling schedule", in the belief that di erent\features" of the solution will\crystallize out" at di erent temperatures. Unfortunately, no combinatorial optimization problem that has been subjected to rigorous theoretical analysis has exhibited this phenomenon: those problems that can be solved e ciently by simulated annealing, can be solved ju
st as e ectively by\annealing" at a single carefully selected temperature. (Sorkin has exhibited fractal-like\energy landscapes" that require a non-trivial cooling schedule for fast convergence to a low energy state 20], but these landscapes do not correspond to a\naturally de ned" optimization problem.) A rigorous demonstration that annealing is provably bene cial for some natural optimization problem would, in the authors' view, rate as a signi cant theoretical advance. Simulated annealing at constant temperature is called the Metropolis algorithm, and the stochastic process (actually a Markov chain) on which it is based the Metropolis process. The theoretical results so far obtained relate to the Metropolis algorithm rather than simulated annealing as such. The results are few in number and can be brie y summarized. The most extensively studied problem is that of nding a maximum matching in a graph. Jerrum and Sinclair 14, 13] (see also Frieze 9] and Motwani 17]) showed that the Metropolis algorithm performs well on random graphs, even though| as Sasaki and Hajek 19] had previously demonstrated| pathological instances exist on which the algorithm fails badly. Jerrum considered the problem of nding a maximum clique in a random graph 12], and showed (in rough terms) that the Metropolis algorithm is no more e ective than hillclimbing (i.e., simulated annealing at temperature 0). Aside from these results, Sasaki 18] has used a\density of states" argument to construct instances of various optimization problems that cause the Metropolis algorithm to run for exponential time. By analyzing the performance of the Metropolis algorithm| and more generally simulated annealing| in the context of various simple, paradigmatic optimization problems, we may hope to learn to recognize when these approaches are likely to be e ective, and to understand why they work when they do. In this paper we extend the study of the Metropolis algorithm to the problem of graph bisection, i.e., nding a partition of the vertex set of an undirected graph into two equal-sized sets so that the number of crossing edges is minimized. The problem is known to be NP-complete 11, 10], so we cannot expect good performance in the worst case. Instead, we study the e ectiveness of the Metropolis algorithm on\random" instances of the problem, and show that its performance is surprisingly good. Thus, this paper and 12] can be viewed as complementary. We remark in passing that the bisection problem in various random graph models has received considerable attention 5, 4, 6, 3]. To describe our positive result, we require some notation. For n even, a random graph G= (V; E ) 2 Gnpr is one with n=2 white and n=2 black vertices, with edge probability p between pairs of vertices of the same color and edge probability r between pairs of opposite 2
Simulated Annealing_工学_高等教育_教育专区。Simulated AnnealingSimulated Annealing (模拟退火法)报告人:陈世明 Simulated Annealing 1 大纲 简介 攀登演算法 模拟...
Novel Adaptive Simulated Annealing Algorithm for Constrained Multi-Objective Optimization_专业资料。/专h rii j ioncnf CamuasnntCoNovel AdapiSiuledAnnealgtve mat ...
4.Simulated Annealing_计算机软件及应用_IT/计算机_专业资料。模拟退火算法Practical Optimization Algorithm Design Lesson 4: Simulated Annealing Thomas Weise Nature...
Parallel Genetic Simulated Annealing Hybrid Algorithm for Task Scheduling 隐藏>> 维普资讯 http://www.cqvip.com VoI1 No. 20 17—32. 15063818 Naur ...
A hybrid genetic-simulated annealing algorithm for optimization of hydraulic manifold blocks_专业资料。维普资讯 http://www.cqvip.com A Jhnh nEgE)20,23:6...
Genetic simulated annealing algorithm for task scheduling based on cloud computing environment_天文/地理_自然科学_专业资料。Genetic Simulated Annealing Algorithm...
Optimization by simulated annealing: A necessary and su cient condition for convergence. In Van Ryzin, J., editor, Adaptive Statistical Procedures and ...
To address the problem of the self-optimization of coverage and capacity in LTE networks, we introduce an approach based on a simulated annealing algorithm...
Leighton, \Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms," in Proc. ACM/IEEE Design Automation Conf., ...
4] T. N. Bui, \Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms", in Proc. ACM/IEEE Design Automation...
热门文档