【正文】 nt i = 0。 } 倒序變異算子：private void backMutate(int index, int loc1, int loc2) { int center = (loc1 + loc2) / 2。 population[index].citys[loc1]=population[index].citys[loc2]。 break。 break。 break。 } // 采用多種變異方式混合 int select = (int) (() * 3)。 loc2 = loc1。 loc2 = (int) (() * (cityNum 1)) + 1。 i++) { random = ()。 for (int i = 0。例如：Px= [ 0 1 2 3 4 5 6 7]，隨機(jī)取兩個(gè)位置1和4（基因位從0開(kāi)始），將位置4上的基因插入到位置1后得：Px= [ 0 4 1 2 3 5 6 7]Java實(shí)現(xiàn)代碼如下： 變異主體函數(shù)public void mutate() { double random?；旌系姆椒ㄊ牵看螆?zhí)行變異操作之前，先生成02的隨機(jī)數(shù)，然后根據(jù)生成的隨機(jī)數(shù)來(lái)選擇此次使用哪種變異方式。 } } } }變異簡(jiǎn)單的說(shuō)就是個(gè)體位串內(nèi)基因的位置發(fā)生改變，種群的個(gè)體有一定的可能性（變異概率）發(fā)生變異。 population[y].citys[k] == population[y].citys[i]) { population[y].citys[k] = tempY。 k++) { if (k != i amp。 } } // 修復(fù)個(gè)體Y for (int k = 1。 population[x].citys[j] == population[x].citys[i]) { population[x].citys[j] = tempX。 j++) { if (j != i amp。 // 修復(fù)個(gè)體X for (int j = 1。 population[x].citys[i] = tempY。 i++) { int tempX = population[x].citys[i]。 // 交換兩個(gè)個(gè)體切點(diǎn)之間的城市序列 for (int i = location1。 } } 雙切點(diǎn)交叉函數(shù)private void doublePointCrossover(int x, int y) { // 第一個(gè)切點(diǎn)在0到cityNum1之間隨機(jī)選擇 int location1 = (int) (() * (cityNum 1)) + 1。 } // x,y兩個(gè)體執(zhí)行雙切點(diǎn)交叉 doublePointCrossover(x, y)。 while (true) { y = (int) (() * popSize)。 // 計(jì)算有多少個(gè)個(gè)體會(huì)發(fā)生交叉 int pop = (int) (popSize * pxover / 2)。例如：C1=0 4 2 1 0 6 7 6C2=4 3 2 3 1 5 7 5P1= 0 4 2 | 3 1 5 | 7 6P2= 4 3 2 | 1 0 6 | 7 5 隨機(jī)生成切點(diǎn) 非法個(gè)體 映射關(guān)系： 31 10 56 修復(fù)后的個(gè)體P1= 3 4 2 1 0 6 7 5P2= 4 0 2 3 1 5 7 6 圖32雙切點(diǎn)交叉Java實(shí)現(xiàn)雙切點(diǎn)交叉的代碼如下： 交叉主體函數(shù) public void crossover() { int x = 1。首先從種群中隨機(jī)選擇兩個(gè)個(gè)體進(jìn)行配對(duì)，然后在生成兩個(gè)0cityNum（城市個(gè)數(shù)）之間（不包括cityNum）的隨機(jī)數(shù)，將這兩個(gè)隨機(jī)數(shù)做為位串上的兩個(gè)切點(diǎn)位置，再交換兩個(gè)切點(diǎn)之間的基因。 // 增加變異概率 } count++。 j++) { population[i].citys[j]=bestPopualtion[index].citys[j]。 for (int j = 1。 } population[i].pmultation = 1。 j cityNum。 i popSize。實(shí)現(xiàn)代碼如下： public void copy() { int count = 0。從最優(yōu)種群中選擇隨機(jī)選擇一部分個(gè)體（但是保證當(dāng)前最優(yōu)的個(gè)體一定被選擇）來(lái)覆蓋當(dāng)前種群中被淘汰掉的個(gè)體，并且增大這些局部最優(yōu)個(gè)體的變異概率。 if (population[i].expectP random) { // 根據(jù)期望概率選擇優(yōu)良個(gè)體 population[i].isSelected = true。 i popSize。 i++) { fitnessSum += population[i].fitness。 for (int i = 0。 } 其中fitnessSum是種群中所有個(gè)體的適應(yīng)度之和。 = (double) ( * popSize)。 if (fitnessSum != 0) { = (double) / fitnessSum。把當(dāng)前最優(yōu)解復(fù)制到最優(yōu)種群的第一個(gè)個(gè)體，再分別把前面popSize1次迭代產(chǎn)生的最優(yōu)解復(fù)制到最優(yōu)種群的其它個(gè)體，生成最優(yōu)種群。 } 選擇操作本遺傳算法的選擇操作采用了最優(yōu)保存策略，有利于加快收斂，策略的實(shí)現(xiàn)如下： 定義一個(gè)最優(yōu)種群，最優(yōu)種群初始時(shí)和初始種群一樣。 j++) { += distance[[j]][[j + 1]]。 // 計(jì)算節(jié)點(diǎn)0n1之間的距離之和 for (int j = 0。 }若種群大小為M，則循環(huán)執(zhí)行操作2 M次就可以生成M個(gè)個(gè)體，再由這M個(gè)個(gè)體組成種群就完成了種群的隨機(jī)初始。 num[r] = num[temp 1]。 j++) { // 產(chǎn)生0到temp間的隨機(jī)整數(shù),不包括temp int r = (int) (() * (temp 1) + 1)。 for (int j = 1。 j++) {//生成1n1之間的種子 num[j] = j。 for (int j = 1。例如求解n個(gè)城市的TSP，隨機(jī)初始化的方法如下： 對(duì)n個(gè)城市使用0(n1)的順序?qū)崝?shù)編碼 生成一個(gè)訪問(wèn)順序隨機(jī)的訪問(wèn)序列的關(guān)鍵代碼如下： // 使所有的個(gè)體都是從第一個(gè)城市出發(fā), //0表示第一個(gè)城市，1表示第二個(gè)城市,依次類推） population[i].citys[0] = 0。最優(yōu)種群大小一般設(shè)置為種群大小的二分之一。算法采用增大較優(yōu)個(gè)體的變異概率，因此這里設(shè)置的只是個(gè)體的初始變異率。交叉率：發(fā)生交叉運(yùn)算的個(gè)體個(gè)數(shù)占全體個(gè)體總數(shù)的比例，~。最大相同解次數(shù)：如果算法迭代了最大相同解次數(shù)都沒(méi)有找到更好的解，說(shuō)明種群的進(jìn)化趨勢(shì)已經(jīng)減弱到一定閥值，種群已經(jīng)趨于成熟，此時(shí)算法應(yīng)該停止。最大迭代次數(shù)：本算法的最大迭迭代次數(shù)，與最大相同解次數(shù)一起決定算法是否停止。 個(gè)體的選擇概率：使用公式21計(jì)算個(gè)體的選擇概率 個(gè)體的期望概率：個(gè)體的期望概率=(個(gè)體選擇概率*種群大小) 個(gè)體的變異概率：因?yàn)樗惴ㄖ械牟捎玫脑黾虞^優(yōu)個(gè)體的變異概率的策略，因此不同的個(gè)體有不同的變異概率（較優(yōu)個(gè)體有更大的變異概率） 是否被選擇：boolean類型，為true表示該個(gè)體被選擇，進(jìn)入下一代，表示false被淘汰，是否被淘汰由期望概率決定。例如： n個(gè)城市的TSP的一個(gè)位串X=[0 1 2 … n1]（編碼從0開(kāi)始）。 個(gè)體(individual)是遺傳算法中處理的基本對(duì)象、數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng)于自然遺傳學(xué)中的生物個(gè)體。解碼就是求出一條染色體所對(duì)應(yīng)的路徑長(zhǎng)度的過(guò)程。但要注意的是在進(jìn)行交叉操作的時(shí)候可能產(chǎn)生不合法個(gè)體，因此需要對(duì)編碼進(jìn)行合法性檢查，并對(duì)不合法的個(gè)體進(jìn)行合法性修復(fù)。這里在求解TSP中采用自然數(shù)的符號(hào)編碼，對(duì)于n個(gè)城市的TSP，采用1n的自然數(shù)編碼，分別表示第1到第n個(gè)城市。這就為遺傳算法的應(yīng)用提供了機(jī)會(huì)，下面我們就來(lái)看一求解TSP問(wèn)題的改進(jìn)遺傳算法。假設(shè)使用世界運(yùn)算速度最快的超級(jí)計(jì)算機(jī)，即擁有每秒鐘4700萬(wàn)億次（1015）的運(yùn)算峰值速度由我國(guó)自主研發(fā)的“天河一號(hào)”超級(jí)計(jì)算機(jī)來(lái)窮舉搜索（并假設(shè)一次運(yùn)算就可以求兩個(gè)城市之間的距離和足夠大的存儲(chǔ)空間）10134年的時(shí)間。下面我們就看下使用窮舉法解決TSP的難度到底有多大。這就是窮舉搜索法的思想，理論上它可以解決任何組合優(yōu)化問(wèn)題，但是對(duì)于n個(gè)城市的TSP來(lái)說(shuō)，從任何一個(gè)城市出發(fā)，經(jīng)過(guò)n1個(gè)城市各一次后在回到出發(fā)點(diǎn)，可能的合法回路有(n1)!條,計(jì)算每一條路徑需求n個(gè)距離之和，因此計(jì)算量正比于n!。旅行商問(wèn)題的數(shù)學(xué)模型可以描述為：對(duì)于n個(gè)城市V={v1,v2,…,vn}的一訪問(wèn)次序?yàn)門(mén)=(t1,t2,…,tn), tiVi（i=1，2,…，n）,tn+1 = t1,則問(wèn)題即要求min，其中表示城市 i與城市i+1 之間的距離?；旌系姆椒ㄊ牵看螆?zhí)行變異操作之前，先生成02的隨機(jī)數(shù)，然后根據(jù)生成的隨機(jī)數(shù)來(lái)選擇此次使用哪種變異方式。同時(shí)還加大了最優(yōu)個(gè)體的變異率，保持種群多樣性，這樣有效的防止了算法陷入局部最優(yōu)解而早熟，提高了解的質(zhì)量。常有的判定準(zhǔn)則有下面兩種： 連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一極小的閥值； 群體中所有個(gè)體適應(yīng)度的方差小于某一個(gè)極小的閥值第三章　遺傳算法求解TSP 本章介紹使用一種求解TSP的改進(jìn)遺傳算法（Improved genetic algorithm 簡(jiǎn)稱IGA），相對(duì)與基本遺傳算法所做的改良策略主要有下面兩個(gè)方面：選擇操作采用了最優(yōu)保存策略：首先使用最優(yōu)種群保存了用當(dāng)前最優(yōu)個(gè)體和前面數(shù)次（最優(yōu)種群群體大小1次）迭代的種群中的最優(yōu)個(gè)體，然后從最優(yōu)種群中隨機(jī)選擇部分個(gè)體（保證當(dāng)前最優(yōu)個(gè)體一定被選擇）來(lái)覆蓋當(dāng)前種群中被淘汰的個(gè)體。遺傳算法最簡(jiǎn)單的終止條件就是設(shè)定終止代數(shù)，當(dāng)算法的迭代次數(shù)大于終止代數(shù)時(shí)就停止迭代，算法結(jié)束。最常用的變異操作是按位交換變異，它的基本思想：對(duì)于同一個(gè)個(gè)體的基因如果發(fā)生變異，則隨機(jī)與同一個(gè)個(gè)體的另一個(gè)基因交換位置。 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)交叉 變異本身是一種局部隨機(jī)搜索，與選擇、交叉算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。 切點(diǎn) 切點(diǎn) 切點(diǎn) 切點(diǎn)P1=A1∣B2∣A3P2=B1∣A2∣B3P1=A1∣A2∣A3P2=B1∣B2∣B3 圖23雙切點(diǎn)交叉（3）循環(huán)交叉（cycle crossover）循環(huán)交叉的基本思想是子串位置上的值必須與父母相同位置上的值相等。 切點(diǎn) 切點(diǎn)C1= A1 A2|B3 B4C2 = B1 B2|A3 A4P1=A1 A2∣A3 A4P2=B1 B2∣B3 B4 圖22單切點(diǎn)交叉單切點(diǎn)交叉操作的信息量比較小，交叉位置的選擇可能帶來(lái)較大的偏差，并且染色體末尾的基因總是被交換?；具z傳算法中常用的交叉算子有單切點(diǎn)交叉、雙切點(diǎn)交叉[12]、循環(huán)交叉，下面我們來(lái)進(jìn)行依次介紹（1）單切點(diǎn)交叉（singlepoint crossover）單切點(diǎn)交叉的思想是從種群中選出兩個(gè)個(gè)體P1和P2，隨機(jī)地選擇一個(gè)切點(diǎn)（cutting），將切點(diǎn)兩側(cè)分別看成一個(gè)子串，將右側(cè)的子串分別進(jìn)行交換，這樣就得到了兩個(gè)新的個(gè)體C1和C2。這里選擇概率的計(jì)算公式：P(xi)= (22)其中f為適應(yīng)度函數(shù)，f(xi)為的適應(yīng)度注：此公式只適應(yīng)于選中概率與適應(yīng)度值大小成正比的情況（也就是適應(yīng)度值越大表示適應(yīng)度越優(yōu)），對(duì)于某些適應(yīng)度值越小表示的適應(yīng)度越優(yōu)的情況，需要使用下面公式：P(xi)= (23)其中f為適應(yīng)度函數(shù)，f(xi)為的適應(yīng)度遺傳算法中的交叉操作是先對(duì)種群中的個(gè)體進(jìn)行隨機(jī)兩兩配對(duì)（若種群大小為M，則有M/2對(duì)），然后根據(jù)交叉概率從配對(duì)的個(gè)體中選出一部分 （Pc*（M/2）對(duì)）執(zhí)行交叉。最常用的選擇策略是賭輪選擇策略。例如n個(gè)城市旅行商問(wèn)題（TSP）中，用來(lái)表示個(gè)體適應(yīng)度的就可以是按個(gè)體的位串表示的巡