【正文】 1xx0xx，有 0 H ＝ 2，δ H ＝ 4。一般取 n＝ 30 （ 4）變異 根據生物遺傳中基因變異的原理，以變異概率 Pm 對某些個體的某些“位”執(zhí)行變異。 （ 3）遺傳算法有極強的容錯能力。遺傳算法已經成為解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用?；谶z傳算法的進化模 型是研究人下生命現象的重要基礎理論。許多學者從不同的角度對遺傳算法進行了改進，使遺傳算法的尋優(yōu)能力有了不同程度的提高。這樣可以保護解的多樣性，也可以避免大量重復的解充斥整個解空間。這些區(qū)別，使得量子遺傳算法表現出比標準遺傳算法更好的種群多樣性、更強的全局搜索能力和更快的收斂速度。 （ 2） 模式定理 首先定義兩個重要的概念：模式階（ schema order）和定義長度（ schema defining length）。 編碼技術 編碼的方式有多種，下面作簡要的介紹： 一維染色體編碼 所謂一維染色體編碼是指搜索空間的參數轉換到遺傳空間后，其相應的基因呈一維排列構成染色體。另外，群體規(guī)模的確定受遺傳操作中選擇操作的 影響很大。通常采用的定標方式為： ① 線性定標 af + b ； ②σ 截斷 f cσ ； ③乘冪定標 fk； 遺傳操作 1 選擇算子 從群體中選擇優(yōu)勝的個體，淘汰劣質個體的操作叫做選擇。此 外 還 有 一 些 比 較 常 用 的 選 擇 方 法 如 期 望 值 方 法 （ Expected value model）、聯(lián)賽選 擇方法（ Tournament selection model）等。 3 變異算子 變異操作的基本內容是對群體中的個體串的某些基因座上的基因值作變動。 基于群體中各個個體的表現型，進行局部搜索，從而找出各個個體在目前環(huán)境下所對應的局部 最優(yōu)解，以便達到改善群體總體性能的目的。選擇操作是建立在群體中個體的適應度評估基礎上的，目前常用的選擇算子有： （ 1）適應度比例方法（ Fitness proportional model） 適應度比例方法是目前遺傳算法中最基本最常用的選擇方法。例如： A 9 8 4 | 5 6 7 | 1 3 2 0 B 8 7 1｜ 2 3 0 | 9 5 4 6 首先交換 A 和 B 的兩個匹配區(qū)域，得到： 9 8 4 | 2 3 0 | 1 3 2 0 8 7 1 | 5 6 7 | 9 5 4 6 然后依據匹配區(qū)域內的位置映射關系，對于重復的位逐一替換： 9 8 4 | 2 3 0 | 1 6 5 7 8 0 1 | 5 6 7 | 9 5 4 6 PMX 操作保留了部分城市的“絕對訪問”順序，但是它更多的產生出了父代巡回路線中沒有的部分新路線，所以這種操作方法的性狀遺傳特性不太好。具體方式是，隨機選擇串中的兩點，交換碼值，例如在下面的串中交換 4 和 7： A 1 2 3 4 5 6 7 8 9 1 2 3 7 5 6 4 8 9 （ 4）插入變異 這種變異操作的具體方法是：從“串”中隨機選擇一個碼，將此碼插入隨機選擇的插入點中間，例如在下面的串中，插入碼為 5 A 1 2 3 4 5 6 7 8 9 1 2 5 3 4 6 7 8 9 變異的實質是對某個個體的某一段或某些段交換數值。 上面的數據顯示 OX 要好于 PMX。 child1 ***792*** child2 *** 789*** 4. 將 temp2 中刪去 child1 中交叉點之間的數據（因為將要把 temp2 復制到 child1） 同樣把 temp1 中刪去 child2 中交叉點之間的數據（將要把 temp1 復制到child2） temp2 456813 temp1 135246 temp2復制到 child1,temp1復制到 child2. 部分映射交叉產生的個體 child1 456792813 child2 135789246 child1,child2 的交叉點之間的數據排前，得到新的child3,child4.（順序交叉產生的個體） child3 792456813 child4 789135246 （見上面的 PMX 和 OX 介紹） PMX（部分映射交叉） 操作保留了部分城市的“絕對訪問”順序，但是它更多的產生出了父代巡回路線中沒有的部分新路線。具 體方法是，以一定的概率（通常取數很?。┳儺惔械闹?。 ② 交叉設計和編碼設計是相互聯(lián)系的。實驗中求 51 個城市等的距離，考慮個方面因素，群體規(guī)模設為 100。另外，遺傳算法也無法避免多次搜索同一個可行 解，這也是影響遺傳算法運行效率的一個因素。 遺傳算法的收斂性不僅取決于編碼，初始化群體，適應度函數，選擇算子的設計，而且還取決于交叉算子和下面要提到的變異算子。這種選擇方法也稱為穩(wěn)態(tài)復制。在遺傳進化的初期，通常出現一些超常的個體 ，這些異常個體有可能在群體中占據很大的比例，因而可能導致未成熟收斂現象。先隨機生成一定數目的個體，然后從中挑出最好的個體加到初始群體中。所以遺傳算法不能直接處理問題空間的參數，必須把它們轉換成遺傳空間的由基因按一定結構組成的染色體或個體。那么，兩代之間 究竟保留了什么性質，破壞了什么性質，我們無法知到，因為我們所看到的“串”都是相互獨立的，互不聯(lián)系的。可以利用混沌的遍歷性產生 初始種群，也可以運用混沌的遍歷性對優(yōu)良個體進行變異操作，混沌遺傳算法增強了遺傳算法的全局尋優(yōu)能力。我們可以通過注射疫苗的方法來減少遺傳操作的盲目性，加強遺傳算法收斂性能，多次的測試結果證明了該改進方法的有效性。 遺傳算法發(fā)展 方向 遺傳算法發(fā)展方向其實就是和其他方法結合優(yōu)化問題，單方面改進遺傳算法的各種算子不能取得明顯進展。目前已在模式識別 包括漢字識別 、圖像恢復、圖像邊緣特征提取等方而得到了應用。對于這類復雜問題，使用遺傳算法求解可行解就顯得更加有實際價值。遺 傳算法從“串集”開始搜索，覆蓋面大，利于全局擇優(yōu)。在選中的位置實行交換。變異概率 Pm 太小時難以產生新的基因結構，太大使遺傳算法成了單純的隨機搜索。它的有關內容如下： 1 摸式 Schema 概念 [1] 一個基因串用符號集 0， 1， * 表示，則稱為一個因式；其中 *可以是 0 或 1。這個過程是通過選擇和交叉完成的，其中繁殖包括 crossover 和突變 mutation 。 （ 7）串結構空間（ SS） 在串中，基因任意組合所構成的串的集合。在環(huán)境變化時，只有那些能適應環(huán)境的個體特征方能保留下來。 把遺傳算法和計算機程序結合起來的思想出現在遺傳算法中， Holland 把產生式語言和遺傳算法結合起來實現分類系統(tǒng)，還有一些遺傳算法應用領域的 研究者將類似于遺傳算法的遺傳操作施加于樹結構的程序上。 1994 年，他又出版了《遺傳程序設計，第二冊 :可重用程序的自動發(fā)現》深化了遺傳程序設計的研究，使程序設計自動化展現了新局面。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（ schema theory）。遺傳算法的廣泛應用和發(fā)展?jié)撃苁购芏鄬W者深入研究遺傳算法，并出版了很多關于它的書籍。此后， Holland 指導學生完成了多篇有關遺傳算法研 究的論文。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向。 在標準的遺傳算法中，由定長字符串 問題的可行解 組成的群體借助于復制、交叉、變異等遺傳操作不斷進化找到問題的最優(yōu)解或次優(yōu)解。 Darwin 進化論最重要的是適者生存原理?；蛭恢糜纱畯淖笙蛴矣嬎?，例如在串 S＝ 1101 中， 0 的基因位置 是 3。種群中的“個體”被按照適應度排序，適應度高的在前面。這樣的過程不斷的重復：每個“個體”被評價，計算出適應度，兩個個體交配，然后突變，產生第三代。一般 n＝ 30 這樣，就產生了對環(huán)境適應能力較強的后代。 遺傳算法的特點 （ 1）遺傳算法從問題解的中集開始嫂索，而不是從單個解開始。很多人工構造的各種各樣復雜形式的測試函數，有連續(xù)函數也有離散函數，有單峰函數也有多峰函數等，利用這些函數來評價遺傳算法的性能。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一次誤差，從而影響圖像的效果。因此，應用遺傳算法在數據庫中進行搜索，對隨機產生的一組規(guī)則進行進化 .直到數據庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數據庫中的規(guī)則。但如果將遺傳算法和模擬退火算法相結合，互相取長補短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法。 （ 5）混沌遺傳算法 混沌是自然界廣泛存在的一種非線性現象，它充分體現了系統(tǒng)的復雜性。 [4] 定義 基于三值字符集 0， 1， * 所產生的能描述具有某些結構相似的 0、 1 字符串稱作模式。 【定義】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長度，并且平均適應度高于群體平均適應度的模式將按“指數級”增長。雖然此時也可以把“圖結構”編碼為一維染色體來處理，但是“圖結構”特性不能在適應度評估中充分體現出來。但是遺傳算法中，適應度函數要進行比較排序并且在此基礎上計算選擇概率，所以適應度函數的值要取正值。也就是說，該方法的全局搜索能力不強，它更加適合于單峰性質的搜索空間搜索。 ④算術交叉（ Arithmetic Crossover） 算術交叉是指由兩個個體的線性組合而產生出兩個新的個體。 混合遺傳算法 混合遺傳算法簡述 遺傳算法由于其運算簡單和解決問題的有效能力而被廣泛應用于眾多領域。群體規(guī)模越大，群體中個體的多樣性越高，算法陷入局部解的危險就小。此外，它和適應度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計誤差。遺傳算法中，交叉算子因為其全局搜索能力作為主要算子，變異算子因其局部搜索能力作為輔助算子。 圖（ .3） 改進的交叉算子：產生多個個體的部分映射與順序交叉結合的算子 . 先看一個交叉過程： 第一個交叉點 jcross1,第二個交叉點 jcross2 [10][11] par1,par2. par1 135792468 par2 456789123 temp1,temp2 用于交換的臨時變量。群體個數是一百，有一百個新一代個體。 求 51個城市最短距離：（交叉或變異至少有一個取合理的值，遺傳代數 1500，分別有十三組） 遺 傳代數 交叉概率 變異概率 群體大小 第一次 第二次 第三次 第四次 第五次 平均距離 最短距離 第一組 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） 取遺傳代數為 1500 的什么原因 ,取 2021 不是更能得到最優(yōu)解嗎？ 正是因為能得到最優(yōu)解，我想才應該 避開，因為每一個都能得到最優(yōu)，那么他們的數據就較集中，那么實驗就無意義了。 交叉的實質是對交叉的兩個個體的某一段逆序 例如下面的實驗結果； 箭頭指向的是城市，下同 第 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