【文章內(nèi)容簡介】 010100010 10010010 雜交操作 （ Crossover Revisited） 這一函數(shù)要求２個染色體在同一隨機位置上斷裂開，然后將它們在斷開點以后部分進行互換，以形成 2 個新的染色體 ( 子代 ) 。 void CgaBob::Crossover( const vectorint amp。mum, const vectorint amp。dad, vectorint amp。baby1, vectorint amp。baby2){ 這一函數(shù)共傳入 4 個參數(shù)，參數(shù)傳遞均采用引用 reference 方式，其中前 2 個傳入父輩 parent 的染色體（染色體只是一個整數(shù)型的矢量 std::vector ），后 2 個是用來 copy 子代染色體的空矢量。 if ( (RandFloat() mdCrossoverRate) || (mum= dad) ){ baby1 = mum。 baby2 = dad。 return。 } 這里，首先是進行檢測，看 mum 和 dad 兩個上輩是否需要進行雜交。 雜交發(fā)生的概率是由參數(shù) m_dCrossoverRate 確定。 如果不發(fā)生雜交，則２個上輩染色體就直接復(fù)制為子代，函數(shù)立即返回。 int cp = RandInt(0, m_iChromoLength 1) ； 沿染色體的長度隨機選擇一個點來裂開染色體。 for (int i=0。 icp。 i++){ (mum[i])。 (dad[i])。 } for (i=cp。 i()。 i++){ (dad[i])。 (mum[i])。} 這兩循環(huán)把 2 個 parent 染色體在雜交點 （ CP,crossover point ） 以后的所有位進行了互換 ， 并把新染色體賦給了 2 個子代 : baby1 和 baby2 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 45 什么是變異率？ ( What39。s the Mutation Rate? ) 變異率 （ 突變率 ） 就是在一個染色體中將位實行翻轉(zhuǎn) （ flip， 即 0 變 1， 1變 0） 的幾率 。 這對于二進制編碼的基因來說通常都是很低的值 ，比如 。 因此 ， 無論你從群體中怎樣選擇染色體 ， 你首先是檢查是否要雜交 ， 然后再從頭到尾檢查子代染色體的各個位 ， 并按所規(guī)定的幾率對其中的某些位實行突變 （ 翻轉(zhuǎn) ） 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 46 變異操作 （ Mutation Revisited） 這一函數(shù)所做的工作，不過就是沿著一個染色體的長度，一 bit一bit地進行考察，并按 m_dMutationRate給定的幾率，將其中某些bit實行翻轉(zhuǎn)。 void CgaBob::Mutate(vectorint amp。vecBits){ for (int curBit=0。 curBit()。 curBit++) { //是否要翻轉(zhuǎn)此 bit? if (RandFloat() m_dMutationRate){ //是，就翻轉(zhuǎn)此 bit vecBits[curBit] = !vecBits[curBit]。 } }//移到下一個 bit } 遺傳算法程序也就這樣完成了！ 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 47 用遺傳算法解決問題時 ， 首先要對待解決問題的模型結(jié)構(gòu)和參數(shù)進行編碼 ， 一般用字符串表示 ， 這個過程就將問題符號化 、 離散化了 。 也有在連續(xù)空間定義的 GA(Geic Algorithm in Continuous Space, GACS)， 暫不討論 。 ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 48 一個串行運算的遺傳算法 (Seguential Geic Algoritm, SGA)按如下過程進行 (1)對待解決問題進行編碼； (2)隨機初始化群體 X(0):=(x1, x2, … xn)； (3)對當(dāng)前群體 X(t)中每個個體 xi計算其適應(yīng)度 F(xi)， 適應(yīng)度表示了該個體的性能好 壞； (4)應(yīng)用選擇算子產(chǎn)生中間代 Xr(t)； (5)對 Xr(t)應(yīng)用其它的算子 ， 產(chǎn)生新一代群體X(t+1)， 這些算子的目的在于擴展有限個體的覆蓋面 ， 體現(xiàn)全局搜索的思想； (6)t:=t+1；如果不滿足終止條件繼續(xù) (3) 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 49 GA中最常用的算子 (1)選擇算子 (selection/reproduction): 選擇算子從群體中按某一概率成對選擇個體 ， 某個體 xi被選擇的概率 Pi與其適應(yīng)度值成正比 。 最通常的實現(xiàn)方法是輪盤賭 (roulett e wheel)模型 。 (2)交叉算子 (Crossover): 交叉算子將被選中的兩個個體的基因鏈按概率 pc進行交叉 ， 生成兩個新的個體 ，交叉位置是隨機的 。 其中 Pc是一個系統(tǒng)參數(shù) 。 (3)變異算子 (Mutation): 變異算子將新個體的基因鏈的各位按概率 pm進行變異 ， 對二值基因鏈 (0,1編碼 )來說即是取反 。 上述各種算子的實現(xiàn)是多種多樣的 ， 而且許多新的算子正不斷提出 ， 以改進 GA的某些性能 。 系統(tǒng)參數(shù) (個體數(shù) n,基因鏈長度 l,交叉概率 Pc,變異概率 Pm等 )對算法的收斂速度及結(jié)果有很大的影響 ， 應(yīng)視具體問題選取不同的值 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 50 TPopulation類包含兩個重要過程： FillFitness:評價函數(shù) ， 對每個個體進行解碼(decode)并計算出其適應(yīng)度值 ， 具體操作在用戶類中實現(xiàn) 。 Statistic:對當(dāng)前群體進行統(tǒng)計 ， 如求總適應(yīng)度sumfitness、 平均適應(yīng)度 average、 最好個體 fmax、 最壞個體 fmin等 。 TSGA類在 TPopulation類的基礎(chǔ)上派生 ， 以 GA的系統(tǒng)參數(shù)為構(gòu)造函數(shù)的參數(shù) ， 它有 4個重要的成員函數(shù)： Select:選擇算子 ， 基本選擇策略采用輪盤賭模型 。 輪盤經(jīng)任意旋轉(zhuǎn)停止后指針?biāo)赶騾^(qū)域被選中 ， 所以 fi值大的被選中的概率就大 。 Crossover:交叉算子 ， 以概率 Pc在兩基因鏈上的隨機位置交換子串 。 Mutation:變異算子 ， 以概率 Pm對基因鏈上每一個基因進行隨機干擾 (取反 )。 Generate: 產(chǎn)生下代 ， 包括了評價 、 統(tǒng)計 、 選擇 、 交叉 、 變異等全部過程 ， 每運行一 次 ， 產(chǎn)生新的一代 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 51 二、遺傳算法的主要特征 遺傳算法 目的是獲得 “ 最好解 ” ， 可以把這種任務(wù)看成是一個優(yōu)化過程 。 對于小空間 ， 經(jīng)典的窮舉法就足夠了； 而對大空間 ， 則需要使用特殊的人工智能技術(shù) 。 遺傳算法 (Geic Algorithm)是人工智能技術(shù)中的一種 ， 是一類模擬生物進化過程而產(chǎn)生的 ,由選擇算子 、雜交算子和變異算子三個基本算子組成的全局尋優(yōu)算法 。 過程： 它從一個初始族出發(fā) ， 由選擇算子選出性狀好的父本 ，由雜交算子進行雜交運算 ， 變異算子進行少許變異 ，在一定概率規(guī)則控制下隨機搜索模型空間 。 一代代進化 ， 直到最終解族對應(yīng)的誤差泛函值達到設(shè)定的要求 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 52 遺傳算法的結(jié)構(gòu) ： Procedure Geic Algorithm begin t=0 initialize p(t) evaluate p(t) while (not terminationcondition) do begin t=t+1 select p(t) from p(t1) alter p(t) evaluate p(t) end end 二、遺傳算法的主要特征： 圖 1遺傳算法的結(jié)構(gòu) ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 53 在第次迭代 ， 遺傳算法維持一個潛在解的群體 },{)( 21 tntt xxxtp ?? 每個解 tix1?t用其 “ 適應(yīng)值 ” 評價 。 然后通過選擇更合適個體 （ t+1 次迭代 ） 形成一個新的群體 。 新的群體的成員通過雜交和變異進行變換 ， 形成新的解 。 雜交組合了兩個親體染色體 （ 即待求參數(shù)的二進制編碼串 ） 的特征 ， 通過交換父代相應(yīng)的片斷形成了兩個相似的后代 。 例如父代染色體為 ),( 11111 edcba ),( 22222 edcba和 在第二個基因后雜交，產(chǎn)生的后代為 ),(22211 edcba),( 11122 edcba和 二、遺傳算法的主要特征： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 54 雜交算子的目的是在不同潛在解之間進行信息交換 。 變異是通過用一個等于變異率的概率隨機地改變被選擇染色體上的一個或多個基因 （ 染色體中的一個二進制位 ） 。 變異算子的意圖是向群體引入一些額外的變化性 。 二、遺傳算法的主要特征： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 55 遺傳算法的特點 ： (1).它不是直接作用于參變量集上 ， 而是作用于參變量的某種編碼形成的數(shù)字串上 。 (2).它不是從單個點 ， 而是從一個解族開始搜索解空間 ， 與傳統(tǒng) “ 點對點 ” 式的搜索方法不同 。 (3).它僅僅利用適應(yīng)值信息評估個體的優(yōu)劣 ， 無須求導(dǎo)數(shù)或其它輔助信息 。 (4).它利用概率轉(zhuǎn)移規(guī)則 ， 而非確定性規(guī)則 。 優(yōu)勢 ： (1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。 (2). 由于其固有的并行性，適合于大規(guī)模并行計算。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 56 三、遺傳算法的運行步驟： 1. 一般性描述： 不失一般性 ， 考慮求最大值的問題 。 問題： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 57 1) 編碼和解碼 2)產(chǎn)生潛在解初始群體 3)根據(jù)適應(yīng)值評價解的適應(yīng)程度并據(jù)此生成新群體 4)雜交 (crossover)和變異 (mutation)—決定新群體的性狀 隨著選擇 、 雜交和變異的進行 ， 新群體就為下一次的評價做好了準(zhǔn)備 。 該評價是用來為下一次選