第2章 伪随机数的产生

1第二章伪随机数的产生2第二章伪随机数的产生一.伪随机数产生的意义二.产生U(0,1)的乘同余法三.正态分布N(0,1)的产生四.逆变法与其它分布随机数的产生31.随机数的产生是进行随机优化的第一步也是最重要的一步，智能优化方法中都要用到随机数2.传统手工方法：抽签，掷骰子，抽牌，摇号等，无法满足产生大量随机数的需求3.伪随机数方法：利用计算机通过某些数学公式计算而产生，从数学意义上说不是随机的，但只要通过随机数的一系列统计检验，就可以作为随机数来使用一.伪随机数产生的意义（1）44.伪随机数的产生过程确定一个数学模型或者某种规则规定几个初始值按照一定步骤产生第一个随机数用产生的上一个随机数作为新的初值，按照相同的步骤产生下一个随机数，重复之，得一伪随机数序列一.伪随机数产生的意义（2）55.一个良好的伪随机数产生器应具有的特性产生的随机数要具有均匀总体随机样本的统计性质，如分布的均匀性，抽样的随机性，数列间的独立性等产生的数列要有足够长的周期产生数列的速度要快，占用计算机的内存要尽可能的少一.伪随机数产生的意义（3）6二.产生U(0,1)的乘同余法（1）1.均匀随机数是产生其他随机数的基础2.乘同余法是目前应用最广泛的方法之一乘同余法的计算公式1mod()kkSASM整数常数取模运算大的模数7二.产生U(0,1)的乘同余法（2）2.乘同余法是目前应用最广泛的方法之一如何确定A和M的值，以保证产生的随机数周期最长？数论的理论可以证明：当时，若或，且为奇数时，可以获得的最长随机数序列长度为2(2)LML83Ak4+1Ak0S22L8二.产生U(0,1)的乘同余法（3）3.计算举例令，则可以产生随机整数序列为4216MI.II.III.03,1AS{1,3,9,11,1,3,9,11,...}S05,1AS{1,5,9,13,1,5,9,13,...}S03,2AS{2,6,2,6,...}S9二.产生U(0,1)的乘同余法（4）3.计算举例若想产生U(0,1)，则令即可/iiSMI.II.III.03,1AS{1/16,3/16,9/16,11/16,...}05,1AS{1/16,5/16,9/16,13/16,...}03,2AS{2/16,6/16,...}10二.产生U(0,1)的乘同余法（5）4.混合同余法公式：初始参数取值：，，C与M互为质数，则可以获得最长的随机数序列长度为上例中，若M=16，A=5，C=3，则产生的随机整数序列？1()mod()kkSASCM2LM4+1Ak2L11三.正态分布N(0,1)的产生（1）221()2xfxe0()fxx221()2txFxedt(0,1)N12三.正态分布N(0,1)的产生（2）正态分布可以由多个U(0,1)来近似若是独立同分布，且n较大，则近似于正态分布且满足及则12,,,nYYY12nxYYY12xnn2222212xnn2(,)xNnn13令，则由于，故三.正态分布N(0,1)的产生（3）xxxz(0,1)zN2212iiyixxynyynyznn(0,1)iyU12y2112y14注：三.正态分布N(0,1)的产生（4）22222120310()1()212134112yEYEYfydyydyy15一般n取12，则：若想产生服从一般正态分布的随机数x，则只需产生，再按公式即可获得三.正态分布N(0,1)的产生（5）12160,1iizyN2(,)N(0,1)zNxz16思考与练习练习1：编写一个服从N(5,2)分布随机数的程序，并产生100个随机数，利用数理统计理论检验所产生随机数满足随机分布的要求。171.逆变法四.逆变法与其它分布随机数的产生（1）密度函数101(0,1)U0,1yU101分布函数()()xxFxPXxfxdxx()Fx()fxxx18①是分布函数，，如何产生X？设，Y是随机变量产生，G(y)是U(0,1)分布函数②逆变法的目的：产生f(x)分布的随机数四.逆变法与其它分布随机数的产生（2）()FxxFxPXx()YFX11()()()yyyGyPYyPFXyPXFyFFyy0,1yU19③逆变法的步骤：I.已知F(x)，或由f(x)求F(x)即，令II.推导III.产生IV.用得到四.逆变法与其它分布随机数的产生（3）)(1yFx1,0Uy)(1yFxiixxxxx,,,,,1210()()xFxfxdx()yFx202.负指数分布的产生负指数函数的密度函数：四.逆变法与其它分布随机数的产生（4）)(xfx0)(xexfx21负指数函数的分布函数的产生过程：①令②③产生则④即四.逆变法与其它分布随机数的产生（5）00()1xxxxxFxedxee)(xFyyyF1ln1)(1yu11,0Uy)1,0(UuuyFln1)(1uxln122产生，令则，X是负指数分布的四.逆变法与其它分布随机数的产生（6）(0,1)YU1lnXY23思考与练习思考1：爱尔朗（Erlang）分布是m个负指数分布的和。设为负指数分布，则为Erlang分布。试设计其随机数的产生。12mXYYY12,,mYYY24作业思考2：试用逆变法设计分布如图所示密度函数f(x)的伪随机数序列的产生方法。12f(x)x0