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

伪随机数发生器的统计性质检验及其应用摘要：在解决一些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-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 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, 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; Statistical Test; t Test; 3Opt-TSP; RLS-MCP11引言在科学研究中，我们常常需要用到随机数，然而真的随机数的产生比较复杂，因此我们通常使用伪随机数发生器PRNG。所谓“伪”是因为其产生的随机数并不是真正意义上的随机，而是在某个范围内是可预测的。随机局部搜索算法SLS是我们解决组合优化问题最有效、最广泛的方法之一。在SLS过程中都需要用到伪随机数发生器，PRNG在SLS中的应用是非常重要的。一般认为，不同的PRNG对SLS的影响是相同的1。但是这种观点至今仍没有相关的理论论证证明。对于实验支持的文献，就只有2：SLS算法中的随机决策的作用只是使搜索多样化，PRNG的质量和随机决策的数量都对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)产生随机序列，主要参数为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)的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很小，特别是rq，且0z t(n-1)，则P认为H0不成立否则不拒绝H0。2.2.2Monte Carlo Monte Carlo 方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。它是通过计算机产生的随机数，计算圆周率的值。随机数法求的近似值的思路：在一个单位边长的正方形中，以边长为半径，以一个顶点为圆心，在正方形上作四分之一圆，随机的向正方形内扔点，若落入四分之一圆内则计数；重复向正方形内扔足够多的点，将落入四分之一圆内的计数除以总的点数，其值就是值四分之一的近似值。Monte Carlo 是可以被称为独立地PRNG的性质测试，又可以被称为PRNG的最简单的应用。2.2.3排列检验对于输入序列U0,U1,Un-1，我们将其分为n组，每组t个元素，即(Ujt,Ujt+1, ,Ujt+t-1)，其中0jn。每组中的元素可以有t!种可能的相对顺序，应用2检验，计算每种排序出现的次数，其中k=t!，每种排序的概率为1/t!。我们之所以选择此检验，因为在下面我们要考察的PRNG对3Opt-TSP应用中，我们要求使用PRNG产生一个随机排列对相关的边进行优化，由于排列的不同，可能会导致优化的次序不同，故不同的排列对TSP可能会有不同的作用，从而我们要对随机数进行排列检验。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，则认为两个随机数序列有显著差异，即相应的随机数发生器的性质质量不同。我们将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求出的值最偏离圆周率的值，我们认为方法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中我们指明了直观上它们之间存在差异行为；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首先产生一个排列，长度为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-TSP的最后结果。我们对3Opt-TSP选取了不同规模的不同实例进行了实验，其中小规模的实例5个(n1000)，中规模实例5个(1000n3000)。我们对每个实例所得到的1000个最好解进行统计检验分析。这里我们使用假设检验，假设PRNG与TSP的应用是独立的，即不同的PRNG对TSP的应用结果是没有本质差别的。本程序运行的主要参数是：l num-ants: 蚂蚁的个数，小中大规模分别设置为30、100和500；l num-neighbour: 在解的建立过程中，每个城市的邻居数目，设为20；l Alpha, Beta : 分别用来控制信息素与路径长度的相对重要程度，设为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次所求的最好解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的影响是不同的。接着，我们又分别对中规模和大规模的实例进行检验分析，统计结果如表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对解决大规模实例的最好解结果在统计意义上存在着显著性差异。我们发现，相比小规模的实例统计结果，表S5和表S6中小于的p值增多了。于是，我们有下面结论：对于表1中的PRNG，不管是应用到小规模的实例，还是中规模、大规模的实例，进行t 检验后，表中的统计数据p值都有一些远远小于我们的比较参数，即对于PRNG应用于某些实例时，不同的PRNG所得到的结果有差异，从而说明这些PRNG对3Opt-TSP有着不同的影响。4PRNG在RLS-MCP中的应用为了进一步验证我们的认识，我们进一步考察PRNG在RLS-MCP中的作用。最大团问题（Maximum Clique Problem, MCP）：给定一个无向图G，要求G的最大团(团是指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的统计数据分析，我们可以得到结论：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问题中。对于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的应用有着影响，从而也与Knuth提出PRNG与应用有关这一观点相符合。下一步我们将继续通过测试更多的元启发解决NP难问题，并选用更加有力的检验方法，以进一步研究PRNG对SLS的影响，并研究SLS对PRNG的选择问题。References:1 Holger H.Hoos and Thomas Sttzle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann Publishers, 20042 Dave A.D Tompkins and Holger H.Hoos. On the Quality and 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 generators: good ones are hard to find. Communications of the ACM, 1988, 31(5):1192-12015 P. LEcuyer. Efficient and portable combined random number generators. Communications of the ACM, 1988, 31(6):742-7746 L. Schrage. A more portable fortran random number generator. ACM Transactions on Mathematical Software, 1979, 5(2):132-1387 William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C, chapter 7 Random Numbers. Cabrrige University Press, 19988 M. Dorigo, V. Maniezze and A. Colorni. The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man,and Cybernetics Part B: Cybernetics, 1996, 26(1):1-139 K. Helsgaun. An effiective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 2000, 126(1): 106-13010http:/www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB9511 Roberto Battiti and Marco Protasi. Reactive local Search for the Maximum clique problem. Algorithmica, 2001, 29(4):610-63712