A simulated annealing algorithm with constant temperature for discrete stochastic optimization
A simulated annealing algorithm with constant temperature for discrete stochastic optimization
复制标题
DOI：
10.1287/mnsc.45.5.748
复制
发表时间：
1999-05-01
影响因子：
5.4
通讯作者：
Andradóttir, S
中科院分区：
文献类型：
--
作者：
Alrefaei, MH;Andradóttir, S
我们提出了用于解决离散随机优化问题的模拟退火算法的修改。像原始的模拟退火算法一样，我们的方法具有爬山功能，因此它可以通过许多本地解决方案找到全局最佳解决方案来离散随机优化问题。但是，我们的方法与原始模拟退火算法有所不同，因为它使用常数（而不是降低）温度。我们考虑了估计最佳解决方案的两种方法。第一种方法使用算法对不同的访问次数：状态（由归一化器分开）来估计最佳解决方案。第二种方法使用具有最佳平均估计目标函数值作为最佳解决方案的估计的状态。我们表明，我们方法的两个变体都可以确保几乎可以肯定地融合到一组全局最佳解决方案，并讨论我们的工作如何在离散确定性优化设置中应用。我们还展示了当使用瞬态或稳态模拟估算目标函数值时，如何应用两个变体来解决离散优化问题。最后，我们包括一些令人鼓舞的数值结果，记录了算法的两个变体的行为，用于求解两个特定离散随机优化问题的两个版本，并将其性能与模拟退火算法的其他变体的性能进行比较随机优化问题。
We present a modification of the simulated annealing algorithm designed for solving discrete stochastic optimization problems. Like the original simulated annealing algorithm, our method has the hill climbing feature, so it can find global optimal solutions to discrete stochastic optimization problems with many local solutions. However, our method differs from the original simulated annealing algorithm in that it uses a constant (rather than decreasing) temperature. We consider two approaches for estimating the optimal solution. The first approach uses the number of visits the algorithm makes to the different: states (divided by a normalizer) to estimate the optimal solution. The second approach uses the state that has the best average estimated objective function value as estimate of the optimal solution. We show that both variants of our method are guaranteed to converge almost surely to the set of global optimal solutions, and discuss how our work applies in the discrete deterministic optimization setting. We also show how both variants can be applied for solving discrete optimization problems when the objective function values are estimated using either transient or steady-state simulation. Finally, we include some encouraging numerical results documenting the behavior of the two variants of our algorithm when applied for solving two versions of a particular discrete stochastic optimization problem, and compare their performance with that of other variants of the simulated annealing algorithm designed for solving discrete stochastic optimization problems.