【文章內(nèi)容簡介】 體也選擇不上。在遺傳算法的運行過程中，雖然隨著群體的進化過程會產(chǎn)生出越來越多的優(yōu)良個體，但是由于選擇、交叉、變異等操作的隨機性，優(yōu)良個體也有可能被破壞掉，這并不是我們所希望的。要使適應(yīng)度最好的個體盡可能的遺傳到下一代群體中，可以使用最優(yōu)保存策略進化模型來進行優(yōu)勝劣汰操作，即當前群體中適應(yīng)度最高的個體不參與交叉運算和變異運算，而用它來代替掉本代群體中經(jīng)過交叉、變異等操作后所產(chǎn)生的適應(yīng)度最低的個體。確定式采樣選擇方法是按照一種確定的方式來進行選擇操作。這種選擇操作方法可保證適應(yīng)度較大的一些個體一定能夠被保留在下一代群體中，并且操作也比較簡單。這種選擇操作方法也叫期望值選擇方法，它的基本思想是根據(jù)每個個體在下一代群體中的生存期望值來進行選擇運算。這種選擇操作方法能夠降低一些選擇誤差，但操作不太方便。無回放余數(shù)隨機選擇可保證適應(yīng)度比平均適應(yīng)度大的一些個體一定能夠被遺傳到下一代群體中，所以它的選擇誤差比較小。前面所介紹的一些選擇操作方法中，其選擇依據(jù)主要是各個個體適應(yīng)度的具體數(shù)值，一般要求它取非負值，所以在選擇操作之前必須先對一些負的適應(yīng)度進行變換處理。而排序選擇方法的主要著眼點是個體適應(yīng)度之間的大小關(guān)系，對個體適應(yīng)度是否取正值或負值以及個體適應(yīng)度之間的數(shù)值差異程度并無特別要求。排序選擇方法的主要思想是：對群體中的所有個體按其適應(yīng)度大小進行排序，基于這個排序來分配各個個體被選中的概率。其具體操作過程是：（1）對群體中的所有個體按其適應(yīng)度大小進行降序排序。（2）根據(jù)具體求解問題，設(shè)計一個概率分配表，將各個概率值按上述排序次序分配給各個個體。（3）以各個個體所分配到的概率值作為其能夠被遺傳到下一代的概率，基于這些概率值用比例選擇的方法來產(chǎn)生下一代群體。該方法的實施必須根據(jù)對所研究問題的分析和理解情況預(yù)先設(shè)計一個概率分配表，雖然依據(jù)個體適應(yīng)度之間的大小次序給各個個體分配了以個選中概率，但由于具體選中那一個個體仍是使用了隨機性較強的比例選擇方法，所以排序選擇方法仍具有較大的選擇誤差。因此本文中選擇利用賭盤選擇和最優(yōu)保存策略來對群體進行選擇。遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個體的主要方法。交叉算子的設(shè)計包括以下兩方面的內(nèi)容：（1）如何確定交叉點的位置？（2）如何進行部分基因交叉？下面介紹幾種適合于二進制編碼個體或浮點數(shù)編碼個體的交叉算子。單點交叉又稱簡單交叉，它是指在個體編碼串中只隨機設(shè)置一個交叉點，然后在該點相互交換兩個配對個體的部分基因。單點交叉的重要特點是：若鄰接基因座之間的關(guān)系能提供較好的個體性狀和較高的個體適應(yīng)度的話，則這種單點交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。例如：A：1 0 1 1 0 1 1 1 0 0 A180。：1 0 1 1 0 1 1 1 1 1 B：0 0 0 1 1 1 0 0 1 1 B180。：0 0 0 1 1 1 0 0 0 0雙點交叉是指在個體編碼串中隨機設(shè)置二個交叉點，然后再進行部分基因交換。雙點交叉的操作過程如下：（1）在相互配對的兩個個體編碼串中隨機設(shè)置兩個交叉點。（2）交換兩個個體在所設(shè)定的兩個交叉點之間的部分染色體。雙點交叉操作的示例如下：例如取兩個父代個體如下：P1：A B C D E FP2：B D F E C A對第三到第五個字符進行交叉操作后，得到子代個體為：C1：A B F E C FC2：B D C D E A多點交叉是指在個體編碼串中隨機設(shè)置多個交叉點，然后進行基因交換。均勻交叉是指兩個配對個體的每一個基因座上的基因都以相同的概率進行交換，從而形成兩個新的個體。A：x x x x x x x x x x A180。：x y x y x y x y x y 均勻交叉B：y y y y y y y y y y B180。：y x y x y x y x y x算術(shù)交叉是指由兩個個體的線性組合而產(chǎn)生出兩個新的個體。假設(shè)在兩個個體、之間進行算術(shù)交叉，則交叉后運算所產(chǎn)生的兩個新個體是：上式中，為一參數(shù)，它可以是一個常數(shù)，此時所進行的交叉運算稱為均勻算術(shù)交叉；它也可以是一個由進化代數(shù)所決定的變量，此時所進行的交叉運算稱為非均勻算術(shù)交叉。部分匹配交叉[13]是由Goldberg在1985年針對TSP提出的基于路徑表示的交叉操作。部分匹配交叉操作要求隨機選取兩個交叉點，以便確定一個匹配段，根據(jù)兩個父個體中兩個交叉點之間的中間段給出的映射關(guān)系生成兩個子個體。如假設(shè)TSP的城市數(shù)為8，兩個父代染色體分別為：fl{25036147}和f2{34072516}，首先隨機選取兩個點比如3和6標記為x，那么f1和f2就變?yōu)橐韵滦问剑篺l{250x36lx47}f2{340x725xl6}觀察兩個父代的中段，記錄下對應(yīng)關(guān)系，即3一7，6一2，1一5，逐個檢查父代的每一個基因，每次找到相匹配的基因，就進行交換：3和7交換：s1{25076143}，s2{74032516}6和2交換：s1{65072143}，s2{74036512}l和5交換：s1{61072543}，s2{74036152}交叉完成，得到sl和s2兩個新的城市序列。但在算法實現(xiàn)中發(fā)現(xiàn)部分匹配交叉在某些情況下會出現(xiàn)重復(fù)，例如：f1{21x654x3} s1{2143545}f2{12x435x6} s2{1265454}觀察這兩個父代的中段，記錄下對應(yīng)關(guān)系，即6一4，5一3，4一5，由此對應(yīng)關(guān)系得到的s1和s2出現(xiàn)重復(fù)現(xiàn)象。在遺傳算法中使用變異算子主要有兩個目的：（1）改善遺傳算法的局部搜索能力。（2）維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。變異算子的設(shè)計包括如下兩方面內(nèi)容：（1）如何確定變異點的位置？（2）如何進行基因值替換？基本位變異操作是指對個體編碼串中以變異概率Pm隨機指定的某一位或某幾位基因座上的基因值作變異運算，它的改變只是在個體編碼串中的個別幾個基因座上的基因值，并且變異發(fā)生的概率也比較小，所以發(fā)揮的作用比較慢，作用效果也不明顯。均勻變異操作是指分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。邊界變異操作[14]是均勻變異操作的一個變形，它是隨機取基因座的二個對應(yīng)邊界基因值之一去替代原有基因值。為了方便對某些重點區(qū)域進行局部搜索，而對原有基因值做隨機擾動，以擾動后的結(jié)果作為變異后的新基因值。對每個基因座都以相同的概率進行變異運算之后，相當于整個解向量在解空間中作了個輕微的變動，這就是非均勻變異[15]。它的重點是搜索原個體附近的微小區(qū)域。高斯變異是改進遺傳算法對重點搜索區(qū)域的局部搜索性能的另一種變異操作方法。它在操作時，用符合均值為181。、方差為2的正態(tài)分布的一個隨機數(shù)來替代原有基因值。4基于遺傳算法的密碼分析方法根據(jù)遺傳算法的基本流程，涉及的關(guān)鍵內(nèi)容有：染色體編碼和初始種群的產(chǎn)生、適應(yīng)度函數(shù)的定義和計算、遺傳操作和新一代種群的產(chǎn)生等等。常量與變量說明：maxpop 表示最大群體大小MAXSTRING 表示最大字符串長度lchrom 表示個體長度popsize 表示種群規(guī)模maxgen 表示最大運行代數(shù)pcross 表示交叉概率pmutation 表示變異概率本文首先是通過隨機產(chǎn)生的密鑰對某段英文文章進行加密，這就可以使用替換密碼來解決。本文考慮到密鑰是由26個全部大寫（或全部小寫）的英文字母組成，并且不能出現(xiàn)重復(fù)字母，即種群中個體的染色體編碼不能出現(xiàn)相同字母，在此可使用check數(shù)組來防止重復(fù)出現(xiàn)同一字母。設(shè)計代碼如下：for (i=0。ilchrom。i++) check[i]=false。for(i=0。ilchrom。i++){ while(temp==0) { flag=rand()%lchrom。 if(check[flag]==false) { tempcipher[i]=flag。 temp=1。 check[flag]=true。 } } temp=0。}這就實現(xiàn)了對本文中密鑰的編碼。要產(chǎn)生初始種群只要對上述代碼實行循環(huán)就可以得到所需的群體。在遺傳算法當中，適應(yīng)度函數(shù)一般是由待求問題的目標函數(shù)轉(zhuǎn)換而成的。針對不同的密碼算法或者不同的分析方法，可以確定不同的適應(yīng)度函數(shù)。從大量的英文書籍、報刊的文章中會很容易發(fā)現(xiàn)英文字母出現(xiàn)的頻率有許多統(tǒng)計規(guī)律可循。比如E字母出現(xiàn)的次數(shù)最多，其次是T、A、O等字母。若統(tǒng)計的英文篇幅足夠長時，會發(fā)現(xiàn)各個英文字母的頻率相當穩(wěn)定。根據(jù)英文字母的頻率可將英文字母分成幾類，其中E為極高頻率字母類，V、K、J、X、Q、Z為甚低頻率字母類。而且，雙字母(相鄰的兩個字母)和三字母(相鄰的三個字母)也和單字母一樣出現(xiàn)相當穩(wěn)定的字母分布[16]。這些統(tǒng)計資料對于密碼分析者破譯密碼是非常重要的信息。本文正是基于英文字符的統(tǒng)計特性，可以選取如下適應(yīng)度函數(shù)：式中：SF(i)為第i個字符在正常的英文使用中出現(xiàn)的頻率，DF(i)是經(jīng)過對密文C進行解密運算后得到的明文M=(m0，m1，m2，…，mn1)，對mi出現(xiàn)的頻率進行統(tǒng)計計算的結(jié)果。而對DF(i) 的計算首先要得到文章中一共有多少字符，如果有空格就會少一個字符，從而得到明文的字符總數(shù)。然后對文中的每個字母出現(xiàn)的次數(shù)進行統(tǒng)計；最后兩者相除就可以算出DF(i)。解密后明文中字符出現(xiàn)的頻率越接近正常因為出現(xiàn)的頻率，其適應(yīng)度就越大。本文中還采用了最優(yōu)保存策略即上一代群體中最優(yōu)密鑰的適應(yīng)度若是大于本代群體中最差密鑰的適應(yīng)度，則上一代的最優(yōu)密鑰取代本代最差密鑰。在選擇算子中采用的賭輪算法是一種典型的選擇算法，其基本思想是首先計算出當前種群所有個體的適應(yīng)度∑Fitness，由此產(chǎn)生一個取值范圍在0和∑Fitness之間均勻分布的偽隨機數(shù)r，則滿足條件的第i個個體被選作父代個體（其中F(pi)為第i個個體的適應(yīng)度，n為種群規(guī)模）。選擇代碼如下：int select(){ double rand1,partsum。 int j。 partsum=。 j=0。 rand1=random1()*sumfitness。 do { partsum=partsum+oldpop[j].fitness。 j=j+1。 }while((partsumrand1)amp。amp。(jpopsize))。 r