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

Quiksort(a,n);}第5頁，課件共38頁，創作于2023年2月2023/9/125計算機算法設計與分析隨機抽樣在n個元素的集合中隨機抽取m(0<m≤n)個無重復的元素。為簡單起見，假定所有元素的值都位于1至n之間。第6頁，課件共38頁，創作于2023年2月2023/9/126計算機算法設計與分析隨機抽樣我們采用下面的方法進行選擇：1、首先將n個元素都標記為“未選擇”；2、重復下列步驟直到抽取了m個不同的元素⑴產生一個1至n間的隨機數r；⑵如果r標記為“未選擇”，將它標記為“已選擇”，并加入到抽樣中。第7頁，課件共38頁，創作于2023年2月2023/9/127計算機算法設計與分析隨機抽樣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頁，創作于2023年2月2023/9/128計算機算法設計與分析判定素數的概率算法

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

中是否存在n的因子，該算法的復雜度為O(n?)。篩法：將小于n的合數預先篩掉，而不用判斷其是否為n的因子。它雖然沒有降低算法的復雜度，但實際運行速度比前者要快得多。概率算法，保證一定概率的前提下簡單判斷。第9頁，課件共38頁，創作于2023年2月2023/9/129計算機算法設計與分析Fermat素數測試法Fermat定理：若p是素數，則對任意整數a，gcd(a,p)=1，則有ap–1≡1(modp)。顯然，對素數p有pp–1≡1(modp)。對于一般的整數n，滿足nn–1≡1(modn)的數目很少。滿足的稱為偽素數。就用是否滿足nn–1≡1(modn)來判斷n是否為素數。第10頁，課件共38頁，創作于2023年2月2023/9/1210計算機算法設計與分析Fermat素數測試法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頁，創作于2023年2月2023/9/1211計算機算法設計與分析合數的見證者設n為測試的自然數，不妨設n是大于2的奇數，則有n–1=2im，其中i是非負整數，m是正奇數。取一自然數b，1<b<n，記W(b)為條件：①bn–1≠1(modn)或②

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

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

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

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

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

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

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

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