Simulated Annealing for Graph Bisection
Lemma 6.3 Let p? r and T be as in Theorem 6.1, and select G 2 G4n;p;r. At con-
stant temperature T and starting at any initial state, the Metropolis process on bisections p of G reaches a bisection with imbalance at least n in time O(n1+" ), with overwhelming probability. Proof Let= n?1=2. By Corollary 5.3," with overwhelming probability no -atypical states are encountered in the rst O(n1+ ) steps of the Metropolis process. It is therefore enough to prove the result under the assumption that no -atypical states are encountered. p Set b= d n e, and consider the random walk Y (t) on N de ned by transition probabilities ( u if 0 k< Pr Y (t+ 1)= k+ 1 j Y (t)= k]= 0 otherwise; b;
d Pr Y (t+ 1)= k? 1 j Y (t)= k]= 1 if 0< k b; if k> b; 1 where u= 1?, d= 8+, and> 0 is a constant to be chosen shortly. (Loop 8 probabilities are implicitly de ned by complementation.) Let k(t), t= 0; 1;:::, be the sequence of imbalances recorded as the Metropolis process evolves from a random initial state. Under the assumption that the current state is not -atypical, Corollary 3.3 assures us that k-increasing and k-decreasing transitions both occu
r with probability 1 O(n?1=2) 8 p when k b= d n e. Thus, for some choice of= O(n?1=2) the random walk Y (t) stands in relation to k(t) as its namesake does to the process X (t) in Theorem 6.2.1 We are thus reduced to showing that the random walk Y reaches b in time O(n1+" ) with overwhelming probability when started in state 0. For 0 k b, let i be the expected time for the random walk Y to hit state b, given that the initial state is i. According to Feller 7, eq. XIV.3.3], the general solution for i is2 d i i (10)= d?u+A+B u; i where A and B are constants that must be tted to the boundary conditions; in our case, these are b= 0 and 0= 1+ u 1+ (1? u) 0, the latter simplifying to 0? 1= u?1. Substituting the general solution from equation (10) into each of these in turn yields d b b A+B u+ d?u=0 and d d B 1? u? u(d? u)= 0: correspondence with the condition of Theorem 6.2; in fact we are only interested in the evolution of k(t) until k(t) b. 2 Feller has the convention u+ d= 1, but his derivation is valid for the general case. 1 The transition probabilities for Y when Y (t) exceeds b are arti cially de ned to ensure a formal
and
(
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...
热门文档