试析伪随机数发生器对随机局部搜索的影响

被引：1

作者：

王为磊

吕强

机构：

[1] 苏州大学计算机科学与技术学院

来源：

苏州大学学报(自然科学版) | 2008年 / 03期

关键词：

伪随机数发生器; 3Opt-TSP; RLS-MCP;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

在解决一些NP难的组合优化问题时,很多优秀的元启发算法利用了随机局部搜索(SLS)策略.而随机局部搜索策略的关键在于随机数发生器(PRNG),从随机数发生器的周期和速度特性探索了其对随机局部搜索的影响.主要实验方法是,测试多个实例及运行多遍程序,目的是消除随机意义的偶然性.分析了两个案例:一个是3Opt方法,它是优化旅行商问题(TSP)的有效方法;另一个是RLS方法,其为解决最大团(MCP)的目前最优方法.另外,探索了是否存在较好的随机数发生器.结果表明,对这两个案例,不同特性的随机数发生器对实例有不同程度的影响,而且也存在较好的随机数发生器.

引用

页码：34 / 38

页数：5