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

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

Towards the impact of PRNG to stochastic local search

When tackling many NP-hard combinatorial optimization problems, a lot of excellent meta-heuristics must integrate some kind of strategy of stochastic local search （SLS）. The PRNG is the key to SLS, therefore, many running at many instances is to get the steady performance. The experiments include two cases, the first taking one is to analyze the different behaviors when a SIS, 3Opt, being applied to the Traveling Salesman Problem （TSP） with different PRNGs. The other is about different behaviors when another SIS, Reactive Local Search, being applied to the Maximum Clique Problem. The secondary work is to try to find a good PRNG for 30pt-TSP. The result shows different PRNGs have some different impacts to some instances, and the good PRNG also exists.