期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

随机算法重启策略的构造及其在TSP中的应用 被引量：4

Designing Restart Strategy for Randomized Algorithms and Its Application in Solving the TSP
在线阅读 下载PDF
导出
摘要 NP难解问题是计算机算法和理论界长期研究的课题 .在求解 NP难解问题时 ,随机算法的性能往往很不稳定 .在以往的实验中 ,人们发现基于重启的优化方法可以提高 L as Vegas算法的性能和稳定性 .尽管它的思想比较直观 ,但对它的性能进行理论分析却并不容易 ,这在很大程度上限制了其应用 .该文使用连续概率分布对算法性能分布建模 ,针对 L as Vegas算法提出了一种高效的重启策略构造方法 .该文从平均性能和稳定性两个角度分析了该方法的效率 ,同时通过将其应用于求解大规模旅行商问题 (TSP) This paper focuses on improving the performance of randomized algorithms by exploiting the properties of their performance distributions. In previous research, it is found that strategies based on restart can dramatically improve the performance and stability of Las Vegas algorithms in many cases. Though this idea is rather simple, it is difficult to analyze their performance. This will greatly limit the application of restart strategies. In this paper, continuous probability functions are used to model the performance distribution of randomized algorithms, and an efficient designing method of restart strategy for Las Vegas algorithms is proposed. It is pointed out that if the performance of a randomized algorithm can be approximated by the lognormal distribution model, then the peak point of this distribution will be the best choice for setting restart period. The efficiency of this strategy is analyzed considering both the average performance and the stability. Experimental results in solving large traveling salesman problems (TSP) also verify the analysis.
作者 陈国良 谢幸 徐云 顾钧
机构地区 中国科学技术大学计算机科学与技术系 香港科技大学计算机科学系
出处 《计算机学报》 EI CSCD 北大核心 2002年第5期514-519,共6页 Chinese Journal of Computers
基金 国家"九七三"重点基础研究发展规划项目 (G19980 3 0 40 3 )资助
关键词 NP问题 计算机算法 随机算法 重启策略 TSP Algorithms Optimization Stability
分类号 O22 [理学—运筹学与控制论] TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献19

  • 1Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, 1979
  • 2Goldberg D E. Genetic Algorithm in Search, Optimization and Machine Learning. New York: Addison-Wesley, 1989
  • 3Kirkpatrick S, Gelatt C D,d Vecchi M P. Optimization by simulated annealing. Science, 1983, (4598):671-680
  • 4Gambardella L M, Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In:Proc the 12th International Conference on Machine Learning, San Francisco, USA, 1995. 252-260
  • 5Johnson D S, McGeoch L A. The traveling salesman: A case study in local optimization. In: Aarts E H L, Lenstra J K eds. Local Search in Combinatorial Optimization. New York: Wiley and Sons, 1996.215-310
  • 6Motwani R, Raghavan P. Randomized algorithms. ACM Computing Surveys, 1996, 28(1):33-37
  • 7朱洪 陈增武 等.算法设计与分析[M].上海:上海科学技术文献出版社,1989.119-120.
  • 8Hoos H, Stutzle T. Developing new concepts to characterize empirical phenomena. In: Proc IJCAI'99 workshop on empirical AI, Stockholm, Sweden, 1999. 59-67
  • 9Hoos H. Stochastic local search-methods, models, applications[Ph D dissertation]. Computer Science Department of the Darmstadt University of Technology, Germany, 1998
  • 10Hogg T, Williams C. Expected gains from parallelizing constraint solving for hard problems. In: Proc AAAI'94, Seattle, USA, 1994. 331-336

二级参考文献12

  • 11，Motwani R， Raghavan P. Randomized algorithms. New York: Cambridge University Press, 1995
  • 22，Goldberg D E. Genetic algorithm in search, optimization and machine learning. New York: Addison-Wesley, 1989
  • 33，Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220:671-680
  • 44，Gambardella L M, Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. In: Proceedings of the 12th International Conference on Machine Learning, Tahoe City, USA, 1995. 252-260
  • 55，Johnson D S, McGeoch L A. The traveling salesman: A case study in local optimization. In: Local Search in Combinatorial Optimization. New York: John Wiley and Sons, 1996
  • 66，Huberman B A, Lukose R M, Hogg T. An economics approach to hard computational problems. Science, 1997, 275:51-54
  • 77，Ertel W. Random competition: A simple, but efficient method for parallelizing inference systems. In: Fronhoer B, Son G W ed. BParallelization in Inference Systems. Dagstuhl, Berlin: Springer, 1992. 195-209
  • 88，Luby M, Sinclair A, Zuckerman D. Optimal speedup of Las Vegas algorithms. Information Processing Letters, 1993, 47(1):173-180
  • 99，Junger M, Reinelt G, Rinaldi G. The traveling salesman problem. In: Handbook on Operations Research and Management Sciences: Networks. Amsterdam: Elsevier Science BV, 1995. 225-330
  • 1010，Garey M R, Johnson D S. Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman, 1979

共引文献8

同被引文献47

  • 1吴湛击,吴伟陵.随机排序的优化算法[J].电子学报,2000,28(z1):76-79. 被引量：5
  • 2肖化昆.系统仿真中任意概率分布的伪随机数研究[J].计算机工程与设计,2005,26(1):168-171. 被引量：31
  • 3刘志强,汪东升,郑纬民.随机测试程序生成器研究[J].计算机工程与设计,2005,26(2):281-284. 被引量：2
  • 4张超勇,饶运清,李培根,邵新宇.柔性作业车间调度问题的两级遗传算法[J].机械工程学报,2007,43(4):119-124. 被引量：105
  • 5王晓东.算法设计与分析[M].北京:清华大学出版社,2008.
  • 6Yang Qiang, Wu Xindong. 10 challenging problems in data mining research[J]. International Journal of Information Technology & Decision Making, 2006, 5(4): 597-604.
  • 7Turney P D. Cost-sensitive classification: empirical evalua- tion of a hybrid genetic decision tree induction algorithm[J]. Journal of Artificial Intelligence Research, 1994, 2(1): 369-409.
  • 8Ling C X, Sheng V S, Yang Qiang. Test strategies for cost- sensitive decision trees[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1055-1067.
  • 9Domingos R Metacost: a general method for making classi- fiers cost-sensitive[C]//Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '99), San Diego, USA, Aug 15-18, 1999. New York, NY, USA: ACM, 1999: 155-164.
  • 10Zhou Zhihua, Liu Xuying. Training cost-sensitive neural networks with methods addressing the class imbalance problem[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, ! 8(1): 63-77.

引证文献4

二级引证文献8

计算机学报
2002年 第5期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部