【正文】 ： 使用基本遺傳算法求解旅行商問題（TSP）。最早的旅行商問題的數(shù)學(xué)規(guī)劃是由Dantzig（1959）等人提出[10]。（9）機器學(xué)習(xí)：基于GA的機器學(xué)習(xí)、特別分類器系統(tǒng)，在調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)、神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化設(shè)計、和多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。目前，GA已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識別等方面得到了應(yīng)用。（4）自動控制：GA在自動控制領(lǐng)域中的應(yīng)用日益增加，并顯示了良好的效果。 遺傳算法由于具有魯棒性強，實現(xiàn)簡單，對問題依賴性小等優(yōu)點，為求解復(fù)雜系統(tǒng)優(yōu)化問題提供了通用框架，下面是一些主要應(yīng)用領(lǐng)域：（1）函數(shù)優(yōu)化：是GA的經(jīng)典應(yīng)用領(lǐng)域，也是對GA進行性能評價的常用算例，對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，GA卻可以得到較好的結(jié)果。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。遺傳算法僅用適應(yīng)度函數(shù)值來評估個體，而無須搜索空間的知識或其它輔助信息。 遺傳算法的基本作用對象是多個可行解的集合，而非單個可行解。這一特點使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域，例如：通過對連接矩陣的操作，遺傳算法可用來對神經(jīng)網(wǎng)絡(luò)或自動機的結(jié)構(gòu)或參數(shù)加以優(yōu)化。然后，把這些假設(shè)解置于問題的“環(huán)境”中，設(shè)定相應(yīng)的適應(yīng)度函數(shù)，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體” 群。變異率：發(fā)生變異的基因位數(shù)所占全體個體的基因總位數(shù)的比例，~。選擇（selection）操作：選擇（selection）操作是模擬生物界優(yōu)勝劣汰的自然選擇法則，從種群中選擇適應(yīng)度較好（較好可能是高于種群的平均適應(yīng)度也可能是低于種群的平均適應(yīng)度，取決于要解決的問題和使用什么作為適應(yīng)度）的個體來生成下一代種群進行交叉變異?；? gene)：位串中的元素，表示不同的特征，對應(yīng)于生物學(xué)中的遺傳物質(zhì)單位，以DNA序列形式把遺傳信息譯成編碼。為了在下面的研究中做到準確、清晰、規(guī)范的描述，對本文使用到的遺傳算法術(shù)語解釋如下[3]：個體(individual)：遺傳算法中處理的基本對象、數(shù)據(jù)結(jié)構(gòu)，對應(yīng)于自然遺傳學(xué)中的生物個體。2002年，戴曉明等應(yīng)用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Buildingblock Coded Parallel GA，BCPGA）。實驗結(jié)果表明，SIGH與單點交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力[2]。 遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體（優(yōu)勝劣汰），利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標為止。最后一代候選解群中的最優(yōu)解就是所求得的最優(yōu)解。（simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（simplex crossover），該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實上他的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。種群( population)：個體的集合，對應(yīng)于自然遺傳學(xué)中的生物種群。基因位( locus)：某一基因在位串（染色體）中的位置適應(yīng)度(fitness)：某一個體對于環(huán)境的適應(yīng)程度，或者在環(huán)境壓力下的生存能力，取決于遺傳特性。交叉(crossover)操作：交叉就是互換兩個染色體某些位上的基因以產(chǎn)生新的個體，普通遺傳算法中常用的交叉算子有單切點交叉、雙切點交叉、循環(huán)交叉。遺傳算法是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。這樣，一代一代地進化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，得到問題的最優(yōu)解或者近似最優(yōu)解。通過對集合的操作，遺傳算法可實現(xiàn)對規(guī)則集合或知識庫的精練而達到高質(zhì)量的機器學(xué)習(xí)目的[5]。它是采用同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進行評估。遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。遺傳算法執(zhí)行選擇、交叉、變異等類似生物進化過程的簡單隨機操作，具有極強的魯棒性。（2）組合優(yōu)化[6]：隨問題規(guī)模的擴大，搜索空間急劇擴大，對這類復(fù)雜問題，實踐證明，GA對于組合優(yōu)化的NP完全問題非常有效。如在參數(shù)辨識、人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)，都顯示了GA的應(yīng)用優(yōu)勢。（7）人工生命[7]：基于GA的進化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，已在其進化模型、學(xué)習(xí)模型、行為模型等方面得到應(yīng)用。（10）生物信息學(xué)：多重序列比對是生物信息學(xué)的重要研究內(nèi)容，它的目標是通過同時比較多個序列，發(fā)現(xiàn)它們之間的相似區(qū)域和保守性位點, 進而推斷未知生物分子的結(jié)構(gòu)和功能， 或者重構(gòu)系統(tǒng)發(fā)育樹，尋找物種之間的進化關(guān)系[8]。顧名思義，旅行商問題就是有一個推銷員，要到n個城市推銷商品，最后再回到出發(fā)點，為了節(jié)約時間和成本，他想找出一個包含所有n個城市并且總路徑（包括回到出發(fā)點）最短的環(huán)路。 在基本遺傳算法基礎(chǔ)上，對算法加以改進，加快算法的收斂速度和提高解的質(zhì)量。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中的選擇、交叉、變異機理的模仿，來完成對問題最優(yōu)解的自適應(yīng)搜索過程。（4）對種群中的個體進行隨機兩兩配對（若種群大小為M，則有M/2對），然后根據(jù)交叉概率從配對的個體中選出一部分執(zhí)行交叉操作。 end for for i=1 to M/2 do //執(zhí)行交叉操作 Crossover operation to P(t)。遺傳算法通過對這種個體編碼的操作，不斷搜索出適應(yīng)度較高的個體，并在群體中逐漸增加其數(shù)量，最終尋求出問題的最優(yōu)解或近似最優(yōu)解。由于遺傳算法應(yīng)用的廣泛性，迄今為止人們已經(jīng)提出了許多種不同的編碼方法。若將各個城市按其代號的小標進行編號，則這個個體也可以表示為Xt=[1,2,…,n] 這種編碼方案問題得到自然表示符合上述兩個編碼原則，并且便于與相關(guān)近似算法（如模擬退火算法）混合使用。需要說明的是，這四個運行參數(shù)對遺傳算法的求解結(jié)果的質(zhì)量和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)，在遺傳算法的實際應(yīng)用中往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。與此相類似，遺傳算法中也使用適應(yīng)度這個概念來度量群體中各個個體在優(yōu)化計算中有可能達到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。而對目標函數(shù)值得使用是通過評價個體的適應(yīng)度來體現(xiàn)的。例如n個城市旅行商問題（TSP）中，用來表示個體適應(yīng)度的就可以是按個體的位串表示的巡回這n個城市的順序的環(huán)路總距離。這里選擇概率的計算公式：P(xi)= (22)其中f為適應(yīng)度函數(shù)，f(xi)為的適應(yīng)度注：此公式只適應(yīng)于選中概率與適應(yīng)度值大小成正比的情況（也就是適應(yīng)度值越大表示適應(yīng)度越優(yōu)），對于某些適應(yīng)度值越小表示的適應(yīng)度越優(yōu)的情況，需要使用下面公式：P(xi)= (23)其中f為適應(yīng)度函數(shù)，f(xi)為的適應(yīng)度遺傳算法中的交叉操作是先對種群中的個體進行隨機兩兩配對（若種群大小為M，則有M/2對），然后根據(jù)交叉概率從配對的個體中選出一部分 （Pc*（M/2）對）執(zhí)行交叉。 切點 切點C1= A1 A2|B3 B4C2 = B1 B2|A3 A4P1=A1 A2∣A3 A4P2=B1 B2∣B3 B4 圖22單切點交叉單切點交叉操作的信息量比較小，交叉位置的選擇可能帶來較大的偏差，并且染色體末尾的基因總是被交換。 C1=2 _ _3 _ _ 6 _ _C2= 3 _ _6_ _ 2 _ _循環(huán)2：94P1=2 4 5 3 8 9 6 1 7P1=3 9 8 6 5 4 2 7 1循環(huán)1：236C1=2 9 5 3 8 4 6 _ _C2= 3 4 8 6 5 9 2 _ _循環(huán)4：7－1 C1=2 9 _ 3 _ 4 6 _ _C2= 3 4 _ 6 _ 9 2 _ _循環(huán)3：5－8C1=2 9 5 3 8 4 6 7 1C2=3 4 8 6 5 9 2 1 7 圖24循環(huán)交叉 變異本身是一種局部隨機搜索，與選擇、交叉算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力；同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。遺傳算法最簡單的終止條件就是設(shè)定終止代數(shù)，當算法的迭代次數(shù)大于終止代數(shù)時就停止迭代，算法結(jié)束。同時還加大了最優(yōu)個體的變異率，保持種群多樣性，這樣有效的防止了算法陷入局部最優(yōu)解而早熟，提高了解的質(zhì)量。旅行商問題的數(shù)學(xué)模型可以描述為：對于n個城市V={v1,v2,…,vn}的一訪問次序為T=(t1,t2,…,tn), tiVi（i=1，2,…，n）,tn+1 = t1,則問題即要求min，其中表示城市 i與城市i+1 之間的距離。下面我們就看下使用窮舉法解決TSP的難度到底有多大。這就為遺傳算法的應(yīng)用提供了機會，下面我們就來看一求解TSP問題的改進遺傳算法。但要注意的是在進行交叉操作的時候可能產(chǎn)生不合法個體，因此需要對編碼進行合法性檢查，并對不合法的個體進行合法性修復(fù)。 個體(individual)是遺傳算法中處理的基本對象、數(shù)據(jù)結(jié)構(gòu)，對應(yīng)于自然遺傳學(xué)中的生物個體。 個體的選擇概率：使用公式21計算個體的選擇概率 個體的期望概率：個體的期望概率=(個體選擇概率*種群大小) 個體的變異概率：因為算法中的采用的增加較優(yōu)個體的變異概率的策略，因此不同的個體有不同的變異概率（較優(yōu)個體有更大的變異概率） 是否被選擇：boolean類型，為true表示該個體被選擇，進入下一代，表示false被淘汰，是否被淘汰由期望概率決定。最大相同解次數(shù)：如果算法迭代了最大相同解次數(shù)都沒有找到更好的解，說明種群的進化趨勢已經(jīng)減弱到一定閥值，種群已經(jīng)趨于成熟，此時算法應(yīng)該停止。算法采用增大較優(yōu)個體的變異概率，因此這里設(shè)置的只是個體的初始變異率。例如求解n個城市的TSP，隨機初始化的方法如下： 對n個城市使用0(n1)的順序?qū)崝?shù)編碼 生成一個訪問順序隨機的訪問序列的關(guān)鍵代碼如下： // 使所有的個體都是從第一個城市出發(fā), //0表示第一個城市，1表示第二個城市,依次類推） population[i].citys[0] = 0。 j++) {//生成1n1之間的種子 num[j] = j。 j++) { // 產(chǎn)生0到temp間的隨機整數(shù),不包括temp int r = (int) (() * (temp 1) + 1)。 }若種群大小為M，則循環(huán)執(zhí)行操作2 M次就可以生成M個個體，再由這M個個體組成種群就完成了種群的隨機初始。 j++) { += distance[[j]][[j + 1]]。把當前最優(yōu)解復(fù)制到最優(yōu)種群的第一個個體，再分別把前面popSize1次迭代產(chǎn)生的最優(yōu)解復(fù)制到最優(yōu)種群的其它個體，生成最優(yōu)種群。 = (double) ( * popSize)。 for (int i = 0。 i popSize。從最優(yōu)種群中選擇隨機選擇一部分個體（但是保證當前最優(yōu)的個體一定被選擇）來覆蓋當前種群中被淘汰掉的個體，并且增大這些局部最優(yōu)個體的變異概率。 i popSize。 } population[i].pmultation = 1。 j++) { population[i].citys[j]=bestPopualtion[index].citys[j]。首先從種群中隨機選擇兩個個體進行配對，然后在生成兩個0cityNum（城市個數(shù)）之間（不包括cityNum）的隨機數(shù)，將這兩個隨機數(shù)做為位串上的兩個切點位置，再交換兩個切點之間的基因。 // 計算有多少個個體會發(fā)生交叉 int pop = (int) (popSize * pxover / 2)。 } // x,y兩個體執(zhí)行雙切點交叉 doublePointCrossover(x, y)。 // 交換兩個個體切點之間的城市序列 for (int i = location1。 population[x].citys[i] = tempY。 j++) { if (j != i amp。 } } // 修復(fù)個體Y for (int k = 1。 population[y].citys[k] == population[y].citys[i]) { population[y].citys[k] = tempY?；旌系姆椒ㄊ牵看螆?zhí)行變異操作之前，先生成02的隨機數(shù)，然后根據(jù)生成的隨機數(shù)來選擇此次使用哪種變異方式。 for (int i = 0。 loc2 = (int) (() * (cityNum 1)) + 1。 } // 采用多種變異方式混合 i