文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Simulated Annealing for Graph Bisection
侵权投诉

Simulated Annealing for Graph Bisection

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

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email