Simulated Annealing for Graph Bisection
Blu er: Metropolis: 0
P1 b
P2 b
P3 b
P1
P2
\excess"\shortfall" (reserved) (redistributed)
1
Figure 1: Sample space for Blu er and Metropolis process run at temperature T for t= state with probability at most exp(? (
Claim 5.2 For any temperature 0< T
p ( 2T 3= n log2 n) steps encounters a -atypical 2 T 2= log 2 n)).
poly(n) and any tolerance, the Metropolis
Proof Acting in parallel with the Metropolis process, we introduce a second random b b b
process, the blu er, which should shadow it closely without knowledge of the graph G. The blu er is de ned as follows. Given the current state^, the next state^ 0 is chosen as i with probability Pi= P (^; i). This will be implemented by partitioning 0; 1) into intervals of length Pi, and selecting^ 0= i when the random\coin toss" falls into the i'th interval. This\blu er's mapping" taking^ to^ 0 is applied to^ ( ) to yield^ (p+ 1). We modify the blu er's procedure according to a correction tape: a set of O(t n=T ) times j and associated moves m( j ). For any time j,^ ( j ) will be the state obtained from^ ( j? 1) by applying move m( j ), rather than the state obtained by applying the blu er's mapping. Note that an initial state^ (0), a random sequence ( ( ))t=1, and a correction tape, completely determine the blu er's sequence (^( ))t=1. Base a trajectory of the Metropolis process on the same sample space of 's as used for the blu er, as follows. For any=^, take as a starting point the same partitioning of 0; 1) into intervals of length Pi . Now| given the graph G| imagine overlaying each of these intervals with an interval of length Pi= PG (; i), matching up the left ends. (Refer to Figure 1.) When Pi< Pi, the Pi -long interval is\labeled" i, and the\excess" interval of length Pi? Pi is reserved. When Pi> Pi, the label i is applied to the interval Pi, giving a\shortfall" of Pi? Pi . Because the total of the excesses is equal to the total of the shortfalls, we end by arbitrarily distributing the labels that fell short into the reserved excess spaces. By construction, each i labels a collection of intervals of total length Pi, so 0= i is chosen with the correct Metropolis probability PG (; i). Furthermore, if^ ( )= ( ), the blu er's uncorrected successor for^ ( ) and the 1 Metropolis's (+1) are equal with probability 1? 2 kP?P k, over random (+1) 2 0; 1): they are unequal only if (+ 1) falls into one of the\excess" regions, and the total size 1 of these is 2 kP? P k. We now claim that for graph G satis es P? P k= pn=T ) for all bisections any from any which is not^rough (whichwith high kprobability ), initial state (0)= (0), O( b b b b b b b b b

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...
热门文档