Simulated Annealing for Graph Bisection
over random sequences ( ), some correction tape makes^ ( )= ( ) for all 0 t. To see this, we will\reverse-engineer" the correction tape: the\bad" times i are those at which the blu er's choice for the state following^ ( i? 1)
| given^ ( i? 1)= ( i? 1)| fails to agree with the true Metropolis state ( i); the suggested moves m( i) are those required to take state^ ( i? 1) to state ( i). It should be clear that this construction makes the corrected blu er's sequence identical to the Metropolis trajectory. It remains to verify that the number of bad times is small, so that the correction tape is of acceptable brevity. A given time is bad only if falls intopone of the\excess" intervals, which occurs 1 with probability at most 2 kP?p k O( n=T ). Thus the number of bad times is P distributed binomially as B (t; O( n=T )).pOver the space of coin tosses, the probability p that the total number of bad moves is O(t n=T ) is 1? exp(? (t n=T )), which by choice of t is 1? exp(? ( 2T 2= log2 n)). We now close the argument. For any initial state and with overwhelming probability over graphs and random coin tosses, for some correction tape, the sequence (^( ))t=1 produced by a blu er (without access to G) is identical to the Metropolis trajectory ( ( ))t=1. Since there are only ptn=T )= exp(O(pn t log t=T )) O(t possibilities for the set of times at which the corrector can act, and p p (4n2)O(t n=T )= exp(O( n t log n=T )) p possibilities for how it can act at those times, there are only exp(O(t n log n=T )) possible correction tapes. (Note that, by assumption, T is polynomial in n, and hence log t= O(log n).) Given an initial state (0) and the sequence of coin tosses ( ), run the blu er in p turn with all possible correction tapes, producing a set of exp(O(t n log n=T )) states. Only now choose a random G 2 G4n;p;r. Applying Claimp the probability that any 3.6, state in the set is -atypical for G is at most t exp(O(t n log n=T )) 4 exp(?4 2 T 2), which is exp(? ( 2T 2)), by choice of t. Since, with overwhelming probability, the set includes the Metropolis trajectory ( ), it is overwhelmingly likely that no -atypical state is encountered by the Metropolis algorithm. Specializing the parameters T,, and t appearing in Claim 5.2 we obtain the following. Corollary 5.3 Let"> 0, T= n5=6+",= n?1=2, t= (n1+2"), and select G 2 G4n;p;r. With overwhelming probability, the Metropolis process run at temperature T for t steps starting at an arbitrary initial state encounters no -atypical state. b !
6 Progress of Annealing: Detailed Analysis We now re ne the argument sketched in Section 4 to demonstrate that the Metropolis process on bisections, when run at an appropriate temperature, converges rapidly to the optimal bisection with overwhelming probability. 12
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...
热门文档