【正文】 在的不足，從而使得系統(tǒng)的優(yōu)化設(shè)計(jì)更靈活、方便，取得好的設(shè)計(jì)效果?；煦邕\(yùn)動(dòng)的上述性質(zhì)作為避免陷入局部極小的優(yōu)化搜索機(jī)制，恰好可以彌補(bǔ)遺傳算法易陷入局部最優(yōu)、收斂速度慢的缺陷。 隨著人們對(duì)遺傳算法研究的不斷深入，可以預(yù)見(jiàn)，會(huì)有更多的理論和方法被引入到遺傳算法中來(lái)。在引入模式概念前，我們看到的遺傳算法是：在某一代中， N 個(gè)互不相同的串在選擇、交叉、變異等遺傳算子的作用下產(chǎn)生下一代的 N 個(gè)新的互不相同的串。顯然，一個(gè)模式的“階數(shù)”越高，其樣本數(shù)就越少，因而確定性越高。 遺傳算法主要通過(guò)遺傳操作對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加結(jié)構(gòu)重組處理，從而不斷的搜索出群體中個(gè)體間的結(jié)構(gòu)相似性。此時(shí)若采用一維染色體編碼就顯得不方便了。 群體設(shè)定 群體的設(shè)定可以采取下面的策略：根據(jù)問(wèn)題固有知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問(wèn)題空間的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。另一方面，如果群體規(guī)模太小，會(huì)使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。在通常情況下，為了把一個(gè)最小化問(wèn)題轉(zhuǎn)化為最大化問(wèn)題，只需要簡(jiǎn)單的把原函數(shù)乘以 1 即可 . 2 適應(yīng)度尺度變換（適應(yīng)度函數(shù)定標(biāo)） 應(yīng)用遺傳算法時(shí)，常常會(huì)出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的，目前常用的選擇算子有： ①適應(yīng)度比例方法（ Fitness proportional model） 適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法，它也叫“賭輪”或蒙特卡羅（ Monte Carlo）選擇。另外，最佳個(gè)體保存方法還可加以推廣，即在每一代的進(jìn)化過(guò)程中保留多個(gè)最優(yōu)個(gè)體不參加交叉、變異等遺傳操 作，而直接將它們復(fù)制到下一代群體中。也就是說(shuō)，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作。 交叉算子與遺傳算法的收斂性關(guān)系。遺傳算法引入變異的目的有兩個(gè)：一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。并且一般來(lái)說(shuō)，對(duì)不少問(wèn)題，基本遺傳算法的求解效果往往不是最為有效的，它比專(zhuān)門(mén)針對(duì)某一問(wèn)題的知識(shí)性啟發(fā)算法的求解效率要差。 第三章 TSP 問(wèn)題描述與實(shí)算 旅行商問(wèn)題描述 旅行商問(wèn)題（ Traveling Salesman Problem ， TSP）中文又稱(chēng)貨郎擔(dān)問(wèn)題 旅行商問(wèn)題 設(shè) G V , E 是一個(gè)圖，其中是 V 頂點(diǎn)集， E 是邊集，旅行商問(wèn)題就是要決定一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的最短 距離回路，這樣的回路就是哈密爾頓回路。另一方面，如果群體規(guī)模太小，會(huì)使遺傳算法的搜索空間分布范 圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。個(gè)體適應(yīng)度越大，被選擇的概率就越高。 考慮到求的是 TSP 城市最短路徑問(wèn)題 ,我采用適應(yīng)度比例方法（ Fitness proportional model） 交叉算子的設(shè)計(jì) 實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問(wèn)題有關(guān)，一般包括以下一些要點(diǎn)： ① 任何交叉算子需要滿(mǎn)足交叉算子的評(píng)估準(zhǔn)則，就是說(shuō)交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。 交叉的實(shí)質(zhì)是對(duì)交叉的兩個(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ù)的逆序）。 （ 1）常規(guī)變異 常規(guī)變異也稱(chēng)為位點(diǎn)變異。 求 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)該 避開(kāi)，因?yàn)槊恳粋€(gè)都能得到最優(yōu)，那么他們的數(shù)據(jù)就較集中，那么實(shí)驗(yàn)就無(wú)意義了。 將 temp2 中 jcross1 到 jcross2 之間的數(shù)據(jù)復(fù)制到 child2 中相應(yīng)位置。群體個(gè)數(shù)是一百，有一百個(gè)新一代個(gè)體。 如果一個(gè)算子能中和這兩種方法的優(yōu)點(diǎn)，那將取得明顯的改進(jìn)。 圖（ .3） 改進(jìn)的交叉算子：產(chǎn)生多個(gè)個(gè)體的部分映射與順序交叉結(jié)合的算子 . 先看一個(gè)交叉過(guò)程： 第一個(gè)交叉點(diǎn) jcross1,第二個(gè)交叉點(diǎn) jcross2 [10][11] par1,par2. par1 135792468 par2 456789123 temp1,temp2 用于交換的臨時(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ù)主要說(shuō)明變異的結(jié)果就是這樣的值交換，我們的變異算子就可以寫(xiě)成一個(gè)數(shù)值交換的算子。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。 （ 2）順序交叉 OX, order crossover 這種交叉操作的主要思想是：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個(gè)體巡回路線(xiàn)的有效順序修改，修改時(shí)，要盡量的維持各城市原有的相對(duì)訪問(wèn)順序。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計(jì)誤差。它也叫賭輪（ roulette wheel）或蒙特卡羅（ Monte Carlo）選擇。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。 2 增加了編碼變換操作過(guò)程。 混合遺傳算法 混合遺傳算法簡(jiǎn)述 遺傳算法由于其運(yùn)算簡(jiǎn)單和解決問(wèn)題的有效能力而被廣泛應(yīng)用于眾多領(lǐng)域。例如，基于字符集 0,1 的“二值碼串”，變異操作就 是把 1 變成 0 或者把 0 變成 1。 ④算術(shù)交叉（ Arithmetic Crossover） 算術(shù)交叉是指由兩個(gè)個(gè)體的線(xiàn)性組合而產(chǎn)生出兩個(gè)新的個(gè)體。 2 交叉算子 交叉算子的設(shè)計(jì) 實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問(wèn)題有關(guān)，一般包括以下一些要點(diǎn)： ① 任何交叉算子需要滿(mǎn)足交叉算子的評(píng)估準(zhǔn)則，就是說(shuō)交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。也就是說(shuō)，該方法的全局搜索能力不強(qiáng)，它更加適合于單峰性質(zhì)的搜索空間搜索。選擇算子又叫再生算子（ Reproduction Operator）。但是遺傳算法中，適應(yīng)度函數(shù)要進(jìn)行比較排序并且在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。雖然此時(shí)也可以把“圖結(jié)構(gòu)”編碼為一維染色體來(lái)處理，但是“圖結(jié)構(gòu)”特性不能在適應(yīng)度評(píng)估中充分體現(xiàn)出來(lái)。一維染色體編碼中最常用的符號(hào)集是二值符號(hào)集 0,1 ，基于此符號(hào)集的個(gè)體呈“二值碼串”。 【定義】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長(zhǎng)度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按“指數(shù)級(jí)”增長(zhǎng)。 定義 模式 H 中確定位置的個(gè)數(shù)稱(chēng)作該模式的模式階，記作 O H 。 [4] 定義 基于三值字符集 0， 1， * 所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似的 0、 1 字符串稱(chēng)作模式。還有其他的算法已被引入到遺傳算法中來(lái)（如禁忌―并行 ，分層），在此， 就不再過(guò)多介紹。 （ 5）混沌遺傳算法 混沌是自然界廣泛存在的一種非線(xiàn)性現(xiàn)象，它充分體現(xiàn)了系統(tǒng)的復(fù)雜性。用小生境思想來(lái)實(shí)現(xiàn)遺傳算法的選擇操作，使遺傳算法的全局尋優(yōu)能力得到了明顯提高。但如果將遺傳算法和模擬退火算法相結(jié)合，互相取長(zhǎng)補(bǔ)短，則有可能開(kāi)發(fā)出性能優(yōu)良的新的全局搜索算法。和其它方法結(jié) 合的遺傳算法才有生命力。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫(kù)中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直到數(shù)據(jù)庫(kù)能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫(kù)中的規(guī)則。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一次誤差，從而影響圖像的效果。 （ 4）自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解。很多人工構(gòu)造的各種各樣復(fù)雜形式的測(cè)試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有單峰函數(shù)也有多峰函數(shù)等，利用這些函數(shù)來(lái)評(píng)價(jià)遺傳算法的性能。 遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過(guò)選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串，這是一個(gè)強(qiáng)烈的濾波過(guò)程，并且是一個(gè)并行濾波機(jī)制。 遺傳算法的特點(diǎn) （ 1）遺傳算法從問(wèn)題解的中集開(kāi)始嫂索，而不是從單個(gè)解開(kāi)始。在變異時(shí)，對(duì)執(zhí)行變異的串的“對(duì)應(yīng)位”求反，即把 1 變?yōu)?0，把 0變?yōu)?1。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。 通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合 bi,i＝ 1， 2， ...n。一般 n＝ 30