【正文】 3 Holland 摸式定理 低階，短長度的模式在群體遺傳過程中將會(huì)按指數(shù)規(guī)律增加。這樣的過程不斷的重復(fù)：每個(gè)“個(gè)體”被評(píng)價(jià)，計(jì)算出適應(yīng)度，兩個(gè)個(gè)體交配，然后突變，產(chǎn)生第三代。例如，交配概率為 ，則80%的“夫妻”會(huì)生育后代。種群中的“個(gè)體”被按照適應(yīng)度排序，適應(yīng)度高的在前面。 遺傳算法的原理 遺傳算法 GA 把“問題的解”表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串?；蛭恢糜纱畯淖笙蛴矣?jì)算，例如在串 S＝ 1101 中， 0 的基因位置 是 3。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。 Darwin 進(jìn)化論最重要的是適者生存原理。 生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過程， 它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。 在標(biāo)準(zhǔn)的遺傳算法中，由定長字符串 問題的可行解 組成的群體借助于復(fù)制、交叉、變異等遺傳操作不斷進(jìn)化找到問題的最優(yōu)解或次優(yōu)解。目前， 關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。這些國際會(huì)議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動(dòng)向?？梢哉J(rèn)為， De Jong 的研究工作為遺傳算法及其應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研 究的論文。最后我做了一個(gè) TSP 簡單應(yīng)用。遺傳算法的廣泛應(yīng)用和發(fā)展?jié)撃苁购芏鄬W(xué)者深入研究遺傳算法，并出版了很多關(guān)于它的書籍。 TSP。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論（ schema theory）。 1989 年， Hollandberg 出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（ Geic Algorithms in Search , Optimization, and Machine Learning）。 1994 年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè) :可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。此后，遺傳算法的研究引起了國內(nèi)外學(xué)者的關(guān)注。 把遺傳算法和計(jì)算機(jī)程序結(jié)合起來的思想出現(xiàn)在遺傳算法中， Holland 把產(chǎn)生式語言和遺傳算法結(jié)合起來實(shí)現(xiàn)分類系統(tǒng)，還有一些遺傳算法應(yīng)用領(lǐng)域的 研究者將類似于遺傳算法的遺傳操作施加于樹結(jié)構(gòu)的程序上。當(dāng)時(shí)，其主要目的不是對(duì)遺傳算法系統(tǒng)研究而是說明自然和人工系統(tǒng)的自適應(yīng)過程。在環(huán)境變化時(shí)，只有那些能適應(yīng)環(huán)境的個(gè)體特征方能保留下來。 2 群體 Population 個(gè)體的集合稱為群體，“串”是群體的元素 （ 3）群體大小 Population Size 在群體中個(gè)體的數(shù)量稱為群體的大小。 （ 7）串結(jié)構(gòu)空間（ SS） 在串中，基因任意組合所構(gòu)成的串的集合。這樣，“一代一代”地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問題的最優(yōu)解。這個(gè)過程是通過選擇和交叉完成的，其中繁殖包括 crossover 和突變 mutation 。不過這里的半段并不是真正的一半，這個(gè)位置叫做交配點(diǎn)，也是隨機(jī)產(chǎn)生的，可以是染色體的任意位置。它的有關(guān)內(nèi)容如下： 1 摸式 Schema 概念 [1] 一個(gè)基因串用符號(hào)集 0， 1， * 表示，則稱為一個(gè)因式；其中 *可以是 0 或 1。一般把問題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。變異概率 Pm 太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。在選擇時(shí)，以適應(yīng)度為選擇原則。在選中的位置實(shí)行交換。 對(duì)其的第 1， 4 位置的基因進(jìn)行變異，則有 001111 單靠變異不能在求解中得到好處。遺 傳算法從“串集”開始搜索，覆蓋面大，利于全局擇優(yōu)。 遺傳算法中的選擇、交叉和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。對(duì)于這類復(fù)雜問題，使用遺傳算法求解可行解就顯得更加有實(shí)際價(jià)值。都顯出了遺傳算法在這此領(lǐng)域中應(yīng)用的可能性。目前已在模式識(shí)別 包括漢字識(shí)別 、圖像恢復(fù)、圖像邊緣特征提取等方而得到了應(yīng)用。目前公開的遺傳編程實(shí)驗(yàn)系統(tǒng)有十多個(gè)。 遺傳算法發(fā)展 方向 遺傳算法發(fā)展方向其實(shí)就是和其他方法結(jié)合優(yōu)化問題，單方面改進(jìn)遺傳算法的各種算子不能取得明顯進(jìn)展。由于遺傳算法具有開放式的結(jié)構(gòu)，與問題的關(guān)聯(lián)性不大，很容易和其他算法進(jìn)行結(jié)合，所以融合了其他的算法思想和遺傳算法思想的混合遺傳算法成了目前改進(jìn)遺傳算法研究的一個(gè)重要方向。我們可以通過注射疫苗的方法來減少遺傳操作的盲目性，加強(qiáng)遺傳算法收斂性能，多次的測試結(jié)果證明了該改進(jìn)方法的有效性。首先，在模糊遺傳算法中引入“論域”的概念。可以利用混沌的遍歷性產(chǎn)生 初始種群，也可以運(yùn)用混沌的遍歷性對(duì)優(yōu)良個(gè)體進(jìn)行變異操作，混沌遺傳算法增強(qiáng)了遺傳算法的全局尋優(yōu)能力。相信通過遺傳算法與其他算法的結(jié)合以及自身實(shí)現(xiàn)方式的不斷改進(jìn)，在不久的將來，遺傳算法的優(yōu)化能力會(huì)有一個(gè)質(zhì)的提高 . 第二章．遺傳算法的基本原理和實(shí)現(xiàn)技術(shù) 前一章講了遺傳算法的原理，概念，這一章就具體將編碼。那么，兩代之間 究竟保留了什么性質(zhì)，破壞了什么性質(zhì)，我們無法知到，因?yàn)槲覀兯吹降摹按倍际窍嗷オ?dú)立的，互不聯(lián)系的。 但是，模式的“階”并不能反映模式的所有性質(zhì)。所以遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體。例如圖像恢復(fù)處理是指把一個(gè)被干擾的圖像盡量恢復(fù)到它的原始面目。先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加到初始群體中。 函數(shù) 遺傳算法在進(jìn)化搜索中基本上不用外部信息，僅僅使用目標(biāo)函數(shù)即適應(yīng)度函數(shù)為依據(jù)。在遺傳進(jìn)化的初期，通常出現(xiàn)一些超常的個(gè)體 ，這些異常個(gè)體有可能在群體中占據(jù)很大的比例，因而可能導(dǎo)致未成熟收斂現(xiàn)象?！皞€(gè)體”被選擇的概率反映了個(gè)體的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。這種選擇方法也稱為穩(wěn)態(tài)復(fù)制。這也就是所謂的編碼――交叉設(shè)計(jì)。 遺傳算法的收斂性不僅取決于編碼，初始化群體，適應(yīng)度函數(shù)，選擇算子的設(shè)計(jì)，而且還取決于交叉算子和下面要提到的變異算子。當(dāng)遺傳算法通過交叉算子已接近局部最優(yōu)解時(shí)，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。另外，遺傳算法也無法避免多次搜索同一個(gè)可行 解，這也是影響遺傳算法運(yùn)行效率的一個(gè)因素。即尋找一條最短的遍歷 “ n 個(gè)”城市的路徑。實(shí)驗(yàn)中求 51 個(gè)城市等的距離，考慮個(gè)方面因素，群體規(guī)模設(shè)為 100。 （ 2）最佳個(gè)體保存方法（ Elitist model） 此方法的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中。 ② 交叉設(shè)計(jì)和編碼設(shè)計(jì)是相互聯(lián)系的。這里交叉作用使局部路徑縮短，從而使總路徑變短，所以被選擇而保留下來成為新一帶“最優(yōu)” 子的設(shè)計(jì) 變異操作的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。具 體方法是，以一定的概率（通常取數(shù)很?。┳儺惔械闹?。那么又問 1500 的時(shí)候到是這個(gè)結(jié)果了，到 2021 的時(shí)候能得到這個(gè)結(jié)果嗎，不是算法 2021 代才更容易得到最優(yōu)解嗎 ,的確求 51 城市時(shí)我們實(shí)驗(yàn)或?qū)嶋H應(yīng)用都是 2021 或以上的遺傳代數(shù)，但這里主要討論遺傳代數(shù)，雜交，變異等參數(shù)大小對(duì)最優(yōu)收斂的影響，而如果取 2021代是到是都能得到更好的結(jié)果，但是效果就不明顯了，有些基因可能早就得到最優(yōu)解了，到 2021 代還沒更好的基因代替它，而有的參數(shù)取值根本就不好，但是代數(shù)是 2021，它還是能得到更好結(jié)果。 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（部分映射交叉） 操作保留了部分城市的“絕對(duì)訪問”順序，但是它更多的產(chǎn)生出了父代巡回路線中沒有的部分新路線。兩個(gè)個(gè)體的新一代改進(jìn)是明顯的，眾多的個(gè)體就有更大的改進(jìn)了。 上面的數(shù)據(jù)顯示 OX 要好于 PMX。 比較十組，十一組，十二組，二組，十三組 橫軸群體大小，豎軸最優(yōu)解，如圖（ .3） 分析最優(yōu)值的大小是關(guān)于群體大小漸進(jìn)下劃的值，在考慮運(yùn)行和效率方面，我們一般取群體大小為 100 左右的大小，這是求 51 個(gè)城市的實(shí)驗(yàn)，取值一般是100 左右，其他的城市數(shù)值大小要相應(yīng)取值，但規(guī)律是一定的。具體方式是，隨機(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ù)值。二是使遺傳算法可以維持群體多樣性，以防止出現(xiàn)早熟現(xiàn)象。例如： 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ì)訪問”順序，但是它更多的產(chǎn)生出了父代巡回路線中沒有的部分新路線，所以這種操作方法的性狀遺傳特性不太好。這種方法的不足之處在于選擇概率和序號(hào)的關(guān)系必須事先確定。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的，目前常用的選擇算子有： （ 1）適應(yīng)度比例方法（ Fitness proportional model） 適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法。另外，群體規(guī)模的確定受遺傳操作中選擇操作的影響很大。 基于群體中各個(gè)個(gè)體的表現(xiàn)型，進(jìn)行局部搜索，從而找出各個(gè)個(gè)體在目前環(huán)境下所對(duì)應(yīng)的局部 最優(yōu)解，以便達(dá)到改善群體總體性能的目的。遺傳算法通過交叉和變異這一對(duì)相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。 3 變異算子 變異操作的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。 ③一致交叉（ Uniform crossover） 一致交叉是指通過設(shè)定屏蔽字（ mask）來決定新個(gè)體的基因繼承兩個(gè)舊個(gè)體中哪個(gè)個(gè)體的對(duì)應(yīng)基因。此 外 還 有 一 些 比 較 常 用 的 選 擇 方 法 如 期 望 值 方 法 （ Expected value model）、聯(lián)賽選 擇方法（ Tournament selection model）等。但是，這是這樣可能隱含了一種危機(jī)――導(dǎo)致早熟，即局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有可能限于局部解。通常采用的定標(biāo)方式為： ① 線性定標(biāo) af + b ； ②σ 截?cái)? f cσ ； ③乘冪定標(biāo) fk； 遺傳操作 1 選擇算子 從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫做選擇。即使某一問題可自然地表示求最大值形式，也不能保證對(duì)于所有的 x,使 f x 取“非負(fù)值”。另外，群體規(guī)模的確定受遺傳操作中選擇操作的 影響很大。 樹結(jié)構(gòu)編碼 在實(shí)際應(yīng)用中，許多問題本身可以采用結(jié)構(gòu)描述，比如，人工智能中知識(shí)獲取和提煉中采用的語義網(wǎng)絡(luò)，神經(jīng)網(wǎng)絡(luò)中神經(jīng)元連接狀態(tài)圖表示等。 編碼技術(shù) 編碼的方式有多種，下面作簡要的介紹： 一維染色體編碼 所謂一維染色體編碼是指搜索空間的參數(shù)轉(zhuǎn)換到遺傳空間后，其相應(yīng)的基因呈一維排列構(gòu)成染色體。比如模式 110*10*的定義長度為 4，而模式 0*****定義長度 0。 （ 2） 模式定理 首先定義兩個(gè)重要的概念：模式階（ schema order）和定義長度（ schema defining length）。這樣二值字符集 0,1 就可擴(kuò)展成三值字符集 0， 1， * 。這些區(qū)別，使得量子遺傳算法表現(xiàn)出比標(biāo)準(zhǔn)遺傳算法更好的種群多樣性、更強(qiáng)的全局搜索能力和更快的收斂速度。模糊遺傳算 法運(yùn)用模糊控制的思想來自適應(yīng)改變遺傳算法的種群規(guī)模、交叉概率、變異概率、適應(yīng)度函數(shù)以及控制策略等。這樣可以保護(hù)解的多樣性，也可以避免大量重復(fù)的解充斥整個(gè)解空間。遺傳算法的局部搜索能力較差，但把握搜索過程總體的能力較強(qiáng)；而模擬退火算法具有較強(qiáng)的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但它卻對(duì)整個(gè)搜索空間的