【正文】 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 的變化是使兩個位置的數(shù)值作了交換，這里可能是變異的結(jié)果，注意也可能是交叉的結(jié)果，數(shù)據(jù)主要說明變異的結(jié)果就是這樣的值交換，我們的變異算子就可以寫成一個數(shù)值交換的算子。 比 較一組，二組，三組，四組，五組。 圖（ .3） 改進的交叉算子：產(chǎn)生多個個體的部分映射與順序交叉結(jié)合的算子 . 先看一個交叉過程： 第一個交叉點 jcross1,第二個交叉點 jcross2 [10][11] par1,par2. par1 135792468 par2 456789123 temp1,temp2 用于交換的臨時變量。 例如上面的 child1 456792813 產(chǎn)生了 par1 135792468 中沒有的線路 4 5 6 和 6 7 9 2 8. OX（順序交叉） 操作保留了部分城市的相對訪問順序，但是它也更多的產(chǎn)生出了父代巡回路線中所沒有的部分新路線。 如果一個算子能中和這兩種方法的優(yōu)點，那將取得明顯的改進。 （ 1）改進的算法求同一城市問題（ 51 個城市）： 初始種群為 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 個城市一定“比率尺”下的相對坐標： 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 坐標對應(yīng)的圖（ .1） 下面畫出我試驗中最好結(jié)果的路徑圖： 路徑從第 48 個城市開始，它的坐標是 48（ 25， 55） 從 48 237 43 依次畫出得下圖（ .2）
。群體個數(shù)是一百，有一百個新一代個體。 絕對順序就是 3 在 1 的后面且相臨，相對順序就不一定相臨。 將 temp2 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child2 中相應(yīng)位置。 （ 2）比較六組，七組，八組，二組，九組： 橫軸交叉概率，豎軸“最有解”（交叉概率 ，變異概率 ）如圖（ .2） 圖（ .2） 分析交叉概率從 0 到 之間，最優(yōu)值隨交叉概的增大變小，變小是我們愿意看到的，變異概率從 到 1 時，最優(yōu)值浮動于一個值，所以我們的交叉要取大于 的一 個值。 求 51個城市最短距離：（交叉或變異至少有一個取合理的值，遺傳代數(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ōu)解，我想才應(yīng)該 避開，因為每一個都能得到最優(yōu)，那么他們的數(shù)據(jù)就較集中，那么實驗就無意義了。 A 1 2 3 | 4 5 6｜ 7 8 9 0 1 2 3｜ 6 5 4 | 7 8 9 0 （ 3）交換變異 交換變異也稱為對換變異。 （ 1）常規(guī)變異 常規(guī)變異也稱為位點變異。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會因為變異而遭到破壞。 交叉的實質(zhì)是對交叉的兩個個體的某一段逆序 例如下面的實驗結(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ù)的逆序）。 （ 1） 部分映射交叉 PMX, partially mapped crossover 這種交叉操作的主要思想是：整個交叉操作過程由兩步完成，首先對“個體編碼串”進行常規(guī)的雙點交叉操作，然后根據(jù)交叉區(qū)域內(nèi)各個基因值之間的映射關(guān)系來修改交叉區(qū)域之外的各個基因座的基因值。 考慮到求的是 TSP 城市最短路徑問題 ,我采用適應(yīng)度比例方法（ Fitness proportional model） 交叉算子的設(shè)計 實現(xiàn)個體結(jié)構(gòu)重組的交叉算子設(shè)計一般與所求解的具體問題有關(guān)，一般包括以下一些要點： ① 任何交叉算子需要滿足交叉算子的評估準則，就是說交叉算子需要保證前一代中優(yōu)秀個體的性狀能在后一代的新個體中盡可能得到遺傳和繼承。 （ 3）排序選擇方法（ Rankbased） 排序選擇方法是指在計算每個個體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體排序，然后把事先設(shè)計好的概率表按順序分配給個體，作為各自的選擇概率。個體適應(yīng)度越大，被選擇的概率就越高。選擇的目的是把“優(yōu)化的解”直接遺傳到下一代或者通過配對交叉產(chǎn)生新的個體再遺傳到下一代。另一方面，如果群體規(guī)模太小，會使遺傳算法的搜索空間分布范 圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。所以在實際應(yīng)用中，群體個數(shù)的取值范圍一般在幾十到幾百。 第三章 TSP 問題描述與實算 旅行商問題描述 旅行商問題（ Traveling Salesman Problem ， TSP）中文又稱貨郎擔(dān)問題 旅行商問題 設(shè) G V , E 是一個圖，其中是 V 頂點集， E 是邊集，旅行商問題就是要決定一條通過所有頂點且每個頂點只通過一次的最短 距離回路，這樣的回路就是哈密爾頓回路。 簡言之，混合遺傳算法是在標準遺傳算法中融合了局部搜索方法的思想， 其特點主要體現(xiàn)在下面兩個方面： 1 引入了局部搜索過程。并且一般來說，對不少問題，基本遺傳算法的求解效果往往不是最為有效的，它比專門針對某一問題的知識性啟發(fā)算法的求解效率要差。遺傳算法中，交叉算子因為其全局搜索能力作為主要算子 ，變異算子因其局部搜索能力作為輔助算子。遺傳算法引入變異的目的有兩個：一個是使遺傳算法具有局部的隨機搜索能力。需要指出的是，交叉算子并未提供收斂性保證。 交叉算子與遺傳算法的收斂性關(guān)系。 ②二點交叉（ Two point crossover） 二點交叉與“一點交叉”類似，只是設(shè)值 2 個交叉點（隨機設(shè)定）。也就是說，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計誤差。另外，最佳個體保存方法還可加以推廣，即在每一代的進化過程中保留多個最優(yōu)個體不參加交叉、變異等遺傳操 作，而直接將它們復(fù)制到下一代群體中。采用這種選擇方法的優(yōu)點是：進化過程中某一代的最優(yōu)解可以不被交叉和變異操作所破壞。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的，目前常用的選擇算子有： ①適應(yīng)度比例方法（ Fitness pro