【文章內(nèi)容簡介】 強(qiáng)。 遺傳算法的工作原理 遺傳算法是將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制，交叉及變異對(duì)個(gè)體進(jìn)行篩選，使適應(yīng)度高的個(gè)體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。其 執(zhí)行過程如下： ① 編碼： GA 在搜索之前先將變量進(jìn)行編碼，形成一個(gè)定長的字符串。 ② 產(chǎn)生初始群體：隨機(jī)產(chǎn)生 M 個(gè)初始字符串，每個(gè)字符串為一個(gè)個(gè)體或者是一個(gè)染色體。 M 個(gè)個(gè)體構(gòu)成一個(gè)群體。 GA 以這 M 個(gè)字符串作為初始點(diǎn)開始迭代。 ③ 計(jì)算適應(yīng)值：適應(yīng)性函數(shù)表明個(gè)體對(duì)環(huán)境的適應(yīng)能力的強(qiáng)弱，不同的問題，適應(yīng)函數(shù)的定義方式也不同。 ④ 選擇：一個(gè)群體中同時(shí)有 M 個(gè)個(gè)體存在，在這些個(gè)體中哪個(gè)被選去繁殖后代，哪個(gè)被淘汰，是根據(jù)它們對(duì)環(huán)境的適應(yīng)能力來決定的，適應(yīng)性強(qiáng)的個(gè)體有更多的機(jī)會(huì)被保留下來。 ⑤ 交叉：對(duì)于選中的繁殖個(gè)體，按照某種交 叉方式交換兩個(gè)字符串相應(yīng)的位段，產(chǎn)生兩個(gè)新的個(gè)體，新的個(gè)體組合其父輩的特性。 ⑥ 變異：變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)選中的個(gè)體以一定的概率隨機(jī)的改變字符串中某個(gè)字符的值。 ⑦ 收斂判斷：是否達(dá)到收斂標(biāo)準(zhǔn)，若是，則把適應(yīng)度值好的字符串作為搜索的結(jié)果。否則轉(zhuǎn)入第（ 3）步重復(fù)以上過程。 ⑧ 編程上機(jī)運(yùn)行：完成上述工作以后，既可以按照演化計(jì)算的算法結(jié)構(gòu)編程來進(jìn)行問題求解。由于遺傳算法的隨機(jī)性和不確定性等特點(diǎn)，洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 8 通常要運(yùn)行多次才能得到可靠的解。應(yīng)該注意上述各基本步驟是密切相關(guān)的，編碼方案與遺傳算子的設(shè)計(jì)等是同步考慮的 ，有時(shí)甚至需要上機(jī)運(yùn)行與算法設(shè)計(jì)交替進(jìn)行。 遺傳算法的基本操作 （ 1） 復(fù)制（ Reproduction Operator） 復(fù)制 是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過程。根據(jù)位串的適配值拷貝，也就是指具有高度配值的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。它模仿了自然現(xiàn)象，應(yīng)用是指具有高度適配值的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。它模仿了自然現(xiàn)象，應(yīng)用了達(dá)爾文的適者生存理論。復(fù)制操作可以通過隨機(jī)方法來實(shí)現(xiàn)。若用計(jì)算機(jī)程序來實(shí)現(xiàn)，可考慮首先產(chǎn)生 0~1 之間均勻分布的隨機(jī)數(shù)，若某 串的復(fù)制概率為 40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在 0~ 之間時(shí)，該串被復(fù)制，否則被淘汰。此外，還可以通過計(jì)算方法實(shí)現(xiàn)，其中較典型的幾種較典型的幾種方法為適應(yīng)度比例法、期望值法、排位次法等。適應(yīng)度比例法較常用。 （ 2）交叉（ Crossover Operator） 復(fù)制操作 從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進(jìn)化過程的繁殖現(xiàn)象，通過兩個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。它的過程為：在匹配池中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換位置；交換雙親染色體交換點(diǎn)右邊的部分，即可得到兩個(gè)新染色體 數(shù)字串。交換體出現(xiàn)了自然界中信息交換思想。交叉有一點(diǎn)交叉、多點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉和周期交叉。一點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，例： A： 101100 1110→ 101100 0101 B： 001010 0101→ 001010 1110 （ 3）變異（ Mutation Operator） 變異運(yùn)算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號(hào)的某一位）的值。在染色體以 二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由 1 變?yōu)?0，或由 0 變?yōu)?，而沒有變異，則無洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 9 法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過程在早期就陷入局部解而進(jìn)入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。 遺傳算法的數(shù)學(xué)基礎(chǔ) 模式的階和模式的定義距 模式是指種群個(gè)體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個(gè)字符集 (0,1,*)的字符串，符號(hào) *代表任意字符，即 0 或者 1。 模式示例： 10**1 定義 1：模式 H 中確定位置的個(gè)數(shù)稱為模式 H 的階，記作 O(H)。例如 O(10**1)=3 。 定義 2：模式 H 中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式 H 的定義距，記作δ (H)。例如δ (10**1)=4 。 模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。 模式定理 模式定理：具有低階、短定義距以及平均適應(yīng)度高于 種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。 從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的模式幾乎沒有影響。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 10 積木塊假設(shè) 在模式定理中所指的具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式被定義為積木塊（ building block）。它們?cè)谶z傳算法中很重要，早子代中呈指數(shù)增長，在遺傳操作下相互影響，產(chǎn)生適應(yīng)度更高的個(gè)體，從而找到更優(yōu)的可行解。 積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。 基本遺傳算法 (SGA)的組成 遺傳算法被認(rèn)為是對(duì)人類自然演化過程的模擬。人類的自然演化過程是進(jìn)化過 程，這種進(jìn)化過程發(fā)生在染色體上。自然選擇是適應(yīng)度值較好的染色體比那些適應(yīng)度值較差的染色體有更多的繁殖機(jī)會(huì)；變異算子可以使子代染色體不同于父代染色體；通過兩個(gè)父代染色體的結(jié)合與重組可以產(chǎn)生全新的染色體。染色體的選擇、交叉與變異進(jìn)程是無記憶的。將這些概念反映在數(shù)學(xué)上就形成了遺傳算法的基礎(chǔ)操作。它的基本流程圖如 圖 21 所示。 由 圖 21 可知，遺傳算法是一種群體型操作，該操作以群體中 的所有個(gè)體為對(duì)象，選擇 ( Selection )、交叉 (Crossover)、變異 (Mutation )是遺傳算法的 3 個(gè)主要操作算子，它們構(gòu)成了所謂的遺傳操作 (Geic Operation )，使遺傳算法具有了其它傳統(tǒng)方法所沒有的特性。遺傳算法中包含如下 5 個(gè)基本要素：（ 1）參數(shù)編碼；（ 2）初始群體的設(shè)定；（ 3）適應(yīng)度函數(shù)的設(shè)計(jì)；（ 4）遺傳操作設(shè)計(jì)；（ 5）控制參數(shù)的設(shè)定 (主要是群體大小和使用遺傳操作的概率等 )。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 11 否產(chǎn) 生 初 始 群 體計(jì) 算 個(gè) 體 適 應(yīng) 度選 擇變 異交 叉結(jié) 束輸 出 結(jié) 果是 否 滿 足 終 止條 件 ？開 始是 圖 21 基本遺傳算法流程圖 編碼 用遺傳算法設(shè)計(jì)一個(gè)優(yōu)秀的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，首先是要解決網(wǎng)絡(luò)結(jié)構(gòu)的編碼問題；然后才能以選擇、交叉、變異操作得出最優(yōu)結(jié)構(gòu)?；具z傳算法使用固定長度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集 {0,1}所組成，編碼包括以下幾個(gè)步驟： (1)據(jù)具體問題確定待尋優(yōu)的參數(shù)； (2)對(duì)每個(gè)參數(shù)確定它的變化范圍，并用一個(gè)二進(jìn)制數(shù)來表示； (3)將所有表示參數(shù)的二進(jìn)制數(shù)串接起來組成一個(gè)長的二進(jìn)制串。 除了二進(jìn)制編碼之外，還有浮點(diǎn)數(shù)編碼、符號(hào)編碼等方法。所 謂浮點(diǎn)數(shù)編碼方法，是指個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示，個(gè)體的編碼長度等于其決策變量的個(gè)數(shù)。就二進(jìn)制編碼和浮點(diǎn)數(shù)編碼比較而言，一般二進(jìn)制編碼比浮點(diǎn)數(shù)編碼搜索能力強(qiáng)，但浮點(diǎn)數(shù)編碼洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 12 比二進(jìn)制編碼在變異操作上能夠保持更好的種群多樣性。符號(hào)編碼方法很少采用，這里就不再介紹了 適應(yīng)度函數(shù) 在遺傳算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體中的概率，因此適應(yīng)度函數(shù)的定義方法對(duì)遺傳算法具有極大的影響。 在遺傳算法中，目標(biāo)函數(shù)到適應(yīng)度函數(shù)的映射方式需要保證以下兩點(diǎn)： 1． 映射后的適應(yīng)度 值是非負(fù)的； 2． 目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)適應(yīng)度值的增大或減小方向。 對(duì)于求最大值的問題一般采用如下的適應(yīng)度函數(shù) ()fx和目標(biāo)函數(shù)()gx的映射關(guān)系： ? ? ? ?? ? ? ?? 0m i nm i n , 0m i n,0 ??? ??? CxgifCxg Cxgifxf (21) 式中， minC 可以是一個(gè)輸入?yún)?shù)在理論上的最小值，也可以是到目前所有代中 ()gx的最小值，此時(shí) minC 會(huì)隨著代數(shù)而變化。 對(duì)于求最小值的問題一般采用如下的適應(yīng)度函數(shù) ()fx和目標(biāo)函數(shù)()gx的映射關(guān)系： ? ? ? ?? ? ? ?? 0m a x,m a x 0m a x,0 ??? ??? CxgifxgC Cxgifxf (22) 式中， Cmax 可以是一個(gè)輸入?yún)?shù)在理論上的最 大 值，也可以是到目前所有代中 ()gx的最小值，此時(shí) Cmax 會(huì)隨著代數(shù)而變化。 遺傳算子 遺傳算法操作包括選擇、交叉和變異三個(gè)基本遺傳算子，綜合考慮三種算子，可以得知它們有如下的特點(diǎn)： A． 遺傳操作的效果和它們所取的操作概率、編碼方式、群體大小、初始群體以及適應(yīng)度函數(shù)的設(shè)定密切相關(guān)； 洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 13 B． 它們的操作方式或操作策略隨 著 具體 的 求解問題的不同而異。 選擇算子又稱復(fù)制算子（ Reproduction），是從種群中選擇生命力強(qiáng)的染色體，產(chǎn)生新種群的過程。常見的有以下幾種方法： （ 1）適應(yīng)度 比例選擇方法 (Proportional Model)， 又稱為輪盤賭法(Roulette Wheel)或蒙特卡洛 (Monte Carlo)模型，是目前最常用的選擇方法，具體表達(dá)方法如下： ?? mipis ,2,1FFm1i ii??? ?? (23) 式中， isp 為個(gè)體 i 被選中的概率， iF 為個(gè)體 i 的適應(yīng)度， M 為群體大小。 （ 2） 確定式采樣選擇 (Deterministic Sampling)， 它的基本思想 是 按照一種確 定的方式來進(jìn)行選擇操作，其具體操作過程如下： a、 計(jì)算群體中各個(gè)個(gè)體在下一代群體中的期望生存數(shù)目 Ni ： ? ?MiFFMi iii ,2,1*Nm1 ??? ?? (24) b、 用 iN 的整數(shù)部分 iN 確定各個(gè)對(duì)應(yīng)個(gè)體在下一代群體中的生存數(shù)目。其中 x 表示不大于 x 的最大的整數(shù)。由該步可以確定出下一代群體中的 ? ???Mi iN1個(gè)個(gè)體。 c、 按照 Ni 的小數(shù)部分對(duì)個(gè)體進(jìn)行降序排序，順序取前 ???Mi iNM 1個(gè)個(gè)體加入 到下一代群體中。至此可完全確定出下一代群體中的 M 個(gè)個(gè)體。 （ 3） 排序選擇法 (Rankbased Model)，是按個(gè)體的適應(yīng)度的大小排序，然后按事先設(shè)計(jì)的概率表分配給每一個(gè)個(gè)體，作為各自的選擇概率。 洛陽理工學(xué)院畢業(yè)設(shè)計(jì)（論文） 14 所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 SGA 中交叉算子采用單點(diǎn)交叉算子。 所謂變異運(yùn)算，是指依據(jù)變異概率 Pm 將個(gè)體編碼串中的某些基因值用其它基因值來替換，從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。 在遺傳算法中使用變異算子主要有以下兩 個(gè)目的： 1)改善遺傳算法的局部搜索能力； 2)維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。 遺傳算法的運(yùn)行參數(shù) 遺傳算法中需要選擇的運(yùn)行參數(shù)主要有個(gè)體編碼串長度 L、群體大小 M、交叉率 Pc、變異率 Pm、終止代數(shù) T 等 (a) L ： 編碼串長度 。 (b) M ： 種群規(guī)模。一般取為 20~100； (c) Pc ： 交叉概率。一般取為 ~。 (d) Pm ： 變異概率。一般取為 ~ (b) T ： 遺傳運(yùn)算的終止進(jìn)化代數(shù)。一般取為 100~1000； 至于遺傳算 法的終止條件，還可以利用某種判定準(zhǔn)則，當(dāng)判定出群體已經(jīng)進(jìn)化成熟且不再有進(jìn)化趨勢(shì)時(shí)就可以終止算法的運(yùn)行過程。常用的判定準(zhǔn)則有下面兩種： ①連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一個(gè)極小的閾值；