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