Efficient Stochastic Approximation Monte Carlo Sampling for Heterogeneous Redundancy Allocation Problem

Abstract

Existing optimization methods to heterogeneous redundancy allocation problem often suffer from the local-trap problem in optimization, due to the rugged energy landscapes. In this paper, a new optimization paradigm based on the Markov chain Monte Carlo sampling is proposed for solving the heterogeneous redundancy allocation for multi-state systems. We address this in an optimization-by-sampling framework, and propose to sample the intricate distribution over the combinatorial space by a doubly adaptive sampling approach, where the target adaptation favors free random walk on the rugged energy landscape to substantially alleviate the local-trap problem by updating the target distribution on-the-fly, while the proposal adaptation helps improve the sampling efficiency by learning the proposal distribution based on chain history in optimization. Experimental results performed on a range of benchmark instances demonstrated the superiority of the proposed optimization approach compared with the state-of-the-art alternatives in terms of the solution quality or computational efficiency.

Keywords

• Optimization-by-sampling
• multi-state system
• redundancy allocation problem
• Markov chain Monte Carlo