對偽隨機數(shù)生成算法的隨機性評價方法的研究

丁豪杰， 唐 迪， 姚 琳， 顧幸生

(1. 上海立信會計金融學(xué)院 校長辦公室， 上海 201209； 2. 華東理工大學(xué) 化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室， 上海 200237； 3. 云南師范大學(xué)文理學(xué)院， 昆明 650222； 4. 上海第二工業(yè)大學(xué) 工學(xué)部， 上海 201209 )

目前較為流行的啟發(fā)式算法中，有一類基于種群的元啟發(fā)式算法，對于解決諸如生產(chǎn)調(diào)度等被證明屬于NP-complete或NP-hard問題的實際問題已經(jīng)取得了不俗的成果[1]。這類基于種群的元啟發(fā)式算法被稱為群智能算法[2]。

調(diào)度是使用一定的基本規(guī)則在眾多制造業(yè)和服務(wù)業(yè)中進行決策的過程,它研究在給定的時間周期內(nèi)將稀缺(或有限)的資源分配給待執(zhí)行的任務(wù)，目標是優(yōu)化一個或多個目標[3]。以汽車等機械加工制造企業(yè)的生產(chǎn)為例，企業(yè)的生產(chǎn)調(diào)度任務(wù)就是優(yōu)化資源分配，合理分配生產(chǎn)計劃任務(wù)[4]。當生產(chǎn)加工和整車裝配過程中出現(xiàn)未預(yù)期事件，如生產(chǎn)設(shè)備故障、某些零部件的加工時間異常、部件原材料供應(yīng)發(fā)生問題導(dǎo)致無法及時生產(chǎn)等問題，都要及時予以處理，以保證企業(yè)的生產(chǎn)能正常進行[5]。類似的調(diào)度問題處理都可以轉(zhuǎn)化成為對隨機優(yōu)化問題的處理。

運用群智能算法借助計算機處理此類隨機優(yōu)化問題時，往往采用全局搜索與局部搜索相結(jié)合的方法進行，在開始階段以全局搜索為主，而在后續(xù)階段則以局部的鄰域搜索為主。群智能算法在搜索過程中，需要大量的隨機數(shù)對算法進行支持，故隨機數(shù)的選取成為一個不可忽視和回避的問題。在全局搜索階段，為不遺漏可能的解，應(yīng)盡可能使與隨機數(shù)相對應(yīng)的解充滿整個解空間，宜選用符合均勻分布的隨機數(shù)；而在后續(xù)有趨勢解呈現(xiàn)時，則可以選擇符合某種分布的隨機數(shù)來加速求解，后者主要靠前者與經(jīng)驗及規(guī)則函數(shù)配合完成。由于目前啟發(fā)式算法主要借助于計算機來完成，因此，使用計算機來產(chǎn)生隨機數(shù)從而完成相應(yīng)的求解是必要的步驟。但由于目前的主流計算機設(shè)計架構(gòu)尚未突破馮·諾依曼體系架構(gòu)[6]，真正的隨機數(shù)是無法在馮·諾依曼機上產(chǎn)生和實現(xiàn)的(參閱下文之基本概念)，只能依靠采用以偽隨機數(shù)算法指導(dǎo)的程序生成偽隨機數(shù)序列來進行近似逼近。因此，一個盡量隨機的偽隨機數(shù)算法是必要的。這種指導(dǎo)程序生成偽隨機數(shù)序列算法的隨機性決定了該算法的性能。正確的評價一個偽隨機數(shù)生成算法的性能，對指導(dǎo)實際求解問題的開展具有決定意義。

本文以運用群智能算法求解生產(chǎn)調(diào)度問題為例，對正確評價偽隨機數(shù)生成算法進行深入探討和研究。

1 基本概念

1.1 隨機數(shù)

隨機數(shù)是指一組不能被預(yù)測的數(shù)字或符號序列，這些數(shù)字和序列是完全偶然產(chǎn)生的[7]，即隨機數(shù)是客觀世界不確定性的理論抽象[8]。隨著概率論及數(shù)理統(tǒng)計等學(xué)科的發(fā)展，研究人員對隨機數(shù)的產(chǎn)生機理等逐漸明晰。同時，為了研究的深入進行，從軟硬件等方面盡可能設(shè)計了多種計算機實現(xiàn)方法。但是，依據(jù)馮·諾依曼架構(gòu)設(shè)計的計算機在不借助于外部硬件，僅從軟件自身角度，真實的隨機數(shù)是無法實現(xiàn)的。因為馮·諾依曼機自身的架構(gòu)決定了這種機型只能做“按存儲指令的順序來執(zhí)行具體指令”的確定性行為。

1.2 馮·諾依曼機和馮·諾依曼架構(gòu)

馮·諾依曼機是指使用馮諾依曼體系架構(gòu)的電子數(shù)字計算機。早在1945年2月，世界上第一臺電腦誕生前，馮·諾依曼就提出了在數(shù)字計算機內(nèi)部的存儲器中存放程序的概念，正是按照馮·諾依曼的設(shè)計理念，在美國的賓夕法尼亞大學(xué)設(shè)計實現(xiàn)了第一臺計算機ENIAC[9]，用以計算彈道軌道。這是當今主流計算機的模板，被稱為馮·諾依曼結(jié)構(gòu)[10]，目前，所有在用的成熟計算機設(shè)備均采用馮·諾依曼結(jié)構(gòu)設(shè)計。馮·諾依曼機主要由邏輯運算單元、控制器、存儲單元、輸入輸出設(shè)備和其間相關(guān)總線組成，主要特點是：① 程序經(jīng)編譯后形成固定順序的指令，以二進制代碼的形式存放在存儲器中；② 所有的指令都是由操作碼和地址碼組成；③ 指令按照存儲的順序調(diào)入內(nèi)部的堆棧，并進行調(diào)用；④ 以邏輯運算單元和控制器作為計算機處理的中心，并依次執(zhí)行指令。

由上述馮·諾依曼機設(shè)計架構(gòu)的特點可以推斷出：其內(nèi)部的每一個核心在調(diào)用和執(zhí)行指令時是一種串行機理，執(zhí)行結(jié)果只依賴于存儲的程序和編譯生成的指令代碼調(diào)用次序。因此，依據(jù)馮·諾依曼機架構(gòu)設(shè)計制造的計算機只能精確而有序地實現(xiàn)程序指令，不具備隨機不確定性，在不引入外部隨機量的情況下，單純依靠精確而有序地執(zhí)行指令的馮·諾依曼機自身來產(chǎn)生真隨機數(shù)，本身就是一個悖論。因此，只能使用偽隨機數(shù)來逼近真實的隨機數(shù)。

1.3 偽隨機數(shù)和偽隨機數(shù)生成器

偽隨機數(shù)則是指一組特性接近隨機數(shù)特性的數(shù)的序列，多由偽隨機數(shù)生成器產(chǎn)生[11]。偽隨機數(shù)生成器也被稱為確定的隨機二進制數(shù)位生成器，是生成一組偽隨機數(shù)的算法。由上述定義及相關(guān)研究[12]可知，偽隨機數(shù)實際是確定的數(shù)的序列，只是其序列周期的長度遠長于所研究的問題集分布序列的長度。而在基于馮·諾依曼架構(gòu)的計算機上，不依靠外部設(shè)備引入隨機性，只能通過計算機程序產(chǎn)生偽隨機數(shù)序列，該程序即相當于偽隨機數(shù)生成器。

2 偽隨機數(shù)評價方法構(gòu)建

2.1 偽隨機數(shù)算法評價的必要性

當今，各領(lǐng)域所使用的主流計算機均未突破馮·諾依曼機的設(shè)計理念。各領(lǐng)域若僅借助于計算機進行研究，其所需的隨機數(shù)只能通過偽隨機數(shù)生成器程序所生成的偽隨機數(shù)序列逼近。如何選擇適用于待解問題的已有偽隨機數(shù)生成器程序，或如何改進已有的偽隨機數(shù)生成算法，編制適合于待解問題的偽隨機數(shù)生成程序具有重要意義。正確的選擇或改進已有的偽隨機數(shù)生成算法就必須要對待研究的偽隨機數(shù)算法進行正確的評價。根據(jù)沒有免費午餐定理[13]，任何相對較優(yōu)的算法，不可能對該領(lǐng)域的所有問題均產(chǎn)生同樣顯著的效果；其只會在某些問題上產(chǎn)生較優(yōu)的效果，而在另一些問題上則不會產(chǎn)生顯著效果。因此，問題不同，指導(dǎo)程序設(shè)計的偽隨機數(shù)算法就可能不同，正確評價才能針對特定問題產(chǎn)生有效的隨機數(shù)。

2.2 新評價方法的設(shè)計誘因

對隨機數(shù)性能的評價主要基于對其測試的基礎(chǔ)之上?，F(xiàn)有的主要測試方法是使用美國國家標準與技術(shù)研究院(National Iustitute of Standards and Technology, NIST)隨機性測試方法中的一種或幾種組合，NIST隨機性測試方法主要包括：頻數(shù)測試、塊內(nèi)頻數(shù)測試、游程測試、塊內(nèi)最長連續(xù)“1”測試、矩陣秩測試、離散傅里葉變換測試、非重疊模板匹配測試、重疊模板匹配測試、通用統(tǒng)計測試、壓縮測試、線性復(fù)雜度測試、連續(xù)性測試、近似熵測試、部分和測試、隨機游走測試及隨機游走變量測試等[14]。

由于傳統(tǒng)偽隨機數(shù)生成器的測試方法過于關(guān)注其數(shù)學(xué)性能，即關(guān)注于評價其是否符合某些隨機分布的特性，而忽略了其工程應(yīng)用方面的實際需求，使得設(shè)計的算法過于復(fù)雜。根據(jù)自身領(lǐng)域經(jīng)驗，針對符合均勻隨機分布的偽隨機數(shù)生成器的測試，本文提出了新的測試方法，并用此測試方法對偽隨機數(shù)的性能進行了評價，從而達到了對所測試的偽隨機數(shù)算法進行正確評價的目的。

2.3 新評價方法的設(shè)計實現(xiàn)

由于研究的數(shù)字應(yīng)服從均勻分布，其數(shù)值中的各個權(quán)重位上的數(shù)字均應(yīng)呈現(xiàn)出均勻隨機特性，即在0～9的10個數(shù)字中均勻產(chǎn)生。據(jù)此，可以將所需精度的數(shù)字一分為二，作為類似位圖填充的橫、縱坐標點來進行考量，即在前半部分和后半部分數(shù)字形成的平面坐標點所對應(yīng)的位置進行填充。具體實施時，可以借助二維0-1矩陣來較為簡捷地實現(xiàn)。此時隨機數(shù)的前半部分和后半部分數(shù)字對應(yīng)著矩陣具體的行數(shù)和列數(shù)。

以0到1間服從均勻分布的2位有效數(shù)字的偽隨機數(shù)生成器為例，此時可以構(gòu)建10×10的初始零矩陣M，如果生成器產(chǎn)生了偽隨機數(shù)0.34，則對應(yīng)將M(3，4)置1，此時可以利用相關(guān)軟件對此0-1矩陣繪圖，將矩陣值為1的方格進行填充，如圖1所示(為突出顯示效果，應(yīng)盡量用深色表示矩陣中較少的顏色)。最終在執(zhí)行若干次類似操作后，M矩陣的相應(yīng)元素將會被陸續(xù)置1，此時繪出的填充示例圖可以直觀表示出所產(chǎn)生隨機數(shù)的分布狀態(tài)?？紤]到隨機數(shù)生成器的數(shù)學(xué)特性，測試執(zhí)行的次數(shù)應(yīng)與矩陣元素的個數(shù)相等；否則，從概率角度審視，過多的執(zhí)行次數(shù)會使整個矩陣絕大部分元素置1，一方面無法考察其隨機特性，另一方面使相應(yīng)繪出的矩陣填充圖失去其應(yīng)有的直觀性。另外，為了直觀起見，選擇測試有效位數(shù)時，應(yīng)盡可能選擇偶數(shù)位數(shù)的偽隨機數(shù)，以便于對等拆分，并在拆分之后以前后兩個數(shù)字作為坐標生成相應(yīng)的方陣和繪制相應(yīng)的測試結(jié)果示例圖。

圖1 示例說明

3 新測試評價過程實例

本文選擇了3種偽隨機數(shù)算法指導(dǎo)下編制的程序，即目前程序設(shè)計中常用的C語言自帶的rand()隨機函數(shù)，Kiss隨機函數(shù)和Mersenne隨機函數(shù)[15]。測試在SUSE Linux Enterprise 12軟件虛擬機平臺上進行，使用C語言編程調(diào)用相關(guān)函數(shù)進行測試，并借助Matlab 2015b軟件對生成的矩陣進行填充圖繪制?？紤]到位圖較小，為了增強圖像色差效果，便于對比觀察，繪圖時省略了網(wǎng)格線，并且用淺色表示矩陣中較多的元素“1”，用深色表示矩陣中相對較少的元素“0”。執(zhí)行次數(shù)定為10 000次(100×100)，對初始零矩陣的覆蓋率(最終矩陣中1的元素個數(shù)與矩陣總元素的百分比)，及首次達到60%覆蓋率所執(zhí)行的次數(shù)進行了考察，結(jié)果如表1所示。首次達到60%覆蓋率直觀顯示了算法的分散度或隨機性。

表1 測試結(jié)果對比

*矩陣M為M1、M2與M3運算合成，而非程序生成，故“覆蓋率首次達60%的執(zhí)行次數(shù)”處填“-”。

從表1中可以看出，3種方法各方面數(shù)據(jù)相差并不顯著，但是所示的矩陣填充圖卻直觀給出了3種函數(shù)具體的數(shù)值分布情況。仔細觀察3張?zhí)畛鋱D，可以發(fā)現(xiàn)3個偽隨機函數(shù)生成器所產(chǎn)生的偽隨機數(shù)分布是有錯落的。據(jù)此，對3張圖進行類似位圖的異或邏輯運算，即比對3個矩陣，凡是對應(yīng)位置元素相異的則置1，最終生成矩陣M如圖2所示(M=M1?M2?M3)，其覆蓋率和對應(yīng)的矩陣填充圖列于表格的最后一行。也有了產(chǎn)生新偽隨機數(shù)方法的一種啟示，即依靠機理不同的偽隨機數(shù)算法簡單加權(quán)組合生成新的偽隨機數(shù)算法。

圖2 M1、M2、M3矩陣重疊為M矩陣

4 實例分析和討論

4.1 實例分析

由表1可以看出，最后一行組合后的矩陣填充圖的效果最好，其覆蓋率達到了95.09%，而單獨的每一個偽隨機函數(shù)生成器所產(chǎn)生的隨機數(shù)覆蓋率只有63%左右。這主要是合成圖相當于每次填充時進行了3次隨機填充，即執(zhí)行了原迭代次數(shù)的3倍(30 000次)。為統(tǒng)一比較單獨偽隨機數(shù)函數(shù)與組合偽隨機數(shù)函數(shù)的優(yōu)劣，本文以上述3個偽隨機函數(shù)為基礎(chǔ)，計算所得數(shù)據(jù)平均值如表2所示。

表2中使用了簡單的等權(quán)組合各種偽隨機數(shù)算法。由表2不難看出，對偽隨機函數(shù)算法進行不同組合，有可能會指導(dǎo)產(chǎn)生效果更好的偽隨機數(shù)生成器，如同樣進行2次填充，M12偽隨機數(shù)生成器覆蓋范圍更大。這啟示當采用不同的組合加權(quán)系數(shù)時，有機會生成效果更適合的偽隨機數(shù)生成器。

4.2 測試評價過程理論分析

對比表1和表2可以發(fā)現(xiàn)：每種方法的覆蓋率與函數(shù)無關(guān)，只與函數(shù)的個數(shù)有關(guān)，其原因可以用離散性隨機變量的概率進一步證明。論證如下：

表2 函數(shù)組合測試結(jié)果

說明：表中“×2”表示每次填充時進行了2次隨機填充，“×3”表示每次填充時進行了3次隨機填充。

上述每次繪點的過程是完全獨立的，而點的位置也是隨機的，因此，該過程可以看成是符合伯努利二項式分布的。其可以對應(yīng)為初始零矩陣中的元素被選中置1的事件過程。

設(shè)隨機變量X表示：初始零矩陣中的元素被選中置1的事件，則X～B(n,p)。其中，

n=10 000，p=1/10 000

由于此時n很大，且p很小，故可近似認定X服從泊松分布，即X～P(λ)。其中，

λ=np=1

因此，初始零矩陣每次置1的事件概率為

P(X)=P{X=1}+P{X=2}+…+

P{X=10 000}=1-P{X=0}=

1-e-1=63.21%

由此證明可以推知：表1中的初始零矩陣覆蓋率維系在63%附近是合理的；選取“覆蓋率首次達到60%的執(zhí)行次數(shù)”來體現(xiàn)函數(shù)的速度也是恰當?shù)?；同時還證明實驗中所選的偽隨機函數(shù)生成器都具有良好的數(shù)學(xué)特性，是值得信賴的。當進一步使用兩種隨機函數(shù)混合運算時，并不是簡單對兩個函數(shù)求均值，而是在一次置1的事件過程中依次使用隨機函數(shù)對初始零矩陣置1。

再設(shè)所選用的每一個偽隨機函數(shù)具有上述數(shù)學(xué)特性且保持獨立，函數(shù)個數(shù)為N。則上述每次被選中置1的概率為：p=N/10 000，相應(yīng)的λ=np=N。由此可得函數(shù)個數(shù)與覆蓋率的函數(shù)關(guān)系，即覆蓋率CN=1-e-N。表3所示列出了N取1～5時的理論覆蓋率。

表3 1～5個函數(shù)時的覆蓋率

由表3中的理論覆蓋率可以看出，使用獨立的隨機函數(shù)越多，覆蓋效果越好。而從實際執(zhí)行層面看，程序在一次置1事件的執(zhí)行過程中，實際又獨立執(zhí)行了N次置1事件，增加了置1概率，從而增加了最終的初始零矩陣覆蓋率。

4.3 實例的指導(dǎo)意義

根據(jù)上述分析可以看出，既然所選的偽隨機函數(shù)生成器相互間獨立，其置1過程也是獨立的，多次獨立使用同一個偽隨機函數(shù)生成器來達到多個偽隨機數(shù)生成器的效果也可作進一步的研究。筆者利用3個函數(shù)中最簡單的偽隨機函數(shù)rand()，在程序執(zhí)行一次置1的過程中，進行了N次獨立隨機使用，所得數(shù)據(jù)列于表3的最后兩列。由數(shù)據(jù)看，同樣達到了組合隨機函數(shù)的效果，隨著使用次數(shù)的增加，覆蓋率逐漸接近于1，且“覆蓋率首次達到60%時的執(zhí)行次數(shù)”也顯著降低。因此，這種生成均勻分布偽隨機數(shù)的方法，對某些高精度初始化的應(yīng)用提供了有益的嘗試方向。

圖3所示為e的負指數(shù)曲線。從圖3可以看出，當實驗次數(shù)N>5時，參數(shù)效果提升已不明顯；而從運算開銷考慮，選取N=3已足夠滿足日常對均勻分布偽隨機數(shù)的精度需求。

圖3 e的負指數(shù)曲線

5 結(jié) 語

通過本文的討論，可以看出使用偽隨機數(shù)生成器逼近真實的隨機數(shù)是目前各類研究中較為可行的一種方法。而使用本文中的評價方法，對所構(gòu)建的偽隨機數(shù)生成算法進行評價，可以有效地指導(dǎo)實際應(yīng)用，并應(yīng)用到各種群智能算法中，如粒子群算法[16]等。同時針對特定問題，也可以對已有的偽隨機數(shù)算法進行簡單的組合改進，進行評價和改進指導(dǎo)，以更好的解決問題。