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

Simulated Annealing for Graph Bisection

Simulated Annealing for Graph Bisection

a result of Bui 5] to the e ect that hillclimbing (randomized greedy, or the Metropolis algorithm at temperature 0) is ine ective for very sparse graphs, and cannot even discover 1 the obvious minimum bisection existing between a pair of 2 n-vertex random cubic graphs. Bui also conjectured that simulated annealing, and maybe even hillclimbing, would be e ective for dense random graphs, and this is now seen to be correct, at least for simulated annealing. The performance of hillclimbing on dense random graphs remains unanalyzed.

2 Annealing Model and Key Notation An annealing algorithm is begun in a random state. Moves are generated or proposed at random, and may be accepted (in which case the current state is updated) or rejected (in which case the state is left unchanged). A move which would increase the cost by a (positive or negative) quantity cost is accepted with probability A( cost). We consider the most obvious application of annealing to the graph bisection problem, in which a state is a bisection of G into sets L and R, the cost (or\energy") cost(L; R) of a state (L; R) is its cut-width, and a move is the exchange of a vertex in L with a vertex in R. We take as the acceptance function 1 exp(? cost=T ) A( cost)= 1+ exp(? cost=T )= 1+ exp( cost=T ); where T is the temperature parameter for the annealing. This acceptance function is common, albeit not as common as A( cost)= minf1; exp(? cost=T )g whose nonuniformity complicates the analysis. Both acceptance rules de ne an ergodic Markov chain on bisections, and both share the stationary distribution in which the probability of (L; R) is proportional to exp(? cost(L; R)=T ). (The stationary distribution gives the limiting probability of being at state (L; R) as time t ! 1.) So that the graph can be bisected exactly, it is natural to restrict the number of vertices to be even. In fact, we shall further restrict it to be a multiple of 4, so that henceforth we consider random graphs drawn from G4n;p;r . This restriction is immaterial to the results but conveniently makes the imbalance{ a key quantity in our analysis{ an integral value, The imbalance of any partitioning of G 2 G4n;p;r is the value k 0 for which there are n? k white vertices in one partition (which without loss of generality we call partition L) and n+ k in the other (partition R). (L and R are labeled arbitrarily for k= 0.) A given annealing move will either leave k unchanged, or will increase or decrease it by 1. 4

2.1 Annealing algorithm

2.2 Graph model and parameterization

上一页第4页

你可能喜欢

热门文档

相关文档

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