《伪随机数发生器的统计性质检验及其应用》由会员分享，可在线阅读，更多相关《伪随机数发生器的统计性质检验及其应用（16页珍藏版）》请在金锄头文库上搜索。
1、1Towards the Statistical Properties of PRNG and its Application伪随机数发生器的统计性质检验及其应用栾忠兰 吕强 * （苏州大学计算机科学与技术学院）【摘 要】在解决一些 NP 难的组合优化问题时，很多优秀的元启发算法都利用了随机局部搜索（Stochastic Local Search, SLS）策略。一般认为，不同的伪随机数发生器（Pseudo Random Number Generator, PRNG）对 SLS 的影响是相同的。本文对 PRNG 进行统计性质测试，指出不同的 PRNG 之间有着不同的统计性质。将各种不同的 PR
2、NG 应用于 SLS 算法的典型应用：3Opt 优化旅行商问题（Traveling Salesman Problem, TSP）及 RLS 优化最大团问题（Maximum Clique Problem, MCP） ，并对其结果利用有显著意义的统计检验进行测试分析，得出结论：本文多个 PRNG 对 3Opt-TSP 和 RLS-MCP 的影响是不同的。【关键词】伪随机数发生器；统计检验；t 检验；3Opt-TSP ；RLS-MCP【Abstract】When tackling many NP-hard combinatorial optimization problems, a lot of e
3、xcellent meta-heuristics must integrate some kind of stochastic local search (SLS)s. In literature, different PRNGs (Pseudo Random Number Generator) are considered to have the same impact to SLS. This paper gives evidences to show that the properties of PRNGs are varied in terms of statistical tests
4、. By evaluating some significant statistical tests, this paper compares and analyzes the performances of two typical applications: 3Opt-TSP and RLS-MCP, which are the typical cases of SLS applying to NP-hard problems. The results show that different PRNGs have different impact to 3Opt-TSP and RLS-MC
5、P. 【Keywords】 Pseudo Random Number Generator; Statistical Test; t Test; 3Opt-TSP; RLS-MCP*Email: Tel: 0512-65243192ext208 Addr: 江苏省苏州市十梓街 1 号 158 信箱，邮编 21500621. 引言在科学研究中，我们常常需要用到随机数，然而真的随机数的产生比较复杂，因此我们通常使用伪随机数发生器 PRNG。所谓“伪” 是因为其产生的随机数并不是真正意义上的随机，而是在某个范围内是可预测的。随机局部搜索算法 SLS 是我们解决组合优化问题最有效、最广泛的方法之一。在
6、 SLS过程中都需要用到伪随机数发生器，PRNG 在 SLS 中的应用是非常重要的。一般认为，不同的 PRNG 对 SLS 的影响是相同的 1。但是这种观点至今仍没有相关的理论论证证明。对于实验支持的文献，就只有 2：SLS 算法中的随机决策的作用只是使搜索多样化，PRNG的质量和随机决策的数量都对 SLS 算法的执行没有特别重要的作用。但是， Knuth 提出PRNG 与应用有关 3，而且我们的理解也是：各种 PRNG 由于其所应用的具体问题不同，会体现出不一样的性质质量，即各种 PRNG 对问题的解决结果有优劣之分。为了验证，本文我们将对 PRNG 的性质进行统计检验，分析不同的 PRNG
7、 之间是否有着差异；将这些PRNG 运用到 3Opt-TSP 和 RLS-MCP 问题中，并对产生的结果进行分析统计，从而证实了PRNG 对 SLS 的影响是存在的。2. 常用的 PRNG 及其实现2.1 常用的 PRNG2.1.1 线性同余法Xi+1= (a Xi +c) mod m i=0, 1 (2.1)线性同余法 3通过满足公式(2.1)产生随机序列，主要参数为 a, c, m。只有选择合适的参数才能得到随机数的周期接近或达到 m。我们把 a=137,m=256,c=187 用公式(2.1) 产生的PRNG 称为方法 T1（周期为 256）。类似的，我们把 a=1103515245/6
8、5536,m=32768(Linux下 m=2147483647)，c=12345/65536 用公式 (2.1)产生的 PRNG 称为方法 MO，它就是我们通常所使用的标准库函数 rand。2.1.2 素数模乘同余法Xi+1=a Xi mod m i=0, 1 (2.2)素数模乘同余法 4通过满足公式(2.2)来产生随机序列。我们把 a=23,m=108+1，满足公3式(2.2)的 PRNG 称为方法 T2。2.1.3 最小标准（误差）的产生器实践中，利用公式(2.2)，Park 和 Miller 提出的最小标准（误差）的产生器 4，通过了所有的理论测试，取得了成功的应用。该 PRNG 对公
9、式(2.2) 取参数设置：a=75=16807，m=2 31-1=2147483647。但是其实现仍然很困难，因为 32 位机上，a(m-1)大于计算机存储的最大数。于是 Schrage 提出了分解 m 的方法 6：命 m=aq + r，例如，q=m/a，r=m mod a。如果 r 很小，特别是 r t(n-1)，则 P3000)。我们对每个实例所得到的 1000 个最好解进行统计检验分析。这里我们使用假设检验，假设 PRNG 与 TSP 的应用是独立的，即不同的 PRNG 对 TSP 的应用结果是没有本质差别的。本程序运行的主要参数是： num-ants: 蚂蚁的个数，小中大规模分别设置为
10、 30、100 和 500； num-neighbour: 在解的建立过程中，每个城市的邻居数目，设为 20； Alpha, Beta : 分别用来控制信息素与路径长度的相对重要程度，设为 1.0，2.2； Rho: 控制信息素的挥发力度，设为 0.5； max-tries: 一次执行时最大的次数（try） ，设为 1000。由于随机性的作用，每种10方法对同一个实例必须通过多次运行的统计结果来评价该方法，每一次这样的运行称为一个 try； max-time: 每个 try 的最大运行时间，小中大规模分别设为 100s、1000s 和3000s。对于规模太小的 TSP 实例如 eil50，kr
11、oA100 ，不管使用表 1 中何种 PRNG，都能得到一样的最好解，即对 TSP 应用几乎看不出影响。对于另外三个小规模的实验结果见表 5。表 5 对 TSP 其他小规模实例进行 t 检验的结果（概率 p-value）lin318 att532 rat783A&B 0.165477104 0.619663862 1.76477 E-03A&C 0.165477104 0.603507138 1.211066 E-03A&D 0.165477104 0.364788605 7.862781 E-03A&E 0.165477104 0.648134494 1.861635 E-03A&MO 1.
12、27234 E-34 3.4807 E-187 0A&T1 4.68473 E-13 7.5971 E-53 5.7606 E-101A&T2 0.165477104 0.792191398 0.331014029B&C #DIV/0! 0.979819989 0.879995085B&D #DIV/0! 0.156778457 0.680157595B&E #DIV/0! 0.3355694 1B&MO 4.9182 E-37 5.9885 E-186 0B&T1 3.76701 E-14 5.70259 E-51 8.89002 E-80B&T2 #DIV/0! 0.443642722 0
13、.034358285C&D 4.9182 E-37 0.151154745 0.578666903C&E #DIV/0! 0.324959695 0.88056885C&MO 4.9182 E-37 9.6427 E-185 0C&T1 3.76701 E-14 1.80318 E-50 1.91558 E-77C&T2 #DIV/0! 0.43061101 0.025253343D&E #DIV/0! 0.648247756 0.681602955D&MO 4.9182 E-37 2.2976 E-196 0D&T1 3.76701 E-14 5.96291 E-59 1.55569 E-8
14、0D&T2 #DIV/0! 0.517578823 0.094704323E&MO 4.9182 E-37 1.5809 E-193 0E&T1 3.76701 E-14 1.56752 E-56 2.92308 E-79E&T2 #DIV/0! 0.846778639 0.035246102MO&T1 0.001432685 2.71765 E-64 5.5736 E-21811MO&T2 4.9182 E-37 5.1251 E-191 0T1&T2 3.76701 E-14 5.02956 E-55 1.6681 E-9212表 5 显示了对不同实例的 1000 次所求的最好解 t 检验
15、的结果。 （表中字段值：“#DIV/0!”：两种方法作用于 TSP 实例，分别得到的最好解序列的方差为 0，导致除数为0，无法进行 t 检验。 “0”：两个序列平均值差异性显著。 “1”：两个序列具有相同均值。）我们将 p 值与 比较，从表中我们发现：1） 方法 MO 与其他 PRNG 进行 t 检验的 p 值小于 。2） 方法 T1 与其他 PRNG 进行 t 检验的 p 值小于 。3） 实例 rat783 的 p 值相比另两个实例 lin318 和 att532，小于 的 p 值有些增加。从而得出结论：对于一些小规模实例，PRNG 两两进行 t 检验后的 p 值有很多明显小于 值，这说明我
16、们的假设是不成立的，即我们认为这些 PRNG 对 3Opt-TSP 的影响是不同的。接着，我们又分别对中规模和大规模的实例进行检验分析，统计结果如表 6 和表 7。从表 6 中的数据可以观察得到：1） A&D, A&E, A&T2, D&E 及 E&T2 等行的大部分数据仍大于 ，其他行的数据几乎都比 小。2） 这些小于 的数据表明：不同 PRNG 对解决同一实例的最好解结果在统计意义上存在着显著性差异。表 6 对 TSP 中规模实例进行 t 检验的结果（概率 p-value）pcb1173 d1291 fl1577 rl1889 pr2392A&B 7.23397 E-08 1.3662 E-23 2.90054 E-49 3.75621 E-07 0.859860276A&C 3.1759 E-255 0 0 0 0A&D 0.10575575 0.516773288 5.74804
