【正文】 編碼 ，使得它能能被遺傳算法機(jī)制所利用 。 在運(yùn)行開(kāi)始時(shí) ， 創(chuàng)建一個(gè)染色體的群體 ， 每個(gè)染色體都是一組隨機(jī)的２進(jìn)制位 。 作為一個(gè)例子 ， 長(zhǎng)度為 20的染色體的形狀如下 : 01010010100101001111 重要的事情是 ， 每個(gè)染色體都用這樣的方式編碼成為由 0和 1組成的字符串 ， 而它們通過(guò) 譯碼 就能用來(lái)表示你手頭問(wèn)題的一個(gè)解 。 初始群體通常都是 較糟的 ， 有點(diǎn)中國(guó)男足球隊(duì) 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 40 不斷進(jìn)行下列循環(huán) ， 直到尋找出一個(gè)解 : ， 看它解決問(wèn)題的性能怎樣 ， 并相應(yīng)地為它分配一個(gè)適應(yīng)性分?jǐn)?shù) 。 被選出的概率正比于染色體的適應(yīng)性 ， 適應(yīng)性分?jǐn)?shù)愈高 ， 被選中的可能性也就愈大 。 雜交率 （ Crossover Rate ） ， 從每個(gè)選中染色體的一個(gè)隨機(jī)的點(diǎn)上進(jìn)行雜交 （ crossover ） 。 2， 3， 4， 直到 100個(gè)成員的新群體被創(chuàng)建出來(lái) 。 而我把這整個(gè)的循環(huán)稱作一個(gè)時(shí)代 （ epoch） 。s the Roulette Wheel Selection ) 輪盤(pán)賭選擇是從染色體群體中選擇一些成員的方法 ， 被選中的機(jī)率和它們的適應(yīng)性分?jǐn)?shù)成比例 ， 染色體的適應(yīng)性分?jǐn)?shù)愈高 ， 被選中的概率也愈多 。 其工作過(guò)程是這樣的： 設(shè)想群體全體成員的適當(dāng)性分?jǐn)?shù)由一張餅圖來(lái)代表 (見(jiàn)下圖 )， 這一餅圖就和用于賭博的轉(zhuǎn)輪形狀一樣 。 塊的大小與染色體的適應(yīng)性分?jǐn)?shù)成比例 ，適應(yīng)性分?jǐn)?shù)愈高 ， 它在餅圖中對(duì)應(yīng)的小塊所占面積也愈大 。 染色體的輪盤(pán)賭式選擇 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 42 輪盤(pán)賭選擇 SGenomeamp。 我們從零到整個(gè)適應(yīng)分范圍內(nèi)隨機(jī)選取了一實(shí)數(shù) fSlice 。 double cfTotal = O。 for (int i=O。 ++i){ cfTotal += m_vecGenomes[i].dFitness。 break。 } 程序通過(guò)循環(huán)來(lái)考察各基因組，把它們相應(yīng)的適應(yīng)性分?jǐn)?shù)一個(gè)一個(gè)累加起來(lái)，直到這一 部分累加和 大于 fSlice 值時(shí)，就返回該基因組。s the Crossover Rate ) 雜交率就是用來(lái)確定 2個(gè)染色體進(jìn)行局部的位 （ bit） 的互換以產(chǎn)生 2個(gè)新的子代的概率 。 每次 ， 從群體中選擇 2個(gè)染色體 ， 同時(shí)生成其值在 0到 1之間一個(gè)隨機(jī)數(shù) ， 然后根據(jù)此數(shù)據(jù)的值來(lái)確定兩個(gè)染色體是否要進(jìn)行雜交 。 例如 ， 設(shè)給定的 2個(gè)染色體為 : 10001001110010010 01010001001000011 沿著它們的長(zhǎng)度你隨機(jī)選擇一個(gè)位置 ， 比如說(shuō) 10， 然后互換第 10位之后所有位 。 void CgaBob::Crossover( const vectorint amp。dad, vectorint amp。baby2){ 這一函數(shù)共傳入 4 個(gè)參數(shù)，參數(shù)傳遞均采用引用 reference 方式，其中前 2 個(gè)傳入父輩 parent 的染色體（染色體只是一個(gè)整數(shù)型的矢量 std::vector ），后 2 個(gè)是用來(lái) copy 子代染色體的空矢量。 baby2 = dad。 } 這里，首先是進(jìn)行檢測(cè)，看 mum 和 dad 兩個(gè)上輩是否需要進(jìn)行雜交。 如果不發(fā)生雜交，則２個(gè)上輩染色體就直接復(fù)制為子代，函數(shù)立即返回。 for (int i=0。 i++){ (mum[i])。 } for (i=cp。 i++){ (dad[i])。} 這兩循環(huán)把 2 個(gè) parent 染色體在雜交點(diǎn) （ CP,crossover point ） 以后的所有位進(jìn)行了互換 ， 并把新染色體賦給了 2 個(gè)子代 : baby1 和 baby2 。s the Mutation Rate? ) 變異率 （ 突變率 ） 就是在一個(gè)染色體中將位實(shí)行翻轉(zhuǎn) （ flip， 即 0 變 1， 1變 0） 的幾率 。 因此 ， 無(wú)論你從群體中怎樣選擇染色體 ， 你首先是檢查是否要雜交 ， 然后再?gòu)念^到尾檢查子代染色體的各個(gè)位 ， 并按所規(guī)定的幾率對(duì)其中的某些位實(shí)行突變 （ 翻轉(zhuǎn) ） 。 void CgaBob::Mutate(vectorint amp。 curBit()。 } }//移到下一個(gè) bit } 遺傳算法程序也就這樣完成了！ 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 47 用遺傳算法解決問(wèn)題時(shí) ， 首先要對(duì)待解決問(wèn)題的模型結(jié)構(gòu)和參數(shù)進(jìn)行編碼 ， 一般用字符串表示 ， 這個(gè)過(guò)程就將問(wèn)題符號(hào)化 、 離散化了 。 ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 48 一個(gè)串行運(yùn)算的遺傳算法 (Seguential Geic Algoritm, SGA)按如下過(guò)程進(jìn)行 (1)對(duì)待解決問(wèn)題進(jìn)行編碼； (2)隨機(jī)初始化群體 X(0):=(x1, x2, … xn)； (3)對(duì)當(dāng)前群體 X(t)中每個(gè)個(gè)體 xi計(jì)算其適應(yīng)度 F(xi)， 適應(yīng)度表示了該個(gè)體的性能好 壞； (4)應(yīng)用選擇算子產(chǎn)生中間代 Xr(t)； (5)對(duì) Xr(t)應(yīng)用其它的算子 ， 產(chǎn)生新一代群體X(t+1)， 這些算子的目的在于擴(kuò)展有限個(gè)體的覆蓋面 ， 體現(xiàn)全局搜索的思想； (6)t:=t+1；如果不滿足終止條件繼續(xù) (3) 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 49 GA中最常用的算子 (1)選擇算子 (selection/reproduction): 選擇算子從群體中按某一概率成對(duì)選擇個(gè)體 ， 某個(gè)體 xi被選擇的概率 Pi與其適應(yīng)度值成正比 。 (2)交叉算子 (Crossover): 交叉算子將被選中的兩個(gè)個(gè)體的基因鏈按概率 pc進(jìn)行交叉 ， 生成兩個(gè)新的個(gè)體 ，交叉位置是隨機(jī)的 。 (3)變異算子 (Mutation): 變異算子將新個(gè)體的基因鏈的各位按概率 pm進(jìn)行變異 ， 對(duì)二值基因鏈 (0,1編碼 )來(lái)說(shuō)即是取反 。 系統(tǒng)參數(shù) (個(gè)體數(shù) n,基因鏈長(zhǎng)度 l,交叉概率 Pc,變異概率 Pm等 )對(duì)算法的收斂速度及結(jié)果有很大的影響 ， 應(yīng)視具體問(wèn)題選取不同的值 。 Statistic:對(duì)當(dāng)前群體進(jìn)行統(tǒng)計(jì) ， 如求總適應(yīng)度sumfitness、 平均適應(yīng)度 average、 最好個(gè)體 fmax、 最壞個(gè)體 fmin等 。 輪盤(pán)經(jīng)任意旋轉(zhuǎn)停止后指針?biāo)赶騾^(qū)域被選中 ， 所以 fi值大的被選中的概率就大 。 Mutation:變異算子 ， 以概率 Pm對(duì)基因鏈上每一個(gè)基因進(jìn)行隨機(jī)干擾 (取反 )。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 51 二、遺傳算法的主要特征 遺傳算法 目的是獲得 “ 最好解 ” ， 可以把這種任務(wù)看成是一個(gè)優(yōu)化過(guò)程 。 遺傳算法 (Geic Algorithm)是人工智能技術(shù)中的一種 ， 是一類模擬生物進(jìn)化過(guò)程而產(chǎn)生的 ,由選擇算子 、雜交算子和變異算子三個(gè)基本算子組成的全局尋優(yōu)算法 。 一代代進(jìn)化 ， 直到最終解族對(duì)應(yīng)的誤差泛函值達(dá)到設(shè)定的要求 。 然后通過(guò)選擇更合適個(gè)體 （ t+1 次迭代 ） 形成一個(gè)新的群體 。 雜交組合了兩個(gè)親體染色體 （ 即待求參數(shù)的二進(jìn)制編碼串 ） 的特征 ， 通過(guò)交換父代相應(yīng)的片斷形成了兩個(gè)相似的后代 。 變異是通過(guò)用一個(gè)等于變異率的概率隨機(jī)地改變被選擇染色體上的一個(gè)或多個(gè)基因 （ 染色體中的一個(gè)二進(jìn)制位 ） 。 二、遺傳算法的主要特征： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 55 遺傳算法的特點(diǎn) ： (1).它不是直接作用于參變量集上 ， 而是作用于參變量的某種編碼形成的數(shù)字串上 。 (3).它僅僅利用適應(yīng)值信息評(píng)估個(gè)體的優(yōu)劣 ， 無(wú)須求導(dǎo)數(shù)或其它輔助信息 。 優(yōu)勢(shì) ： (1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 56 三、遺傳算法的運(yùn)行步驟： 1. 一般性描述： 不失一般性 ， 考慮求最大值的問(wèn)題 。 該評(píng)價(jià)是用來(lái)為下一次選擇過(guò)程建立概率分布的 ， 即建立一個(gè)根據(jù)當(dāng)前適應(yīng)值構(gòu)造寬距的輪盤(pán) 。 如果確實(shí)有一些關(guān)于最優(yōu)分布的知識(shí) ， 可以使用這些信息來(lái)設(shè)定初始潛在解的集合 。 按照如下方法構(gòu)造輪盤(pán) （ 假設(shè)這里的適應(yīng)值時(shí)正值 ， 否則可以使用一些比例機(jī)制調(diào)整 ） ： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 61 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 62 4)雜交 (crossover)和變異 (mutation)—決定新群體的性狀 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 63 隨著選擇 、 雜交和變異的進(jìn)行 ， 新群體就為下一次的評(píng)價(jià)做好了準(zhǔn)備 。 其它的部分只是上述步驟的循環(huán)重復(fù) ， 見(jiàn)圖 1。 由于 ，因此染色體的第一部分需要 18位 。 例如 ， 第396代中的最好染色體的值為 。 跟蹤進(jìn)化過(guò)程中的最好個(gè)體是容易的 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 81 例 2： 為四個(gè)連鎖飯店尋找最好的經(jīng)營(yíng)決策，其中一個(gè)經(jīng)營(yíng)飯店的決策包括要做出以下三項(xiàng)決定： （ 1）價(jià)格 漢堡包的價(jià)格應(yīng)該定在 50美分還是 1美元？ （ 2）飲料 和漢堡包一起供應(yīng)的應(yīng)該是酒還是可樂(lè)？ （ 3）服務(wù)速度 飯店應(yīng)該提供慢的還是快的服務(wù)？ 目的： 找到這三個(gè)決定的組合以產(chǎn)生最高的利潤(rùn)。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 82 飯店編號(hào) 價(jià) 格 飲 料 速 度 二進(jìn)制表示 1 高 可樂(lè) 快 011 2 高 酒 快 001 3 低 可樂(lè) 慢 110 4 高 可樂(lè) 慢 010 表 1 飯店問(wèn)題的表示方案（其中的 4個(gè)） 群體規(guī)模 N＝ 4 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 83 第 0代 i 串 xi 適應(yīng)值 f（ xi） 1 011 3 2 001 1 3 110 6 4 010