第一章 遺傳算法概述

第一章遺傳算法概述遺傳算法(GeneticAlgorithm,簡稱GA)起源于對生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。美國Michigan大學(xué)的Holland教授及其學(xué)生受到生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化的自適應(yīng)概率優(yōu)化技一遺傳算法。1967年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，他發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上使用雙倍體的編碼方法。Holland教授用遺傳算法的思想對自然和人工自適應(yīng)系統(tǒng)進(jìn)行了研究，提出了遺傳算法的基本定理 模式定理(SchemaTheorem)，并于1975年出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著《AdaptationinNaturalLandArtificialSystems》。80年代，Holland教授實(shí)現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)，開創(chuàng)了遺傳算法的機(jī)器學(xué)習(xí)的新概念。1975年，DeJong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。1989年，Goldberg出版了《GeneticAlgorithminSearch，OptimizationandMachineLearning》一書，系統(tǒng)地總結(jié)了遺傳算法的主要研究成果，全面完整地論述了遺傳算法的基本原理及其應(yīng)用。 1991年，Davis出版了《HandbookofGeneticAlgorithms》一書，介紹了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會經(jīng)濟(jì)中的大量實(shí)例。1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動生成，提出了遺傳編程 (GeneticProgramming，簡稱GP)的概念。遺傳算法被眾多的使用者證明在控制系統(tǒng)的離線設(shè)計(jì)方面是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Cusin已證明使用遺傳優(yōu)化方法在太空應(yīng)用中導(dǎo)出優(yōu)異的控制器結(jié)構(gòu)比使用傳統(tǒng)方法如LQR和Powell(鮑威爾)的增音機(jī)設(shè)計(jì)所用的時間要少(功能評估"Porter和Mohamed展示了使用本質(zhì)結(jié)構(gòu)分派任務(wù)的多變量飛行控制系統(tǒng)的遺傳設(shè)計(jì)方案。與此同時，另一些人證明了遺傳算法怎么能在控制器結(jié)構(gòu)的選擇中使用。從遺傳算法的整個發(fā)展過程來看，70年代是興起階段，80年代是發(fā)展階段，90年代是高潮階段。遺傳算法作為一種實(shí)用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù)，發(fā)展極為迅速，已引起國內(nèi)外學(xué)者的高度重視。1.1遺傳算法概念生物的進(jìn)化(Evolution)過程主要是通過染色體之間的交叉和變異來完成的?；趯ψ匀唤缰猩镞z傳與進(jìn)化機(jī)理的模仿，針對不同的問題，很多學(xué)者設(shè)計(jì)了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的編碼方式來模仿不同環(huán)境下的生物遺傳特性。這樣，由不同的編碼(Coding)方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。什么是遺傳算法？遺傳算法是模仿自然界生物進(jìn)化機(jī)制發(fā)展起來的隨機(jī)全局搜索和優(yōu)化方法，它借鑒了達(dá)爾文的進(jìn)化論和孟德爾的遺傳學(xué)說。其本質(zhì)是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求得最優(yōu)解。遺傳算法操作使用適者生存的原則，在潛在的解決方案種群中逐次產(chǎn)生一個近似最優(yōu)的方案。在遺傳算法的每一代，根據(jù)個體在問題域中的適應(yīng)度值和從自然遺傳學(xué)中借鑒來的再造方法進(jìn)行個體選擇，產(chǎn)生一個新的近似解。這個過程導(dǎo)致種群中個體的進(jìn)化，得到的新個體比原個體更能適應(yīng)環(huán)境，就像自然界中的改造一樣。個體或當(dāng)前近似解被編碼為由字母組成的串，即染色體(Chromosome)，使基因(Gene，染色體值)能在(表現(xiàn))域決策變量上被惟一地描述。盡管可以使用二進(jìn)制、整數(shù)、實(shí)數(shù)等，但是在遺傳算法表現(xiàn)型上最常用的是二進(jìn)制字符串。例如，一個問題具有兩個變量X1和X2,它們的染色體結(jié)構(gòu)能用圖1.1所示的方法描述。1011010011 0101110101001011 X1 X2 ?圖1.1個體的染色體結(jié)構(gòu)X1被編碼為10位，X2被編碼為15位。位數(shù)的多少能夠反應(yīng)精確度水平或個體決策變量的范圍，是一個不含人們試圖解決問題的信息的染色體串。這只是表現(xiàn)值的染色體編碼，任何意義均可應(yīng)用于表現(xiàn)型。無論如何，就像下面的描述，搜索過程將在決策變量的編碼中而不是它們自身中操作，當(dāng)然除了在實(shí)值基因被使用的情況。在決策變量域的染色體表現(xiàn)型已被編碼，就可以估計(jì)種群的個體成員的特性或適應(yīng)度。通過特征目標(biāo)函數(shù)來估計(jì)個體在問題域中的特性。在自然世界中，這就是個體在現(xiàn)行環(huán)境中的生存能力。因此，目標(biāo)函數(shù)建立的基礎(chǔ)是在整個繁殖過程中選擇成對的個體進(jìn)行交配。在再生（復(fù)制）期間，每個個體均被計(jì)算適應(yīng)度值，它來自沒有加工的原始特性度量，由目標(biāo)函數(shù)給出。這個值用來在選擇中偏向更加適合的個體。相對整個種群，適應(yīng)度高的個體具有高的選中參加交配的概率，而適應(yīng)度低的個體具有相對低的選中概率。一旦個體計(jì)算了適應(yīng)度值，個體能根據(jù)它們的相對適應(yīng)度從種群中被選中并重組，產(chǎn)生下一代。遺傳算子直接操作染色體的特征（基因），使用一般情況下個體的基因代碼，產(chǎn)生更適合的個體。重組算子是運(yùn)用在一對個體或一大組個體中交換基因信息。最簡單的重組算子是單點(diǎn)交叉。考慮兩個二進(jìn)制父代串：A=10010110和B=10111000如果一個整數(shù)位置I是隨機(jī)地在1到串長L減1[1，L-1]之間選擇，在這點(diǎn)后，兩個個體間的基因進(jìn)行交換，隨后兩個子代串產(chǎn)生。例如，當(dāng)交叉點(diǎn)1=5時，兩個子代串產(chǎn)生如下：A=10010000和B，=10111110。交叉算子并不是必須在種群的所有串中執(zhí)行。當(dāng)一對個體被選中培育下一代時，代替的是應(yīng)用一個概率Px。進(jìn)一步的遺傳算法稱為變異，再次使用一個概率Pm應(yīng)用到新染色體上。變異能根據(jù)一些概率準(zhǔn)則引起個體基因表現(xiàn)型發(fā)生變化，在二進(jìn)制表現(xiàn)型中，變異引起單個位的狀態(tài)變化，即0變1，或者1變0。例如，在A，中變異第四位，1變0，產(chǎn)生新串為10000000。變異通常被認(rèn)為是一后臺算子，以確保研究問題空間的特殊子空間的概率永不為零。變異具有阻止局部最優(yōu)收斂的作用。在重組和變異后，如果需要，這些個體串隨后被解碼，目標(biāo)函數(shù)評估，計(jì)算每個個體的適應(yīng)度值，個體根據(jù)適應(yīng)度被選擇參加交配，并且這個過程繼續(xù)直到產(chǎn)生子代。在這種方法中，種群中個體的平均性能希望是提高的，好的個體被保存并且相互產(chǎn)生下一代，而適應(yīng)度低的個體則消失。當(dāng)一些判定條件滿足后，遺傳算法則終止，例如，一定的遺傳代數(shù)、種群的均差或當(dāng)遇到搜索空間的特殊點(diǎn)。1.2遺傳算法的特點(diǎn)遺傳算法是一種借鑒生物界自然選擇（NaturalSelection）和自然遺傳機(jī)制的隨機(jī)搜索算法（Randomsearchingalgorithms）。它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于一個單一的度量函數(shù)（評估函數(shù)）的梯度或較高次統(tǒng)計(jì)，以產(chǎn)生一個確定性的試驗(yàn)解序列；遺傳算法不依賴于梯度信息，而是通過模擬自然進(jìn)化過程來搜索最優(yōu)解（OptimalSolution）,它利用某種編碼技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織地、隨機(jī)地信息交換來重新組合那些適應(yīng)性好的串，生成新的串的群體。1.2.1遺傳算法的特點(diǎn)遺傳算法具有如下特點(diǎn)：（1） 對可行解表示的廣泛性。遺傳算法的處理對象不是參數(shù)本身，而是針對那些通過參數(shù)集進(jìn)行編碼得到的基因個體。此編碼操作使得遺傳算法可以直接對結(jié)構(gòu)對象進(jìn)行操作。所謂結(jié)構(gòu)對象，泛指集合、序列、矩陣、樹、圖、鏈和表等各種一維或二維甚至多維結(jié)構(gòu)形式的對象。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。比如：通過對連接矩陣的操作，遺傳算法可用來對神經(jīng)網(wǎng)絡(luò)或自動機(jī)的結(jié)構(gòu)或參數(shù)加以優(yōu)化。通過對集合的操作，遺傳算法可實(shí)現(xiàn)對規(guī)則集合和知識庫的精煉而達(dá)到高質(zhì)量的機(jī)器學(xué)習(xí)目的。通過對樹結(jié)構(gòu)的操作，用遺傳算法可得到用于分類的最佳決策樹。通過對任務(wù)序列的操作，遺傳算法可用于任務(wù)規(guī)劃，而通過對操作序列的處理，可自動構(gòu)造順序控制系統(tǒng)。（2） 群體搜索特性。許多傳統(tǒng)的搜索方法都是單點(diǎn)搜索，這種點(diǎn)對點(diǎn)的搜索方法，對于多峰分布的搜索空間常常會陷于局部的某個單峰的極值點(diǎn)。相反，遺傳算法是采用同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進(jìn)行評估。這一特點(diǎn)使遺傳算法具有較好的全局搜索性能，也使得遺傳算法本身易于并行化。（3） 不需要輔助信息。遺傳算法只適應(yīng)度函數(shù)的數(shù)值來評估基因個體，并在此基礎(chǔ)上進(jìn)行遺傳操作。更重要的是，遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對適應(yīng)度函數(shù)的惟一要求是，編碼必須與可行解空間對應(yīng)，不能有死碼。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。（4） 內(nèi)在啟發(fā)式隨機(jī)搜索特性。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。概率僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動。雖然看起來它是一種盲目搜索方法，實(shí)際上它有明確的搜索方向，具有內(nèi)在的并行搜索機(jī)制。（5） 遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，也能以很大的概率找到全局最優(yōu)解。（6） 遺傳算法采用自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決非常困難的問題。（7） 遺傳算法具有固有的并行性和并行計(jì)算的能力。（8） 遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合。重點(diǎn)注意的是，遺傳算法對給定問題給出大量可能的解答并挑選最終的解答給用戶。要是一個特定問題并沒有單個的解，例如Pareto最優(yōu)解系列中，就像多目標(biāo)優(yōu)化和日程安排的案例中，遺傳算法將盡可能地用于識別可同時替換的解。1.2.2遺傳算法的不足之處遺傳算法作為一種優(yōu)化方法，它存在自身的局限性：（1） 編碼不規(guī)范及編碼存在表示的不準(zhǔn)確性。（2） 單一的遺傳算法編碼不能全面地將優(yōu)化問題的約束表示出來。考慮約束的一個方法就是對不可行解采用閾值，這樣，計(jì)算的時間必然增加。

遺傳算法通常的效率比其它傳統(tǒng)的優(yōu)化方法低。遺傳算法容易出現(xiàn)過早收斂。遺傳算法對算法的精度、可信度、計(jì)算復(fù)雜性等方面，還沒有有效的定量分析方法。1.3遺傳算法與傳統(tǒng)方法的比較對于一個求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類似)，一般可描述為帶約束條件的數(shù)學(xué)規(guī)劃模型：max f(X)(1.1)<s.t. XeR(1.1)RgU,七］t為決策變量，f(X)為目標(biāo)函數(shù)，U為基本空間，R是U的一個子集。滿足約束條件的解稱為可行解(FeasibleSolution)，集合R表示由所有滿足約束條件的解所組成的一個集合，稱為可行解集合。它們之間的關(guān)系如圖1.2所示。圖1.2圖1.2最優(yōu)化問題的可行解及可行解集合對于上述最優(yōu)化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的;有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解是不可能的，也是不現(xiàn)實(shí)的，因而求出其近似最優(yōu)解或滿意解是人們主要研究的問題之一。對于類似上述最優(yōu)化問題，求最優(yōu)解或近似最優(yōu)解的傳統(tǒng)方法主要有解析法、隨機(jī)法和窮舉法。解析法中，主要包括爬山法和間接法。隨機(jī)法中，主要包括導(dǎo)向隨機(jī)方法和盲目隨機(jī)方法。而窮舉法中，包括完全窮舉法、回溯法、動態(tài)規(guī)劃法和限界剪枝法。此類問題可以利用遺傳算法求解。而對于求解此類問題，遺傳算法與一般傳統(tǒng)方法有著本質(zhì)的區(qū)別。圖1.3為傳統(tǒng)算法和遺傳算法對比示意圖。傳統(tǒng)算法起始于單個遺傳算法起始于群體傳統(tǒng)算法起始于單個遺傳算法起始于群體圖1.3傳統(tǒng)算法和遺傳算法對比1.3.1遺傳算法與啟發(fā)式算法的比較啟發(fā)式算法是指通過尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，找到問題的一個最優(yōu)解或近似最優(yōu)解。該方法求解問題的效率較高，但是它對每一個所求的問題必須找出其特有的啟發(fā)式規(guī)則，這個啟發(fā)式規(guī)則一般無通用性，不適合于其他問題。但遺傳算法采用的不是確定性規(guī)則，而是強(qiáng)調(diào)利用概率轉(zhuǎn)換規(guī)則來引導(dǎo)搜索過程。1.3.2遺傳算法與爬山法的比較爬山法是直接法、梯度法和Hessian法的通稱。爬山法首先在最優(yōu)解可能存在的地方選擇一個初始點(diǎn)，然后通過分析目標(biāo)函數(shù)的特性，由初始點(diǎn)移到一個新的點(diǎn)，然后再繼續(xù)這個過程。爬山法的搜索過程是確定的，通過產(chǎn)生一系列的點(diǎn)收斂到最優(yōu)解:有時是局部最優(yōu)解），而遺傳算法的搜索過程是隨機(jī)的，它產(chǎn)生一系列隨機(jī)種群序列。二者的主要差異可以歸納為如下兩點(diǎn)：（1） 爬山法的初始點(diǎn)僅有一個，由決策者給出；遺傳算法的初始點(diǎn)有多個，是隨機(jī)產(chǎn)生的。（2） 通過分析目標(biāo)函數(shù)的特性可知，爬山法由上一點(diǎn)產(chǎn)生一個新的點(diǎn)；遺傳算法通過遺傳操作，在當(dāng)前的種群中經(jīng)過交叉、變異和選擇產(chǎn)生下一代種群。對同一優(yōu)化問題，遺傳算法所使用的機(jī)時比爬山法所花費(fèi)的機(jī)時要多。但遺傳算法可以處理一些爬山法所不能解決的復(fù)雜的優(yōu)化問題。1.3.3遺傳算法與窮舉法的比較窮舉法就是對解空間內(nèi)的所有可行解進(jìn)行搜索，但是通常的窮舉法并不是完全窮舉法，即不是對所有解進(jìn)行嘗試，而是有選擇地嘗試，如動態(tài)規(guī)劃法、限界剪枝法。對于特定的問題，窮舉法有時也表現(xiàn)出很好的性能。但一般情況下，對于完全窮舉法，方法簡單易行，但求解效率太低；對于動態(tài)規(guī)劃法、限界剪枝法，則魯棒性不強(qiáng)。相比較而言，遺傳算法具有較高的搜索能力和極強(qiáng)的魯棒性。1.3.4遺傳算法與盲目隨機(jī)法的比較與上述的搜索方法相比，盲目隨機(jī)搜索法有所改進(jìn)，但它的搜索效率仍然不高。一般而言，只有解在搜索空間中形成緊致分布時，它的搜索才有效。而遺傳算法作為導(dǎo)向隨機(jī)搜索方法，是對一個被編碼的參數(shù)空間進(jìn)行高效搜索。經(jīng)過上面的探討，能看到遺傳算法與更多的傳統(tǒng)優(yōu)化方法在本質(zhì)上有著不同之處。主要有四點(diǎn)不同：（1） 遺傳算法搜索種群中的點(diǎn)是并行的，而不是單點(diǎn)。（2） 遺傳算法并不需要輔助信息或輔助知識，只需要影響搜索方向的目標(biāo)函數(shù)和相對應(yīng)的適應(yīng)度。（3） 遺傳算法使用概率變換規(guī)則，而不是確定的變換規(guī)則。（4） 遺傳算法工作使用編碼參數(shù)集，而不是自身的參數(shù)集（除了在實(shí)值個體中使用）。1.4遺傳算法的基礎(chǔ)用語由于遺傳算法是自然遺傳學(xué)和計(jì)算機(jī)科學(xué)相互結(jié)合滲透而成的新的計(jì)算方法，因此遺傳算法中經(jīng)常使用自然進(jìn)化中有關(guān)的一些基本用語。了解這些用語對于討論和應(yīng)用遺傳算法是十分必要的。生物的遺傳物質(zhì)的主要載體是染色體，DNA是其中最主要的遺傳物質(zhì)，而基因（Gene）又是控制生物性狀的遺傳物質(zhì)的功能單位和結(jié)合單位。復(fù)數(shù)個基因組成染色體，染色體中基因的位置稱為基因座（Locus），而基因所取的值叫做等位基因（Allele）?；蚝突蜃鶝Q定了染色體的特征，也就決定了生物個體的性質(zhì)狀態(tài)。染色體有兩種相應(yīng)的表示模式，即基因型和表現(xiàn)型。所謂表現(xiàn)型，是指生物個體所表現(xiàn)出來的性質(zhì)狀態(tài)，而基因型是指與表現(xiàn)型密切相關(guān)的基因組成。同一種基因型的生物個體在不同的環(huán)境條件下可以有不同的表現(xiàn)型，因此表現(xiàn)型是基因型與環(huán)境條件相互作用的結(jié)果。在遺傳算法中，染色體對應(yīng)的是數(shù)據(jù)或數(shù)組，在標(biāo)準(zhǔn)的遺傳算法中，通常是由一維的串結(jié)構(gòu)數(shù)據(jù)表現(xiàn)的。串上各個位置對應(yīng)上述的基因座，而各位置上所取的值對應(yīng)上述的等位基因。遺傳算法處理的是染色體，或者叫基因型個體。一定數(shù)量的個體組成了群體，也叫集團(tuán)。群體中個體的數(shù)目稱為群體的大小，也叫群體規(guī)模。而各個體對環(huán)境的適應(yīng)程度叫適應(yīng)度。執(zhí)行遺傳算法時包含兩個必要的數(shù)據(jù)轉(zhuǎn)換操作，一個是表現(xiàn)型到基因型的轉(zhuǎn)換，它把搜索空間中的參數(shù)或解轉(zhuǎn)換成遺傳空間中的染色體或個體，此過程稱為編碼操作；另一個是基因型到表現(xiàn)型的轉(zhuǎn)換，它是前者的一個相反操作，稱為譯碼操作。表1.1為自然遺傳學(xué)和人工遺傳算法中所使用的基礎(chǔ)用語的對應(yīng)關(guān)系。表1.1遺傳學(xué)和遺傳算法中基礎(chǔ)用語對照表自然遺傳算法人工遺傳算法染色體(chromosome)解的編碼（數(shù)據(jù)、數(shù)組、位串）基因（gene）解中每一分量的特征（特性、個性、探測器、位）等位基因（allele）特性值基因座（locus）串中位置基因型（genptype）結(jié)構(gòu)表現(xiàn)型（phenotype）參數(shù)集、解碼結(jié)構(gòu)、候選解遺傳隱匿非線性個體(individual)解適者生存在算法停止時，最優(yōu)目標(biāo)值的解有最大的可能被留住適應(yīng)性（fitness）適應(yīng)度函數(shù)值群體(population)選定的一組解（其中解的個數(shù)為群體的規(guī)模）復(fù)制(reproduction)根據(jù)適應(yīng)函數(shù)值選取的一組解交配（。rossover）通過交配原則產(chǎn)生一組新解的過程變異(mutation)編碼的某一個分量發(fā)生變化的過程1.5遺傳算法的研究方向遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物，它已經(jīng)發(fā)展成一種自組織、自適應(yīng)的綜合技術(shù)，其研究方向主要有下面幾個方面。基礎(chǔ)理論遺傳算法的數(shù)學(xué)理論并不完善，張鈴等對遺傳算法的“模式定理”和“隱性并行性”進(jìn)行分析研究，指出其不足并指出遺傳算法本質(zhì)上是一個具有定向制導(dǎo)的隨機(jī)搜索技術(shù)。在遺傳算法中，群體規(guī)模和遺傳算子的控制參數(shù)的選取非常困難，但它們又是必不可少的實(shí)驗(yàn)參數(shù)，在這方面，已有一些具有指導(dǎo)性的實(shí)驗(yàn)結(jié)果。遺傳算法還有一個過早收斂的問題，如何阻止過早收斂也是人們正在研究的問題之一。分布并行遺傳算法遺傳算法在操作上具有高度的并行性，許多研究人員都在探索在并行機(jī)和分布式系統(tǒng)上高效執(zhí)行遺傳算法的策略。對分布遺傳算法的研究表明，只要通過保持多個群體和恰當(dāng)控制群體間的相互作用來模擬并發(fā)執(zhí)行過程，即使不使用并行計(jì)算機(jī)，也能提高算法的執(zhí)行效率。遺傳算法的并行性主要從三個方面考慮，即個體適應(yīng)度評價的并行性、整個群體各個個體適應(yīng)度評價的并行性及子代群體產(chǎn)生過程的并行性。分類系統(tǒng)分類系統(tǒng)屬于基于遺傳算法的機(jī)器學(xué)習(xí)中的一類，包括一個簡單的基于串規(guī)則的并行生成子系統(tǒng)、規(guī)則評價子系統(tǒng)和遺傳算法子系統(tǒng)。分類系統(tǒng)被人們越來越多地應(yīng)用在科學(xué)、工程和經(jīng)濟(jì)領(lǐng)域中，是目前遺傳算法研究中一個十分活躍的方向。遺傳神經(jīng)網(wǎng)絡(luò)遺傳神經(jīng)網(wǎng)絡(luò)包括連接級、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)規(guī)則的進(jìn)化。遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合，成功地用于從時間序列分析來進(jìn)行財政預(yù)算。在這些系統(tǒng)中，訓(xùn)練信號是模糊的，數(shù)據(jù)是有噪聲的，一般很難正確給出每個執(zhí)行的定量評價，如果采用遺傳算法學(xué)習(xí)，就能克服這些困難，顯著提高系統(tǒng)性能。Muhlenbein分析了多層感知網(wǎng)絡(luò)的局限性，并猜想下一代神經(jīng)網(wǎng)絡(luò)將是遺傳神經(jīng)網(wǎng)絡(luò)。進(jìn)化算法模擬自然進(jìn)化過程可以產(chǎn)生魯捧的計(jì)算機(jī)算法一一進(jìn)化算法。遺傳算法是其三種典型的算法之一，其余兩種算法是進(jìn)化規(guī)劃和進(jìn)化策略，這三種算法是獨(dú)立發(fā)展起來的。人工生命與遺傳算法近幾年來，通過計(jì)算機(jī)模擬，再現(xiàn)種種生命現(xiàn)象以達(dá)到對生命更深刻理解的人工生命的研究正在興起。已有不少學(xué)者對生態(tài)系統(tǒng)的演變、食物鏈的維持以及免疫系統(tǒng)的進(jìn)化等用遺傳算法作了生動的模擬。但是實(shí)現(xiàn)人工生命的手段很多，遺傳算法在實(shí)現(xiàn)人工生命中的基本地位和能力究竟如何，這是值得研究的課題。1.6基于遺傳算法的應(yīng)用遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題具體的領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于許多學(xué)科。近十年來，遺傳算法得到了迅速發(fā)展，其主要表現(xiàn)在眾多的應(yīng)用領(lǐng)域。目前，遺傳算法在生物技術(shù)和生物學(xué)、化學(xué)和化學(xué)工程、計(jì)算機(jī)輔助設(shè)計(jì)、物理學(xué)和數(shù)據(jù)分析、動態(tài)處理、建模與模擬、醫(yī)學(xué)與醫(yī)學(xué)工程、微電子學(xué)、模式識別、人工智能、生產(chǎn)調(diào)度、機(jī)器人學(xué)、開礦工程、電信學(xué)、售貨服務(wù)系統(tǒng)等領(lǐng)域都得到應(yīng)用，成為求解全局優(yōu)化問題的有力工具之一。下面給出遺傳算法一些主要的應(yīng)用領(lǐng)域。i.函數(shù)優(yōu)化函數(shù)優(yōu)化(FunctionOptimization)是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進(jìn)行性能評價的常用算例?？梢杂酶鞣N各樣的函數(shù)來驗(yàn)證遺傳算法的性能。對一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，使用遺傳算法可得到較好的結(jié)果。2組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時在目前的計(jì)算機(jī)上用枚舉法很難甚至不能求出問題的最優(yōu)解，對這類問題，人們已意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效。生產(chǎn)調(diào)度問題采用遺傳算法能夠解決復(fù)雜的生產(chǎn)調(diào)度問題。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面，遺傳算法都得到了有效的應(yīng)用。自動控制在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步應(yīng)用