Simulated Annealing for Graph Bisection
4 Progress of Annealing: Sketch In this section we begin by proving that for any"> 0, p? r= n?1=6+2", T= n1=2+",= n?1=6, and any t= O(n2=3+" ), in the course of t moves it is almost certain that a -atypical state is never encountered. Presuming that this is so, the probabilities for k increasing (or decreasing or remaining the same) are closely bounded by Corollary 3.3. We go on to present an intuitive justi cation that with these parameter values, and p assuming an initial imbalance of k= ( n ), the pessimistic values for these bounds on the transition probabilities su ce to drive k from (n1=2) to (n2=3) within t moves. For now we simply note that this is a comparatively huge imbalance, and do not consider completion to k= n. In later sections we will tighten up what is essentially the same reasoning. First, if p we do not presume that k= ( n ) initially, getting to such a k calls for both a greater number of moves and a larger T (and consequently a smaller ), requiring a more sophisticated argument to show that no atypical state is likely to be encountered (Claim 5.2). Then, it is proved
that the pessimistic values for the probabilities of k increasing, decreasing, or unchanging, when interpreted as the transition probabilities for a Markov chain (which k is not), do indeed yield pessimistic bounds for k (Theorem 6.2). Finally, from the point k= (n) at which these arguments leave o, di erent arguments show that after about n2 additional moves, with high probability k is exactly n (Subsection 6.3). a random G 2 G4n;p;r and any initial partition (0): with overwhelming probability, the Metropolis process run at temperature T for t moves encounters no -atypical partition of G.
Claim 4.1 Let= n?1=6 and T= n1=2+", and let t be any time bound t= O(n2=3+" ). For Proof In addition to (0), let the sequence of t= O(n2=3+") proposed moves be given.
For any such sequence, over all possible choices of accepting or rejecting each move, there are 2 states possible at time, for a set of 2t+1? 1 states possible over all t moves. By Claim 3.6, for a random graph G the expected number of -atypical states in this set is at most 2t+1 4 exp(?4 2 T 2), which for the given parameter values is exp(O(n2=3+")? 4n2=3+2")= exp(? (n2=3+2")). It follows that it is exponentially unlikely that any -atypical state exists among these t+1? 1 states, and in particular that there is unlikely to be one among the t+ 1 states 2 in the actual\trajectory" where the Metropolis rule determines the acceptances and rejections. Presuming now that no -atypical states are encountered, by Corollary 3.3 and the de nition of -atypicality, at every step, 1 f+ 8+ (minfk (p? r)=T; 1g)? O(k=n)? 1= 8+ (minfkn?2=3+"; 1g)? O(k=n)? O(n?1=6) 1 which for (n1=2) k O(n2=3) is f+= 8+ (minfkn?2=3+"; 1g): Symmetrically, f?=?2=3+"; 1g): 1 8? (minfkn
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...
热门文档