【正文】 （ 1）改進(jìn)的算法求同一城市問題（ 51 個(gè)城市）： 初始種群為 POPSIZE、最大遺傳代數(shù)為 GENS、交叉概率 PXOVER、變異概率 PMUTATION、最大值 FLT_ +308 如下表：（ .1） 城市 POPSIZE PXOVER PMUTATION CENS 51 100 2021 表（ .1） 次數(shù) 第一次 第二次 第三次 第四次 第五次 第六次 第七次 第八次 第九次 第十次 平均值 最好值 最短距離 438 452 440 450 454 439 448 470 457 448 449 438 最小生成代數(shù) 1680 1919 1306 1830 1992 1919 1653 1671 1989 1903 1791 1306 表（ .2） 最好結(jié)果：代數(shù)： 1680 最短路徑 438 路徑： 48 23 7 43 24 25 14 6 27 46 51 12 5 37 17 4 47 18 13 41 40 19 42 44 15 45 33 39 10 30 34 21 16 50 9 49 38 11 32 1 22 2 29 20 35 36 3 28 31 26 8 下面為 51 個(gè)城市一定“比率尺”下的相對坐標(biāo)： 1 37， 52 2 49 ， 49 3 52 ， 64 4 20， 26 5 40 ， 30 6 21 ， 47 7 17， 63 8 31 ， 62 9 52， 33 10 51 ， 21 11 42 ， 41 12 31， 32 13 5， 25 14 12 ，42 15 36， 16 16 52 ， 41 17 27 ， 23 18 17， 33 19 13 ， 13 20 57 ， 58 21 62， 42 22 42 ， 57 23 16 ， 57 24 8， 52 25 7， 38 26 27 ， 68 27 30 ， 48 28 43， 67 29 58， 48 30 58 ， 27 31 37， 69 32 38 ， 46 33 46， 10 34 61 ， 33 35 62 ，63 36 63 ， 69 37 32 ， 22 38 45， 35 39 59， 15 40 5 ， 6 41 10 ， 17 42 21 ，10 43 5， 64 44 30， 15 45 39 ， 10 46 32， 39 47 25 ， 32 48 25， 55 49 48， 28 50 56 ， 37 51 30 ， 40 坐標(biāo)對應(yīng)的圖（ .1） 下面畫出我試驗(yàn)中最好結(jié)果的路徑圖： 路徑從第 48 個(gè)城市開始，它的坐標(biāo)是 48（ 25， 55） 從 48 237 43 依次畫出得下圖（ .2）
。群體個(gè)數(shù)是一百，有一百個(gè)新一代個(gè)體。 如果一個(gè)算子能中和這兩種方法的優(yōu)點(diǎn)，那將取得明顯的改進(jìn)。 絕對順序就是 3 在 1 的后面且相臨，相對順序就不一定相臨。 例如上面的 child1 456792813 產(chǎn)生了 par1 135792468 中沒有的線路 4 5 6 和 6 7 9 2 8. OX（順序交叉） 操作保留了部分城市的相對訪問順序，但是它也更多的產(chǎn)生出了父代巡回路線中所沒有的部分新路線。 將 temp2 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child2 中相應(yīng)位置。 圖（ .3） 改進(jìn)的交叉算子：產(chǎn)生多個(gè)個(gè)體的部分映射與順序交叉結(jié)合的算子 . 先看一個(gè)交叉過程： 第一個(gè)交叉點(diǎn) jcross1,第二個(gè)交叉點(diǎn) jcross2 [10][11] par1,par2. par1 135792468 par2 456789123 temp1,temp2 用于交換的臨時(shí)變量。 （ 2）比較六組，七組，八組，二組，九組： 橫軸交叉概率，豎軸“最有解”（交叉概率 ，變異概率 ）如圖（ .2） 圖（ .2） 分析交叉概率從 0 到 之間，最優(yōu)值隨交叉概的增大變小，變小是我們愿意看到的，變異概率從 到 1 時(shí)，最優(yōu)值浮動(dòng)于一個(gè)值，所以我們的交叉要取大于 的一 個(gè)值。 比 較一組，二組，三組，四組，五組。 求 51個(gè)城市最短距離：（交叉或變異至少有一個(gè)取合理的值，遺傳代數(shù) 1500，分別有十三組） 遺 傳代數(shù) 交叉概率 變異概率 群體大小 第一次 第二次 第三次 第四次 第五次 平均距離 最短距離 第一組 1500 0 100 1346 1430 1461 1463 1413 1422 1346 第二組 1500 100 452 457 472 449 475 461 449 第三組 1500 100 478 470 483 473 463 473 463 第四組 1500 100 479 467 475 456 448 465 448 第 五組 1500 1 100 470 475 461 475 456 456 第六組 1500 0 100 547 563 538 569 537 550 537 第七組 1500 100 475 505 511 506 452 489 452 第八組 1500 100 444 446 455 457 460 444 第九組 1500 1 100 455 460 448 469 457 448 第十組 1500 20 483 486 484 500 495 483 第十一組 1500 50 476 463 476 472 456 456 第十二組 1500 80 450 480 458 472 458 450 第十三組 1500 120 471 447 451 449 453 447 表（ .1） 取遺傳代數(shù)為 1500 的什么原因 ,取 2021 不是更能得到最優(yōu)解嗎？ 正是因?yàn)槟艿玫阶顑?yōu)解，我想才應(yīng)該 避開，因?yàn)槊恳粋€(gè)都能得到最優(yōu)，那么他們的數(shù)據(jù)就較集中，那么實(shí)驗(yàn)就無意義了。 第 1621 代 最優(yōu)值： 442 路徑： 33 45 15 37 44 42 19 40 41 13 4 17 47 12 46 51 27 6 14 25 18 24 43 7 23 48 8 26 31 28 3 36 35 20 29 21 34 30 9 50 16 2 22 1 32 11 38 5 49 10 39 第 1622 帶 最優(yōu)值： 439 路徑： 33 45 15 37 44 42 19 40 41 13 4 17 47 12 46 51 27 6 14 18 25 24 43 7 23 48 8 26 31 28 3 36 35 20 29 21 34 30 9 50 16 2 22 1 32 11 38 5 49 10 39 發(fā)現(xiàn)局部路徑： 25 18 與 18 25 的變化是使兩個(gè)位置的數(shù)值作了交換，這里可能是變異的結(jié)果，注意也可能是交叉的結(jié)果，數(shù)據(jù)主要說明變異的結(jié)果就是這樣的值交換，我們的變異算子就可以寫成一個(gè)數(shù)值交換的算子。 A 1 2 3 | 4 5 6｜ 7 8 9 0 1 2 3｜ 6 5 4 | 7 8 9 0 （ 3）交換變異 交換變異也稱為對換變異。 （ 2）倒位變異 倒位變異也稱為逆轉(zhuǎn)變異。 （ 1）常規(guī)變異 常規(guī)變異也稱為位點(diǎn)變異。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會因?yàn)樽儺惗獾狡茐摹? 遺傳算法引入 變異的目的有兩個(gè)：一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。 交叉的實(shí)質(zhì)是對交叉的兩個(gè)個(gè)體的某一段逆序 例如下面的實(shí)驗(yàn)結(jié)果； 箭頭指向的是城市，下同 第 767 代 最優(yōu)值： 454 路徑： 18 14 25 13 41 40 19 42 44 37 15 45 33 39 10 30 50 9 49 34 21 16 38 5 11 32 1 22 2 29 20 35 36 3 28 31 8 26 7 23 24 43 48 6 27 51 46 12 47 17 4 第 768 代 最優(yōu)值： 446 路徑： 18 14 25 13 41 40 19 42 44 37 15 45 33 39 10 49 9 50 30 34 21 16 38 5 11 32 1 22 2 29 20 35 36 3 28 31 8 26 7 23 24 43 48 6 27 51 46 12 47 17 4 發(fā)現(xiàn)局部路徑 30 50 9 49 調(diào)整為： 49 9 50 30 這是交叉的作用（注意這里的一段是連續(xù)的，交叉的結(jié)果不一定是連續(xù)的逆序）。 （ 2）順序交叉 OX, order crossover 這種交叉操作的主要思想是：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個(gè)體巡回路線的有效順序修改，修改時(shí)，要盡量的維持各城市原有的相對訪問順序。 （ 1） 部分映射交叉 PMX, partially mapped crossover 這種交叉操作的主要思想是：整個(gè)交叉操作過程由兩步完成，首先對“個(gè)體編碼串”進(jìn)行常規(guī)的雙點(diǎn)交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各個(gè)基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個(gè)基因座的基因值。也就是說，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作。 考慮到求的是 TSP 城市最短路徑問題 ,我采用適應(yīng)度比例方法（ Fitness proportional model） 交叉算子的設(shè)計(jì) 實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問題有關(guān)，一般包括以下一些要點(diǎn)： ① 任何交叉算子需要滿足交叉算子的評估準(zhǔn)則，就是說交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計(jì)誤差。 （ 3）排序選擇方法（ Rankbased） 排序選擇方法是指在計(jì)算每個(gè)個(gè)體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個(gè)體排序，然后把事先設(shè)計(jì)好的概率表按順序分配給個(gè)體，作為各自的選擇概率。采用這種選擇方法的優(yōu)點(diǎn)是：進(jìn)化過程中某一代的最優(yōu)解可以不被交叉和變異操作 所破壞。個(gè)體適應(yīng)度越大，被選擇的概率就越高。它也叫賭輪（ roulette wheel）或蒙特卡羅（ Monte Carlo）選擇。選擇的目的是把“優(yōu)化的解”直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個(gè)體再遺傳到下一代。 適應(yīng)函數(shù)度 因?yàn)橐蟪鞘械淖疃叹嚯x，所以適應(yīng)度函數(shù)就是各距離的倒數(shù) 選擇算子的設(shè)計(jì) 從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫做選擇。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范 圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。所以在實(shí)際應(yīng)用中，群體個(gè)數(shù)的取值范圍一般在幾十到幾百。下面為用 EXCEL 畫的一個(gè) 51 個(gè)城市的坐標(biāo)。 第三章 TSP 問題描述與實(shí)算 旅行商問題描述 旅行商問題（ Traveling Salesman Problem ， TSP）中文又稱貨郎擔(dān)問題 旅行商問題