随机竞争策略在Monte Carlo算法中的性能分析

摘要：

随机算法在组合优化问题中具有广泛的应用,Las Vegas算法和Monte Carlo算法是主要的两类随机算法.随机算法的性能和稳定性常常得不到保证,以往的研究针对Las Vegas算法提出了一种有效的性能改进策略--随机竞争策略,但其在Monte Carlo算法中的性能尚未被研究.文中研究了随机竞争策略对Monte Carlo算法性能和稳定性的影响,分析了使其效率大于1的条件,在求解TSP问题时的实验结果显示该策略具有显著的应用价值,在同等时间内能够将解的质量提高一倍以上.

关键词：Monte Carlo算法、随机竞争策略、随机算法、组合优化

所属期刊栏目：23

分类号：TP301(计算技术、计算机技术)

资助基金：科技部科研项目G1998030403

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1015-1020