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