随机数发生器

在许多仿真过程中,事件的发生是随机的,或者事件的属性值的确定具有偶然性。例如,仿真中广泛应用的决策逻辑中,偶然性的影响和作用是非常大的,在一个系统的运行中,已知按照一条给定的路径运行有一定的可能性。在对系统的仿真中需要有一种方法能够选定这条路径,从而使仿真器的长期行为更加接近真实系统。由于在多数情况下这个决策是不确定的,对路径的选择通常要基于概率关系。

由此或其他一些原因,几乎在所有的仿真模型中都需要有某种装备用来产生随机数。这种装备必须能够给出一个特定的值使得在任何给定的仿真运行中,事件看起来像是随机发生的。在这种情况下需要有一个决策模块,它必须能够指导仿真器在某些运行中采用一条给定的路径,而在其他的运行中采用其他的路径。

由于这些随机因素的存在,在建模过程中就可能需要用服从各种分布的随机变量来描述系统中存在的随机和偶然性问题。随机变量的产生基础是随机数,随机数可以通过对[0,1]区间上均匀分布抽样生成。

目前使用的大多数随机数发生器是线性同余发生器,它是Lehmer在1951年提出的。另一类是组合发生器。

(1)线性同余发生器

线性同余发生器采用下式产生随机数,

　　Z_i=(aZ_i-1+C)mod(m)

式中,Z:第i个随机数;

a:乘子;

C:增量;

m:模数;

Z₀:称为随机数源或种子,它们均为非负整数。显然,Z_i满足:

　　0≤Z_i≤m-1

为了得到[0,1]区间上所需要的随机数U_i可令:

　　U_i=Z_i/m

显然,Z_i实质上完全不是随机的,原因如下:

设 K_i=mod(aZ_i-1+C,m)

则 Z₁=a²Z₀+C-mK₁

Z₂=a²Z₀+C(1+a)-m(K₂+aK₁)=a²Z₀+C(1+a)-m(K₂+aK₁)

Z₃=a³Z₀+C(1+a+a²)-m(K₃+K₂a+K₁a₂)

　 …

Z_n=a_nZ₀+C(1+a+…+a_n-1)-m(K_n+K_n-1a+…+K₁a_n-1)

=a_nZ₀+Cmod(m)

即一旦m,a,C,Z₀确定,Z_i就完全确定下来了。

另外,由于Z_i是[0,m-1]区间上的整数,那么由Z_i得到的U_i仅仅是有限个数,即为0,1/m,2/m,…,m-1/m,而不可能位于这些数值之外。

对于线性同余发生器适当选择m,a,C,可使Z_i循环产生,无论Z₀取何值,其循环顺序是相同的,循环一次称为发生器的一个周期,记为P。如果P=m,则称该发生器具有满周期。适当选择m,a,C,可保证Z_i在[0,m-1]区间上一个周期内每个整数正好出现一次,从而保证了均匀性。为提高U_i的均匀性,要求加大m。

在实际使用中,可按以下规则选择a和m:

①选择m=2^b,b是某个整数,C为奇数,一般m选择在机器所能表示的数的范围内;

②a一般取与a≈2^p/2最接近而又满足a=8K±3的那个数,其中K是任意整数,P为机器字长。Z₀可为0到m-1之间的任意奇数,而不会对随机数发生器的周期产生任何影响。

线性同余发生器有两种形式,即混合乘同余(Ckengdiegt;0)和乘同余(C=0)。

(2)组合发生器

为了提高线性同余发生器的性能,可将两个独立的线性同余发生器组合起来,即用一个发生器控制另一个发生器产生的随机数,这种发生器称为组合发生器。迄今为止,有两种方法使用得比较广泛。

第一种方法是:首先从第一个发生器产生K个Z_i(U_i),得到数组U=(U₁,U₂,…,U_K)或Z=(Z_l,Z₂,…,Z_K);然后用第二个随机数发生器产生在[1,K]区间上均匀分布的随机整数I;以I作为数组U(或Z)的元素下标,将U₁或Z₁作为组合发生器产生的随机数,然后从第一个发生器再产生一个随机数来取代U₁或Z₁,依次下去。

第二种方法是:设与分别是由第一个与第二个线性同余发生器产生的随机数,则令的二进制表示的数循环移位次,得到一个新的位于0到m-1间的整数;然后将与的相应二进制位“异或”相加得到组合发生器的随机变量Z_i,且U_i=Z_i/m。

组合发生器的优点是,大大减少了线性同余发生器带来的自相关,提高了独立性;还可以加长发生器的周期,提高随机数的密度,从而提高了均匀性,而且它一般对构成组合发生器的线性同余发生器的统计特性要求较低,得到的随机数的统计特性却比较好。组合发生器的缺点是速度慢,因为要得到一个随机数,需要产生两个基础的随机数,并执行一些辅助操作。