【導(dǎo)讀】遺傳算法的廣泛應(yīng)用和發(fā)展?jié)撃苁购芏鄬W(xué)者深入研究遺傳算法，并出版了很。多關(guān)于它的書籍。TSP問題是古老的經(jīng)典的問題，有關(guān)的研究有幾百年的時(shí)間。題是一類典型的NP完全問題，遺傳算法是解決NP問題的一種較理想的方法。單討論幾種編碼方法，并改進(jìn)了交叉算子。接著對改進(jìn)的遺傳算法做了實(shí)驗(yàn)，得。出結(jié)果并分析了數(shù)據(jù)。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點(diǎn)和趨。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論。1971年，stien在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。此有人把1975年作為遺傳算法的誕生年。Holland在該書中系統(tǒng)地闡述了遺傳。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得并行性的。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個(gè)里程碑，這是因?yàn)?，的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。1985年，在美國召開了第一屆遺傳算法國際會議。后每兩年舉行一次。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提

　　

【正文】 ，交叉的結(jié)果不一定是連續(xù)的逆序）。這里交叉作用使局部路徑縮短，從而使總路徑變短，所以被選擇而保留下來成為新一帶“最優(yōu)” 子的設(shè)計(jì) 變異操作的基本內(nèi)容是對群體中的個(gè)體串的某些基因座上的基因值作變動。 遺傳算法引入 變異的目的有兩個(gè)：一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近局部最優(yōu)解時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會因?yàn)樽儺惗獾狡茐摹６鞘惯z傳算法可以維持群體多樣性，以防止出現(xiàn)早熟現(xiàn)象。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。 （ 1）常規(guī)變異 常規(guī)變異也稱為位點(diǎn)變異。具 體方法是，以一定的概率（通常取數(shù)很小）變異串中的值。 （ 2）倒位變異 倒位變異也稱為逆轉(zhuǎn)變異。具體方法是，在串中，隨機(jī)選擇兩點(diǎn)，在將這兩點(diǎn)內(nèi)的“子串”按反序插入到原位置中，如串 A 的逆轉(zhuǎn)點(diǎn)為 3， 6，則經(jīng)過逆轉(zhuǎn)后稱為 。 A 1 2 3 | 4 5 6｜ 7 8 9 0 1 2 3｜ 6 5 4 | 7 8 9 0 （ 3）交換變異 交換變異也稱為對換變異。具體方式是，隨機(jī)選擇串中的兩點(diǎn)，交換碼值，例如在下面的串中交換 4 和 7： A 1 2 3 4 5 6 7 8 9 1 2 3 7 5 6 4 8 9 （ 4）插入變異 這種變異操作的具體方法是：從“串”中隨機(jī)選擇一個(gè)碼，將此碼插入隨機(jī)選擇的插入點(diǎn)中間，例如在下面的串中，插入碼為 5 A 1 2 3 4 5 6 7 8 9 1 2 5 3 4 6 7 8 9 變異的實(shí)質(zhì)是對某個(gè)個(gè)體的某一段或某些段交換數(shù)值。 第 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ù)值交換的算子。 變異我采用的是倒位變異 對 TSP 遺傳算法的改進(jìn)： TSP 遺傳算法參數(shù)實(shí)驗(yàn) 遺傳算法自身參數(shù)有 3 個(gè)，即群體大小 n、交叉概率 Pc 和變異概率 Pm。 求 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)就無意義了。那么又問 1500 的時(shí)候到是這個(gè)結(jié)果了，到 2021 的時(shí)候能得到這個(gè)結(jié)果嗎，不是算法 2021 代才更容易得到最優(yōu)解嗎 ,的確求 51 城市時(shí)我們實(shí)驗(yàn)或?qū)嶋H應(yīng)用都是 2021 或以上的遺傳代數(shù)，但這里主要討論遺傳代數(shù)，雜交，變異等參數(shù)大小對最優(yōu)收斂的影響，而如果取 2021代是到是都能得到更好的結(jié)果，但是效果就不明顯了，有些基因可能早就得到最優(yōu)解了，到 2021 代還沒更好的基因代替它，而有的參數(shù)取值根本就不好，但是代數(shù)是 2021，它還是能得到更好結(jié)果。 比 較一組，二組，三組，四組，五組。 （ 1）橫軸變異概率，豎軸最優(yōu)值 ,畫出圖（圖中沒有畫除變異概率為 0 時(shí)的點(diǎn)，它的值太大影響其它點(diǎn)的對比） 如圖（ .1） 圖（ .1） 從圖中看出，最優(yōu)值是關(guān)于變異概率波動圖，也看出變異得到交好結(jié)果。 （ 2）比較六組，七組，八組，二組，九組： 橫軸交叉概率，豎軸“最有解”（交叉概率 ，變異概率 ）如圖（ .2） 圖（ .2） 分析交叉概率從 0 到 之間，最優(yōu)值隨交叉概的增大變小，變小是我們愿意看到的，變異概率從 到 1 時(shí)，最優(yōu)值浮動于一個(gè)值，所以我們的交叉要取大于 的一 個(gè)值。 比較十組，十一組，十二組，二組，十三組 橫軸群體大小，豎軸最優(yōu)解，如圖（ .3） 分析最優(yōu)值的大小是關(guān)于群體大小漸進(jìn)下劃的值，在考慮運(yùn)行和效率方面，我們一般取群體大小為 100 左右的大小，這是求 51 個(gè)城市的實(shí)驗(yàn)，取值一般是100 左右，其他的城市數(shù)值大小要相應(yīng)取值，但規(guī)律是一定的。 圖（ .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í)變量。 temp1 135792468 temp2 456789123 temp1 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child1 中相應(yīng)位置。 將 temp2 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child2 中相應(yīng)位置。 child1 ***792*** child2 *** 789*** 4. 將 temp2 中刪去 child1 中交叉點(diǎn)之間的數(shù)據(jù)（因?yàn)閷⒁?temp2 復(fù)制到 child1） 同樣把 temp1 中刪去 child2 中交叉點(diǎn)之間的數(shù)據(jù)（將要把 temp1 復(fù)制到child2） temp2 456813 temp1 135246 temp2復(fù)制到 child1,temp1復(fù)制到 child2. 部分映射交叉產(chǎn)生的個(gè)體 child1 456792813 child2 135789246 child1,child2 的交叉點(diǎn)之間的數(shù)據(jù)排前，得到新的child3,child4.（順序交叉產(chǎn)生的個(gè)體） child3 792456813 child4 789135246 （見上面的 PMX 和 OX 介紹） PMX（部分映射交叉） 操作保留了部分城市的“絕對訪問”順序，但是它更多的產(chǎn)生出了父代巡回路線中沒有的部分新路線。 例如上面的 child1 456792813 產(chǎn)生了 par1 135792468 中沒有的線路 4 5 6 和 6 7 9 2 8. OX（順序交叉） 操作保留了部分城市的相對訪問順序，但是它也更多的產(chǎn)生出了父代巡回路線中所沒有的部分新路線。 OX 也產(chǎn)生了 1 3 5 2 等線路。 絕對順序就是 3 在 1 的后面且相臨，相對順序就不一定相臨。 上面的數(shù)據(jù)顯示 OX 要好于 PMX。 如果一個(gè)算子能中和這兩種方法的優(yōu)點(diǎn)，那將取得明顯的改進(jìn)。 我改進(jìn)了交叉方式，讓上一代兩個(gè)個(gè)體通過兩種交叉產(chǎn)生 4 個(gè)個(gè)體， 4 個(gè)個(gè)體中和了兩種交叉的優(yōu)點(diǎn)，通過一個(gè)選擇找出 4 個(gè)中最優(yōu)秀的兩個(gè)，作為上一代兩個(gè)個(gè)體的新一帶，新一帶將和眾多的新一代一起競爭最優(yōu)。群體個(gè)數(shù)是一百，有一百個(gè)新一代個(gè)體。兩個(gè)個(gè)體的新一代改進(jìn)是明顯的，眾多的個(gè)體就有更大的改進(jìn)了。 （ 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）