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

摘要

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