1、伪随机数发生器统计性质检验及其应用

1、Towards the Statistical Properties of PRNG and itsApplication伪随机数发生器的统计性质检验及其应用栾忠兰吕强 *苏州大学计算机科学与技术学院）【 摘 要】 在解决一些 NP 难的组合优化问题时，很多优秀的元启发算法都利用了随机局 部搜索 Stochastic Local Search, SLS ）策略。一般认为，不同的伪随机数发生器PseudoRandom Number Generator, PRNG ）对 SLS 的影响是相同的。本文对 PRNG 进行统计性质 考试，指出不同的 PRNG 之间有着不同的统计性质。将各种不同的 PRN

2、G 应用于 SLS 算法 的典型应用： 3Opt 优化旅行商问题 Traveling Salesman Problem,TSP ）及 RLS 优化最大团 问题 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 arevaried in terms of statistical tests. By

3、 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 havedifferent impact to 3Opt-TSP and RLS-MCP.【 Ke

4、ywords】 Pseudo Random Number Generator。 Statistical Test。 t Test。 3Opt-TSP 。 RLS-MCP*Email: Tel: 2ext208 Addr: 江 苏 省 苏 州 市 十 梓 街 1 号 158 信 箱 ， 邮 编 2150061. 引言在科学研究中，我们常常需要用到随机数，然而真的随机数的产生比较复杂，因此我 们通常使用伪随机数发生器PRNG。所谓 “伪 ”是由于其产生的随机数并不是真正意义上的随机，而是在某个范围内是可预测的。随机局部搜索算法 SLS 是我们解决组合优化问题最有效、最广泛的方法之一。在 SLS 过

5、程中都需要用到伪随机数发生器， PRNG 在 SLS 中的应用是非常重要的。一般认为，不 同的 PRNG 对 SLS 的影响是相同的 1 。但是这种观点至今仍没有相关的理论论证证明。对 于实验支持的文献，就只有 2：SLS算法中的随机决策的作用只是使搜索多样化，PRNG 的质量和随机决策的数量都对 SLS 算法的执行没有特别重要的作用。但是， Knuth 提出 PRNG 与应用有关 3，而且我们的理解也是：各种PRNG 由于其所应用的具体问题不同，会体现出不一样的性质质量，即各种 PRNG 对问题的解决结果有优劣之分。为了验证，本 文我们将对 PRNG 的性质进行统计检验，分析不同的 PRNG

6、 之间是否有着差异；将这些 PRNG 运用到 3Opt-TSP 和 RLS-MCP 问题中，并对产生的结果进行分析统计，从而证实了 PRNG 对 SLS 的影响是存在的。2. 常用的 PRNG 及其实现常用的 PRNG线性同余法 1.2.2Xi+1= (aX i+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 ， c=12345/65536 用公式 (2.1产生的 PRNG 称为方

7、法 MO ，它就是我们 通常所使用的标准库函数 rand。素数模乘同余法 1.2.1X i+1=aX i mod m i=0, 1 (2.2素数模乘同余法 4通过满足公式 (2.2 来产生随机序列。我们把a=23,m=108+1，满足公式(2.2 的 PRNG 称为方法 T2。最小标准 ，Park 和 Miller 提出的最小标准 取参数设置： a=75=16807 ， m=231-1=2147483647 。但是其实现仍然很困难，由于32 位机上， a(m-1 大于计算机存储的最大数。于是 Schrage 提出了分解 m 的方法 6：命 m=aq+r ，例如， q=m/a ，r=m mod

8、a。如果 r很小，特别是 rq，且 0z m-1， 0 rz/q m-1 时，利 用公式 (2.3 ：(2.3就可以产生性能很好的随机数，这里的参数主要是指a,q,r。如何选择合适的 a,q,r 是这种类型的 PRNG 的关键。我们把满足 a=16807,q=127773,r=2836 的 PRNG 称为方法 A，这 也就是 ACOTSP 软件包采用的 PRNG 。类似地，满足 a=48271,q=44488,r=3399 的 PRNG 称 为方法 B； a=69621,q=30845,r=23902 的 PRNG 称为方法 C。扩大周期法 1.2.2利用两个随机数产生器相结合扩大周期的方法5

9、。假设结合前的两个序列分别为：序列 1：，周期为 m1；序列 2：，周期为 m2。那么对任意非零整数ca, cb，公式 (2.4：产生的 Xi 就是新组合的随机序列。这里我们运用上面提到的最小标准 的 PRNG 称为方法 D。查表法 1.2.2Knuth 提出的加速方法 3 ，是利用随机数序列相减得到的。利用公式：Xn= (X n-55-X n-24, 55 n795 (2 .实现的思路为：利用给定的初始值作为seed，构建一张并非真正随机的表 (Table，长度取为 56。然后利用此表产生随机数：对于一个序号为index 的随机数， index 要模 56 ，使其处理后的序号可以对应到表中。

10、利用公式 (2.5可以得到 Xindex，把 Xindex 赋值给 X n-56， 改变 Table 元素。从而利用新的 Table 产生下一个随机数。我们把这样的 PRNG 称为方法 E。本文考察的 PRNG 小结 1.2.2面我们主要介绍了本文要考察的 PRNG ，现将它们小结如下，见表 1。表 1 本文考察的 PRNG 的实现方法及参数PRNG 名 称实现方法及参数运行速度 7T1公式 (2.1 其中 a=137,m=256,c=1871.3MO公式 (2.1 标准库函数 rand其中 a=1103515245/65536,m=32768, c=12345/655361.3T28公式 (

11、2.2 其中 a=23 ， m=108+11.3A公式 (2.3 其中 a=16807,q=127773,r=28361B公式 (2.3 其中 a=48271,q=44488,r=33991C公式 (2.3 其中 a=69621,q=30845,r=239021D公式 (2.4 其中 m1=2147283563,m2=21474833990.6E公式 (2.52表 1 中速度一栏根据参考文献 7 以及我们的实现获得，该栏数据越高表示相应的PRNG 运行速度越快。 我们之所以选取上面的几种 PRNG 是由于至少它们在程序行为上有明显的不同。 MO 是默认的使用得最多的 PRNG ，一般在标准 C

12、 库中就是使用这种方法，既然它可 以被作为库函数使用，必有其独特之处。我们把它作为基准系统来看待。 T1方法可以明显看出周期相比 MO 缩短了很多，从随机序列行为上明显有别与MO。T2 方法使用了另外一种实现方法，但其周期比较大。A,B,C 是同一个 PRNG ，只是具有不同的参数，参数的设置不同，对 PRNG 的性质是 否有影响。E 方法是速度最快的，它只要通过填表就能完成。但显然在随机序列的行为上哟比除T1 外的 PRNG 简单得多。D 方法是速度最慢的，它使用两个 PRNG 相结合的方法，这两个 PRNG 序列可由上面 的 PRNG 产生，集合了上面几种 PRNG 的特点。常用的统计性质

13、检验上面我们介绍了一些 PRNG ，并在宏观上明显地指出它们是有差异的，那么在微观上 如何描述一个随机序列的性质呢？ Knuth 在其经典著作中 3 ，详细描述了 14 种统计检验、 12 种经验检验以及多种理论检验及谱检验等，并且推断， PRNG 的好坏取决于特定的应 用。本节将简单介绍几种那些最常用的统计检验。t 检验的基本步2.2.1 t 检验t 检验可用于只涉及两个样本平均数时的检验假设。两样本均数比较的 骤为：第一步建立假设并确定检验水准检验假设 H0: 1=2备择假设 H1: 12常取 =0.05或 =0.01第二步选定统计方法计算统计量统计量为自由度 =n1+n2-2其中，第三步

14、确定 P值和作出推断结论如 t t(n-1，则 P，其中 0 jn。每组中的元素可以有 t!种可能的相对顺序，应用 2检验，计算每种排序出 现的次数，其中 k=t! ，每种排序的概率为 1/t!。我们之所以选择此检验，由于在下面我们要考察的 PRNG 对 3Opt-TSP 应用中，我们 要求使用 PRNG 产生一个随机排列对相关的边进行优化，由于排列的不同，可能会导致优 化的次序不同，故不同的排列对 TSP 可能会有不同的作用，从而我们要对随机数进行排列 检验。2.3 PRNG 的统计性质我们对表 1 中的几种 PRNG 选择三种统计检验方法给出其性质检验。对每个 PRNG ， 我们运行三次，

15、分别产生 10 万个随机数来进行下面的统计检验。实验的运行环境如下： Pentium 4 CPU 2.80GHz, 512 MB 内存， Windows 平台， VC 6.0 。2.3.1 t 检验我们对上文提到的 PRNG 实现方法进行两两间的 t 检验，判断两个样本是否可能具有 相同的平均值。我们进行等方差双尾双样本假设检验，直接计算出 t 检验的 p-value，将 p- value 与 比较。如果 p-value ，则认为两个随机数序列有显著差异，即相应的随机数 发生器的性质质量不同。我们将 p-value 与 比较，这里我们取 =0.05。如果 P-value 为 125961703

16、，表格中数据为方法的 f 值与 f(mo 的比值。表 4 排列检验中 f 的值123A4.222.215.5B33.820.19.5C18.51.78.1D6.06.514.2E3.35.413.5MO111T1111T24.916.025.2对于一个好的随机序列，由于其随机性较好，当进行排列检验时，两两交换的次数增 多，会使得 f 值稍大些。从表 4中我们发现，在几次运行中，方法 T1 和方法 MO 的 f值相 当 ， 但 是 相 比 其 他 的 都 小 ， 则 我 们 认 为 方 法 MO 及 T1 劣 于 其 他 方 法 。2.4 本文 PRNG 统计检验小结对于我们在表 1中列举的一些

17、 PRNG 来说，在 2.1.6中我们指明了直观上它们之间存在 差异行为； 2.3 的统计性质检验表明，它们的确有差异。3. PRNG 在 3Opt-TSP 中的作用旅行商问题 Traveling Salesman Problem,TSP ）是一个典型的 NP难问题：已知 n个城 市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度为 所有路径之中的最小值？ACOTSP 软件包利用元启发方法 ACO 来解决 TSP 问题 8，组合以相对与 TSP 最好的 局部搜索 3Opt 方法9 这是一种

18、典型的 SLS 方法），我们把这种组合简称为3Opt-TSP 。3Opt-TSP 利用 PRNG 首先产生一个排列，长度为 TSP 实例规模，然后依次取排列的元素对 其相关的边进行局部优化。 3Opt 事实上是局部搜索 3-exchange 的一种近似 9。我们的工作策略是，在保持各个运行参数相同的情况下，在同一个运行平台 IBMp550 计算机，每个 powerPC 的主频为 1.5GHz；内存： 6825292kB ；操作系统： SuseLinux ；编译 器： gcc3.3.3 版本），针对 ACOTSP 软件包，利用不同的 PRNG 对 TSPLib 10中的实例进行 考试，从而考察不

19、同 PRNG 在应用中的影响。注意到表 1 中的 PRNG 生成速度不一样，但是在 3Opt-TSP 中调用 PRNG 的次数并不 多，所以我们假设 PRNG 生成时间上的差异不足以影响 3Opt-TSP 的最后结果。我们对 3Opt-TSP 选取了不同规模的不同实例进行了实验，其中小规模的实例5 个 （n，中规模实例 5 个（1000n ，大规模实例 3个（n3000 。我们对每个实例所得到的 1000 个 最好解进行统计检验分析。这里我们使用假设检验，假设 PRNG 与 TSP 的应用是独立的， 即不同的 PRNG 对 TSP 的应用结果是没有本质差别的。本程序运行的主要参数是：num-a

20、nts: 蚂蚁的个数，小中大规模分别设置为30、100 和 500；num-neighbour: 在解的建立过程中，每个城市的邻居数目，设为20；Alpha,Beta: 分别用来控制信息素与路径长度的相对重要程度，设为1.0， 2.2；Rho: 控制信息素的挥发力度，设为 0.5；max-tries: 一次执行时最大的次数 try ），设为 1000。由于随机性的作用，每种方法对同一个实例必须通过多次运行的统计结果来评价该方法，每一次这样的运 行称为一个 try ；max-time: 每个 try 的最大运行时间，小中大规模分别设为100s、 1000s 和 3000s。对于规模太小的 TSP

21、 实例如 eil50 ，kroA100 ，不管使用表 1 中何种 PRNG，都能得到 一样的最好解，即对 TSP 应用几乎看不出影响。对于另外三个小规模的实验结果见表5。表 5 对 TSP 其他小规模实例进行 t 检验的结果 概率 p-value)lin318att532rat783A&B0.1654771040.6196638621.76477 E-03A&C0.1654771040.6035071381.211066 E-03A&D0.1654771040.3647886057.862781 E-03A&E0.1654771040.6481344941.861635 E-03A&MO1.2

22、7234 E-343.4807 E-1870A&T14.68473 E-137.5971 E-535.7606 E-101A&T20.1654771040.7921913980.331014029B&C#DIV/0!0.9798199890.879995085B&D#DIV/0!0.1567784570.680157595B&E#DIV/0!0.33556941B&MO4.9182 E-375.9885 E-1860B&T13.76701 E-145.70259 E-518.89002 E-80B&T2#DIV/0!0.4436427220.034358285C&D4.9182 E-370.1

23、511547450.578666903C&E#DIV/0!0.3249596950.88056885C&MO4.9182 E-379.6427 E-1850C&T13.76701 E-141.80318 E-501.91558 E-77C&T2#DIV/0!0.430611010.025253343D&E#DIV/0!0.6482477560.681602955D&MO4.9182 E-372.2976 E-1960D&T13.76701 E-145.96291 E-591.55569 E-80D&T2#DIV/0!0.5175788230.094704323E&MO4.9182 E-371.

24、5809 E-1930E&T13.76701 E-141.56752 E-562.92308 E-79E&T2#DIV/0!0.8467786390.035246102MO&T10.0014326852.71765 E-645.5736 E-218MO&T24.9182 E-375.1251 E-1910T1&T23.76701 E-145.02956 E-551.6681 E-92表 5 显示了对不同实例的 1000 次所求的最好解 t 检验的结果。 表中字段值：“#DIV/0! ”：两种方法作用于 TSP 实例，分别得到的最好解序列的方差为0，导致除数为0 ，无法进行 t 检验。“ 0”：

25、两个序列平均值差异性显著。“1”：两个序列具有相同均值。)我们将 p 值与 比较，从表中我们发现：方法 MO 与其他 PRNG 进行 t 检验的 p值小于 。方法 T1 与其他 PRNG 进行 t 检验的 p值小于 。实例 rat783的 p值相比另两个实例 lin318 和 att532，小于 的 p值有些增加。 从而得出结论：对于一些小规模实例， PRNG 两两进行 t 检验后的 p值有很多明显小于 值，这说明我们的假设是不成立的，即我们认为这些 PRNG 对 3Opt-TSP 的影响是不同 的。接着，我们又分别对中规模和大规模的实例进行检验分析，统计结果如表 6 和表 7。 从表 6 中

26、的数据可以观察得到：1) A&D, A&E,A&T2,D&E 及 E&T2 等行的大部分数据仍大于 ，其他行的数据几乎 都比 小。2) 这些小于 的数据表明：不同 PRNG 对解决同一实例的最好解结果在统计意义上 存在着显著性差异。表 6 对 TSP 中规模实例进行 t 检验的结果 概率 p-value)pcb1173d1291fl1577rl1889pr2392A&B7.23397 E-081.3662 E-232.90054 E-493.75621 E-070.859860276A&C3.1759 E-2550000A&D0.105755750.5167732885.74804 E-080

27、.0405127320.759966283A&E0.8939329170.5469610770.0844432170.2835776180.994916191A&MO0000.4947469622.1366 E-43A&T100000A&T20.1559333386.84031 E-030.5236054140.8406496080.892477096B&C00000B&D1.19523 E-034.55079 E-217.15714 E-920.0024147430.877889612B&E2.23442 E-081.53446 E-212.72059 E-633.66797 E-050.8

28、62656112B&MO0004.65383 E-111.76221 E-54B&T100000B&T21.62544 E-137.74989 E-358.24623 E-541.56529 E-070.747697903C&D1.001 E-2650000C&E4.6282 E-2560000C&MO0#DIV/0!000C&T10#DIV/0!#DIV/0!01.3341 E-221C&T21.1889 E-2500000D&E0.0790850830.9582821351.5548 E-050.3063255340.761127896D&MO0000.0263875782.42537 E

29、-37D&T100000D&T22.31256 E-038.42566 E-041.58621 E-060.0254293750.661195849E&MO0000.4019635945.22885 E-46E&T100000E&T20.1972249338.98469 E-040.2793342150.204141160.885687052MO&T1#DIV/0!#DIV/0!0#DIV/0!0MO&T20000.3395475194.68785 E-45T1&T200000表7对TSP大规模实例进行 t检验的结果概率 p-value)fl3795fnl4461A&B9.95331 E-04

30、7.17985 E-11A&C3.2617 E-2306.32608 E-44A&D0.9882940580.887445928A&E0.7788850110.770660999A&MO00A&T100A&T2995331 E-040.043572736B&C01.09303 E-71B&D7.74121 E-041.26235 E-10B&E1.96599 E-041.46968 E-11B&MO00B&T100B&T29.92257 E-051.38343 E-06C&D3.4259 E-2335.39888 E-46C&E6.5305 E-2321.42091 E-41C&MO00C&T

31、100C&T21.412 E-2361.49267 E-59D&E0.788216970.663671706D&MO00D&T100D&T20.7427410970.058595668E&MO00E&T100E&T20.9557166170.02114812MO&T10#DIV/0!MO&T200T1&T200表 7 是大规模实例最好解进行 t 检验的结果，由表中数据可以观察得到：1) A&D, A&E,A&T2,D&E 及 D&T2 等行数据大于 。2 ) 除上面所说的行外，其他小于 的 p 值数据表明：不同 PRNG 对解决大规模实例 的最好解结果在统计意义上存在着显著性差异。我们发现，相

32、比小规模的实例统计结果，表6和表 7 中小于 的 p 值增多了。于是，我们有下面结论：对于表 1 中的 PRNG ，不管是应用到小规模的实例，还是中 规模、大规模的实例，进行 t 检验后，表中的统计数据 p 值都有一些远远小于我们的比较 参数 ，即对于 PRNG 应用于某些实例时，不同的 PRNG 所得到的结果有差异，从而说明 这些 PRNG 对 3Opt-TSP 有着不同的影响。4. PRNG 在 RLS-MCP 中的应用为了进一步验证我们的认识，我们进一步考察PRNG 在 RLS-MCP 中的作用。最大团问题 。如果一个团有 n 个点，则此团的大小为 n，问题就是找到满足条件的最大 n。R

33、LS(Reactive Local Search ，是利用反馈机制的一种 SLS 方法。运用在 MCP 问题中， 称为 RLS-MCP ，该方法是目前解决 MCP 问题的最好方法 11 。我们这里只比较三种 PRNG，一个是 RLS-MCP 软件包里的方法，记为 MO ；另外两个 是上文提到的方法 T1 与 T2。我们运行了 32 个实例，三种方法分别找到了最好解。为了进行 t 检验，我们对上面三种方法及 32 个实例，分别运行 1000 次。这里我们只 列出部分实例的统计结果。表 8对 MCP 运行结果进行的 t TestMO&T1MO&T2T1&T2C500.9#DIV/0!#DIV/0!

34、#DIV/0!C1000.93.0844E-1100.70441482.6578E-107C2000.98.80622E-320.3827979632.92714E-37DSJC500.5#DIV/0!#DIV/0!#DIV/0!DSJC1000.50.3174315990.317431599#DIV/0!C2000.56.06609 E-040.3381506560.010078639C4000.50.6456469360.9337396690.720677912MANN a27#DIV/0!#DIV/0!#DIV/0!MANN a451.64149E-170.5089809173.5940

35、2E-15MANN a812.33574E-140.5314660971.44273E-16brock200 41.0505E-174#DIV/0!1.0505E-174gen200 p0.9 44#DIV/0!#DIV/0!#DIV/0!gen200 p0.9 55#DIV/0!#DIV/0!#DIV/0!gen400 p0.9 55#DIV/0!#DIV/0!#DIV/0!gen400 p0.9 65#DIV/0!#DIV/0!#DIV/0!gen400 p0.9 75#DIV/0!#DIV/0!#DIV/0!keller60.982274680.6488086630.606030553p

36、 hat1500-10.1888905190.0902450160.703793862根据表 8 的统计数据分析，我们可以得到结论：1) 对于实例 C1000.9 , C2000.9 和 C2000.5 ，方法 T1 与 MO, T2 有着显著性差异。2) 对于实例 MANN_a45 和 MANN_a81 ，方法 T1与 MO, T2 有着显著性差异。对于实例 brock200_4 ，方法 T1 与 MO, T2 有着显著性差异。5. 结束语本文首先介绍了各种 PRNG 的实现方法及统计检验方法，选择了一些具有显著统计特 性的检验方法分别应用于这些 PRNG ，例如 t Test， Monte

37、 Carlo 及排列检验等。通过统计 分析，我们发现这些 PRNG 性质上存在着差异，即它们产生的随机数序列的质量不一样。接着我们将这些 PRNG 应用到 3Opt-TSP 和 RLS-MCP 问题中。对于 3Opt-TSP ，我们 选取了小、中、大三种规模的实例，将它们分别运行 1000 次，根据规模设定不同的蚂蚁数 及每次运行的时间，统计出它们所求出的最好解；对于 RLS-MCP ，我们选取了 RLS-MCP 软件包中的 32 个实例进行实验，运用了 MO, T1 和 T2 三种方法分别求最好解。我们对得 到的最好解进行 t 检验，根据检验结果及评价规则，从而得出：这些 PRNG 对 3O

38、pt-TSP 及 RLS-MCP 的这些实例有着不同的影响。这样的结果与我们的理解相一致：根据性质检验，方法A， B 等与 T1 、T2 、 MO 之间 存在着显著性的差异，它们的 3Opt-TSP 应用的实验结果也表明 PRNG 的选取对 3Opt-TSP 的应用有着影响，从而也与 Knuth 提出 PRNG 与应用有关这一观点相符合。下一步我们将继续通过考试更多的元启发解决 NP 难问题，并选用更加有力的检验方 法，以进一步研究 PRNG 对 SLS 的影响，并研究 SLS对 PRNG 的选择问题。 参考文献Holger H.Hoos and Thomas St tzle. Stochastic Local Search: Foundations and Applications.Morgan Kaufmann Publishers, 2004Dave A.D Tompkins and Holger H.Hoos. On the Quality and Quantity of Random Decisionin Stochasti