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

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

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

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

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

7、法 MO ，它就是我們 通常所使用的標(biāo)準(zhǔn)庫(kù)函數(shù) rand。素?cái)?shù)模乘同余法 1.2.1X i+1=aX i mod m i=0, 1 (2.2素?cái)?shù)模乘同余法 4通過(guò)滿足公式 (2.2 來(lái)產(chǎn)生隨機(jī)序列。我們把a(bǔ)=23,m=108+1，滿足公式(2.2 的 PRNG 稱(chēng)為方法 T2。最小標(biāo)準(zhǔn) ，Park 和 Miller 提出的最小標(biāo)準(zhǔn) 取參數(shù)設(shè)置： a=75=16807 ， m=231-1=2147483647 。但是其實(shí)現(xiàn)仍然很困難，由于32 位機(jī)上， a(m-1 大于計(jì)算機(jī)存儲(chǔ)的最大數(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 時(shí)，利 用公式 (2.3 ：(2.3就可以產(chǎn)生性能很好的隨機(jī)數(shù)，這里的參數(shù)主要是指a,q,r。如何選擇合適的 a,q,r 是這種類(lèi)型的 PRNG 的關(guān)鍵。我們把滿足 a=16807,q=127773,r=2836 的 PRNG 稱(chēng)為方法 A，這 也就是 ACOTSP 軟件包采用的 PRNG 。類(lèi)似地，滿足 a=48271,q=44488,r=3399 的 PRNG 稱(chēng) 為方法 B； a=69621,q=30845,r=23902 的 PRNG 稱(chēng)為方法 C。擴(kuò)大周期法 1.2.2利用兩個(gè)隨機(jī)數(shù)產(chǎn)生器相結(jié)合擴(kuò)大周期的方法5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、比小規(guī)模的實(shí)例統(tǒng)計(jì)結(jié)果，表6和表 7 中小于 的 p 值增多了。于是，我們有下面結(jié)論：對(duì)于表 1 中的 PRNG ，不管是應(yīng)用到小規(guī)模的實(shí)例，還是中 規(guī)模、大規(guī)模的實(shí)例，進(jìn)行 t 檢驗(yàn)后，表中的統(tǒng)計(jì)數(shù)據(jù) p 值都有一些遠(yuǎn)遠(yuǎn)小于我們的比較 參數(shù) ，即對(duì)于 PRNG 應(yīng)用于某些實(shí)例時(shí)，不同的 PRNG 所得到的結(jié)果有差異，從而說(shuō)明 這些 PRNG 對(duì) 3Opt-TSP 有著不同的影響。4. PRNG 在 RLS-MCP 中的應(yīng)用為了進(jìn)一步驗(yàn)證我們的認(rèn)識(shí)，我們進(jìn)一步考察PRNG 在 RLS-MCP 中的作用。最大團(tuán)問(wèn)題 。如果一個(gè)團(tuán)有 n 個(gè)點(diǎn)，則此團(tuán)的大小為 n，問(wèn)題就是找到滿足條件的最大 n。R

33、LS(Reactive Local Search ，是利用反饋機(jī)制的一種 SLS 方法。運(yùn)用在 MCP 問(wèn)題中， 稱(chēng)為 RLS-MCP ，該方法是目前解決 MCP 問(wèn)題的最好方法 11 。我們這里只比較三種 PRNG，一個(gè)是 RLS-MCP 軟件包里的方法，記為 MO ；另外兩個(gè) 是上文提到的方法 T1 與 T2。我們運(yùn)行了 32 個(gè)實(shí)例，三種方法分別找到了最好解。為了進(jìn)行 t 檢驗(yàn)，我們對(duì)上面三種方法及 32 個(gè)實(shí)例，分別運(yùn)行 1000 次。這里我們只 列出部分實(shí)例的統(tǒng)計(jì)結(jié)果。表 8對(duì) MCP 運(yùn)行結(jié)果進(jìn)行的 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)計(jì)數(shù)據(jù)分析，我們可以得到結(jié)論：1) 對(duì)于實(shí)例 C1000.9 , C2000.9 和 C2000.5 ，方法 T1 與 MO, T2 有著顯著性差異。2) 對(duì)于實(shí)例 MANN_a45 和 MANN_a81 ，方法 T1與 MO, T2 有著顯著性差異。對(duì)于實(shí)例 brock200_4 ，方法 T1 與 MO, T2 有著顯著性差異。5. 結(jié)束語(yǔ)本文首先介紹了各種 PRNG 的實(shí)現(xiàn)方法及統(tǒng)計(jì)檢驗(yàn)方法，選擇了一些具有顯著統(tǒng)計(jì)特 性的檢驗(yàn)方法分別應(yīng)用于這些 PRNG ，例如 t Test， Monte

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

38、pt-TSP 及 RLS-MCP 的這些實(shí)例有著不同的影響。這樣的結(jié)果與我們的理解相一致：根據(jù)性質(zhì)檢驗(yàn)，方法A， B 等與 T1 、T2 、 MO 之間 存在著顯著性的差異，它們的 3Opt-TSP 應(yīng)用的實(shí)驗(yàn)結(jié)果也表明 PRNG 的選取對(duì) 3Opt-TSP 的應(yīng)用有著影響，從而也與 Knuth 提出 PRNG 與應(yīng)用有關(guān)這一觀點(diǎn)相符合。下一步我們將繼續(xù)通過(guò)考試更多的元啟發(fā)解決 NP 難問(wèn)題，并選用更加有力的檢驗(yàn)方 法，以進(jìn)一步研究 PRNG 對(duì) SLS 的影響，并研究 SLS對(duì) PRNG 的選擇問(wèn)題。 參考文獻(xiàn)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