tailieunhanh - SIMULATION AND THE MONTE CARLO METHOD Episode 10

Tham khảo tài liệu 'simulation and the monte carlo method episode 10', 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ả | 250 THE CROSS-ENTROPY METHOD As soon as the associated stochastic problem is defined we approximate the optimal solution say X of by applying Algorithm for rare-event estimation but without fixing 7 in advance. It is plausible that if 7 is close to 7 then v-r assigns most of its probability mass close to X . Thus any X drawn from this distribution can be used as an approximation to the optimal solution X and the corresponding function value as an approximation to the true optimal 7 in . To provide more insight into the relation between combinatorial optimization and rare-event estimation we first revisit the coin flipping problem of Example but from an optimization rather than an estimation perspective. This will serve as a highlight to all real combinatorial optimization problems such as the maximal cut problem and the TSP considered in the next section in the sense that only the sample function S X and the trajectory generation algorithm will be different from the toy example below while the updating of the sequence 7t vt will always be determined from the same principles. EXAMPLE Flipping n Coins Example Continued Suppose we want to maximize n S x 52 Xi i 1 where Xi 0 or 1 for all i 1 . n. Clearly the optimal solution to is X 1 . 1 . The simplest way to put the deterministic program into a stochastic framework is to associate with each component Xi i l . n a Bernoulli random variable Xi i 1 . n. For simplicity assume that all Xt are independent and that each component i has success probability 1 2. By doing so the associated stochastic problem becomes a rare-event estimation problem. Taking into account that there is a single solution X 1 . 1 using the CMC method we obtain 7 where 2n which for large n is a very small probability. Instead of estimating 7 via CMC we can estimate it via importance sampling using Xi Ber pi i 1 . n. The next step is clearly to apply Algorithm to without fixing 7 in advance. As .