Stochastic discrete optimization
Stochastic discrete optimization
复制标题
DOI：
10.1137/0330034
复制
发表时间：
1992-06
影响因子：
2.2
通讯作者：
D. Yan;H. Mukai
中科院分区：
文献类型：
--
作者：
D. Yan;H. Mukai
本文提出了一种随机搜索方法，用于寻找目标函数必须用蒙特卡罗模拟估计的随机离散优化问题的全局解。尽管在制造工程、运筹学和管理科学领域中存在许多这类实际问题，但对于这种具有随机基础设施的离散问题，还没有提出任何非启发式方法。该方法简单，但能找到全局最优解。该方法利用蒙特卡罗模拟的随机性，生成一系列的解估计。所生成的序列是一个非平稳马尔可夫链，并证明在温和条件下，该马尔可夫链是强遍历的，且当前解估计全局最优的概率收敛于1。此外，还分析了算法的收敛速度。
In this paper a stochastic search method is proposed for finding a global solution to the stochastic discrete optimization problem in which the objective function must be estimated by Monte Carlo simulation. Although there are many practical problems of this type in the fields of manufacturing engineering, operations research, and management science, there have not been any nonheuristic methods proposed for such discrete problems with stochastic infrastructure. The proposed method is very simple, yet it finds a global optimum solution. The method exploits the randomness of Monte Carlo simulation and generates a sequence of solution estimates. This generated sequence turns out to be a nonstationary Markov chain, and it is shown under mild conditions that the Markov chain is strongly ergodic and that the probability that the current solution estimate is global optimum converges to one. Furthermore, the speed of convergence is also analyzed.