【正文】 要求的連續(xù)函數(shù)優(yōu)化問題，使用二進(jìn)制編碼來表示個(gè)體時(shí)將會(huì)有一些不利之處。 二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。個(gè)體長度較知時(shí)，可能達(dá)不到精度要求，而個(gè)體編碼長度較長時(shí)，雖然能提高精度，但卻使遺傳算法的搜索空間急劇擴(kuò)大。 所謂浮點(diǎn)法，是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示。在浮點(diǎn)數(shù)編 10 碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等 11 遺傳算子也必須保證其運(yùn)算結(jié)果所產(chǎn)生的新個(gè)體的基因值也在這個(gè)區(qū)間限制范圍內(nèi)。 浮點(diǎn)數(shù)編碼方法有下面幾個(gè)優(yōu)點(diǎn)： （ 1)適用于在遺傳算法中表示范圍較大的數(shù) （ 2)適用于精度要求較高的遺傳算法 （ 3)便于較大空間的遺傳搜索 （ 4)改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算交率 （ 5)便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用 （ 6)便于設(shè)計(jì)針對(duì)問題的專門知識(shí)的知識(shí)型遺傳算子 （ 7)便于處理復(fù)雜的決策變量約束條件 ： 符號(hào)編碼法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號(hào)集如｛ A,B,C?｝。 符號(hào)編碼的主要優(yōu)點(diǎn)是： （ 1)符合有意義積術(shù)塊編碼原則 （ 2)便于在遺傳算法中利用所求解問題的專門知識(shí) （ 3)便于遺傳算法與相關(guān)近似算法之間的混合使用。 但對(duì)于使用符號(hào)編碼方法的遺傳算法，一般需要 認(rèn)真設(shè)計(jì)交叉、變異等遺傳運(yùn)算的操作方法，以滿足問題的各種約束需 求，這樣才能提高算法的搜索性能。 使用遺傳算法第一件事情就是確定染色編碼方式，它根據(jù)不同的問 題模型使用不同 的編碼方式，本系統(tǒng) 使用的是 Grefenstette 等提出 的 一種新的巡回路線編碼方法， 是 一種 整數(shù)編碼的方式 。 對(duì)于每個(gè)城市用一個(gè)整數(shù)來編號(hào)，例如有 45 個(gè)城市，就用 0 到 45 來標(biāo)識(shí)每一個(gè)城市，然后一個(gè)路徑就是一條染色體編碼，染色體長度為 45，如： 0,1,2,3,4...44 就是一個(gè)染色體，它表達(dá)的意思就是旅行者從 0 號(hào)城市出發(fā)，依次訪問 1,2,...44 號(hào)城市再回到0 號(hào)城市；下面 具體 具體 介紹一 下 這一種 編碼方法 。 對(duì)于 給定的旅行商問題 ， 設(shè) 其 城市列表 W， 假定 對(duì) 各個(gè) 城市的 訪問順序?yàn)?T： T=（ T1， T2， T3， ….. ， Tn） 規(guī)定 每訪問完一個(gè) 城市， 就 從 城市列表 W 中 將 該城市 除去，則用第 i（ i=1,2,3……n ）個(gè)所訪問的城市 Ti 在所有未訪問城市列表 W={T1， T2， T3，? ..， Ti1}中的對(duì)應(yīng)位置序號(hào) Gi（ 1≤ Gi≤ ni+1）就可表示具體訪問哪個(gè)城市，如此這樣直到處理完 W 中所有的城市。將全部 Gi 順序排列在一起所得到的一個(gè)列表： G=（ G1， G2， G3， …… ， Gn） 這樣就 可以表示一條 巡回 路線，它就是遺傳算法中的一個(gè) 個(gè)體 基因。例如 ， 假設(shè)現(xiàn)在有這樣一個(gè)城市序列： W=(A,B,C,D,E,F,G,H,I,J) 有 如下兩條 巡回 路線 ： T1=(A,D,B,H,F,I,J,G,E,C) T2=(B,C,A,D,E,J,H,I,F,G) 則按本 系統(tǒng)所用的編碼方法 ， 這兩 條 巡回路線可以編碼為： G1 =(1,3,1,5,3,4,4,3,2,1) 12 G2 =(2,2,1,1,1,5,3,3,1,1) 這種 編碼方式的 優(yōu)點(diǎn) 在于任意的染色體都對(duì)應(yīng)一條有實(shí)際意義的巡回路線， 因此 可以使用常規(guī)的交叉算子對(duì)它 進(jìn)行 計(jì)算，有利于算 法的實(shí)現(xiàn)。 算子的設(shè)計(jì)（ 交叉 、選擇、變異） 交叉 算子 交叉運(yùn)算，一般 指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 求解 旅行商 問題的遺傳算法的交叉算法主要有：部分匹配交叉（ PMX） 、 循環(huán)交叉（ CX） 、次序 交叉（ OX） 、線性次序 交叉（ LOX） 、 邊重組交叉（ EX） 等 。 本 系統(tǒng)使用的是常規(guī)的 單點(diǎn) 交叉算子 。 由于 在確定算法的編碼方式的過程中使用的是 Grefenstette 等提出的 編碼方式，用這種編碼方式表示個(gè)體時(shí)，個(gè)體的 基因型 和表現(xiàn)型之間是一一對(duì)應(yīng)的， 它使 經(jīng)過運(yùn)算之后得到的每一個(gè)基因型都是一條有 實(shí)際 意義的 巡回 路線。因此 ， 就可以使用常規(guī)的單點(diǎn)交叉算子 。使用 單點(diǎn)交叉，即在個(gè)體的編碼串上隨機(jī)設(shè)置一個(gè)交叉點(diǎn)， 然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。產(chǎn)生 下一代個(gè)體在使用 Grefenstette 等提出的 編碼方式 時(shí) ， 染色體 編碼串 前面 的一 些 基因發(fā)生變化 時(shí) ，會(huì)對(duì)后面的基因值 產(chǎn)生巨大 的影響 ，產(chǎn)生 的新的個(gè)體 與 上一代的性狀變化 就會(huì) 十分明顯，有利于整個(gè)算法 跳出 局部最優(yōu)解。 如下 是具體代碼： for(i=0。im_CrossNum。i++) { int nPos, temp=0。 int parent1=0。 //父代基因 1 int parent2=0。 //父代基因 2 parent1=RandomInt(0,m_nGroupSize1)。 temp=RandomInt(0,m_nGroupSize1)。 if(parent1temp) parent1=temp。 parent2=RandomInt(0,m_nGroupSize1)。 temp=RandomInt(0,m_nGroupSize1)。 if(parent2temp) parent2=temp。 //復(fù)制用于交叉的基因?qū)? PopNode pop1。 PopNode pop2。 (amp。oldpop[parent1])。 (amp。oldpop[parent2])。 13 // 基因序列中用于交叉的基因位 nPos=RandomInt(3,MAXCHROM3)。 (amp。pop2, nPos)。 //交叉完成 ,保存結(jié)果 newpop[m_nGroupSize+2*i].CopyNode(amp。pop1)。 newpop[m_nGroupSize+2*i+1].CopyNode(amp。pop2)。 選擇 算子 選擇操作是建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上的。選擇操作的目的是為了避免基因缺失、提高全局收斂 性和計(jì)算效率。本課題采用最常用的選擇算子 —— 比例選擇算子（又 稱輪盤賭選擇） 。其基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。適應(yīng)度越高的個(gè)體被選中的概率也越大；反之，適應(yīng)度越低的個(gè)體被選中的概率也越小。具體 操作如下： 計(jì)算出群體中每個(gè)個(gè)體的適應(yīng)度 f(i=1， 2，?， M)， M 為群體大?。? 歸一化 適應(yīng)度 f 的值 將 適應(yīng)度 f 的 值從 大 到小排列， 查找 其中 最小 費(fèi) 用 的個(gè)體 然后 將其作為 下一代 選擇出來。 具體 代碼如下： for(int gen=0。genm_GANum。gen++) { // 計(jì)算當(dāng)前一代群體中個(gè)體的適應(yīng)度數(shù)值 F for(int i=0。im_nGroupSize。i++) TotalF+=1/oldpop[i].CalcCost(m_distance)。 // 歸一化 F 值 for(i=0。im_nGroupSize。i++) oldpop[i].fit=1/oldpop[i].cost/TotalF*100。 // 將當(dāng)前一代群體中的個(gè)體按 F 值從大到小排序 for(i=0。im_nGroupSize1。i++) { double max=。 int maxpos。 for(int j=i。jm_nGroupSize。j++) if(oldpop[j].fitmax) { max=oldpop[j].fit。 maxpos=j。 14 } if(i!=maxpos) oldpop[i].SwapNode(amp。oldpop[maxpos])。 } m_CurGANum=gen。 // 查找當(dāng)前一代中的最小費(fèi)用個(gè) 體 m_MiniCost=oldpop[0].cost。 (amp。oldpop[0])。 m_GAFitness=。 //AfxMessageBox(顯示數(shù)據(jù) )。 UpdateData(false)。 UpdateWindow()。 if (m_CurGANum == m_GANum 1) { // 繪制圖形 DrawNetwork()。 } //繼承所有父代基因 for(i=0。im_nGroupSize。i++) newpop[i].CopyNode(amp。oldpop[i])。 變異 算子 變異運(yùn)算，是指改變個(gè)體編碼串中的某些基因值，從而形成新的個(gè)體。變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，決定遺傳算法的局部搜索能力，保證了種群的多樣性。交叉運(yùn)算可以和變異運(yùn)算相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。本系統(tǒng)中變異算子采用基本位變異算子。 基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。 因?yàn)?使用由 Grefenstette 等所提出的編譯方法來表示個(gè)體，一個(gè)個(gè) 體經(jīng)過遺傳運(yùn)算后所得到的任意一個(gè)基因型個(gè)體 與交叉后的情況相同， 都能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線 。 對(duì)于二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為 0，則將其變?yōu)?1；反之，若原有基因值為 1，則將其變?yōu)?0 ?；疚蛔儺愃阕拥膱?zhí)行過程如下： 15 （ 1）對(duì)個(gè)體的每一個(gè)基因座，依變異概率 Pm 指定其為變異點(diǎn)。 （ 2）對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其他等位基因值來代替，從而產(chǎn)生出一個(gè)新個(gè)體。 針對(duì)旅行商問題對(duì)變異算子的設(shè)計(jì)要求，基本位變異即交換變異。 變異是單個(gè)個(gè)體內(nèi)部發(fā)生變化，導(dǎo)致產(chǎn)生新個(gè)體， 從而產(chǎn)生出一條新的巡回路線。例如： Tx=（ B C A D E J H I F G） （ B C A I E J H D F G） =Tx′ 具體 代碼如下 ： for(i=0。im_VariNum。i++) { int nPos1,nPos2,parent=0。 //變異父代基因 parent=RandomInt(0,m_nGroupSize1) （ 定義 變異范圍 ） nPos1=RandomInt(3,MAXCHROM3)。 （ 取 其中 第三位與 倒數(shù)第三位做 nPos2=RandomInt(3,MAXCHROM3)。 為變異結(jié)點(diǎn) ） PopNode pop。 (amp。oldpop[0])。 (nPos1,nPos2)。（ 執(zhí)行結(jié)點(diǎn)操作 ） newpop[m_nGroupSize+m_CrossNum*2+i].CopyNode(amp。pop)。（ 保存變異結(jié)果 ） } 適應(yīng)度函數(shù) 在遺傳算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體中的概率。個(gè)體 的 適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體 的 適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小。 因此適應(yīng)度函數(shù)的選擇至關(guān)重要，直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。 本 系統(tǒng) 中以每條路徑長度的倒數(shù)作為適應(yīng)度函數(shù)值，并對(duì)其進(jìn)行 統(tǒng) 一化 的 操作，即按從大到小 進(jìn)行 排序，為下一步選擇操作做準(zhǔn)備。 為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。具體代碼如下所示 ： for(int i=0。im_nGroupSize。i++) （ nGroupSize 是 城市 之間 的距離） TotalF+=1/oldpop[i].CalcCost(m_distance)。（父代 結(jié)點(diǎn)的城市距離的倒數(shù)作為它的適應(yīng)度） 遺傳算法求解 TSP問題的具體流程圖 16 圖 35 遺傳算法 求解旅行商問題的具體流程圖 開始產(chǎn)生城市對(duì)城市進(jìn)行編碼初始化遺傳算法相關(guān)參數(shù)計(jì)算個(gè)體適應(yīng)度是否符合終止條件 ？輸出正確的T S P 結(jié)果比例選擇算法常規(guī)單點(diǎn)交叉基本位變異算法G E N = G E N + 1是否 17 4 45個(gè)城市旅行