遺傳算法及其應(yīng)用-畢業(yè)(完整版)資料

遺傳算法及其應(yīng)用-畢業(yè)（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）

遺傳算法及其應(yīng)用-畢業(yè)（完整版）資料(可以直接使用，可編輯優(yōu)秀版資料，歡迎下載）摘要遺傳算法是一種模擬自然界生物進化的搜索算法，由于它的簡單易行、魯棒性強，尤其是其不需要專門的領(lǐng)域知識而僅用適應(yīng)度函數(shù)作評價來指導(dǎo)搜索過程，從而使它的應(yīng)用范圍極為廣泛，并且己在眾多領(lǐng)域得到了實際應(yīng)用，取得了許多令人矚目的成果，引起了廣大學者和工程人員的關(guān)注。在簡要的介紹了遺傳算法的發(fā)展歷史和研究現(xiàn)狀及其生物學、數(shù)學基礎(chǔ)后，文中引出了遺傳算法的基本概念和原理、分析了遺傳算法的基本實現(xiàn)技術(shù)。如：編碼、適應(yīng)度函數(shù)、遺傳算法的三大遺傳操作、參數(shù)規(guī)則等。最后在介紹了遺傳算法程序設(shè)計原則的基礎(chǔ)上，編程實現(xiàn)了遺傳算法在圖像識別中的應(yīng)用，在實踐中檢驗了遺傳算法的實際效果。關(guān)鍵詞：遺傳算法，適應(yīng)度函數(shù)，圖像識別ABSTRACTThegeneticalgorithmisakindofsearchingmethodwhichsimulatesthenaturalevolution.Itissimpleandeasytoimplement,especiallyitdonotneedthespecialfieldknowledge,soithasbeenusinginverybroadfields.Nowthegeneticalgorithmhasgotalotoffruits,andmoreandmorescholarsbegintopayattentiononit.Afterbriefintroductedthegeneticalgorithmandstudyedthehistoryofthedevelopmentstatusandbiology,mathematicalbasis,webroughtoutthebasicgeneticalgorithmconceptsandprinciples,analysisedthegeneticalgorithmtoachievethebasictechnology.Suchas:coding,fitnessfunction,geneticalgorithmofthethreemajorgeneticmanipulation,andotherparametersoftherules.Finally,introducedageneticalgorithmproceduresbasedontheprinciplesofdesign,programmingageneticalgorithmintheapplicationofimagerecognition,inpractice,wetestthepracticaleffectsofgeneticalgorithm.Keyword：geneticalgorithm，F(xiàn)itnessfunction，imagerecognition引言當前科學技術(shù)正進入多學科互相交叉、互相滲透、互相影響的時代，生命科學與工程科學的交叉、滲透和相互促進是其中的一個典型例子，也是近代科學技術(shù)發(fā)展的一個顯著特點。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學發(fā)展的這一特點和趨勢。制造機器智能一直是人類的夢想，人們?yōu)榇烁冻隽司薮蟮呐?。近年來，隨著人工智能應(yīng)用領(lǐng)域的不斷拓廣，傳統(tǒng)的基于符號處理機制的人工智能方法在知識表示、處理模式信息及解決組合爆炸等方面所碰到的問題已變得越來越突出，這些困難甚至使某些學者對人工智能提出了強烈批判，對人工智能的可能性提出了質(zhì)疑。在人工智能領(lǐng)域中，有不少問題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或準優(yōu)解。因此，研究能在搜索過程中自動獲得和積累有關(guān)搜索空間的知識，并能自適應(yīng)地控制搜索過程，從而得到最優(yōu)解或準優(yōu)解的通用搜索算法一直是令人矚目的課題。遺傳算法就是在這種背景下產(chǎn)生并經(jīng)實踐證明特別有效的算法。遺傳算法(GeneticAlgorithmGA)是近年來迅速發(fā)展起來的一種全新的隨機搜索與優(yōu)化算法,其基本思想是基于Darwin的進化論和Mendel的遺傳學說。該算法由密執(zhí)安大學教授Holland及其學生于1975年創(chuàng)建。自1985年以來。國際上已召開了多次遺傳算法的學術(shù)會議和研討會。國際遺傳算法學會組織召開的ICGA(InternationalConferenceonGeneticAlgorithms)會議FOGA(Workshop-onFoundationofGeneticAlgorithms)會議。為研究和應(yīng)用遺傳算法提供了國際交流的機會。作為一種通用的問題求解方法，遺傳算法采用簡單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇，來指導(dǎo)學習和確定搜索的方向。近年來，遺傳算法已被成功地應(yīng)用于工業(yè)、經(jīng)濟管理、交通運輸、工業(yè)設(shè)計等不同領(lǐng)域。解決了許多問題。例如：可靠性優(yōu)化、流水車間調(diào)度、作業(yè)車間調(diào)度、機器調(diào)度、設(shè)備布局設(shè)計、圖像處理以及數(shù)據(jù)挖掘等。第一章緒論1.1遺傳算法的發(fā)展歷史與研究現(xiàn)狀20世紀60年代，美國Michigan大學的JohnHolland教授開始研究自然和人工系統(tǒng)的自適應(yīng)行為，在這些研究中，他試圖發(fā)展一種用于創(chuàng)造通用程序和機器的理論，使得通用程序和機器具有適應(yīng)任意環(huán)境的能力。他意識到用群體方法搜索以及選擇、交換等操作策略的重要性。在六十年代中期至七十年代末期，基于語言智能和邏輯數(shù)學智能的傳統(tǒng)人工智能十分興盛，而基于自然進化的思想則遭到懷疑和反對，Holland及其數(shù)位博士生仍堅持了這一方向的研究。Bagley發(fā)明“遺傳算法”一詞，并發(fā)表了第一篇有關(guān)遺傳算法應(yīng)用的論文，在他開創(chuàng)性的博士論文中采用雙倍體編碼，發(fā)展了與目前類似的復(fù)制、交換、突變、顯性、倒位等基因操作，他還敏銳地察覺到防止早熟收斂的機理，并發(fā)展了自組織遺傳算法的概念。與此同時，Rosen-berg在他的博士論文中進行了單細胞生物群體的計算機仿真研究，對以后函數(shù)優(yōu)化的研究頗有啟發(fā)，并發(fā)展了自適應(yīng)交換策略。Cavicohio1970年研究了基于遺傳算法的子程序選擇和模式識別問題，在模式識別問題上，采用整數(shù)編碼，檢索空間很大，他提出了以預(yù)選擇策略保證群體多樣性，對遺傳算法參數(shù)進行中心控制的方法。同年，Weinberg研究了生物體的計算機仿真，他的貢獻在于提出運用多層遺傳算法來進行遺傳算法的參數(shù)自優(yōu)化。1968至1971年，Holland提出了重要的模式理論，建議采用二進制編碼。與前面幾位博士不同，Holland首次采用二進制編碼來研究函數(shù)優(yōu)化問題，并指出了運用Gray碼的一些優(yōu)點，他研究了從生物系統(tǒng)引申出的各種不同的選擇和配對策略。1972年，F(xiàn)rantz的博士論文中研究了許多新的問題，如基因非線性(異位顯性)現(xiàn)象，基因遷移操作及多點交換操作等，由于沒有設(shè)計出諸如GA－eception之類合適的非線性優(yōu)化問題，實驗結(jié)果并不具備說服力。這一年，Holland的模式理論也漸趨成熟，但在編碼策略上出現(xiàn)了至今仍執(zhí)爭論的二派，一派根據(jù)模式定理建議用盡量少的符號編碼，一派以數(shù)值優(yōu)化計算的方便和精度為準采用一個基因一個參數(shù)的方法，并把相應(yīng)的基因操作改造成適合實數(shù)操作的形式，Bosworth，Zoo和Zeigler是后者的開創(chuàng)者。1975年豎立了遺傳算法發(fā)展史上的兩塊里程碑，一是Holland出版了經(jīng)典著作《AdaptationinNatureandArtificialSystem》，該書是作者十幾年間許多思想及其實現(xiàn)的結(jié)晶，詳細闡述了遺傳算法的理論，并為其奠定了數(shù)學基礎(chǔ)，發(fā)展了一整套模擬生物自適應(yīng)系統(tǒng)的理論；二是DeJong完成了具有指導(dǎo)意義的博士論文《AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem》，他深入領(lǐng)會了模式定理并做了大量嚴格的計算實驗，給出了明確的結(jié)論，他還建立了著名的DeJong五函數(shù)測試平臺，定義了性能評價標準，并以函數(shù)優(yōu)化為例，對遺傳算法的六種方案的性能及機理進行了詳細實驗和分析，他的工作成為后繼者的范例并為以后的廣泛應(yīng)用奠定了堅實的基礎(chǔ)。為克服DeJong的輪盤賭(隨機)選擇操作中的隨機誤差，Brindle于1981年在她的博士論文中研究了六種復(fù)制策略。進入八十年代，隨著以符號系統(tǒng)模仿人類智能的傳統(tǒng)人工智能暫時陷入困境，神經(jīng)網(wǎng)絡(luò)、機器學習和遺傳算法等從生物系統(tǒng)底層模擬智能的研究重新復(fù)活并獲得繁榮。Goldberg在遺傳算法研究中起著繼往開來的作用，他在1983年的博士論文中第一次把遺傳算法用于實際的工程系統(tǒng)—煤氣管道的優(yōu)化，從此，遺傳算法的理論研究更為深入和豐富，應(yīng)用研究更為廣泛和完善，自1985年起，遺傳算法及其應(yīng)用國際會議每二年召開一次，有關(guān)人工智能的會議和刊物上大多有遺傳算法的專題，Goldberg的課本，及其他學者的專著的出版有力地推動了遺傳算法的傳播。進入九十年代，以不確定性、非線性、時間不可逆為內(nèi)涵，以復(fù)雜問題為對象的科學新范式得到學術(shù)界普遍認同，如廣義進化綜合理論。由于遺傳算法能有效地求解屬于NPC類型的組合優(yōu)化問題及非線性多模型、多目標的函數(shù)優(yōu)化問題，從而得到了多學科的廣泛重視，一些學者也認識到求解復(fù)雜問題最優(yōu)解是不現(xiàn)實的，故而尋求滿意解，而遺傳算法是最佳工具之一，生物進化的歷史比任何數(shù)學證明都強有力，問題是遺傳算法在吸收遺傳學、進化論及分子生物學最新成果和在實驗得到證明和證偽的同時本身也在進化。目前，遺傳算法引起包括數(shù)學、物理、化學、生物學、計算機科學等領(lǐng)域的科學家的極大興趣。遺傳算法的研究領(lǐng)域和內(nèi)容十分的廣泛，如遺傳算法的設(shè)計與分析，遺傳算法的理論基礎(chǔ)及其在各個領(lǐng)域的應(yīng)用。隨著理論的深入研究和應(yīng)用領(lǐng)域的不斷拓展，遺傳算法必將取得更大的發(fā)展。1.2遺傳算法的生物學基礎(chǔ)生物的進化過程19世紀50年代。英國生物學家達爾文根據(jù)他對世界各地生物的考察結(jié)果和人工選擇實驗。提出了“生物進化論”。1859年達爾文發(fā)表了《物種起源》巨著。提出了以自然選擇為基礎(chǔ)的生物進化論學說。根據(jù)達爾文的進化論，生物進化的發(fā)展來源于三種動力：遺傳、變異和選擇。遺傳就是子代總是保持和親代的相似性，遺傳性是一切生物所共有的特征。正是這種遺傳性，使得生物能夠把它的特性、性狀傳給后代，并在后代中保持相似?，F(xiàn)代遺傳學研究表明，生物都具有遺傳性。遺傳學的建立和發(fā)展有力地推動和促進了進化論，變異是子代和親代有某些不相似的現(xiàn)象。即子代永遠不會和親代完全一樣，變異是一切事物所具有的共同特征，是生物個體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是生活條件的影響，器官使用的不同及雜交。變異性為生物的進化發(fā)展創(chuàng)造了條件，選擇決定了生物進化的方向，所謂選擇是指生物具有保留和淘汰的特性，選擇分為人工選擇和自然選擇。人工選擇是在人為環(huán)境下把對人有利的生物保留下，把對人不利的個體淘汰掉；自然選擇就是指生物在自然界的生存環(huán)境中適者生存，世界上所有形形色色的生物都是在自然選擇的影響下、在悠久的歲月中形成的。自然選擇的過程是通過生存斗爭的過程來實現(xiàn)生存斗爭的結(jié)果，優(yōu)勝劣汰。這樣就保證了生物去適應(yīng)環(huán)境，通過不斷地自然選擇，那些有利于生存的變異就遺傳下去，日積月累越來越大，逐步產(chǎn)生了新的物種。生物的各項生命活動都有他的物質(zhì)基礎(chǔ)。生物的遺傳和變異也不例外。遺傳物質(zhì)的主要載體為染色體。研究表明，染色體主要有脫氧核糖核酸和蛋白質(zhì)，其中脫氧核糖核酸在染色體中含量穩(wěn)定，結(jié)構(gòu)相對穩(wěn)定，能夠自我復(fù)制，前后保持一定的連續(xù)性，能夠產(chǎn)生可遺傳的變異。因此它是主要的遺傳物質(zhì)。生物的性狀遺傳主要是通過染色體傳遞給后代。因此，基因是控制生物性狀的遺傳物質(zhì)的功能和結(jié)構(gòu)單位。生物變異與遺傳一樣，也是很復(fù)雜的，由遺傳物質(zhì)引起的變異稱為遺傳變異。它有三種來源：基因重組、基因變異和基因突變?；蛑亟M是控制不同性狀的基因的重新組合；基因變異是指基因內(nèi)部的化學變化；基因突變的產(chǎn)生是在一定外界環(huán)境條件和生物內(nèi)部因素的作用下，基因的分子結(jié)構(gòu)發(fā)生改變的結(jié)果。每種生物染色體無論結(jié)構(gòu)和數(shù)目都是相對恒定的。但在自然條件和人為條件的影響下染色體結(jié)構(gòu)和數(shù)目都可以發(fā)生變化，染色體數(shù)目的改變是染色體變異的一個重要方面。遺傳算法正是借鑒生物自然選擇和遺傳機制的隨機搜索算法。它之所以能夠增強解決問題的能力，是因為自然演化過程本質(zhì)就是一個學習與優(yōu)化的過程。遺傳算法通過模擬“優(yōu)勝劣汰，適者生存”的規(guī)律激勵好的結(jié)構(gòu)，通過模擬孟德爾的遺傳變異理論在迭代過程中保持已有的結(jié)構(gòu)，同時尋找更好的結(jié)構(gòu)。生物學對遺傳算法的啟示生物是在遺傳的過程中保持物種性狀的，而變異是生物在綜合作用過程中不斷向前發(fā)展和進化的動力，選擇通過遺傳和變異起作用，變異為選擇提供資料。遺傳鞏固與積累選擇資料，而選擇則能控制變異與遺傳的方向。使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。雖然生物進化論揭示了生物長期自然選擇的進化發(fā)展規(guī)律。然而科學家從中受到了啟迪，進化論的自然選擇過程蓄含一種搜索和優(yōu)化的先進思想。而將這種思想用于工程技術(shù)領(lǐng)域發(fā)展起來的遺傳算法，為解決許多傳統(tǒng)的優(yōu)化問題提供了許多途徑。1.3遺傳算法的數(shù)學基礎(chǔ)遺傳算法之所以能在眾多優(yōu)化問題中得到廣泛應(yīng)用且效果較好，必然有其理論上的機理。Holland提出的模式定理和積木塊假設(shè)即是遺傳算法的理論基礎(chǔ)。模式定理作為描述遺傳算法動力學機理的基本定理，奠定了遺傳算法的數(shù)學基礎(chǔ)。1.3.1模式理論定義1.1：模式是表示一些相似的模塊，它描述了在某些位置上具有相似結(jié)構(gòu)特征的個體在編碼串的一個子集。為不失一般性，考慮二值字符集{0,1}，由此可產(chǎn)生通常的0,1字符串，為了方便描述一個模式，增加一個通配符“*”，也稱為無關(guān)符，用它來表示不確定字符，它既可代表字符集中的0，也可代表字符集中的1，并且可在字符集中的任意位置，這樣，二值字符集{0,1}就擴展成三值字符集{0，1，*}。引入模式的概念后，我們可以看到一個串實際上隱含著多個模式，一個模式可以隱含在多個串中，不同的串之間通過模式而相互聯(lián)系。定義1.2：在模式H中具有確定基因值的位置數(shù)目稱為該模式的模式階(SchemaOrder)，記為O(H)。如模式011*1*的模式階為4，模式0******的模式階為1。顯然，一個模式的階數(shù)越高，其樣本個數(shù)越少，因而確定性越高。定義1.3：模式H中第一個確定基因值的位置和最后一個確定基因值的位置之間的距離稱為該模式的模式定義長度(SchemaDefiningLength)或模式定義距，記為S(H)。如模式011*1*的定義距為4，而模式0******的定義距為0。在研究交叉算子對模式的作用時可以發(fā)現(xiàn)：對于單點交叉算子，模式1***0比模式10***更易被破壞，這兩個模式具有相同的階，為了描述這一性質(zhì)，我們引入了模式定義距。定理1.1(模式定理)：在遺傳算子選擇、交叉和變異的作用下，具有低階、短模式距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中以指數(shù)級增長。模式定理從模式角度論證了N個初始種群在經(jīng)過選擇、交叉、變異算子后模式H的變化：（1.1）其中，表示第代種群中模式所能匹配的樣本的數(shù)量,?()、?分別表示第代所有模式的平均適應(yīng)度與種群平均適應(yīng)度，表示串的長度，、分別表示交叉概率與變異概率。定理中的三項分別說明了GA運算中選擇、交叉和變異對種群中模式數(shù)量的影響：(1)模式的增長(減少)，即樣本數(shù)量的增加(減少)，依賴于模式的平均適應(yīng)度與群體適應(yīng)度之比，那些平均適應(yīng)度高于種群平均適應(yīng)度的將在下一代中得以增長，而那些平均適應(yīng)度低于種群平均適應(yīng)度的將在下一代中減少；（2）具有短模式距的模式經(jīng)過交叉后樣本的數(shù)量越多；（3）具有低階的模式經(jīng)過變異后的生存率越大，它大約為：。從定理可以簡單地分析一下交叉概率PC和變異概率Pm的作用，當其它值不變時，PC、Pm越小，則模式在下一代(代)群體中的個體數(shù)量越大，即個體趨向相似和一致，新個體的數(shù)量減少，從而使搜索范圍減小，能快速收斂但也容易產(chǎn)生“早熟”現(xiàn)象；PC、Pm增大，群體多樣性增強，搜索范圍擴大，但有可能破壞群體中好的模式，使收斂速度變慢。因此，在實際應(yīng)用時，可參照該定理設(shè)置或調(diào)整PC、Pm的值。作為指導(dǎo)遺傳算法的基本理論，模式定理同時還對遺傳算法作了如下的啟示：（1）編碼中根據(jù)模式定理，遺傳過程中存活的都是長度短、階次低、適應(yīng)度高的模式，因此編碼時應(yīng)使所研究的主要性質(zhì)用一長度短、階次低的模式表示；而次要性質(zhì)用其它模式表示。因為二進制字符串擁有的內(nèi)涵(模式數(shù)目)比較大，編碼時盡量使用二進制或字符變化少的字符串。（2）交叉操作中當親代的優(yōu)良模式介于字符串首尾之間時，如果采用一點交叉方式，它必然被破壞，在子代中就沒法保留其優(yōu)良模式，而相反，若采用兩點交叉，其子代個體不僅保留原來親代個體1的優(yōu)良模式，而且兼容親代個體2的優(yōu)良模式，從而形成比原來更優(yōu)良的模式。因此，在遺傳算法中常使用該交叉方式，尤其是當字符串長度比較大的時候。1.3.2積木塊假設(shè)符合模式定理的這類模式在GA中非常有用，我們將它定義為積木塊。GA模擬了生物的進化機制，模式定理則提供了一種解釋這種機理的數(shù)學工具。定義1.4：具有低階、短模式距以及高適應(yīng)度的模式稱為積木塊。積木塊假設(shè)：低階、短定義距、高平均適應(yīng)度的模式(積木塊)在遺傳算子作用下，相互結(jié)合，能生成高階、長距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。模式定理保證了較優(yōu)的模式(GA的較優(yōu)解)的樣本呈指數(shù)級增長，從而滿足了尋找最優(yōu)解的必要性，即GA存在著尋找到全局最優(yōu)解的可能性；而積木塊假設(shè)指出了遺傳算法具備尋找到全局最優(yōu)解的能力，即積木塊在遺傳算子的作用下，能生成高階、長距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。積木塊假設(shè)被認為是解釋GA尋優(yōu)原理的較完善的理論，它對GA在理論上的深入研究提供了較好的基礎(chǔ)，并為GA性能的改進和應(yīng)用的拓展提供了理論指導(dǎo)。雖然積木塊假設(shè)還未被理論證明，只是稱為假說，但大量的實踐都支持這一假說，實際應(yīng)用領(lǐng)域表明其成功之處，如平滑多峰問題，帶干擾多峰問題，組合優(yōu)化等問題?？梢?，大量的實踐都證明了遺傳算法的適用性。1.3.3遺傳算法的收斂性由模式定理知道了一個給定模式遺傳算子作用在下一代中出現(xiàn)的期望比例，但由此還不能知道算法的收斂性。通過建立遺傳算法搜索的馬爾可夫模型，可證明算法的強收斂性。定義1.5：兩個模式Sa和Sb是非重疊的，當且僅當他們所定義的子集合不相交時，即Sa∩Sb=Φ時，他們非重疊。例如模式00**與01**是非重疊的。定義1.6：兩個模式Sa和Sb是位置等價的，當且僅當（1.2）例如，模式0*1*和1*0*是位置等價的；模式00**和1*0*不是位置等價的。定義1.7：設(shè)ψ是一個非重疊的且位置等價的模式集合，令字母集{0，*}被映射到整數(shù)0，字母L被映射到整數(shù)1，則模式族函數(shù)?：ψ→Z+定義為：（1.3）例如，?（**011）=3。定義1.8：設(shè)Sa,Sb∈ψ,令字母集{0，*}，被映射到整數(shù)0，則模式距離函數(shù)：ψψ→Z+為（1.4）其中=，是異或算子。定義1.9：對任意S∈∑，設(shè)∏={0，1，2，…，-1}是S上位置指標的集合，則所有可能交叉段的集合記為（1.5）定義1.10：設(shè)，,，，∈ψ，廣義交叉算子C：ψψZ→ψψ定義為（1.6）其中對，當，∈Z，，=，=;其他情況下=,=。定義1.11：對于任意,∈ψ,Oab通過所有可能的廣義交叉算子作用在模式,所得到的模式集合。引理1.1：對某個，如果如果(,,Z)={=}，則 (1)（1.7）(2)（1.8）(3)（1.9）其中函數(shù)h表示兩個模式間的Hamming距離，即兩個模式間不同位的數(shù)目。1.4遺傳算法的應(yīng)用領(lǐng)域遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強的魯棒性，所以廣泛應(yīng)用于很多學科。下面是遺傳算法的一些主要應(yīng)用領(lǐng)域：(l)函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進行性能評價的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有凸函數(shù)也有凹函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機函數(shù)，有單峰值函數(shù)也有多峰值函數(shù)等。用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能，更能反映算法的本質(zhì)效果。而對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便地得到較好的結(jié)果。(2)組合優(yōu)化。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴大，有時在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復(fù)雜問題，人們已意識到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于組合優(yōu)化中的NP類問題非常有效。例如：遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱間題、圖形劃分問題等方面得到成功的應(yīng)用。(3)生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解，也會因簡化得太多而使得求解結(jié)果與實際相差甚遠。而目前在現(xiàn)實生產(chǎn)中也主要是靠一些經(jīng)驗來進行調(diào)度?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到廣泛有效的應(yīng)用。(4)自動控制。在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學習等，都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性。(5)機器人學。機器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應(yīng)系統(tǒng)的研究，所以機器人學理所當然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如：遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。(6)人工生命。人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大主要特征。人工生命與遺傳算法有著密切的關(guān)系，基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供了一個有效的工具，人工生命的研究也必將促進遺傳算法的進一步發(fā)展。(7)遺傳編程。Koza發(fā)展了遺傳編程的概念，他使用了以LISB語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進行的遺傳操作來自動生成計算機程序。雖然遺傳編程的理論尚未成熟，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機器學習等領(lǐng)域。(8)機器學習。學習能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一?；谶z傳算法的機器學習，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。如遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數(shù)，能更好地改進了模糊系統(tǒng)的性能?；谶z傳算法的機器學習可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)，也可用于人工神經(jīng)網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計，分類器系統(tǒng)也在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。第二章遺傳算法簡介2.1遺傳算法的基本概念遺傳算法是對人類自然演化過程的模擬。人類的自然演化過程是進化過程，這種進化過程發(fā)生在染色體上；自然選擇使適應(yīng)值好的染色體比那些適應(yīng)值差的染色體有更多的繁殖機會；變異可以使子代染色體不同于父代染色體；通過兩個父代染色體的結(jié)合與重組可以產(chǎn)生全新的染色體。染色體的選擇、變異與重組進程是無記憶的。將這些概念反映在數(shù)學上就形成了遺傳算法的基本概念。個體和個體空間：所謂l個體X，即是長度為l的0和1字符串，簡稱個體；l稱作個體的鏈長，l個體的全體記作S={(0,1)}l，稱為個體空間。按照遺傳學的術(shù)語，個體也稱作染色體(chromosome)，個體的分量稱作基因(gene)，分量的取值稱作等位基因(allele)。種群和種群空間：所謂N種群是N個個體組成的集合(個體允許重復(fù))，簡稱種群。N稱作種群規(guī)模，稱={=(X1,X2,…,XN),Xi∈S(i≤N)}為N種群空間。對于一個種群，由于是由個體構(gòu)成的，因此它是個體空間的一部分，即是個體空間的一個子集。我們可以記為，，當用時，視為一個子集，當用時，表示中不重復(fù)的個體是中的一個子集。這時和都不視為向量。如果視可表示為矩陣形式，如：（2.1）其中每一行代表一個個體，第i行表示第i個個體。對于鏈長為l種群規(guī)模為N的種群可以表示為N×l階矩陣。（2.2）其中為一個個體。表示第i個個體第j個基因取值。適應(yīng)值函數(shù)：對于一個個體產(chǎn)生的效益稱為適應(yīng)值。適應(yīng)值函數(shù)是個體空間S到正實數(shù)空間的映射，即適應(yīng)值函數(shù)為：。選擇算子：選擇算子即是在一個種群中選擇一個個體，它是隨機映射:（2.3）特別地，按照概率規(guī)則（2.4）選擇個體的方式稱為適應(yīng)值選擇算子。其中表示種群中的個體的適應(yīng)值,0<α<∞。對于α=1稱為比例選擇算子，簡記為。容易看到適應(yīng)值選擇算子依賴于種群，它是種群上的一個概率分布，即對于種群=(X1,X2,…,XN)有概率分布（2.5）即構(gòu)成概率分布向量（2.6）其中滿足以下條件：=1\*GB2⑴＞0（）=2\*GB2⑵稱＞0（）為上的一維概率分布。從選擇算子的執(zhí)行過程，適應(yīng)值大的個體易被選擇，適應(yīng)值小的個體易被淘汰，這樣經(jīng)過不斷地選擇使適應(yīng)值大的個體不斷重復(fù)出現(xiàn)，使一個種群可能變?yōu)辇R次種群。但是選擇算子只是在一個固定的種群中進行選擇；選擇的結(jié)果不可能跑到種群之外。對于種群之外更好的個體是不可能被選擇得到的，選擇的結(jié)果依賴于初始種群。母體和母體空間:所謂母體即是一對個體（X1,X2），其中Xi∈S(i=1,2)所有母體的全體稱為母體空間，即S2={(X1,X2)；X1,X2∈S}（2.7）雜交算子：雜交算子是母體空間到個體空間的映射，記作Ts:S2→S（2.8）(l)單點雜交算子：等概率的隨機確定一個基因位置作為雜交點，再把一對母體兩個個體從雜交點分成前后兩個部分，交換兩個個體的后半部分得到兩個新個體，取第一個個體為雜交結(jié)果。(2)單點隨機雜交算子：等概率的隨機確定一個基因位置作為雜交點，再把一對母體兩個個體從雜交點分為前后兩個部分，以概率Pc交換兩個個體的后半部分，得到兩個新個體，取第一個個體為雜交結(jié)果。稱Pc為雜交概率。如果確定兩個基因位置將一對母體兩個個體分成三部分，交換中間部分，稱為雙點雜交算子。同樣有雙點雜交與雙點隨機雜交之分。(3)均勻隨機雜交算子：獨立地以概率Pc把母體的第一個個體的相應(yīng)的分量交換為第二母體的相應(yīng)分量，從而得到雜交結(jié)果。變異算子：變異算子是個體空間到個體空間的隨機映射，其作用方式為獨立地以概率Pm改變個體分量取值。Pm稱作變異概率?；谏飳W上的考慮，一般認為雜交是自然演化的主要機制，變異為自然演化的背景，它們分別承擔遺傳與變異兩種功能。因此在具體應(yīng)用過程中，雜交概率一般取值較大，在0.6與0.9之間。而變異概率取值較小、一般在0.001與0.01之間。遺傳算法的基本概念構(gòu)成了遺傳算法的基本模型。對于一個實際問題，首先是將問題轉(zhuǎn)化為遺傳算法的基本概念。一旦用遺傳算法的基本概念來表達實際問題，問題的求解過程就不再依賴于實際問題本身。2.2遺傳算法的基本原理遺傳算法類似于自然進化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始群體；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群，從而對這個新種群進行下一輪進化。這就是遺傳算法的基本原理。下面是遺傳算法的基本思想：初始化群體；(2)計算群體上每個個體的適應(yīng)度值；(3)按由個體適應(yīng)度值所決定的某個規(guī)則，選擇將進入下一代的個體；(4)按概率Pc進行交叉操作；(5)按概率Pc進行突變操作；(6)沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進入(7)；(7)輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。程序的停止條件最簡單的有如下二種：完成了預(yù)先給定的進化代數(shù)則停止；種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進時停止。應(yīng)用遺傳算法求解應(yīng)用問題時，需要根據(jù)應(yīng)用問題構(gòu)造遺傳算法，遺傳算法中的各種選擇算子、交叉算子、變異算子，遺傳算法的構(gòu)造過程如圖2.1所示。實際應(yīng)用中的優(yōu)化問題都含有一定的約束條件，在遺傳算法中處理約束條件常用的方法有搜索空間限定法、可行解變換法、罰函數(shù)法。搜索空間限定法的思想是在搜索空間中將個體與解空間中可行解之間建立一一對應(yīng)的關(guān)系；可行解變換法的思想是在由個體基因型到個體表現(xiàn)型的變換中增加滿足約束條件的處理過程；罰函數(shù)法的思想是對解空間中無對應(yīng)可行解的個體計算其適應(yīng)度時處以一個罰函數(shù)降低適應(yīng)度，減少此個體遺傳到下一代的機會。另外，在遺傳算法的研究和應(yīng)用中，開發(fā)出了多種高級實現(xiàn)技術(shù)，利用這些技術(shù)可以有效的利用遺傳算法解決廣泛的應(yīng)用問題。最優(yōu)化問題描述最優(yōu)化問題描述解空間確定決策變量、優(yōu)化條件建立優(yōu)化模型第一步第二步確定決策變量、優(yōu)化條件建立優(yōu)化模型目標函數(shù)f（X）目標函數(shù)f（X）個體表現(xiàn)型X個體表現(xiàn)型X確定適應(yīng)度轉(zhuǎn)換規(guī)則解碼方法編碼方法確定適應(yīng)度轉(zhuǎn)換規(guī)則解碼方法編碼方法適應(yīng)度F（X）個體基因型X第三步第四步第五步適應(yīng)度F（X）個體基因型X設(shè)計遺傳算子第六步設(shè)計遺傳算子確定運行參數(shù)確定運行參數(shù)第七步遺傳算法遺傳算法遺傳空間圖2.1遺傳算法的構(gòu)造過程2.3遺傳算法的特征為解決各種優(yōu)化計算問題，人們提出了各種各樣的優(yōu)化算法，如單純形法、梯度法、動態(tài)規(guī)劃法、分枝定界法等。這些優(yōu)化算法各有各的長處，各有各的適用范圍，也各有各的限制。搜索算法的共同特征為：（1）首先組成一組候選解；（2）依據(jù)某些適應(yīng)性條件測算這些候選解的適應(yīng)度；（3）根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解；（4）對保留的候選解進行某些操作，生成新的候選解。在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交叉操作和變異操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計算的搜索算法，與其他一些優(yōu)化算法相比，它主要有下述幾個特點：遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實際值本身來進行優(yōu)化計算，但遺傳算法不是直接以決策變量的值而是以決策變量的某種形式的編碼為運算對象。這種對決策變量的編碼處理方式，使得我們在優(yōu)化計算過程中可以借鑒生物學中染色體和基因等概念，可以模仿自然界中生物的遺傳和進化等機理，也使得我們可以方便地應(yīng)用遺傳操作算子。特別是對一些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化間題，編碼處理方式更顯示出了其獨持的優(yōu)越性。遺傳算法直接以目標函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標函數(shù)值，而且往往需要目標函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數(shù)位變換來的適應(yīng)度函數(shù)值，就可確定進一步的搜索方向和搜索范圍，無商月標函數(shù)的導(dǎo)數(shù)伍等其他一些輔助信．這個特性對很多目標函數(shù)是無法或很難求導(dǎo)數(shù)的函數(shù)，或?qū)?shù)不存在的函數(shù)的優(yōu)化阿題，以及組合優(yōu)化問題等，應(yīng)用遺傳算法時就顯得比較方便，它避開函數(shù)求導(dǎo)這個障礙。再者，直接利月目標函數(shù)值或個體適應(yīng)度，也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高搜索效率。遺傳算法同時使用多個搜索點的搜索信息。傳統(tǒng)的優(yōu)化算法往往是從解中的一個初始點開始最優(yōu)解的迭代搜索過程。單個搜索點所提供的搜索信息畢竟不多，所以搜索效率不高，有時甚至使搜索過程陷于局部最優(yōu)解而停滯不前。遺傳算法從由很多個體所組成的一個初始群體開始最優(yōu)解的搜索過程．而不是從一個單一的個體開始搜索。對這個群體所進行的選擇、雜交、變異等運算，產(chǎn)生出的仍是新一代的群體，在這之中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點，所以實際上相當于搜索了更多的點，這是遺傳算法所特有的一種隱含特性。遺傳算法使用概率搜索技術(shù)。很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個搜索點到另一個搜索點的轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系，這種確定性往往也有可能使得搜索遠達不到最優(yōu)點，從而也限制了算法的應(yīng)用范圍。而遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了其搜索過程的靈活性。雖然這概率特性也會使群體中產(chǎn)生一些適應(yīng)度不高的個體，但隨著進化過程的進行，新的群體中總更多地產(chǎn)生出許多優(yōu)良的個體，實踐和理論都已證明了在一定條件下遺傳算法總是以概率收斂問題為最優(yōu)解。當然，交叉概率和變異概率等參數(shù)也會影響算法的搜索效果和搜索效率，所以如何選擇遺傳算法的參數(shù)在其應(yīng)用中是一個比較重要的問題。另一方面，與其他一些算法相比，遺傳算法的魯棒性又會使得參數(shù)對其搜索效果的影響會盡可能地低。遺傳算法作為一種快捷、簡便、容錯性強的算法，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。搜索過程是從一組解迭代到另一組解，采用同時處理群體中多個個體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。采用概率的變遷規(guī)則來指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。對搜索空間沒有任何特殊要求（如連通性、凸性等），只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其它輔助信息，適應(yīng)范圍更廣。第三章遺傳算法的基本實現(xiàn)技術(shù)3.1編碼編碼方法遺傳算法主要是通過遺傳操作對群體中具有某種結(jié)構(gòu)形式的個體施加結(jié)構(gòu)重組處理，從而不斷地搜索出群體中個體間的結(jié)構(gòu)相似性，形成并優(yōu)化積木塊以逐漸逼近最優(yōu)解，因此，遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成的染色體或個體。該轉(zhuǎn)換操作就稱為編碼。編碼過程是問題空間向遺傳算法空間的映射過程，所謂問題空間是指由遺傳算法表現(xiàn)個體(有效的候選解)集合所組成的空間；而遺傳算法空間是指由基因型個體所組成的空間。編碼過程是遺傳算法的基石，編碼方法除了決定了個體的染色體排列形式之外，它還決定了個體從遺傳算法空間的基因型變換到問題空間的表現(xiàn)型時的解碼方法；編碼方法也影響到交叉算子、變異算子等遺傳算子的運算方法。由此可見，編碼方法在很大程度上決定了如何進行群體的遺傳進化運算以及遺傳進化運算的效率。一個好的編碼方法，有可能會使得交叉運算、變異運算等遺傳操作可以簡單地實現(xiàn)和執(zhí)行。而一個差的編碼方法，卻有可能會使得交叉運算、變異運算等遺傳操作難以實現(xiàn)，也有可能會產(chǎn)生很多在可行解集合內(nèi)無對應(yīng)可行解的個體，這些個體經(jīng)解碼處理后所表示的解稱為無效解。因此Goldberg提出了三條編碼評估規(guī)范：（1）完備性(Completeness)：問題空間中的所有點都能作為GA空間中的點(染色體)表現(xiàn)。（2）健全性(Soundness)：GA空間中的染色體能對應(yīng)所有問題空間中的候選解。（3）非冗余性(Nonredundancy)：染色體和候選解一一對應(yīng)。大多數(shù)的應(yīng)用中，二進制編碼用得最多，其次是十進制編碼。SGA采用二進制0，l編碼方式，將問題的一個解表示成一個串長為L的二進制串，作為一個個體，L稱為鏈長。編碼表示1.二進制編碼二進制碼編碼即是將原問題的解映射成為0，1組成的位串，然后在位串空間上進行遺傳操作。結(jié)果再通過解碼過程還原成其解空間的解，然后再進行適應(yīng)度的計算。使用二進制編碼方法能表達的模式數(shù)最多。除此之外，該方法還具有如下優(yōu)點：（1）簡單易行；（2）符合最小字符集編碼原則；（3）便于模式定理對算法進行理論分析。但在求解連續(xù)化優(yōu)化問題時，它存在以下缺點：（1）相鄰整數(shù)的二進制編碼可能具有較大的Hamming距離，例如15和16的二進制表示為01111和10000。因此，算法要從15改進到16則必須改變所有的位。這種缺陷將降低遺傳算子的搜索效率。二進制編碼的這一缺點被稱為Hamming懸崖。（2）二進制編碼時，一般要先給出求解的精度以確定串長。而一旦精度確定后，就很難在算法執(zhí)行過程中進行調(diào)整。從而使算法缺乏微調(diào)的功能。若在算法一開始就選取較高的精度，那么位串就很長，這樣也會降低算法的效率。（3）在求解高維優(yōu)化問題時，二進制編碼位串將非常長，從而使得算法的搜索效率很低。2.格雷（Gray）編碼格雷碼即是將二進制編碼通過一個變換而得到的編碼，其目的是克服二進制編碼中Hamming懸崖的缺點。3.實數(shù)編碼為了克服二進制編碼的缺點，對于問題的變量是實向量的情形，可以直接采用十進制進行編碼。這樣，便可直接對解進行遺傳操作，從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力。對實數(shù)編碼的情形，通常需要針對十進制編碼的特性，引入其他一些遺傳算子。實驗證明，對于大部分數(shù)值優(yōu)化問題，通過一些專門設(shè)計的遺傳算子的引入，采用實數(shù)編碼比采用二進制編碼是算法的平均效率要高。4.有序串編碼對于很多組合優(yōu)化問題，目標函數(shù)的值不僅與表示解的字符串中的各字符的值有關(guān)，而且與其所在字符串的位置有關(guān)。這樣的問題稱為排序問題。若目標函數(shù)的值只與表示解的字符串中各字符的位置有關(guān)而與其具體的字符值無關(guān)，則稱為純排序問題。如求解旅行商問題就是用的第一種編碼方式。用遺傳算法求解有序問題時，傳統(tǒng)的遺傳操作將可能產(chǎn)生非法的后代。因此，對這類問題需要針對具體問題專門設(shè)計有效且能保證后代合法的遺傳算子。這類編碼方案在組合優(yōu)化問題中使用較多。5.動態(tài)編碼動態(tài)編碼是當算法收斂到某局部極值時增加搜索的精度。增加精度的辦法是在保持串長不變的前提下減小搜索區(qū)域。用遺傳算法求解有序問題時，傳統(tǒng)的遺傳操作將可能產(chǎn)生非法的后代。因此，對于這類問題需要針對具體問題專門設(shè)計有效且能保證后代合法的遺傳算子。3.2適應(yīng)度函數(shù)3.2.1基本的適應(yīng)度函數(shù)適應(yīng)度函數(shù)(FitnessFunction)的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解，因為遺傳算法在進化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個個體的適應(yīng)度來進行搜索。因為適應(yīng)度函數(shù)的復(fù)雜度是遺傳算法復(fù)雜度的主要組成部分，所以適應(yīng)度函數(shù)的設(shè)計應(yīng)盡可能簡單，使計算的時間復(fù)雜度最小。遺傳算法評價一個解的好壞不是取決于它的解的結(jié)構(gòu)，而是取決于相應(yīng)于該解的適應(yīng)度值，這正體現(xiàn)了遺傳算法“優(yōu)勝劣汰”的特點。遺傳算法不需要適應(yīng)度函數(shù)滿足連續(xù)可微等條件，唯一要求是針對輸入可計算出能加以比較的非負結(jié)果。這一特點使得遺傳算法具有廣泛的適用性。在實際問題中，適應(yīng)度函數(shù)與問題的目標函數(shù)是不完全一致的，如有的問題的目標是要求的最小值(費用問題)，而有的問題的目標是要求得最大值(利潤函數(shù))。因此在不少場合，需要將目標函數(shù)映射成求最大值形式而且函數(shù)值非負的適應(yīng)度函數(shù)是必要的。在函數(shù)優(yōu)化中，適應(yīng)度函數(shù)可由目標函數(shù)變換得到，可以有以下三種處理情況：（1）直接以待求解的目標函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，即：若目標函數(shù)為最大化問題若目標函數(shù)為最小化問題（2）若目標函數(shù)為最小問題，則：（3.1）其中系數(shù)Cmax存在多種選擇方法，它可以是一個合適的輸入值，也可以采用迄今為止進化過程中g(shù)(x)的最大值，但Cmax最好與群體無關(guān)。若目標函數(shù)為最大問題，則：（3.2）其中系數(shù)Cmin存在多種選擇方法，它可以是一個合適的輸入值，也可以采用迄今為止進化過程中g(shù)(x)的最小值，但Cmin最好與群體無關(guān)。（3）若目標函數(shù)為最小問題，則：（3.3）若目標函數(shù)為最大問題，則：（3.4）上兩式C為目標函數(shù)界限的保守估計值。適應(yīng)度函數(shù)對GA的收斂速度和結(jié)果影響很大。如果過分強調(diào)當前的較優(yōu)點，就可能很快降低種群的多樣性，造成不成熟收斂；如果對當前較優(yōu)點強調(diào)不夠，算法就很容易丟失已經(jīng)找到的較優(yōu)點信息，從而不能在合理的時間內(nèi)收斂到較好的點。因此在具體的應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定。目標函數(shù)映射成適應(yīng)度函數(shù)將目標函數(shù)映射成適應(yīng)度函數(shù)，就是將目標函數(shù)映射成求最大值形式且函數(shù)值非負的適應(yīng)度函數(shù)。當把一個最小化問題轉(zhuǎn)化為最大化問題，可采用以下方法進行轉(zhuǎn)換：(3.5)有多種方式來選擇Cmax。Cmax可以是一個合適的輸入值，也可采用迄今為止進化過程中g(shù)(x)的最大值，或g(x)的最大值。如果g(x)非負，也可采用轉(zhuǎn)換f(x)=1/g(x)當待求解問題是求g(x)的最大值時，適應(yīng)度函數(shù)的非負性可用如下變換得到保證(3.6)Cmin可以是合適的輸入值，或是當前一代或前k代中g(shù)(x)的最小值，或g(x)的最小值。適應(yīng)度函數(shù)的調(diào)整應(yīng)用遺傳算法時（尤其用它處理小規(guī)模群體時）常常會出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。在進化的初期，通常會出現(xiàn)一些異常的個體，若按照輪盤賭選擇策略，這些異常個體有可能在群體中占據(jù)很大的比例，這是我們不希望出現(xiàn)的現(xiàn)象，因為這樣可能導(dǎo)致未成熟收斂現(xiàn)象。這是因為，這些異常個體競爭力太突出，因而會控制選擇過程，從而影響算法的全局優(yōu)化性能。對于未成熟收斂現(xiàn)象，設(shè)法降低某些異常個體的競爭力，這可以通過縮小相應(yīng)的適應(yīng)度函數(shù)值來實現(xiàn)。有時也需要擴大相應(yīng)的適應(yīng)度函數(shù)值。這種適應(yīng)度的縮放稱作適應(yīng)度調(diào)整。目前，調(diào)整方式主要有以下幾種。1.線性調(diào)整設(shè)原適應(yīng)度函數(shù)為?()，調(diào)整后的適應(yīng)度函數(shù)為，則線性調(diào)整可采用(3.7)式中系數(shù)a和b滿足：原適應(yīng)度平均值要等于調(diào)整后的適應(yīng)度平均值，調(diào)整后適應(yīng)度函數(shù)的最大值要等于原適應(yīng)度函數(shù)平均值的所指定倍數(shù)。即(3.8)其中C是為得到所期待的最優(yōu)個體的復(fù)制數(shù)。實驗表明，對于一個不太大的群體而言，C可在1.2～2.0范圍內(nèi)取值。2.冪調(diào)整該調(diào)整方式可定義為：(3.9)式中指數(shù)k與待求解問題有關(guān)，而且在算法過程中可按需要做修正。該調(diào)整方式由Gillies提出，他曾在機器視覺實驗中采用了該方法，當時，他取=1.005。3.3選擇算子從群體中選擇優(yōu)勝的個體、淘汰劣質(zhì)個體的操作叫選擇。在生物的遺傳和自然進化過程中，對生存環(huán)境適應(yīng)度較高的物種將有更多的機會遺傳到下一代，而對生存環(huán)境適應(yīng)程度較低的物種遺傳到下一代的機會就相對較少。模仿這個過程，遺傳算法使用選擇算子對群體中的個體進行優(yōu)勝劣汰。選擇運算(SelectionOperator或稱為復(fù)制reproduction運算)把當前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個體將有更多的機會遺傳到下一代群體中。選擇的標準就是各個體的適應(yīng)度值大小，個體的適應(yīng)度值越高，它被選中的概率越大。目前遺傳算法中最常用的選擇算子是比例復(fù)制法。選擇的方法根據(jù)不同的問題采用不同的方案。常見的方法有以下幾種：1.適應(yīng)度比例法(fitnessproportionalmodel)該方法又稱為賭輪法(RouletteWheel或蒙特卡洛伽onteCar.lo)模型，是目前最常用的選擇方法。SGA中的選擇算子采用的就是該策略。它是指個體被選中并遺傳到下一代群體中的概率與該個體的適應(yīng)度大小成正比，是一種有循環(huán)的隨機選擇。具休表達方法如下：(3.10)式中xi為種群中第i個染色體對應(yīng)的數(shù)字串，?(xi)是第i個染色體的適應(yīng)度值，是種群中所有染色體的適應(yīng)度值之和。用適應(yīng)度比例法進行選擇時，首先計算每個染色體的適應(yīng)度，然后按比例于各染色體適應(yīng)度的概率進入交換（匹配）集的染色體，其具體步驟如下：（1）計算每個染色體的適應(yīng)度值?；（2）累加所有染色體的適應(yīng)度值，得最終累加值=（3）產(chǎn)生一個隨機數(shù)，（4）選擇對應(yīng)的中間累加值滿足的染色體進入交換集；（5）重復(fù)（3），（4），直到交換集中包含足夠多的染色體數(shù)字串為止。重復(fù)上述過程，直到交換集中包含足夠多的染色體為止。顯然，此法要求染色體的適應(yīng)度應(yīng)為正值。2.排序選擇法(Rank-basedmodel)排序選擇方法在計算除每個個體適應(yīng)度后，根據(jù)適應(yīng)度大小在群體中對個體排序，然后把事先設(shè)計好的概率表按序分配給個體，作為各自的選擇概率。所有個體按適應(yīng)度大小排序，因而選擇概率和適應(yīng)度無直接關(guān)系而僅與序號有關(guān)。這種方法的不足之處在于選擇概率和序號的關(guān)系需事先確定。此外，它和適應(yīng)度比例方法一樣都是基于概率的選擇，所以仍有統(tǒng)計誤差。3.最佳個體保存法(elitistmodel)該方法的思想是把群體中適應(yīng)度最高的個體不進行配對交叉而直接復(fù)制到下一代中，當然，這樣做的前提是下一代中不存在該個體。采用這種選擇方法的優(yōu)點是，進化過程中某一代的最優(yōu)解可不被交叉或變異操作破壞。但是，這也隱含了一種危機，即局部最優(yōu)個體的遺傳基因會因急速增加，而使進化有可能陷于局部解。也就是說，該方法的全局搜索能力差。它適合于單峰性質(zhì)的優(yōu)化問題的空間搜索，而不適于多峰性質(zhì)的空間搜索。所以，該方法一般都與其他選擇方法結(jié)合使用。4.期望值法(expectedvaluemodel)在輪盤賭選擇方法中，當個體數(shù)不太多時，依據(jù)產(chǎn)生的隨機數(shù)有可能會出現(xiàn)不正確地反映個體適應(yīng)度的選擇。即存在統(tǒng)計誤差，也就是說，適應(yīng)度高的個體有可能被淘汰，適應(yīng)度低的個體也有可能被選擇。為了克服這種缺點，期望值方法用了如下思想：（1）計算群體中每個個體在下一代生存的期望數(shù)目(3.11)（2）若某個個體被選中并要參與配對和交叉，則它在下一代中的生存的期望數(shù)目減去0.5；若不參與配對和交叉，則該個體的期望數(shù)目減1。（3）在（2）的兩種情況中，若一個個體的期望值小于零，則該個體不參與選擇。5.競爭法(tournamentselection)競爭法的個體的選擇公式為：?m=max{?i,?j},即隨機地選取兩個個體，對其適應(yīng)值進行比較，大的被選中，小的被自然淘汰；如果兩個個體的適應(yīng)值相同，則任意選取其中的一個。被選中的個體放入配對庫中。重復(fù)此過程，直至配對庫中包含N個個體為止。這種方法既保證了配對庫中的個體在解空間中有較好的分散性，同時又保證了加入配對庫中的個體具有較大的適應(yīng)值。6.窗口方法(windowingmethod)其方法是首先求出目前解群中適應(yīng)值最小的個體，令其適應(yīng)值為Q。讓解群中的每個個體的適應(yīng)值都減去Q后作為其適應(yīng)值，再用輪盤賭法形成配對庫。采用這種方法時，個體入選配對庫的概率雖不與其適應(yīng)值直接成比例，但關(guān)系比較大，與解群中最大的個體與最小的個體的適應(yīng)值之差以及個體的分散程度有關(guān)。7.線性標準化方法(linearnormalizationmethod)首先，把目前解群中的個體按適應(yīng)值大小降序排列，令最大的適應(yīng)值為U。解群中的其它個體的適應(yīng)值以V線性遞減。再用輪盤賭法產(chǎn)生配對庫。V值越大，對解群中優(yōu)良個體的選擇壓力越大。以上講述的幾種選擇方式均以適應(yīng)度為基礎(chǔ)進行選擇，這就可能在進化過程中導(dǎo)致以下問題：（1）在群體中出現(xiàn)個別或極少數(shù)適應(yīng)度值相當高的個體時，采用這類選擇機制就有可能導(dǎo)致這些個體在群體中迅速繁殖，經(jīng)過少數(shù)幾次迭代后就占滿了群體的位置，這樣GA的求解過程就結(jié)束了，也即收斂了。但這樣很有可能是收斂到局部最優(yōu)解，即遺傳算法的不成熟收斂，即“早熟”現(xiàn)象的出現(xiàn)，這是因為搜索的范圍很有限。因而一般不希望有個別個體在GA運算的最初幾次迭代時就在群體中占據(jù)主導(dǎo)地位。（2）當群體中個體適應(yīng)度彼此非常接近時，這些個體進入配對庫的機會相當，而且交叉后得到的新個體也不會有多大變化，這樣搜索過程就不能有效地進行，這類選擇機制有可能趨向于純粹的隨機選擇，從而使進化過程陷于停頓的狀態(tài)，難以找到全局最優(yōu)解。針對上述問題，可以采用以下幾種提高GA性能的選擇方法：穩(wěn)態(tài)繁殖(steadystatereproduction)：就是在迭代過程中用部分優(yōu)質(zhì)新個體(子代)來更新目前群體中部分舊個體(父代)后，來作為下一代群體。這樣一些優(yōu)質(zhì)父代個體在下一代群體中就得以保留。計算表明，這種方法也有助于改善GA的行為，但需合理地確定每次用多少子代個體來取代父代個體。沒有重串的穩(wěn)態(tài)繁殖(steadystatereproductionwithoutduplicates)：在形成新一代群體時，使其中的個體均不重復(fù)。作法是：在將某個個體加入到新一代群體之前，先檢查該個體與群體中現(xiàn)有的個體是否重復(fù)，如果重復(fù)就舍棄。這種作法會明顯改善GA的行為，因為其增大了個體在群體中的分布區(qū)域，但增加了計算時間。3.4交叉算子交叉(crossover)算子也稱重組(recombination)、配對算子(breeding)。在遺傳算法中，交叉是產(chǎn)生新個體的主要手段，它在遺傳算法中起著核心作用。它仿照生物學中雜交的原理，將兩個父代個體(染色體)的部分字符(基因)互相交換，由此產(chǎn)生新的個體。通過交叉，遺傳算法的搜索能力得以飛躍提高。設(shè)計交叉算子的要點是應(yīng)當保證前一代中優(yōu)秀個體的性狀能在后一代新個體中盡可能得到遺傳和繼承。交叉算子作用于染色體，所以和編碼設(shè)計是相互聯(lián)系的，需要協(xié)調(diào)操作。常用的方法有:1.單點交叉(One-pointcrossover)單點交叉又叫簡單交叉。具體操作是:在個體基因串中隨機設(shè)定一個交叉點。實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進行互換，并生成兩個新個體。當基因鏈碼的長度為n時，可能有n-1個交叉點位置。2.二點交叉(Two-pointcrossover)具體操作是隨機設(shè)定兩個交叉點，互換兩個父代在這兩點間的基因串，分別生成兩個新個體，若染色體有L長，則有((L-2)(L-3)種交叉結(jié)果。單點交叉是常用的交叉算子。在實際應(yīng)用中，研究者往往以單點交又為出發(fā)點對其性能進行研究，但很多情況下其它交叉方法的性能優(yōu)于單點交叉算子。交叉概率Pc的大小也直接影響著遺傳算法的性能，較大的交叉概率可增強遺傳算法開辟新的搜索區(qū)域的能力，但高性能的模式遭到破壞的可能性增大；若交叉概率太低，遺傳算法搜索可能陷入遲鈍狀態(tài)。因而，設(shè)計合適的交叉概率是算法獲得良好性能的條件之一。一般建議的PC取值范圍是0.50.99之間。3.多點交叉(multi-pointcrossover)多點交叉時前述兩種交叉方法的推廣。多點交叉有時又被稱為廣義交叉。若用參數(shù)C表示交叉數(shù)，則當C=1時，廣義交叉就是單點交叉。C=2，廣義交叉就是兩點交叉。一般來說，多點交叉不經(jīng)常被采用。這是因為當基因鏈碼的長度n較小，或交叉點數(shù)C較大時，即使這種模式的階和定義矩較小，具有優(yōu)良特性的模式也很容易被破壞。另外通常情況下，出于計算速度的考慮，基因鏈碼的長度n不會很大。4.均勻交叉(uniformcrossover)均勻交叉則是依概率交換兩個父輩個體基因串的每一位。其過程是：先隨機地產(chǎn)生一個與父輩個體基因串具有同樣長度的二進制串，其中0表示不交換，1表示交換。這個二進制串稱為交叉模板；然后根據(jù)模板對兩個父輩基因串進行交叉，得到的兩個新基因串即為后代新個體。均勻交叉在交換位時并不考慮其所在位置，破壞模式的概率較大。但另一方面它能搜索到一些前面基于點的交叉方法無法搜索到的模式。交叉算子對遺傳算法的收斂性是有影響的。交叉算子并未提供算法向最優(yōu)解收斂的保證。模式定理只是考慮到選擇算子可以維持模式，而交叉算子和變異算子會破壞模式。并在此基礎(chǔ)上指出，低階、短定義距的模式可呈指數(shù)倍增長。但它并沒有確認這些呈指數(shù)增長的模式一定向最優(yōu)解收斂。雖然交叉算子缺乏向最優(yōu)解的收斂保證，但這并不影響遺傳算法的實用性。有時，許多具有向最優(yōu)解收斂的算法卻犧牲了它們的全局性和靈活性。因此，不少很難求解的優(yōu)化問題，對于基于交叉的遺傳算法而言是簡單可解的了。3.5變異算子變異算子的相關(guān)內(nèi)容變異算子主要模擬生物個體的隨機變異現(xiàn)象。對個體串的某些基因位的值進行隨機改變，其作用是增強遺傳算法運行中群體的多樣性，是對有效基因缺失的一種補救措施，同時也對因選擇操作失去的多樣性的恢復(fù)具有潛在的作用，是實現(xiàn)遺傳算法全局優(yōu)化性能的重要算子之一。遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力，這也是使遺傳算法獲得良好收斂性能的前提條件。實際上，交叉運算是遺傳算法區(qū)別于其它進化算法的根本所在，在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的最主要方法，它決定了遺傳算法的全局搜索能力。但因選擇和交叉作用后保留了適應(yīng)度高的個體，便會產(chǎn)生封閉競爭，導(dǎo)致“近親繁殖”，從而引起“早熟”現(xiàn)象。變異操作可增加新的搜索空間，改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)“早熟”現(xiàn)象，但會降低收斂速度。變異是對于二進制編碼方式而言，變異操作就是把某些基因座上的基因值取反，即1變0或0變1。通常情況，變異個體的選擇以及變異位置的確定都是采用隨機的方法產(chǎn)生。變異概率過大將引起遺傳算法的振蕩，過小則影響各進化迭代搜索區(qū)域的范圍。并且變異概率較小，約為0.0010.01。變異算子的基本內(nèi)容是對群體中的個體串的某些基因位置上的基因值作變動。一般來說，變異算子操作的基本步驟如下：（1）在群體中所有個體的碼串范圍內(nèi)隨機地確定基因位置。（2）以事先設(shè)定的變異概率Pm來對這些基因位置的基因值進行變異。遺傳算法通過交叉和變異這一對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合，是指當群體在進化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助于這種擺脫；所謂競爭，是指當通過交叉已形成所期望的基因塊時，變異操作有時可能破壞這些基因塊。遺傳算法中使用變異算子使得遺傳算法有局部的隨機搜索能力，而且可以使遺傳算法維持群體的多樣性。變異算子的搜索能力分析定義3.1：P(b1→b2)，個體b1通過變異算子一步變異到個體b2的概率；對n(b1,b2)，兩個個體差異位數(shù)（可取1,2,…,L）。則有：（3.12）（1）變異概率對P(b1→b2)的影響對（3.12）式求偏導(dǎo)數(shù)可得：（3.13）令得：（3.14）以L=20，n(b1,b2)=3為例，分析對P(b1→b2)的影響，由式（3.14）K可知=n(b1,b2)/L時概率最大，此時P(b1→b2)=2.1301e0.04。對于確定的n(b1,b2)，=n(b1,b2)/L時，P(b1→b2)得到最大值。（2）變異位數(shù)n(b1,b2)對P(b1→b2)的影響對（3.12）式求n(b1,b2)，的偏導(dǎo)可得：（3.15）函數(shù)（3.12）關(guān)于n(b1,b2)嚴格單調(diào)遞減，n(b1,b2)=1時，有：(3.16)以L=20，=0.1為例，進一步觀察n(b1,b2)對P(b1→b2)的影響，由公式可知：n(b1,b2)=1時，P(b1→b2)取得最大值，此時P(b1→b2)=1.3509×10-2}。隨著n(b1,b2)每增加1，搜索范圍迅速變大，同時搜索概率P(b1→b2)迅速減小一個數(shù)量級，這使得在n(b1,b2)大于一定程度時，如此小的概率下的搜索變的缺乏實際意義。同時從中可以看出，雖然，變異策略在理論上保障了算法的全局收斂性，但是，變異算子主要進行的是針對每個個體的局域搜索。（3）多個個體b1變異到b2的概率和期望定義3.2：，K個個體b1通過變異算子變異產(chǎn)生至少一個個體b2的概率；E(b2|K個b1)，K個個體b1通過變異算子變異產(chǎn)生個體b2的期望個數(shù)。則有：（3.17）從式（3.17）可以看出和E(b2|K個b1)是關(guān)于K和P(b1→b2)的嚴格單調(diào)遞增函數(shù)。定義算法中概率的可以接受下界為，則有：（3.19）或者（3.20）3.6遺傳算法的參數(shù)規(guī)則首先定義如下：在合理的進化代數(shù)內(nèi)，個體b能夠搜索到其相鄰區(qū)域的局部極值稱為有效局域搜索。同時，我們把這個合理進化代數(shù)稱為算法最大容許停滯代數(shù)，以M表示。假定待求問題滿足積木塊假設(shè)，我們來分析變異算子的局部搜索能力。算法迭代進化到一定代數(shù)后，一般會收斂到某一或某幾個點上，考慮特殊情況下，群體提前收斂于一點b1，則有：K=N，同時取α=1/M，則有：（3.21）由式（3.13）和（3.15）可得當n(b1,b2)=1，Pb1=1時P(b1→b2)取得最大值。（3.22）由式（3.21）,（3.22）可得：（3.23）在滿足積木塊假設(shè)的前提下，任何不是全局最優(yōu)解的個體b1都可以通過隨機的一個基因位的變異搜索到較優(yōu)解b2，即：存在b2，滿足n(b1,b2)=1，且f(b2)＞f(b1)。所以，可以得到如下的參數(shù)選擇規(guī)則：(3.24)其中，M可以自由設(shè)定，一般可以設(shè)定為最大算法迭代代數(shù)的1/41/3。第四章遺傳算法的程序設(shè)計4.1遺傳算法程序設(shè)計的基本原則設(shè)計遺傳算法程序，利用計算機仿真實際模型或直接求解問題，是研究和應(yīng)用遺傳算法的一個重要領(lǐng)域。自從遺傳算法理論提出后，人們就無時無處不在利用計算機程序來實現(xiàn)各自的遺傳算法研究和應(yīng)用，對算法的改進、新算子的構(gòu)造、算法效果的觀測，都離不開編程實現(xiàn)。本文在前面理論研究和分析的基礎(chǔ)上，也進行了計算機編程實現(xiàn)。一般來講，實際設(shè)計任何GA軟件系統(tǒng)，都要考慮下面三個方面。1.通用性一個好的GA軟件系統(tǒng)，應(yīng)該能滿足不同應(yīng)用場合的需要，具有較大的適用范圍，即使要解決某些特殊問題，所做的修改也應(yīng)盡量少，并且是在原有基礎(chǔ)上適當改動，而不是重頭再來或大幅度改變數(shù)據(jù)結(jié)構(gòu)。2．靈活性實際設(shè)計的GA系統(tǒng)，還應(yīng)有相當?shù)撵`活性，可以采用不同的控制參數(shù)，接受一定范圍內(nèi)的參數(shù)變化，并能針對具體情況允許采用不同的操作策略和操作算子。3.可擴展性好的GA系統(tǒng)還必須能夠滿足在以后進行擴展，如對問題解施行新的編碼方式、采用新的編碼結(jié)構(gòu)、接納新的算子等等。采用模塊描述軟件結(jié)構(gòu)，能給人全面、整體的設(shè)計思路和布局，具有一定的指導(dǎo)意義；而利用matlab強大的矩陣運算能力，使我們能夠不局限于程序設(shè)計的細節(jié)，從算法的整體來進行考慮。4.2程序設(shè)計過程中需要考慮的問題在前面章節(jié)中，我們已經(jīng)說明了遺傳算法在解決實際問題時采用的步驟與方法以及各種具體處理方式，在不同的應(yīng)用場合，遺傳算法的實現(xiàn)形式也不盡相同，但不管這些差別任何GA實現(xiàn)都要處理以下這些問題。l.染色體編碼遺傳算法不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)換成遺傳空間的由基因按一定結(jié)構(gòu)組成染色體。編碼通常包括對變量的處理和編碼方法的選擇