Simulated Annealing for Graph Bisection
Note that a typical random partition has k= O(n1=2), while the canonical partiti
on (which with high probability is the minimum) is uniquely characterized by k= n. As we will see, the cost of a state is equal to a function of k plus an error term which is small (with high probability). Thus the sequence k(t) of imbalances after t attempted moves can be used to study the progress of annealing. That is, while the transition probabilities k 7! k? 1, k 7! k, and k 7! k+1 depend on the full state, under appropriate conditions they can be approximated from k alone, making k(t) a tractable\near Markov chain". Throughout this paper the phrase with overwhelming probability will mean\with probability 1? O( exp(?nc)) for some constant c> 0". The full probability space under consideration is the cross product of the space of random graphs, the random proposed moves over all steps, and the random coin tosses at all steps. We will write EG;M to denote the expectation of some quantity over random graphs and moves, PrM to denote a probability over random moves alone, and so forth. Finally, in Sections 4 and 5 it is presumed that the sequence of all proposed moves is speci ed in advance: this must be done in such a way that the acceptance or rejection of a previous move does not jeopardize the legality or uniform randomness of later moves. The following means of specifying moves satis es this, and is a convenient concrete model for implementation of the algorithm. Consider the collections L and R to be ordered lists of vertices rather than mere sets, so that a state= (L; R) is a permutation. (Conversely, for a state speci ed by the partition, L and R will refer to the rst and last 2n vertices.) Let the move (i; j ) indicate the exchange of Li and Rj: the i'th vertex in L and the j 'th vertex in R. In annealing, moves will be generated by choosing i and j uniformly at random from f1::: 2ng.
2.3 Randomness and move generation
3 Typical Transition Probabilities The transition k 7! k+ 1 occurs i a move taking k to k+ 1 is both proposed and accepted.
Claim 3.1 For any graph G and any partition with imbalance k, the probability that a proposed move would increase k is
1 k k2 (1) 4? 2n+ 4n2: Proof A proposed move (i; j ) increases k if Li is white, and Rj is black, which has probability ((n? k)=2n)2 . For a given k-bisection, and k-increasing move M, let X+= X+ (G) be the random variable representing the cost increase that occurs when move M is applied to the partitioning of the graph G. Recall that A(x)= (1+ exp(x=T ))?1 is the acceptance function. Note that A(X+ ) is the probability that a given k-increasing move is accepted. Pr propose k 7! k+ 1]= M 5
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...
热门文档