第九章概率算法

第九章概率算法第1頁，課件共38頁，創(chuàng)作于2023年2月2023/9/121計算機算法設(shè)計與分析概率計算概率計算就是在算法中可采用隨機選擇計算的步驟、元素或參數(shù)等。它的基本特征是計算具有不確定性。它的解也不一定是最優(yōu)解。它在很大程度上能降低算法的復(fù)雜度。在非標準算法中普遍了應(yīng)用概率方法，主要有：(1)直接用概率進行數(shù)值計算；(2)用概率/隨機進行選擇；(3)利用概率加速搜索或避免陷于局部最優(yōu)。第2頁，課件共38頁，創(chuàng)作于2023年2月2023/9/122計算機算法設(shè)計與分析直接用概率進行數(shù)值計算設(shè)f(x)是[0,1]上的連續(xù)函數(shù)，求I=∫f(x)dx。01y=f(x)G假設(shè)向單位正方形內(nèi)隨機投入n個點(xi,yi)，若有m個點落入G中，則I≈m/n。doubleDarts(intn){doublex,y;intk=0;staticRandomNumberdart;for(inti=1;i<=n;i++){x=dart.fRandom();y=dart.fRandom();if(y<=f(x))k++;}returnk/double(n);}第3頁，課件共38頁，創(chuàng)作于2023年2月2023/9/123計算機算法設(shè)計與分析劃分基準的隨機選擇在快速排序算法中，若用擬中位數(shù)作為劃分標準，可保證在線性時間內(nèi)完成。但是確定擬中位數(shù)要付出額外開銷。若選用第一個元素為劃分基準，最壞時的時間復(fù)雜性為O(n2)。若在算法中采用隨機選擇一個元素作為劃分標準，便可既保證算法的線性時間平均性能，又避免了計算擬中位數(shù)的麻煩。也可先對數(shù)組進行“洗牌”，然后再進行確定的排序算法。這樣依然可取得同樣的效果。第4頁，課件共38頁，創(chuàng)作于2023年2月2023/9/124計算機算法設(shè)計與分析“洗牌”后的快速排序voidShuffle(Typea[],intn){//隨機洗牌算法

staticRandomNumbermd;for(inti=1;i<n;i++){intj=md.Random(n–i+1)+i;Swap(a[i],a[j]);}}VoidQuiksortByShuffle(Typea[],intn){Shuffle(a,n);//將數(shù)組a洗牌

Quiksort(a,n);}第5頁，課件共38頁，創(chuàng)作于2023年2月2023/9/125計算機算法設(shè)計與分析隨機抽樣在n個元素的集合中隨機抽取m(0<m≤n)個無重復(fù)的元素。為簡單起見，假定所有元素的值都位于1至n之間。第6頁，課件共38頁，創(chuàng)作于2023年2月2023/9/126計算機算法設(shè)計與分析隨機抽樣我們采用下面的方法進行選擇：1、首先將n個元素都標記為“未選擇”；2、重復(fù)下列步驟直到抽取了m個不同的元素⑴產(chǎn)生一個1至n間的隨機數(shù)r；⑵如果r標記為“未選擇”，將它標記為“已選擇”，并加入到抽樣中。第7頁，課件共38頁，創(chuàng)作于2023年2月2023/9/127計算機算法設(shè)計與分析隨機抽樣intRandomSampling(S[n],A[m],m){mark[1..n]=False;count=0;while(count<m){r=random(1,n);if(mark[r]==False){count++;A[count]=S[r];mark[r]=True;}}}第8頁，課件共38頁，創(chuàng)作于2023年2月2023/9/128計算機算法設(shè)計與分析判定素數(shù)的概率算法

判定自然數(shù)是否是素數(shù)，不僅有重要理論意義，而且在密碼學(xué)中具有重要實用價值。最簡單的素數(shù)判定方法是依次測定從2到n?

中是否存在n的因子，該算法的復(fù)雜度為O(n?)。篩法：將小于n的合數(shù)預(yù)先篩掉，而不用判斷其是否為n的因子。它雖然沒有降低算法的復(fù)雜度，但實際運行速度比前者要快得多。概率算法，保證一定概率的前提下簡單判斷。第9頁，課件共38頁，創(chuàng)作于2023年2月2023/9/129計算機算法設(shè)計與分析Fermat素數(shù)測試法Fermat定理：若p是素數(shù)，則對任意整數(shù)a，gcd(a,p)=1，則有ap–1≡1(modp)。顯然，對素數(shù)p有pp–1≡1(modp)。對于一般的整數(shù)n，滿足nn–1≡1(modn)的數(shù)目很少。滿足的稱為偽素數(shù)。就用是否滿足nn–1≡1(modn)來判斷n是否為素數(shù)。第10頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1210計算機算法設(shè)計與分析Fermat素數(shù)測試法BoolFermat_Prime(intn){a=2;power=n–1;other=1;while(power>1){if(power%2=

=1){other*=a;other%=n;}power/=2;a=a*a%n;}if(a*other%n==1)returnTrue;returnFalse;}第11頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1211計算機算法設(shè)計與分析合數(shù)的見證者設(shè)n為測試的自然數(shù)，不妨設(shè)n是大于2的奇數(shù)，則有n–1=2im，其中i是非負整數(shù)，m是正奇數(shù)。取一自然數(shù)b，1<b<n，記W(b)為條件：①bn–1≠1(modn)或②

i，使得m=(n–1)/2i

且1<gcd(bm–1,n)<b。若①或②中有一個為真，就認為W(b)滿足，則n必定是合數(shù)，我們稱b是n為合數(shù)的見證者。若n有見證者，則n必定為合數(shù)。第12頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1212計算機算法設(shè)計與分析合數(shù)的見證者多于一半Miller已經(jīng)證明，存在常數(shù)c，使得當n為合數(shù)時，在[1,c(logn)2]范圍內(nèi)有見證者。Rabin證明了：如果n是合數(shù)，則|{b|1<b<n，W(b)滿足}|≥(n–1)/2即，在小于n的自然數(shù)中有多半是n的見證者。任取一個自然數(shù)b<n，若b不是n的見證者，則n是合數(shù)的概率小于1/2。若隨機取m個數(shù)都不是見證者，則n是合數(shù)的概率小于1/2m。第13頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1213計算機算法設(shè)計與分析Miller-Rabin素數(shù)判定概率算法BoolMiller_Rabin_Prime(intn){b[1..m]=RandomSampling(n,m);/*隨機選取m個大于1小于n的無重復(fù)的自然數(shù)for(j=1;j<=m;j++)if(W(b[j])滿足)returnFalse;returnTrue;}若m=100，則n不是素數(shù)的概率小于1/2100。第14頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1214計算機算法設(shè)計與分析LasVegas算法LasVegas算法的特點是隨機性地進行決策。例如對n后問題，LasVegas算法是隨機地產(chǎn)生一組王后放置的位置。若成功了，便找到了一個解；若失敗了，就整個重來，再隨機產(chǎn)生另外一組王后的位置。這樣作，直至找到解。此算法能顯著地改進算法的有效性，甚至對迄今為止找不到有效算法的問題，也能得到滿意的結(jié)果。第15頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1215計算機算法設(shè)計與分析瞎子爬山法與局部最優(yōu)更一般的求解問題的方法是瞎子爬山法。一個瞎子從山腳開始，試探著一步一步向上爬，就可以一直爬到山頂?？墒?，他爬上的可能只是個小山頭，更高的山還在后面。而他無法從小山頭下來，也就無法爬到更高的山頭了。這種情形就被稱為陷入了局部最優(yōu)。如何避免陷入局部最優(yōu)是求解問題中要注意的一個重要問題。第16頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1216計算機算法設(shè)計與分析進化算法(EvolutionaryAlgorithm)達爾文的進化論：適者生存，優(yōu)勝劣汰。1975年霍蘭(Holland)提出了遺傳算法，通過模擬生物進化的過程概率搜索最優(yōu)解。遺傳算法首先產(chǎn)生所謂的個體種群，每個個體是編碼的二進制串(又稱為染色體)。然后對個體進行隨機的選擇，再經(jīng)過復(fù)制、交叉和變異產(chǎn)生下一代的種群。就這樣經(jīng)過一代一代的進化，最終獲得滿意的個體(即問題的解)。第17頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1217計算機算法設(shè)計與分析進化計算中的基本算子適應(yīng)值f(xi)：給出個體xi優(yōu)劣；選擇算子：對個體進行概率選擇。個體的概率為p(xi)=f(xi)/∑f(xj)，優(yōu)秀的個體具有較高的概率。最常用的選擇算子為輪盤賭的方法。這樣優(yōu)秀個體具有較高的被選中的概率。同時差的個體也有被選中的可能。復(fù)制算子copy：對選中的個體進行復(fù)制。交叉算子

：將兩個個體染色體中的某個位彼此交換，從而形成兩個新的個體。變異算子m：改變一個個體的染色體的某些位，得到一個新的個體。停止準則：決定算法停止的準則第18頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1218計算機算法設(shè)計與分析進化算法的基本框架t=0//t為代數(shù)；初始化：P(0)={a1(0),…,an(0)}//初始種群P(0)度量：P(0):{f(a1(0)),…,f(an(0))};while(P(t)不滿足停止準則){

交叉：P’(t)=(P(t));

變異：P’’(t)=m(P’(t));

度量：P’’(t)：{f(a1’’(t)),…,f(an’’(t)));

選擇：P(t+1)=P’’(t)∪Q;t=t+1;}第19頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1219計算機算法設(shè)計與分析進化計算的優(yōu)缺點是一種通用的計算方法，一旦問題表示為種群后，算法便不在依賴于問題。求解不依賴于初始狀況，通常具有較好的收斂性，也不容易陷于局部最優(yōu)。依然有可能陷入局部最優(yōu)(早熟收斂)。選擇問題的表示方案和適應(yīng)值度量的優(yōu)劣、選擇種群的規(guī)模大小、代數(shù)、控制執(zhí)行各種算子的參數(shù)、停止準則等的好壞都可影響算法的功能和效果。第20頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1220計算機算法設(shè)計與分析模擬退火算法1982年Kirkpatrick將固體退火過程應(yīng)用于組合優(yōu)化問題的求解，提出一種有效的近似算法，稱為模擬退火算法。模擬退火算法從初始解i=i0開始，在當前解i的鄰域Si中按照Metropolis準則搜索新解j以取代當前解i。這個過程不斷進行下去，直到達到目標函數(shù)最優(yōu)。第21頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1221計算機算法設(shè)計與分析固體退火過程退火是固體由高溫下粒子排列的無序的液態(tài)冷卻而凝固成粒子排列有序的固體晶態(tài)的過程。退火是系統(tǒng)的熵不斷減小，能量趨于最小值的過程。它遵循熱力學(xué)中的自由能減少定律：F=E–TS其中F、E和S分別表示自由能、能量和熵。系統(tǒng)從非平衡態(tài)自發(fā)變化到平衡態(tài)，都是能量和熵競爭的結(jié)果，溫度決定二者孰重。第22頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1222計算機算法設(shè)計與分析Metropolis接受準則設(shè)i是一個狀態(tài)，j是由i可得到的一個新狀態(tài)。它們的能量分別為Ei和Ej。若Ej＜Ei，則狀態(tài)j可以取代狀態(tài)i。否則固體處于狀態(tài)i和狀態(tài)j的幾率為r=exp((Ei–Ej)/kT)其中k是Boltzmann常數(shù)，T為絕對溫度，r＜1。設(shè)是(0,1)中的隨機數(shù)，若r＞，則狀態(tài)j可以取代狀態(tài)i。第23頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1223計算機算法設(shè)計與分析模擬退火算法的框架k=0;i=i0;t=t0;//初始化while(不滿足停止準則){Gen(Si);//產(chǎn)生i的鄰域Si，|Si|=Lkfor(j∈Si)//用Metropolis準則對Si中的

if(f(i)<f(j))i=j;//每個狀態(tài)j檢測是否可替代ielseif(exp((f(i)–f(j))/t)>random(0,1))i=j;k=k+1;t=tk;//降溫；進入下一輪迭代

}第24頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1224計算機算法設(shè)計與分析算法的性能算法可以漸進地收斂于整體最優(yōu)解。Metropolis準則給算法引入了隨機性，使算法進程方向呈現(xiàn)跳躍性，從而可能避開局部最優(yōu)，但不能完全避開局部收斂。最終解不依賴于初始解。溫度t和|Si|(即Lk)決定算法的收斂速度。算法的復(fù)雜性為O(kLP(n))，其中k為迭代次數(shù)，L=max{|Si|}，P(n)是問題規(guī)模n的多項式函數(shù)。求高質(zhì)量的近似解的耗費也較高。第25頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1225計算機算法設(shè)計與分析模擬退火算法的應(yīng)用(1)確定解問題、能量函數(shù)和初始解：解空間是所有可行解的集合；能量函數(shù)是優(yōu)化目標的數(shù)學(xué)描述；初始解是開始計算的起點。(2)新解的產(chǎn)生和接受準則：從當前解產(chǎn)生新解；用Metropolis準則判斷新解是否可替代當前解；然后用新解/當前解進行下一輪實驗。(3)冷卻進度表及其它參數(shù)：Lk由新解來確定，冷卻溫度tk用冷卻進度表或衰減函數(shù)給出。應(yīng)用模擬退火算法的工作如下：第26頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1226計算機算法設(shè)計與分析用模擬退火算法解TSP解空間為所有的排列，初始解為<1,2,…,n>。能量函數(shù)f為發(fā)、該排列的周游路線長度。即

nf(<di1di2…din>)=min{∑dikdik+1+dindi1}

k=1產(chǎn)生新解：用某種方法將舊排列變換成新排列。例如：在排列中任選u,v，交換u,v，并將u和v之間的順序逆轉(zhuǎn)。比如：取u=2，v=3：<1,2,3,4,5,6,7><1,5,4,3,2,6,7>或者：在排列中任選u,v，和w，將u和v之間的子串插在w之后。比如：選u,v,w分別為2,5,6:<1,2,3,4,5,6,7><1,5,2,6,3,4,7>第27頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1227計算機算法設(shè)計與分析算法中參數(shù)的討論冷卻進度表：用參數(shù)t的一個遞減序列{tk}和與之對應(yīng)的Lk的序列來控制算法的進程。通常選tk的小衰減量以避免過大的Lk值。只要tk和Lk與停止準則選擇恰當，算法不僅收斂而且提高收斂速度。t0值過小導(dǎo)致解質(zhì)量差，過大增加求解時間。如何選擇t0是個重要問題。當tk減小時Lk則增大。一般用個多項式P(n)來限制。一般選迭代次數(shù)6~50次為停止準則。第28頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1228計算機算法設(shè)計與分析人工神經(jīng)網(wǎng)絡(luò)1943年McCulloch和Pitts提出神經(jīng)元的數(shù)學(xué)模型，即MP模型。1957年Rosenblatt設(shè)計制作了“感知機”。這是第一個多層的人工神經(jīng)網(wǎng)絡(luò)。第一個高潮期。1969年之后進入低潮。1980年以后重新進入高潮，并得到蓬勃的發(fā)展。目前人們普遍認為突破圖林機模型的將是人工神經(jīng)網(wǎng)絡(luò)。這是下一代計算機的主體。第29頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1229計算機算法設(shè)計與分析神經(jīng)元右圖是一個神經(jīng)元：神經(jīng)元的構(gòu)造為若干根輸入的突軸和一根輸出的樹軸。神經(jīng)元可以有抑制和激活這兩種狀態(tài)。當輸入的信號達到一定的程度，神經(jīng)元便被激活產(chǎn)生輸出信號。第30頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1230計算機算法設(shè)計與分析神經(jīng)元的數(shù)學(xué)模型(MP模型)右圖是MP模型的示意圖：y=f(∑iwixi–)其中：f稱為激活函數(shù)，

為閾值，wi為權(quán)重。激活函數(shù)的形式通常有兩種形式：第31頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1231計算機算法設(shè)計與分析人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)就是人工神經(jīng)元所構(gòu)成的網(wǎng)絡(luò)。主要有前饋網(wǎng)絡(luò)和反饋網(wǎng)絡(luò)兩種形式。前饋網(wǎng)絡(luò)有若干層神經(jīng)元組成，第i層的神經(jīng)元只接受第i–1層輸出的信息，而不接受同層或高層的輸出信息。反饋網(wǎng)絡(luò)中的神經(jīng)元可以接受外加輸入和其它神經(jīng)元包括自身的反饋輸入。第32頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1232計算機算法設(shè)計與分析人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)神經(jīng)元的計算主要依賴于權(quán)重wi，而權(quán)重wi是通過學(xué)習(xí)獲得的。所謂學(xué)習(xí)(又稱訓(xùn)練)是首先給權(quán)重賦予一個初值，然后將大量的訓(xùn)練樣板(包括正例和反例)輸入計算機，人工神經(jīng)網(wǎng)絡(luò)自己不斷地調(diào)整相應(yīng)的權(quán)重。學(xué)習(xí)的方式主要分為：有監(jiān)督的學(xué)習(xí)和自適應(yīng)的學(xué)習(xí)兩種形式，以及它們的改進。第33頁，課件共38頁，創(chuàng)作于2023年2月2023/9/1233計算機算法設(shè)計與分析BP神經(jīng)網(wǎng)絡(luò)BP神經(jīng)網(wǎng)絡(luò)是一個三層前饋網(wǎng)絡(luò)，分別為輸入層LA，隱含層LB和輸出層LC。每層