tailieunhanh - SIMULATION AND THE MONTE CARLO METHOD Episode 8

Tham khảo tài liệu 'simulation and the monte carlo method episode 8', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 190 MARKOV CHAIN MONTE CARLO is thus to minimize min Six min CXi Xí l Note that the number of elements in is typically very large because T rd. The TSP can be solved via simulated annealing in the following way. First we define the target pdf to be the Boltzmann pdf x ce-s6c T. Second we define a neighborhood structure on the space of permutations 3C called 2-opt. Here the neighbors of an arbitrary permutation X are found by 1 selecting two different indices from 1 . n and 2 reversing the path of X between those two indices. For example if X 1 2 . 10 and indices 4 and 7 are selected then y 1 2 3 7 6 5 4 8 9 10 see Figure . Another example is if X 6 7 2 8 3 9 10 5 4 1 and indices 6 and 10 are selected then y 6 7 2 8 3 1 4 5 10 9 . 10 9 8 7 6 Figure Illustration of the 2-opt neighborhood structure. Third we apply the Metropolis-Hastings algorithm to sample from the target. We need to supply a transition function ợ x y from X to one of its neighbors. Typically the two indices for the 2-opt neighborhood are selected uniformly. This can be done for example by drawing a uniform permutation of 1 . n see Section and then selecting the first two elements of this permutation. The transition function is here constant q x y j y x 1 2 It follows that in this case the acceptance probability is _ J y 1 I x J 1 ifS y S x e- S y -S x T if S y By gradually decreasing the temperature T the Boltzmann distribution becomes more and more concentrated around the global minimizer. This leads to the following generic simulated annealing algorithm with Metropolis-Hastings sampling. SIMULATED ANNEALING 191 Algorithm Simulated Annealing Metropolis-Hastings Sampling 1. Initialize the starting state Xo and temperature To- Set t 0. 2. Generate a new state Y from the symmetric proposal ợ Xt y . 3. IfS Y S Xt let xt 1 Y. If six generate u U o 1 and let Xt i Yif . ư e- S Y -S Xt T . Otherwise letXt 1 xt. 4. Select a new temperature Tt 1 Tt increase t by I and repeat from