Simulated Annealing for Graph Bisection
Theorem 6.1 Let"> 0, p? r= n?1=6+2", and T= n5=6+", and select G 2 G4n;p;r. At constant temperature T, the Metropolis process on bisections of G reaches the unique minimum bisection in time O(n2+" ), with overwhelming probability.
established later in the section. It should be noted that the constant implicit in the de nition of\overwhelming probability" depends on", but on no other parameters. The analysis
leading to Theorem 6.1 tracks the Metropolis process through three regimes. These are now brie y described in order to map out the general shape of the proof. The rst two last for only n1+" time, and hence, by Corollary 5.3, pass without the process visiting atypical states. 1. The rstp regime is in force until the imbalance k of the partition rst reaches a value at least n. (For a fortuitous initial partition, this condition may already hold at the outset.) The evolution of the imbalance k as a function of time is su ciently close to that of an unbiased random walk on N, that we are able to argue (in p Subsection 6.1) that there is an appreciable probability that k reaches n in time O(n). Thus with overwhelming probability we pass to the second regime in time O(n1+" ). 2. The second regime lasts until k= (n). In Subsection 6.2 we show that the process experiences a de nite\drift" towards states (partitions) with higher values of k, with the result that k= (n) holds with overwhelming probability after only O(n1+" ) further steps. 3. When k= (n), convergence begins to slow, because the probability of proposing a k-increasing move diminishes (though the probability of accepting a given k-increasing move is obviously high). As a result, we are no longer covered by Corollary 5.3. Fortunately, the progress towards the optimal partition is now inexorable, as we are able to demonstrate by rather crude arguments in Subsection 6.3. As hinted above, we track the Metropolis process by observing the imbalance k as a function of time. The latter process is not Markovian, as the transition probabilities are a function of a\hidden" variable, namely the current partition . However, we shall be able to reason about the the process k(t) by comparing it with a simple random walk on N. The latter will be chosen so that it approximates the former, and is dominated by it in an appropriate sense. The technology for making this comparison is encapsulated in the following theorem.
Proof The result follows immediately from Lemmas 6.3, 6.4, and 6.5, which will be
Theorem 6.2 Let X (t), t= 1; 2;:::, be a random process on N, not necessarily Markov-
ian, having X (t+ 1) 2 fX (t)? 1; X (t); X (t)+ 1g as its only allowed transitions. (The transition probabilities may depend on some hidden state or even an external stimulus.) Let Y (t), t= 1; 2;:::, be a random walk on N that is totally independent of X, but is
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...
热门文档