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

1、伪随机数发生器的统计性质检验及其应用摘要：在解决一些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

2、），并对其结果利用有显著意义的统计检验进行测试分析，得出结论：本文多个prng对3opt-tsp和rls-mcp的影响是不同的。关键词：伪随机数发生器；统计检验；t 检验；3opt-tsp；rls-mcptowards the statistical properties of prng and its applicationabstract: when tackling many np-hard combinatorial optimization problems, a lot of excellent meta-heuristics must integrate some kind of

3、 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. by evaluating some significant statistical tests,

4、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-mcp. keywords: pseudo random number generator; statist

5、ical test; t test; 3opt-tsp; rls-mcp11引言在科学研究中，我们常常需要用到随机数，然而真的随机数的产生比较复杂，因此我们通常使用伪随机数发生器prng。所谓“伪”是因为其产生的随机数并不是真正意义上的随机，而是在某个范围内是可预测的。随机局部搜索算法sls是我们解决组合优化问题最有效、最广泛的方法之一。在sls过程中都需要用到伪随机数发生器，prng在sls中的应用是非常重要的。一般认为，不同的prng对sls的影响是相同的1。但是这种观点至今仍没有相关的理论论证证明。对于实验支持的文献，就只有2：sls算法中的随机决策的作用只是使搜索多样化，prng的质量

6、和随机决策的数量都对sls算法的执行没有特别重要的作用。但是，knuth提出prng与应用有关3，而且我们的理解也是：各种prng由于其所应用的具体问题不同，会体现出不一样的性质质量，即各种prng对问题的解决结果有优劣之分。为了验证，本文我们将对prng的性质进行统计检验，分析不同的prng之间是否有着差异；将这些prng运用到3opt-tsp和rls-mcp问题中，并对产生的结果进行分析统计，从而证实了prng对sls的影响是存在的。2常用的prng及其实现2.1常用的prng2.1.1线性同余法xi+1= (a xi +c) mod m i=0, 1 (1)线性同余法3通过满足公式(1)

7、产生随机序列，主要参数为a, c, m。只有选择合适的参数才能得到随机数的周期接近或达到m。我们把a=137, m=256,c=187用公式(1)产生的prng称为方法t1（周期为256）。类似的，我们把 a=1103515245/65536, c=12345/65536, m=32768 (在linux下可能为m=2147483647)用公式 (1)产生的prng称为方法mo，它就是我们通常所使用的标准库函数rand。2.1.2素数模乘同余法xi+1=a xi mod m i=0, 1 (2)素数模乘同余法4通过满足公式(2)来产生随机序列。我们把a=23,m=108+1，满足公式(2.2)

8、的prng称为方法t2。2.1.3最小标准（误差）的产生器实践中，利用公式(2)，park 和 miller 提出的最小标准（误差）的产生器4，通过了所有的理论测试，取得了成功的应用。该prng对公式(2)取参数设置：a=75=16807，m=231-1=2147483647。但是其实现仍然很困难，因为32位机上，a×(m-1)大于计算机存储的最大数。于是schrage 提出了分解m的方法6：命m=aq + r，例如，q=m/a，r=m mod a。如果r很小，特别是r<q，且0<z<m-1，那么0a(z mod q) m-1，0rz/q m-1时，利用公式(3)：

9、(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。2.1.4扩大周期法利用两个随机数产生器相结合扩大周期的方法5。假设结合前的两个序列分别为：序列1：x1a, x2a, xm1a, 周期为m1；序列2：x1b, x2b, xm2b, 周期为m2。那么对任意

10、非零整数ca, cb，公式(4)： (4)产生的xi就是新组合的随机序列。这里我们运用上面提到的最小标准（误差）的产生器的改进方法，a= 40014,q=3668,r=12211,m1=2147283563的prng生成序列1，a= 40692,q= 52774,r= 3791, m2=2147483399的prng生成序列2，结合后的周期大约为2.3×1018。常数ca=1, cb=-1，我们把利用公式(4)的prng称为方法d。2.1.5查表法knuth提出的加速方法3，是利用随机数序列相减得到的。利用公式：xn= (xn-55-xn-24), 55n79 (5)实现的思路为：利

11、用给定的初始值作为seed，构建一张并非真正随机的表(table)，长度取为56。然后利用此表产生随机数：对于一个序号为index的随机数，index要模56，使其处理后的序号可以对应到表中。利用公式(5)可以得到xindex，把xindex赋值给xn-56，改变table元素。从而利用新的table产生下一个随机数。我们把这样的prng称为方法e。2.1.6本文考察的prng小结上面我们主要介绍了本文要考察的prng，现将它们小结如下，见表1。2表1 本文考察的prng的实现方法及参数table 1 the prng methods and parameters of this paperp

12、rng名称实现方法及参数运行速度7t1公式(1) 其中a=137,m=256,c=1871.3mo公式(1) 标准库函数rand其中a=1103515245/65536,m=32768, c=12345/655361.3t2公式(2) 其中a=23，m=108+11.3a公式(3) 其中a=16807,q=127773,r=28361b公式(3) 其中a=48271,q=44488,r=33991c公式(3) 其中a=69621,q=30845,r=239021d公式(4) 其中m1=2147283563,m2=21474833990.6e公式(5)26表1中速度一列根据参考文献7以及我们的实

13、现获得，该栏数据越高表示相应的prng运行速度越快。我们之所以选取上面的几种prng是因为至少它们在程序行为上有明显的不同。l mo是默认的使用得最多的prng，一般在标准c库中就是使用这种方法，既然它可以被作为库函数使用，必有其独特之处。我们把它作为基准系统来看待。l t1方法可以明显看出周期相比mo缩短了很多，从随机序列行为上明显有别与mo。l t2方法使用了另外一种实现方法，但其周期比较大。l a,b,c是同一个prng，只是具有不同的参数，参数的设置不同，对prng的性质是否有影响。l e方法是速度最快的，它只要通过填表就能完成。但显然在随机序列的行为上哟比除t1外的prng简单得多。

14、l d方法是速度最慢的，它使用两个prng相结合的方法，这两个prng序列可由上面的prng产生，集合了上面几种prng的特点。2.2常用的统计性质检验上面我们介绍了一些prng，并在宏观上明显地指出它们是有差异的，那么在微观上如何描述一个随机序列的性质呢？knuth在其经典著作中3，详细描述了14种统计检验、12种经验检验以及多种理论检验和谱检验等，并且推断，prng的好坏取决于特定的应用。本节将简单介绍几种那些最常用的统计检验。2.2.1t 检验t检验可用于只涉及两个样本平均数时的检验假设。两样本均数比较的t检验的基本步骤为：第一步 建立假设并确定检验水准检验假设 h0: 1=2备择假设

15、h1: 12常取=0.05或=0.01第二步 选定统计方法计算统计量统计量为自由度=n1+n2-2其中， 第三步 确定p值并作出推断结论 如t> t(n-1)，则p<认为h0不成立否则不拒绝h0。2.2.2monte carlo monte carlo 方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。它是通过计算机产生的随机数，计算圆周率的值。随机数法求的近似值的思路：在一个单位边长的正方形中，以边长为半径，以一个顶点为圆心，在正方形上作四分之一圆，随机的向正方形内扔点，若落入四分之一圆内则计数；重复向正方形内扔足够多的点，将落入四分之一圆内的计数除以总的点数，其值就

16、是值四分之一的近似值。monte carlo 是可以被称为独立地prng的性质测试，又可以被称为prng的最简单的应用。2.2.3排列检验对于输入序列u0,u1,un-1，我们将其分为n组，每组t个元素，即(ujt,ujt+1, ,ujt+t-1)，其中0j<n。每组中的元素可以有t!种可能的相对顺序，应用2检验，计算每种排序出现的次数，其中k=t!，每种排序的概率为1/t!。我们之所以选择此检验，因为在下面我们要考察的prng对3opt-tsp应用中，我们要求使用prng产生一个随机排列对相关的边进行优化，由于排列的不同，可能会导致优化的次序不同，故不同的排列对tsp可能会有不同的作用

17、，从而我们要对随机数进行排列检验。2.3prng的统计性质我们对表1中的几种prng选择三种统计检验方法给出其性质检验。对每个prng，我们运行三次，分别产生10万个随机数来进行下面的统计检验。实验的运行环境如下：pentium 4 cpu 2.80ghz, 512 mb 内存，windows平台，vc 6.0。2.3.1t 检验我们对上文提到的prng实现方法进行两两间的t检验，判断两个样本是否可能具有相同的平均值。我们进行等方差双尾双样本假设检验，直接计算出t检验的p-value，将p-value与比较。如果p-value<，则认为两个随机数序列有显著差异，即相应的随机数发生器的性质

18、质量不同。我们将p-value与比较，这里我们取=0.05。如果p-value<，则认为两个随机数序列有显著差异，即相应的随机数发生器的性质质量不同。p-value详见表s112。根据表s1数据显示，从t检验的角度来说，我们可以结论：1）方法mo与其他方法存在着显著性的差异。2）方法t1与方法c存在着显著性的差异。2.3.2monte carlo 我们通过不同的prng实现方法产生不同的随机数序列，求出各个序列产生的的值，比较值之间的差异，进而判断prng之间是否有优劣区别。关于各种方法产生的随机数序列求值的结果如下表s212。我们仍然运用上面进行t检验的数据，我们发现方法mo求出的值最

19、偏离圆周率的值，我们认为方法mo在monte carlo 的测试中劣于其他方法。2.3.3排列检验表s312显示了多次应用排列检验算法后，当序列为递增序列时，f的值。这里以方法mo作为基准，其f值(f(mo)为125961703，表格中数据为方法的f值与f(mo)的比值。对于一个好的随机序列，由于其随机性较好，当进行排列检验时，两两交换的次数增多，会使得f值稍大些。从表s3中我们发现，在几次运行中，方法t1和方法mo的f值相当，但是相比其他的都小，则我们认为方法mo及t1劣于其他方法。2.4本文prng统计检验小结对于我们在表1中列举的一些prng来说，在2.1.6中我们指明了直观上它们之间存

20、在差异行为；2.3的统计性质检验表明，它们的确有差异。3prng在3opt-tsp中的作用旅行商问题（traveling salesman problem, tsp）是一个典型的np难问题：已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度为所有路径之中的最小值？acotsp软件包利用元启发方法aco来解决tsp问题8，组合以相对与tsp最好的局部搜索3opt方法9 （这是一种典型的sls方法），我们把这种组合简称为3opt-tsp。3opt-tsp利用prng首先产生一个排列，

21、长度为tsp实例规模，然后依次取排列的元素对其相关的边进行局部优化。3opt事实上是局部搜索3-exchange的一种近似9。我们的工作策略是，在保持各个运行参数相同的情况下，在同一个运行平台（ibmp550计算机，每个powerpc的主频为1.5ghz；内存：6825292kb；操作系统：suselinux；编译器：gcc3.3.3版本），针对acotsp软件包，利用不同的prng对tsplib10中的实例进行测试，从而考察不同prng在应用中的影响。注意到表1中的prng生成速度不一样，但是在3opt-tsp中调用prng的次数并不多，所以我们假设prng生成时间上的差异不足以影响3opt

22、-tsp的最后结果。我们对3opt-tsp选取了不同规模的不同实例进行了实验，其中小规模的实例5个(n<1000)，中规模实例5个(1000<n<3000)，大规模实例3个(n>3000)。我们对每个实例所得到的1000个最好解进行统计检验分析。这里我们使用假设检验，假设prng与tsp的应用是独立的，即不同的prng对tsp的应用结果是没有本质差别的。本程序运行的主要参数是：l num-ants: 蚂蚁的个数，小中大规模分别设置为30、100和500；l num-neighbour: 在解的建立过程中，每个城市的邻居数目，设为20；l alpha, beta : 分别

23、用来控制信息素与路径长度的相对重要程度，设为1.0，2.2；l rho: 控制信息素的挥发力度，设为0.5；l max-tries: 一次执行时最大的次数（try），设为1000。由于随机性的作用，每种方法对同一个实例必须通过多次运行的统计结果来评价该方法，每一次这样的运行称为一个try；l max-time: 每个try的最大运行时间，小中大规模分别设为100s、1000s和3000s。对于规模太小的tsp实例如eil50，kroa100，不管使用表1中何种prng，都能得到一样的最好解，即对tsp应用几乎看不出影响。对于另外三个小规模的实验结果见表s412。表s4显示了对不同实例的1000

24、次所求的最好解t 检验的结果。（表中字段值：“#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值有很多明显小于值，这说明我们的假设是不成立的，即我们认为这些prng对3opt-tsp的影响是不

25、同的。接着，我们又分别对中规模和大规模的实例进行检验分析，统计结果如表s5和s612。从表s5中的数据可以观察得到：1）a&d, a&e, a&t2, d&e及e&t2等行的大部分数据仍大于，其他行的数据几乎都比小。2）这些小于的数据表明：不同prng对解决同一实例的最好解结果在统计意义上存在着显著性差异。表s6是大规模实例最好解进行t检验的结果，由表中数据可以观察得到：1）a&d, a&e, a&t2, d&e及d&t2等行数据大于。2）除上面所说的行外，其他小于的p值数据表明：不同prng对解决大规模实例的最好

26、解结果在统计意义上存在着显著性差异。我们发现，相比小规模的实例统计结果，表s5和表s6中小于的p值增多了。于是，我们有下面结论：对于表1中的prng，不管是应用到小规模的实例，还是中规模、大规模的实例，进行t 检验后，表中的统计数据p值都有一些远远小于我们的比较参数，即对于prng应用于某些实例时，不同的prng所得到的结果有差异，从而说明这些prng对3opt-tsp有着不同的影响。4prng在rls-mcp中的应用为了进一步验证我们的认识，我们进一步考察prng在rls-mcp中的作用。最大团问题（maximum clique problem, mcp）：给定一个无向图g，要求g的最大团(

27、团是指g的一个完全子图,该子图不包含在任何其他的完全子图当中)。如果一个团有n个点，则此团的大小为n，问题就是找到满足条件的最大n。rls(reactive local search)，是利用反馈机制的一种sls方法。运用在mcp问题中，称为rls-mcp，该方法是目前解决mcp问题的最好方法11。我们这里只比较三种prng，一个是rls-mcp软件包里的方法，记为mo；另外两个是上文提到的方法t1与t2。我们运行了32个实例，三种方法分别找到了最好解。为了进行t检验，我们对上面三种方法及32个实例，分别运行1000次。这里我们只列出部分实例的统计结果。根据表s712的统计数据分析，我们可以得

28、到结论：1）对于实例c1000.9 , c2000.9和c2000.5，方法t1与mo, t2有着显著性差异。2）对于实例mann_a45和mann_a81，方法t1与mo, t2有着显著性差异。3）对于实例brock200_4，方法t1与mo, t2有着显著性差异。5结束语本文首先介绍了各种prng的实现方法及统计检验方法，选择了一些具有显著统计特性的检验方法分别应用于这些prng，例如t test，monte carlo 及排列检验等。通过统计分析，我们发现这些prng性质上存在着差异，即它们产生的随机数序列的质量不一样。接着我们将这些prng应用到3opt-tsp和rls-mcp问题中。

29、对于3opt-tsp，我们选取了小、中、大三种规模的实例，将它们分别运行1000次，根据规模设定不同的蚂蚁数及每次运行的时间，统计出它们所求出的最好解；对于rls-mcp，我们选取了rls-mcp软件包中的32个实例进行实验，运用了mo, t1和t2 三种方法分别求解最好解。我们对得到的最好解进行t 检验，根据检验结果及评价规则，从而得出：这些prng对3opt-tsp及rls-mcp 的这些实例有着不同的影响。这样的结果与我们的理解相一致：根据性质检验，方法a，b等与t1、t2、mo之间存在着显著性的差异，它们的3opt-tsp应用的实验结果也表明prng的选取对3opt-tsp的应用有着影

30、响，从而也与knuth提出prng与应用有关这一观点相符合。下一步我们将继续通过测试更多的元启发解决np难问题，并选用更加有力的检验方法，以进一步研究prng对sls的影响，并研究sls对prng的选择问题。references:1 holger h.hoos and thomas stützle. stochastic local search: foundations and applications. morgan kaufmann publishers, 20042 dave a.d tompkins and holger h.hoos. on the quality and

31、 quantity of random decision in stochastic local search for sat. proceedings of the nineteenth conference of the canadian society for computational studies of intelligence, 2006, 4013(6):1461583 donald knuth. the art of computer programming, volume 2, chapter 3 random numbers. addison-wesley publishing company, 19814 s.k. park and k.w. miller. random number