Towards the Statistical Properties of PRNG and its Application伪随机数发生器的统计性质检验及其应用栾忠兰 吕强* （苏州大学计算机科学与技术学院）【摘 要】在解决一些NP难的组合优化问题时，很多优秀的元启发算法都利用了随机局部搜索（Stochastic Local Search, SLS）策略。一般认为，不同的伪随机数发生器（Pseudo Random Number Generator, PRNG）对SLS的影响是相同的。本文对PRNG进行统计性质测试，指出不同的PRNG之间有着不同的统计性质。将各种不同的PRNG应用于SLS算法的典型应用：3Opt优化旅行商问题（Traveling Salesman Problem, TSP）及RLS优化最大团问题（Maximum Clique Problem, MCP），并对其结果利用有显著意义的统计检验进行测试分析，得出结论：本文多个PRNG对3Opt-TSP和RLS-MCP的影响是不同的。【关键词】伪随机数发生器；统计检验；t 检验；3Opt-TSP；RLS-
