1、偽隨機數(shù)發(fā)生器統(tǒng)計性質(zhì)檢驗及其應用

1、Towards the Statistical Properties of PRNG and itsApplication偽隨機數(shù)發(fā)生器的統(tǒng)計性質(zhì)檢驗及其應用欒忠蘭呂強 *蘇州大學計算機科學與技術學院）【 摘 要】 在解決一些 NP 難的組合優(yōu)化問題時，很多優(yōu)秀的元啟發(fā)算法都利用了隨機局 部搜索 Stochastic Local Search, SLS ）策略。一般認為，不同的偽隨機數(shù)發(fā)生器PseudoRandom Number Generator, PRNG ）對 SLS 的影響是相同的。本文對 PRNG 進行統(tǒng)計性質(zhì) 考試，指出不同的 PRNG 之間有著不同的統(tǒng)計性質(zhì)。將各種不同的 PRN

2、G 應用于 SLS 算法 的典型應用： 3Opt 優(yōu)化旅行商問題 Traveling Salesman Problem,TSP ）及 RLS 優(yōu)化最大團 問題 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. 引言在科學研究中，我們常常需要用到隨機數(shù)，然而真的隨機數(shù)的產(chǎn)生比較復雜，因此我 們通常使用偽隨機數(shù)發(fā)生器PRNG。所謂 “偽 ”是由于其產(chǎn)生的隨機數(shù)并不是真正意義上的隨機，而是在某個范圍內(nèi)是可預測的。隨機局部搜索算法 SLS 是我們解決組合優(yōu)化問題最有效、最廣泛的方法之一。在 SLS 過

5、程中都需要用到偽隨機數(shù)發(fā)生器， PRNG 在 SLS 中的應用是非常重要的。一般認為，不 同的 PRNG 對 SLS 的影響是相同的 1 。但是這種觀點至今仍沒有相關的理論論證證明。對 于實驗支持的文獻，就只有 2：SLS算法中的隨機決策的作用只是使搜索多樣化，PRNG 的質(zhì)量和隨機決策的數(shù)量都對 SLS 算法的執(zhí)行沒有特別重要的作用。但是， Knuth 提出 PRNG 與應用有關 3，而且我們的理解也是：各種PRNG 由于其所應用的具體問題不同，會體現(xiàn)出不一樣的性質(zhì)質(zhì)量，即各種 PRNG 對問題的解決結(jié)果有優(yōu)劣之分。為了驗證，本 文我們將對 PRNG 的性質(zhì)進行統(tǒng)計檢驗，分析不同的 PRNG

6、 之間是否有著差異；將這些 PRNG 運用到 3Opt-TSP 和 RLS-MCP 問題中，并對產(chǎn)生的結(jié)果進行分析統(tǒng)計，從而證實了 PRNG 對 SLS 的影響是存在的。2. 常用的 PRNG 及其實現(xiàn)常用的 PRNG線性同余法 1.2.2Xi+1= (aX i+c mod m i=0, 1 (2 . 1 線性同余法 3通過滿足公式 (2.1 產(chǎn)生隨機序列，主要參數(shù)為a,c,m。只有選擇合適的參數(shù)才能得到隨機數(shù)的周期接近或達到m。我們把 a=137,m=256,c=187 用公式 (2.1 產(chǎn)生的PRNG 稱為方法 T1 ， c=12345/65536 用公式 (2.1產(chǎn)生的 PRNG 稱為方

7、法 MO ，它就是我們 通常所使用的標準庫函數(shù) rand。素數(shù)模乘同余法 1.2.1X i+1=aX i mod m i=0, 1 (2.2素數(shù)模乘同余法 4通過滿足公式 (2.2 來產(chǎn)生隨機序列。我們把a=23,m=108+1，滿足公式(2.2 的 PRNG 稱為方法 T2。最小標準 ，Park 和 Miller 提出的最小標準 取參數(shù)設置： a=75=16807 ， m=231-1=2147483647 。但是其實現(xiàn)仍然很困難，由于32 位機上， a(m-1 大于計算機存儲的最大數(shù)。于是 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就可以產(chǎn)生性能很好的隨機數(shù)，這里的參數(shù)主要是指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利用兩個隨機數(shù)產(chǎn)生器相結(jié)合擴大周期的方法5

9、。假設結(jié)合前的兩個序列分別為：序列 1：，周期為 m1；序列 2：，周期為 m2。那么對任意非零整數(shù)ca, cb，公式 (2.4：產(chǎn)生的 Xi 就是新組合的隨機序列。這里我們運用上面提到的最小標準 的 PRNG 稱為方法 D。查表法 1.2.2Knuth 提出的加速方法 3 ，是利用隨機數(shù)序列相減得到的。利用公式：Xn= (X n-55-X n-24, 55 n795 (2 .實現(xiàn)的思路為：利用給定的初始值作為seed，構建一張并非真正隨機的表 (Table，長度取為 56。然后利用此表產(chǎn)生隨機數(shù)：對于一個序號為index 的隨機數(shù)， index 要模 56 ，使其處理后的序號可以對應到表中。

10、利用公式 (2.5可以得到 Xindex，把 Xindex 賦值給 X n-56， 改變 Table 元素。從而利用新的 Table 產(chǎn)生下一個隨機數(shù)。我們把這樣的 PRNG 稱為方法 E。本文考察的 PRNG 小結(jié) 1.2.2面我們主要介紹了本文要考察的 PRNG ，現(xiàn)將它們小結(jié)如下，見表 1。表 1 本文考察的 PRNG 的實現(xiàn)方法及參數(shù)PRNG 名 稱實現(xiàn)方法及參數(shù)運行速度 7T1公式 (2.1 其中 a=137,m=256,c=1871.3MO公式 (2.1 標準庫函數(shù) 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 中速度一欄根據(jù)參考文獻 7 以及我們的實現(xiàn)獲得，該欄數(shù)據(jù)越高表示相應的PRNG 運行速度越快。 我們之所以選取上面的幾種 PRNG 是由于至少它們在程序行為上有明顯的不同。 MO 是默認的使用得最多的 PRNG ，一般在標準 C

12、 庫中就是使用這種方法，既然它可 以被作為庫函數(shù)使用，必有其獨特之處。我們把它作為基準系統(tǒng)來看待。 T1方法可以明顯看出周期相比 MO 縮短了很多，從隨機序列行為上明顯有別與MO。T2 方法使用了另外一種實現(xiàn)方法，但其周期比較大。A,B,C 是同一個 PRNG ，只是具有不同的參數(shù)，參數(shù)的設置不同，對 PRNG 的性質(zhì)是 否有影響。E 方法是速度最快的，它只要通過填表就能完成。但顯然在隨機序列的行為上喲比除T1 外的 PRNG 簡單得多。D 方法是速度最慢的，它使用兩個 PRNG 相結(jié)合的方法，這兩個 PRNG 序列可由上面 的 PRNG 產(chǎn)生，集合了上面幾種 PRNG 的特點。常用的統(tǒng)計性質(zhì)

13、檢驗上面我們介紹了一些 PRNG ，并在宏觀上明顯地指出它們是有差異的，那么在微觀上 如何描述一個隨機序列的性質(zhì)呢？ Knuth 在其經(jīng)典著作中 3 ，詳細描述了 14 種統(tǒng)計檢驗、 12 種經(jīng)驗檢驗以及多種理論檢驗及譜檢驗等，并且推斷， PRNG 的好壞取決于特定的應 用。本節(jié)將簡單介紹幾種那些最常用的統(tǒng)計檢驗。t 檢驗的基本步2.2.1 t 檢驗t 檢驗可用于只涉及兩個樣本平均數(shù)時的檢驗假設。兩樣本均數(shù)比較的 驟為：第一步建立假設并確定檢驗水準檢驗假設 H0: 1=2備擇假設 H1: 12常取 =0.05或 =0.01第二步選定統(tǒng)計方法計算統(tǒng)計量統(tǒng)計量為自由度 =n1+n2-2其中，第三步

14、確定 P值和作出推斷結(jié)論如 t t(n-1，則 P，其中 0 jn。每組中的元素可以有 t!種可能的相對順序，應用 2檢驗，計算每種排序出 現(xiàn)的次數(shù)，其中 k=t! ，每種排序的概率為 1/t!。我們之所以選擇此檢驗，由于在下面我們要考察的 PRNG 對 3Opt-TSP 應用中，我們 要求使用 PRNG 產(chǎn)生一個隨機排列對相關的邊進行優(yōu)化，由于排列的不同，可能會導致優(yōu) 化的次序不同，故不同的排列對 TSP 可能會有不同的作用，從而我們要對隨機數(shù)進行排列 檢驗。2.3 PRNG 的統(tǒng)計性質(zhì)我們對表 1 中的幾種 PRNG 選擇三種統(tǒng)計檢驗方法給出其性質(zhì)檢驗。對每個 PRNG ， 我們運行三次，

15、分別產(chǎn)生 10 萬個隨機數(shù)來進行下面的統(tǒng)計檢驗。實驗的運行環(huán)境如下： Pentium 4 CPU 2.80GHz, 512 MB 內(nèi)存， Windows 平臺， VC 6.0 。2.3.1 t 檢驗我們對上文提到的 PRNG 實現(xiàn)方法進行兩兩間的 t 檢驗，判斷兩個樣本是否可能具有 相同的平均值。我們進行等方差雙尾雙樣本假設檢驗，直接計算出 t 檢驗的 p-value，將 p- value 與 比較。如果 p-value ，則認為兩個隨機數(shù)序列有顯著差異，即相應的隨機數(shù) 發(fā)生器的性質(zhì)質(zhì)量不同。我們將 p-value 與 比較，這里我們?nèi)?=0.05。如果 P-value 為 125961703

16、，表格中數(shù)據(jù)為方法的 f 值與 f(mo 的比值。表 4 排列檢驗中 f 的值123A4.222.215.5B33.820.19.5C18.51.78.1D6.06.514.2E3.35.413.5MO111T1111T24.916.025.2對于一個好的隨機序列，由于其隨機性較好，當進行排列檢驗時，兩兩交換的次數(shù)增 多，會使得 f 值稍大些。從表 4中我們發(fā)現(xiàn)，在幾次運行中，方法 T1 和方法 MO 的 f值相 當 ， 但 是 相 比 其 他 的 都 小 ， 則 我 們 認 為 方 法 MO 及 T1 劣 于 其 他 方 法 。2.4 本文 PRNG 統(tǒng)計檢驗小結(jié)對于我們在表 1中列舉的一些

17、 PRNG 來說，在 2.1.6中我們指明了直觀上它們之間存在 差異行為； 2.3 的統(tǒng)計性質(zhì)檢驗表明，它們的確有差異。3. PRNG 在 3Opt-TSP 中的作用旅行商問題 Traveling Salesman Problem,TSP ）是一個典型的 NP難問題：已知 n個城 市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度為 所有路徑之中的最小值？ACOTSP 軟件包利用元啟發(fā)方法 ACO 來解決 TSP 問題 8，組合以相對與 TSP 最好的 局部搜索 3Opt 方法9 這是一種

18、典型的 SLS 方法），我們把這種組合簡稱為3Opt-TSP 。3Opt-TSP 利用 PRNG 首先產(chǎn)生一個排列，長度為 TSP 實例規(guī)模，然后依次取排列的元素對 其相關的邊進行局部優(yōu)化。 3Opt 事實上是局部搜索 3-exchange 的一種近似 9。我們的工作策略是，在保持各個運行參數(shù)相同的情況下，在同一個運行平臺 IBMp550 計算機，每個 powerPC 的主頻為 1.5GHz；內(nèi)存： 6825292kB ；操作系統(tǒng)： SuseLinux ；編譯 器： gcc3.3.3 版本），針對 ACOTSP 軟件包，利用不同的 PRNG 對 TSPLib 10中的實例進行 考試，從而考察不

19、同 PRNG 在應用中的影響。注意到表 1 中的 PRNG 生成速度不一樣，但是在 3Opt-TSP 中調(diào)用 PRNG 的次數(shù)并不 多，所以我們假設 PRNG 生成時間上的差異不足以影響 3Opt-TSP 的最后結(jié)果。我們對 3Opt-TSP 選取了不同規(guī)模的不同實例進行了實驗，其中小規(guī)模的實例5 個 （n，中規(guī)模實例 5 個（1000n ，大規(guī)模實例 3個（n3000 。我們對每個實例所得到的 1000 個 最好解進行統(tǒng)計檢驗分析。這里我們使用假設檢驗，假設 PRNG 與 TSP 的應用是獨立的， 即不同的 PRNG 對 TSP 的應用結(jié)果是沒有本質(zhì)差別的。本程序運行的主要參數(shù)是：num-a

20、nts: 螞蟻的個數(shù)，小中大規(guī)模分別設置為30、100 和 500；num-neighbour: 在解的建立過程中，每個城市的鄰居數(shù)目，設為20；Alpha,Beta: 分別用來控制信息素與路徑長度的相對重要程度，設為1.0， 2.2；Rho: 控制信息素的揮發(fā)力度，設為 0.5；max-tries: 一次執(zhí)行時最大的次數(shù) try ），設為 1000。由于隨機性的作用，每種方法對同一個實例必須通過多次運行的統(tǒng)計結(jié)果來評價該方法，每一次這樣的運 行稱為一個 try ；max-time: 每個 try 的最大運行時間，小中大規(guī)模分別設為100s、 1000s 和 3000s。對于規(guī)模太小的 TSP

21、 實例如 eil50 ，kroA100 ，不管使用表 1 中何種 PRNG，都能得到 一樣的最好解，即對 TSP 應用幾乎看不出影響。對于另外三個小規(guī)模的實驗結(jié)果見表5。表 5 對 TSP 其他小規(guī)模實例進行 t 檢驗的結(jié)果 概率 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 檢驗的結(jié)果。 表中字段值：“#DIV/0! ”：兩種方法作用于 TSP 實例，分別得到的最好解序列的方差為0，導致除數(shù)為0 ，無法進行 t 檢驗?！?0”：

25、兩個序列平均值差異性顯著?！?”：兩個序列具有相同均值。)我們將 p 值與 比較，從表中我們發(fā)現(xiàn)：方法 MO 與其他 PRNG 進行 t 檢驗的 p值小于 。方法 T1 與其他 PRNG 進行 t 檢驗的 p值小于 。實例 rat783的 p值相比另兩個實例 lin318 和 att532，小于 的 p值有些增加。 從而得出結(jié)論：對于一些小規(guī)模實例， PRNG 兩兩進行 t 檢驗后的 p值有很多明顯小于 值，這說明我們的假設是不成立的，即我們認為這些 PRNG 對 3Opt-TSP 的影響是不同 的。接著，我們又分別對中規(guī)模和大規(guī)模的實例進行檢驗分析，統(tǒng)計結(jié)果如表 6 和表 7。 從表 6 中

26、的數(shù)據(jù)可以觀察得到：1) A&D, A&E,A&T2,D&E 及 E&T2 等行的大部分數(shù)據(jù)仍大于 ，其他行的數(shù)據(jù)幾乎 都比 小。2) 這些小于 的數(shù)據(jù)表明：不同 PRNG 對解決同一實例的最好解結(jié)果在統(tǒng)計意義上 存在著顯著性差異。表 6 對 TSP 中規(guī)模實例進行 t 檢驗的結(jié)果 概率 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大規(guī)模實例進行 t檢驗的結(jié)果概率 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 是大規(guī)模實例最好解進行 t 檢驗的結(jié)果，由表中數(shù)據(jù)可以觀察得到：1) A&D, A&E,A&T2,D&E 及 D&T2 等行數(shù)據(jù)大于 。2 ) 除上面所說的行外，其他小于 的 p 值數(shù)據(jù)表明：不同 PRNG 對解決大規(guī)模實例 的最好解結(jié)果在統(tǒng)計意義上存在著顯著性差異。我們發(fā)現(xiàn)，相

32、比小規(guī)模的實例統(tǒng)計結(jié)果，表6和表 7 中小于 的 p 值增多了。于是，我們有下面結(jié)論：對于表 1 中的 PRNG ，不管是應用到小規(guī)模的實例，還是中 規(guī)模、大規(guī)模的實例，進行 t 檢驗后，表中的統(tǒng)計數(shù)據(jù) p 值都有一些遠遠小于我們的比較 參數(shù) ，即對于 PRNG 應用于某些實例時，不同的 PRNG 所得到的結(jié)果有差異，從而說明 這些 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 次。這里我們只 列出部分實例的統(tǒng)計結(jié)果。表 8對 MCP 運行結(jié)果進行的 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根據(jù)表 8 的統(tǒng)計數(shù)據(jù)分析，我們可以得到結(jié)論：1) 對于實例 C1000.9 , C2000.9 和 C2000.5 ，方法 T1 與 MO, T2 有著顯著性差異。2) 對于實例 MANN_a45 和 MANN_a81 ，方法 T1與 MO, T2 有著顯著性差異。對于實例 brock200_4 ，方法 T1 與 MO, T2 有著顯著性差異。5. 結(jié)束語本文首先介紹了各種 PRNG 的實現(xiàn)方法及統(tǒng)計檢驗方法，選擇了一些具有顯著統(tǒng)計特 性的檢驗方法分別應用于這些 PRNG ，例如 t Test， Monte

37、 Carlo 及排列檢驗等。通過統(tǒng)計 分析，我們發(fā)現(xiàn)這些 PRNG 性質(zhì)上存在著差異，即它們產(chǎn)生的隨機數(shù)序列的質(zhì)量不一樣。接著我們將這些 PRNG 應用到 3Opt-TSP 和 RLS-MCP 問題中。對于 3Opt-TSP ，我們 選取了小、中、大三種規(guī)模的實例，將它們分別運行 1000 次，根據(jù)規(guī)模設定不同的螞蟻數(shù) 及每次運行的時間，統(tǒng)計出它們所求出的最好解；對于 RLS-MCP ，我們選取了 RLS-MCP 軟件包中的 32 個實例進行實驗，運用了 MO, T1 和 T2 三種方法分別求最好解。我們對得 到的最好解進行 t 檢驗，根據(jù)檢驗結(jié)果及評價規(guī)則，從而得出：這些 PRNG 對 3O

38、pt-TSP 及 RLS-MCP 的這些實例有著不同的影響。這樣的結(jié)果與我們的理解相一致：根據(jù)性質(zhì)檢驗，方法A， B 等與 T1 、T2 、 MO 之間 存在著顯著性的差異，它們的 3Opt-TSP 應用的實驗結(jié)果也表明 PRNG 的選取對 3Opt-TSP 的應用有著影響，從而也與 Knuth 提出 PRNG 與應用有關這一觀點相符合。下一步我們將繼續(xù)通過考試更多的元啟發(fā)解決 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