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

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