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