Simulated Annealing for Graph Bisection
expectation is over random graphs G 2 G4n;p;r . Proof The distribution of X+ can be expressed as the sum and di erence of 8n? 4 Bernoulli random variables, corresponding to the 8n? 4 potential edges a ected by the speci ed move: X+= 2(n? k? 1) Bp+ 2(n+ k) Br? 2(n+ k) Bp? 2(n? k? 1) Br (2) where the equality sign is to be interpreted as\has the same
distribution as", and the notation t Bp stands for the sum of t Bernoulli r.v.s each with expectation p. Introduce a new r.v. X 0 with distribution X 0= 2n Bp+ 2(n? 1) Br? 2n Bp? 2(n? 1) Br: Observe that the distribution of X 0 is symmetric about the origin, while the function 1 A(x)? 2 is antisymmetric, and hence EA(X 0)= 1 . Our strategy is to estimate EA(X+) 2 by comparing the distributions of X+ and X 0, which are obviously close for small k. We construct a model for X+ and X 0, on a common sample space, that gives the correct distribution for each r.v., even though X+ and X 0 will (intentionally) be highly n? n? correlated. Express X+ as the sum X+= Pi4=1 2 Xi+? Pi8=4n4?1 Xi+ of independent 0,1 r.v.s fXi+ g, where the expectation of individual variables is suggested by expression (2). (Thus the rst 2(n?k?1) have expectation p, the next 2(n+k) have expectation r, and so n? n? on.) Let X 0= Pi4=1 2 Xi0? Pi8=4n4?1 Xi0 be a similar expression for X 0. For pairs (Xi+; Xi0) containing variables of the same type (i.e., both having expectation p, or both r), arrange for the variables to be perfectly correlated, i.e., Xi+= Xi0. For the remaining 4(k+ 1) pairs (e.g., where Xi+ has expectation p and Xi0 has expectation r) arrange for the pvariable to dominate the r-variable (e.g., Xi+ Xi0); this can be achieved by setting Pr(Xi+= Xi0= 0)= 1? p, Pr(Xi+= 1^ Xi0= 0)= p? r, and Pr(Xi+= Xi0= 1)= r. This construction yields the following sharply concentrated distribution for the di erence of X 0 and X+: X 0? X+= (4k+ 2) Bp?r 0: 1 It follows by symmetry that Pr (X 0? X+ 2k(p? r)) 2 . p From usual estimates for the binomial distribution, Pr(jX 0j 4 n ) 3, and hence, 4 p 1 with probability at least 4 the events X 0? X+ 2k(p? r) and jX 0j 4 n occur simultaneously. (This is so, irrespective of any probabilistic dependency between the pn, there is a probability of at least 1 that jX 0=T j 4 and events.) Thus, since T 4 X 0=T? X+=T 2k(p? r)=T hold simultaneously. Note that the conjunction of these two events implies A(X+ )? A(X 0)= (minfk(p? r)=T; 1g), since in any bounded range, the\sigmoid" (1+ex)?1 has negative gradient uniformly bounded away from 0. It follows that 1 EA(X+)? 2= EA(X+ )? EA(X 0)= E(A(X+ )? A(X 0)) (minfk(p? r)=T; 1g) (3)
Claim 3.2 Suppose T pn. Then EG A(X+)
1+ 2
(minfk(p? r)=T; 1g), where the
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...
热门文档