【正文】 傳操作施加于樹結(jié)構(gòu)的程序上。 遺傳程序設(shè)計(jì)是借鑒生物界的自然選擇和遺傳機(jī)制，在遺傳算法的基礎(chǔ)上發(fā)展起來的搜索算法，它已成為進(jìn)化計(jì)算的一個(gè)新分支。此后，遺傳算法的研究引起了國(guó)內(nèi)外學(xué)者的關(guān)注?！?Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合 h 教授為名譽(yù)主編。 1994 年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè) :可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有 Foundations of Geic Algorithms，該會(huì)也是從 1990 年開始隔年召開一次。 1989 年， Hollandberg 出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（ Geic Algorithms in Search , Optimization, and Machine Learning）。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時(shí)又提出了諸如代溝（ generation gap）等新的遺 傳操作技術(shù)。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論（ schema theory）。 1967 年， Holland 的學(xué)生在博士論文中首次提出“遺傳算法”（ Geic Algorithms）一詞。 TSP。接著對(duì)改進(jìn)的遺傳算法做了實(shí)驗(yàn)，得出結(jié)果并分析了數(shù)據(jù)。遺傳算法的廣泛應(yīng)用和發(fā)展?jié)撃苁购芏鄬W(xué)者深入研究遺傳算法，并出版了很多關(guān)于它的書籍。 TSP 問題是古老的經(jīng)典的問題，有關(guān)的研究有幾百年的時(shí)間。最后我做了一個(gè) TSP 簡(jiǎn)單應(yīng)用。 geic operator。此后， Holland 指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研 究的論文。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得并行性的重 要性。可以認(rèn)為， De Jong 的研究工作為遺傳算法及其應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。該書總結(jié)了遺傳算法研究的主要成果，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。這些國(guó)際會(huì)議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動(dòng)向。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在《 Artificial Intelligence》、《 Machine Learning》、《 Information science》、《 Parallel Computing》、《 Geic Programming and Evoluable Machines》、《 IEEE Transactions on Neural Networks》、《 IEEE Transactions on Signal Processing》等雜志上發(fā)表。目前， 關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中。自 1985 年以來 .國(guó)際上已召開了多次遺傳算法的學(xué)術(shù)會(huì)議和研討會(huì) .國(guó)際遺傳算法學(xué)會(huì)組織召開的 ICGA International Conference on Geic Algorithms 會(huì)議和 FOGA Workshop on Foundation of Geic Algorithms 會(huì)議。 在標(biāo)準(zhǔn)的遺傳算法中，由定長(zhǎng)字符串 問題的可行解 組成的群體借助于復(fù)制、交叉、變異等遺傳操作不斷進(jìn)化找到問題的最優(yōu)解或次優(yōu)解。 近年來，遺傳程序設(shè)計(jì)運(yùn)用遺傳算法的思想自動(dòng)生成計(jì)算機(jī)程序解決了許多問題，如預(yù)測(cè)、分類、符號(hào)回歸和圖像處理等，作為一種新技術(shù)，它已經(jīng)與遺傳算法并駕齊驅(qū)。 生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過程， 它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。 遺傳算法簡(jiǎn)稱 GA Geic Algorithm ，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。 Darwin 進(jìn)化論最重要的是適者生存原理。 Mendel 遺傳學(xué)說最重 要的是基因遺傳原理。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。 （ 4）基因 Gene 基因是串中的元素，基因用于表示個(gè)體的特征?；蛭恢糜纱畯淖笙蛴矣?jì)算，例如在串 S＝ 1101 中， 0 的基因位置 是 3。基因操作是在結(jié)構(gòu)空間中進(jìn)行的。 遺傳算法的原理 遺傳算法 GA 把“問題的解”表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。 在遺傳算法里，優(yōu)化問題 的解被稱為個(gè)體，它表示為一個(gè)參數(shù)列表，叫做染色體或者基因串。種群中的“個(gè)體”被按照適應(yīng)度排序，適應(yīng)度高的在前面。選擇則是根據(jù)新個(gè)體的適應(yīng)度進(jìn)行的，適應(yīng)度越高，被選擇的機(jī)會(huì)越高，而適應(yīng)度低的，被選擇的機(jī)會(huì)就低。例如，交配概率為 ，則80%的“夫妻”會(huì)生育后代。再下一步是突變，通過突變產(chǎn)生新的“子”個(gè)體。這樣的過程不斷的重復(fù)：每個(gè)“個(gè)體”被評(píng)價(jià)，計(jì)算出適應(yīng)度，兩個(gè)個(gè)體交配，然后突變，產(chǎn)生第三代。 例如： H 1 x x 0 x x 是一個(gè)模式。 3 Holland 摸式定理 低階，短長(zhǎng)度的模式在群體遺傳過程中將會(huì)按指數(shù)規(guī)律增加。串長(zhǎng)度及編碼形式對(duì)算法收斂影響極大 （ 2）適應(yīng)函數(shù)的確定 適應(yīng)函數(shù) fitness function 也稱對(duì)象函數(shù) object function ，這是問題求解品質(zhì)的測(cè)量函數(shù)；往往也稱為問題的“環(huán)境”。一般 n＝ 30一般取 Pm＝ 0． 010． 2。 通常以隨機(jī)方法產(chǎn)生串或個(gè)體的集合 bi,i＝ 1， 2， ...n。適應(yīng)度選擇原則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。這個(gè)過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。在變異時(shí)，對(duì)執(zhí)行變異的串的“對(duì)應(yīng)位”求反，即把 1 變?yōu)?0，把 0變?yōu)?1。但是，它能保證算法過程不會(huì)產(chǎn)生無法進(jìn)化的單一群體。 遺傳算法的特點(diǎn) （ 1）遺傳算法從問題解的中集開始嫂索，而不是從單個(gè)解開始。 （ 2）遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。 遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串，這是一個(gè)強(qiáng)烈的濾波過程，并且是一個(gè)并行濾波機(jī)制。這說明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。很多人工構(gòu)造的各種各樣復(fù)雜形式的測(cè)試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有單峰函數(shù)也有多峰函數(shù)等，利用這些函數(shù)來評(píng)價(jià)遺傳算法的性能。這類問題包括旅行商問題、背包問題、裝箱問題和圖形劃分等。 （ 4）自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解。 （ 5）機(jī)器人學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一次誤差，從而影響圖像的效果。 （ 7）人工生命 人工生命是用計(jì)算機(jī)、機(jī)械等人下媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。 （ 9）機(jī)器學(xué)習(xí) 學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。遺傳算法以其基本思想簡(jiǎn)單、便于實(shí)現(xiàn)和并行搜索的優(yōu)點(diǎn)贏得了眾多學(xué)者和各種工程人員的青睞，是目前應(yīng)用最廣的優(yōu)化搜索算法之一。和其它方法結(jié) 合的遺傳算法才有生命力。現(xiàn)將比較常見的混合遺傳算法介紹如下。但如果將遺傳算法和模擬退火算法相結(jié)合，互相取長(zhǎng)補(bǔ)短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法。 [4] （ 3）小生境遺傳算法 生物學(xué)上，小生境指在特定環(huán)境中的一種組織功能，它將每一代個(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表，組成一個(gè)新種群，再在 同一種群中以及不同種群之間進(jìn)行雜交、變異，產(chǎn)生新一代個(gè)體群，同時(shí)采用“預(yù)選擇”機(jī)制或排擠機(jī)制或共享機(jī)制完成選擇操作。用小生境思想來實(shí)現(xiàn)遺傳算法的選擇操作，使遺傳算法的全局尋優(yōu)能力得到了明顯提高。在這里，“論域”即指用隸屬函數(shù)來表示遺傳算法的優(yōu)化過程中所采用的約束條件的區(qū)間范圍。 （ 5）混沌遺傳算法 混沌是自然界廣泛存在的一種非線性現(xiàn)象，它充分體現(xiàn)了系統(tǒng)的復(fù)雜性。 （ 6）量子遺傳算法 量子遺傳算法是量子計(jì)算思想與遺傳算法結(jié)合的產(chǎn)物。還有其他的算法已被引入到遺傳算法中來（如禁忌―并行 ，分層），在此， 就不再過多介紹。 模式定理 （ 1） 模式 模式（ schema）是一個(gè)描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。 [4] 定義 基于三值字符集 0， 1， * 所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似的 0、 1 字符串稱作模式。在引入模式概念后，我們看到的一個(gè)串實(shí)際上隱含著多個(gè)模式，一個(gè)模式可以隱含在多個(gè)串中，不同的“串”之間通過模式而相互聯(lián)系。 定義 模式 H 中確定位置的個(gè)數(shù)稱作該模式的模式階，記作 O H 。既使具有“同階”的模式，在遺傳操作下，也會(huì)有著不同的性質(zhì)。 【定義】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長(zhǎng)度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按“指數(shù)級(jí)”增長(zhǎng)。這一操作就是編碼。一維染色體編碼中最常用的符號(hào)集是二值符號(hào)集 0,1 ，基于此符號(hào)集的個(gè)體呈“二值碼串”。用遺傳算法完成此任務(wù)，一個(gè)染色體就代表一個(gè)圖像。雖然此時(shí)也可以把“圖結(jié)構(gòu)”編碼為一維染色體來處理，但是“圖結(jié)構(gòu)”特性不能在適應(yīng)度評(píng)估中充分體現(xiàn)出來。這種過程不斷迭代，直到初始群體中個(gè)體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合。但是遺傳算法中，適應(yīng)度函數(shù)要進(jìn)行比較排序并且在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。這是因?yàn)檫@些異常個(gè)體競(jìng)爭(zhēng)力太突出，控制了整個(gè)選擇過程，從而影響了算法的全局優(yōu)化性能。選擇算子又叫再生算子（ Reproduction Operator）。個(gè)體適應(yīng)度越大，被選擇的概率就越高。也就是說，該方法的全局搜索能力不強(qiáng)，它更加適合于單峰性質(zhì)的搜索空間搜索。 ③排序選擇方法（ Rankbased） 排序選擇方法是指在計(jì)算每個(gè)個(gè)體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個(gè)體排序，然后把事先設(shè)計(jì)好的概率表按順序分配給個(gè)體，作為各自的選擇概率。 2 交叉算子 交叉算子的設(shè)計(jì) 實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問題有關(guān)，一般包括以下一些要點(diǎn)： ① 任何交叉算子需要滿足交叉算子的評(píng)估準(zhǔn)則，就是說交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。 基本的交叉算子 ①一點(diǎn)交叉（ One point crossover） 一點(diǎn)交叉又 叫做簡(jiǎn)單交叉。 ④算術(shù)交叉（ Arithmetic Crossover） 算術(shù)交叉是指由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。但是，遺傳算法的收斂性主要決定于作為其核心操作的交叉算子。例如，基于字符集 0,1 的“二值碼串”，變異操作就 是把 1 變成 0 或者把 0 變成 1。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會(huì)因?yàn)樽儺惗獾狡茐摹? 混合遺傳算法 混合遺傳算法簡(jiǎn)述 遺傳算法由于其運(yùn)算簡(jiǎn)單和解決問題的有效能力而被廣泛應(yīng)用于眾多領(lǐng)域。另一方面，梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有強(qiáng)的局部搜索能力。 2 增加了編碼變換操作過程。下面為用 EXCEL 畫的一個(gè) 51 個(gè)城市的坐標(biāo)。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。 適應(yīng)函數(shù)度 因?yàn)橐蟪鞘械淖疃叹嚯x，所以適應(yīng)度函數(shù)就是各距離的倒數(shù) 選擇算子的設(shè)計(jì) 從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作叫做選擇。它也叫賭輪（ roulette wheel）或蒙特卡羅（ Monte Carlo）選擇。采用這種選擇方法的優(yōu)點(diǎn)是：進(jìn)化過程中某一代的最優(yōu)解可以不被交叉和變異操作 所破壞。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計(jì)誤差。也就是說，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作。 （ 2）順序交叉 OX, order crossover 這種交叉操作的主要思想是：先進(jìn)行常規(guī)的雙點(diǎn)交叉，然后進(jìn)行個(gè)體巡回路線的有效順序修改，修改時(shí)，要盡量的維持各城市原有的相對(duì)訪問順序。 遺傳算法引入 變異的目的有兩個(gè)：一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。 （ 2）倒位變異 倒位變異也稱為逆轉(zhuǎn)變異。 第 1621 代 最優(yōu)值： 442 路徑： 33 45 15 37 44 42 19 40 41 13 4 17 47 12 46 51 27 6 14 25