Simulated Annealing for Graph Bisection
dominated by X in the following sense: if X (t)= Y (t)= k, then and
Pr X (t+ 1)= k+ 1] Pr X (t+ 1)= k? 1]
Pr Y (t+ 1)= k+ 1] Pr Y (t+ 1)= k? 1]:
Furthermore, assume that the loop probabilities Pr Y (t+ 1)= k j Y (t)= k] for the 1 random walk are at least 2, for all k. Then the process X (t) dominates Y (t): for every nal state j, every choice of initial states satisfying Y (0) X (0) j, and every time bound t, it is the case that
Pr X (t0)= j; for some t0 t] Pr Y (t0)= j; for some t0 t]: so that X (0) Y (0) implies X
(t) Y (t) for all t. The result follows immediately. The sample space consists of a sequence (0); (1);::: of independent\coin tosses", the result of the t'th toss being a real number (t) uniformly distributed in 0; 1). Focus attention on time step t, and let p+= Pr X (t+ 1)= X (t)+ 1] and p?= Pr X (t+ 1)= X X X (t)? 1], with analogous de nitions for p+ and p? . (The probabilities p+ and p? may Y Y X X depend on a hidden state or external stimulus: the argument is not a ected.) Then the next state of the process X is given by
Proof We shall base the processes X (t) and Y (t) on a common underlying sample space,
X (t)? 1 if (t)< p?; X X (t+ 1)= X (t)+ 1 if (t) 1? p+; X X (t) otherwise; 8><>:
and similarly for the process Y . Observe that the high loop probabilities of process Y, combined with dominance of 1 1 the transition probabilities of Y by those of X, ensure that p+ 2 and p? 2 . Thus it X Y cannot happen that X (t+ 1)= X (t)? 1 and Y (t+ 1)= Y (t)+ 1, for the former implies 1 (t)< p? 1 and the latter (t) 1? p+ 2 . X 2 Y The proof of X (t) Y (t) for all t is by induction on t, the case t= 0 being satis ed by hypothesis. If X (t)> Y (t) then it is immediate that X (t+ 1) Y (t+ 1) by the previous observation. If X (t)= Y (t) then there are two possible bad cases: either Y increases and X does not; or Y is unchanged and X decreases. But Y increases only if (t) 1? p+ 1? p+, in which case X also increases; similarly a decrease in X requires Y X (t)< p? p?, which in turn requires Y to decrease. X Y The machinery required for analyzing the three regimes described earlier is now in place. Here we consider the Metropolis process on partitions with imbalance at most pn. We show that the process exhibits the following favorable behavior. 14
6.1 Small imbalance
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...
热门文档