遺傳算法及應(yīng)用

遺傳算法及應(yīng)用6.1遺傳算法的原理與特點(diǎn)6.2遺傳算法的基本操作與模式理論6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)6.4遺傳算法在智能控制中的應(yīng)用6.1遺傳算法的原理與特點(diǎn)問題1：什么是“遺傳”和“進(jìn)化”？

歷史遺傳算法是一種新發(fā)展起來的基于優(yōu)勝劣汰、自然選擇、適者生存和基因遺傳思想的優(yōu)化算法，20世紀(jì)60年代產(chǎn)生于美國的密歇根大學(xué)。1967年，JohnH.Holland教授的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法（GeneticAlgorithms）”一詞此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1971年，R.B.Hollstien在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。而JohnH.Holland在1975年出版的“AdaptationinNaturalandArtificialSystems”

（《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》）一書通常認(rèn)為是遺傳算法的經(jīng)典之作，該書給出了遺傳算法的基本定理，并給出了大量的數(shù)學(xué)理論證明。JohnH.Holland的學(xué)生DavidE.Goldberg教授在1989年出版的“GeneticAlgorithms”一書通常認(rèn)為是對(duì)遺傳算法的方法、理論及應(yīng)用的全面系統(tǒng)的總結(jié)。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(jì)(geneticprogramming,

GP)方法，成功地解決了許多問題發(fā)展從1985年起，國際上開始舉行“遺傳算法的國際會(huì)議”，以后則更名為“進(jìn)化算法的國際會(huì)議”，參加的人數(shù)及收錄的文章數(shù)量、廣度和深度逐次擴(kuò)大。遺傳算法已成為人們來解決高度復(fù)雜問題的一個(gè)新思路和新方法。目前遺傳算法已被廣泛應(yīng)用于許多實(shí)際問題，如函數(shù)優(yōu)化、自動(dòng)控制、圖像識(shí)別、機(jī)器學(xué)習(xí)、人工神經(jīng)網(wǎng)絡(luò)、分子生物學(xué)、優(yōu)化調(diào)度等許多領(lǐng)域中的問題。在歐洲，從1990年開始每隔一年舉辦一次ParallelProblemSolvingfromNature學(xué)術(shù)會(huì)議，其中遺傳算法是會(huì)議主要內(nèi)容之一。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有FoundationsofGeneticAlgorithms，該會(huì)也是從1990年開始隔年召開一次。這些國際會(huì)議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動(dòng)向。6.1.1遺傳算法的基本原理遺傳算法的基本原理是基于達(dá)爾文的進(jìn)化論和孟德爾的基因遺傳學(xué)原理。進(jìn)化論認(rèn)為每一物種在不斷的發(fā)展過程中都是越來越適應(yīng)環(huán)境的。物種的每個(gè)個(gè)體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化若適應(yīng)環(huán)境，則被保留下來。在某一環(huán)境中也是那些更能適應(yīng)環(huán)境的個(gè)體特征能被保留下來，這就是適者生存的原理。遺傳學(xué)說認(rèn)為，遺傳是作為一種指令碼封裝在每個(gè)細(xì)胞中，并以基因的形式包含在染色體中，每個(gè)基因有特殊的位置并控制某個(gè)特殊的性質(zhì)，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境有一定的適應(yīng)性，基因雜交和基因突變可能產(chǎn)生對(duì)環(huán)境適應(yīng)性更強(qiáng)的后代，通過優(yōu)勝劣汰的自然選擇，適應(yīng)值高的基因結(jié)構(gòu)就保存下來遺傳算法將問題的求解表示成“染色體”（用編碼表示字符串）。該算法從一群“染色體”串出發(fā)，將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，通過交叉、變異兩種基因操作產(chǎn)生出新的一代更適應(yīng)環(huán)境的“染色體”種群。隨著算法的進(jìn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體。這一過程就如生物進(jìn)化那樣，好的特征被不斷的繼承下來，壞的特征被逐漸淘汰。新一代個(gè)體中包含著上一代個(gè)體的大量信息，新一代的個(gè)體不斷地在總體特性上勝過舊的一代，從而使整個(gè)群體向前進(jìn)化發(fā)展。對(duì)于遺傳算法，也就是不斷接近最優(yōu)解。6.1.2遺傳算法的特點(diǎn)遺傳算法將自然生物系統(tǒng)的重要機(jī)理運(yùn)用到人工系統(tǒng)的設(shè)計(jì)中，與其他尋優(yōu)算法必然有著本質(zhì)的不同。常規(guī)的尋優(yōu)方法主要有3種類型：解析法、枚舉法和隨機(jī)法。解析法尋優(yōu)是研究的最多的一種，它一般又可以分為間接法和直接法。間接法是通過讓目標(biāo)函數(shù)的梯度為零，進(jìn)而求解一組非線性方程來尋求局部極值。直接法是使梯度信息按最陡的方向逐次運(yùn)動(dòng)來尋求局部極值，它即為通常所稱的爬山法。枚舉法上述兩種方法的主要缺點(diǎn)如下：（1）它們只能尋找局部極值而非全局的極值。（2）它們要求目標(biāo)函數(shù)是連續(xù)光滑的，并且需要導(dǎo)數(shù)信息。這兩個(gè)缺點(diǎn)，使得解析尋優(yōu)方法的性能較差。枚舉法可以克服上述解析法的兩個(gè)缺點(diǎn)，即它可以尋找到全局的極值，而且也不需要目標(biāo)函數(shù)是連續(xù)光滑的。它的最大缺點(diǎn)是計(jì)算效率太低，對(duì)于一個(gè)實(shí)際問題，常常由于太大的搜索空間而不可能將所有的情況都搜索到。即使很著名的動(dòng)態(tài)規(guī)劃方法（它本質(zhì)上也屬于枚舉法）也會(huì)遇到“指數(shù)爆炸”的問題，它對(duì)于中等規(guī)模和適度復(fù)雜性的問題，也常常無能為力。隨機(jī)鑒于上述兩種尋優(yōu)方法的嚴(yán)重缺陷，隨機(jī)搜索算法受到人們的青睞。隨機(jī)搜索通過在搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最好結(jié)果，出于效率的考慮，搜索到一定程度便終止。然而所得結(jié)果一般尚不是最優(yōu)值。本質(zhì)上，隨機(jī)搜索仍然是一種枚舉法。遺傳算法雖然也用到了隨機(jī)技術(shù)，但它不同于上述的隨機(jī)搜索。它通過對(duì)參數(shù)空間編碼并用隨機(jī)選擇作為工具來引導(dǎo)搜索過程想著更高效的方向發(fā)展。因此，隨機(jī)搜索并不一定意味著是一種無序的搜索。優(yōu)勢(shì)總的來說，遺傳算法與其他尋優(yōu)算法相比的主要特點(diǎn)可以歸納如下：1)遺傳算法是對(duì)參數(shù)的編碼進(jìn)行操作，而不是對(duì)參數(shù)本身。2）遺傳算法是從許多初始點(diǎn)開始并行操作，而不是從一個(gè)點(diǎn)開始。因而可以有效地防止搜索過程收斂于局部最優(yōu)解，而且有較大可能求得全部最優(yōu)解。3）遺傳算法通過目標(biāo)函數(shù)來計(jì)算適配度，而不要求其他的推導(dǎo)和附屬信息，從而對(duì)問題的依賴性較小。4）遺傳算法使用概率的轉(zhuǎn)變?cè)瓌t，而不是確定性原則。5）遺傳算法在解空間內(nèi)不是盲目地窮舉或完全隨機(jī)測(cè)試，而是一種啟發(fā)式搜索，其搜索效率往往優(yōu)于其他算法。6）遺傳算法對(duì)于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，更不要求可微；既可以是數(shù)學(xué)解析式所表達(dá)的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)等隱函數(shù)，因而應(yīng)用范圍很廣。7）遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。6.2遺傳算法的基本操作與模式理論下面通過一個(gè)簡(jiǎn)單的例子，詳細(xì)描述遺傳算法的基本操作過程，然后給出簡(jiǎn)要的理論分析，從而清晰地展現(xiàn)遺傳算法的原理和特點(diǎn)。6.2.1遺傳算法的基本操作例：設(shè)需要求解的優(yōu)化問題為當(dāng)自變量x在0~31之間取整數(shù)值時(shí)尋找f(x)=x^2函數(shù)的最大值。枚舉的方法是將x取盡所有可能值，觀察能否得到最高的目標(biāo)函數(shù)值。盡管對(duì)如此簡(jiǎn)單的問題該法是可靠的，但這是一種效率很低的方法。下面運(yùn)用遺傳算法來求解這個(gè)問題。編碼遺傳算法的第一步是先進(jìn)行必要的準(zhǔn)備工作，包括“染色體”串的編碼和初始種群的產(chǎn)生。首先要將x編碼為有限長(zhǎng)度的“染色體”串。編碼的方法很多，這里僅舉一種簡(jiǎn)單易行的方法。針對(duì)本例中自變量的定義域，可以考慮采用二進(jìn)制數(shù)來對(duì)其進(jìn)行編碼，這里恰好可用5位數(shù)來表示。例如01010對(duì)應(yīng)x=10，11111對(duì)應(yīng)x=31.許多其他的優(yōu)化方法是從定義域空間的某個(gè)單個(gè)點(diǎn)出發(fā)來求解問題，并且根據(jù)某些規(guī)則，它相當(dāng)于按照一定的路線，進(jìn)行點(diǎn)到點(diǎn)的順序搜索，這對(duì)于多峰值問題的求解很容易陷入局部極值。而遺傳算法則是從一個(gè)種群（由若干個(gè)“染色體”串組成，每個(gè)串對(duì)應(yīng)一個(gè)自變量值）開始，不斷地產(chǎn)生和測(cè)試新一代的種群。這種方法一開始便擴(kuò)大了搜索的范圍，因而可期望較快地完成問題的求解。生成串初始種群的生成往往是隨機(jī)產(chǎn)生。對(duì)于本例，若設(shè)種群大小為4，即含有4個(gè)個(gè)體，則需按位隨機(jī)生成4個(gè)5位二進(jìn)制數(shù)串。例如可以通過擲硬幣的方法來生成隨機(jī)地二進(jìn)制數(shù)串。若用計(jì)算機(jī)，可考慮首先產(chǎn)生0~1之間均勻分布的隨機(jī)數(shù)，然后規(guī)定產(chǎn)生的隨機(jī)數(shù)在0~0.5之間代表0，0.5~1之間代表1.若用上述方法，隨機(jī)生成如下4個(gè)串：01101、11000、01000、10011，這樣便完成了遺傳算法的準(zhǔn)備工作。互動(dòng)現(xiàn)在請(qǐng)大家在紙上計(jì)算出剛才生成的4個(gè)串01101、11000、01000、10011對(duì)應(yīng)的x值以及代入到目標(biāo)函數(shù)所得到的值6.2.1.1復(fù)制操作復(fù)制操作也稱再生或選擇,復(fù)制過程是個(gè)體串按照它們的適配度進(jìn)行復(fù)制.本例中目標(biāo)函數(shù)值即可用作適配度.問題2:如何理解”適配度”?適配度其實(shí)適配度我們完全可以這樣理解：直觀的看，可以將目標(biāo)函數(shù)考慮對(duì)“功效、得率”等的量度。其值越大，越符合解決問題的需要。簡(jiǎn)單的說，適配度表示與最優(yōu)解的接近程度。按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會(huì)提供一個(gè)或多個(gè)子孫。這個(gè)操作步驟主要是模仿自然選擇現(xiàn)象，將達(dá)爾文的適者生存理論運(yùn)用于串的復(fù)制。此時(shí)，適配度相當(dāng)于自然界中的一個(gè)生物為了生存所具備的各項(xiàng)能力的大小，它決定了該串是被復(fù)制還是被淘汰。本例種群的初始串及對(duì)應(yīng)的適配度如表1所示。表1種群的初始串及對(duì)應(yīng)的適配度序號(hào)串x值適配度比重期望復(fù)制實(shí)際值 數(shù)

1 01101 13 169 14.4 0.58 12 11000 24 576 49.2 1.97 23 01000 8 64 5.5 0.22 04 10011 19 361 30.9 1.23 1

總計(jì) 1170100.04.00 4

平均 293 25.0 1.00 1

最大值 576 49.01.97 2復(fù)制操作可以通過隨機(jī)方法來實(shí)現(xiàn)。如果用計(jì)算機(jī)來實(shí)現(xiàn)，可考慮首先產(chǎn)生0~1之間均勻分布的隨機(jī)數(shù)，若某串的復(fù)制概率40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0~0.4之間時(shí)該串被復(fù)制，否則該串被淘汰。另外一種直觀的方法是使用輪盤賭的轉(zhuǎn)盤。群體中的每個(gè)串按照其適配度占總體適配度的比例占據(jù)盤面上的一片扇區(qū)。對(duì)于本例，依表1可以繪制出復(fù)制操作的輪盤賭轉(zhuǎn)盤如圖1所示。復(fù)制過程即是4次旋轉(zhuǎn)這個(gè)經(jīng)劃分的輪盤，從而產(chǎn)生4個(gè)下一代的種群。例如對(duì)于本例，串1所占輪盤的比例為14.4%.因此每轉(zhuǎn)動(dòng)一次輪盤，結(jié)果落入串1所占區(qū)域的概率也就是0.144?？梢妼?duì)應(yīng)大的適配度的串在下一代中將有較多的子孫。當(dāng)一個(gè)串被選中進(jìn)行復(fù)制時(shí)，此串將被完整的復(fù)制，然后將復(fù)制串添入匹配池。問題3：結(jié)合復(fù)制操作我們考慮遺傳算法中的遺傳與生物界中的遺傳現(xiàn)象有何區(qū)別？區(qū)別遺傳算法中復(fù)制的是某一個(gè)串本身，而非串里面所含有的某一個(gè)優(yōu)等基因（當(dāng)然，在本例中，出現(xiàn)1的位數(shù)越高，越可以視為基因優(yōu)良，因?yàn)?的位數(shù)越高，其值越大，也就越接近最優(yōu)解）生物界中的遺傳現(xiàn)象是指基因的遺傳復(fù)制結(jié)果因此旋轉(zhuǎn)4次輪盤即可產(chǎn)生出4個(gè)串。這4個(gè)串是上一代種群的復(fù)制，有的串可能被復(fù)制一次或多次，有的可能被淘汰。本例中，經(jīng)過復(fù)制后的新的種群為01101、11000、11000、

10011，這里串1被復(fù)制了一次，串2被復(fù)制了兩次，串3被淘汰了，串4也被復(fù)制了一次問題4:顯然，復(fù)制操作的過程也是隨機(jī)的，所以我們可以考慮這樣的情況是否會(huì)發(fā)生：占最小比重的串（如本例中串3）奇跡般的存活了下來，而占比重稍大的串（如串1）反而被淘汰了？如果可能發(fā)生，可以猜想會(huì)導(dǎo)致什么后果，是否又會(huì)直接影響遺傳算法的結(jié)果呢？6.2.1.2交叉操作交叉操作操作可以分為如下兩個(gè)步驟：第一步是將新復(fù)制產(chǎn)生的匹配池中的成員隨機(jī)兩兩匹配;第二步是進(jìn)行交叉繁殖。具體過程如下：設(shè)串的長(zhǎng)度為L(zhǎng),則串的L個(gè)數(shù)字位之間的空隙標(biāo)記為1，2，…，L-1.隨機(jī)地從[1，L-1]中選取一整數(shù)位置k，則將兩個(gè)父母串中從位置k到串末尾的子串互相交換，而形成兩個(gè)新串。例如本例中初始種群的兩個(gè)個(gè)體

A1=01101A2=11000

假定從1到4間選取隨機(jī)數(shù)，得到k=4，那么經(jīng)過交叉操作之后將得到如下兩個(gè)新串

A1=01100

A2=11001

其中新串A1和A2是由老串A1和A2將第5位進(jìn)行交換得到的結(jié)果。表2歸納了該例進(jìn)行交叉操作前后的結(jié)果，從表中可以看出交叉操作的具體步驟。首先隨機(jī)地將匹配池中的個(gè)體配對(duì)，結(jié)果串1和串2配對(duì)，串3和串4配對(duì)。此外，隨機(jī)選取的交叉點(diǎn)的位置也如表2所示。結(jié)果串1（01101)和串2（11000）的交叉點(diǎn)為4，兩者只交換最后一位，從而生成兩個(gè)新串01100和11001.剩下的兩個(gè)串在交叉點(diǎn)2交叉，結(jié)果生成兩個(gè)新串11011和10000表2交叉操作前后的結(jié)果新串號(hào)匹配池匹配對(duì)象交叉點(diǎn)新種群x值適配度101101240110012144211000141100125625311000421101127729410011321000016256

總計(jì)1754

平均439

最大值729問題5：交叉操作的結(jié)果使種群發(fā)生了那些變化，這些變化有什么意義么？問題6：由于交叉操作依然是基于隨機(jī)過程之上，那么匹配的對(duì)象也就必然也是隨機(jī)地，如果匹配池中串1（01101）和串4（10011）匹配，串2（11000）和串3（11000）匹配，結(jié)果怎樣，有什么意義？6.2.1.3變異操作變異是以很小的概率隨機(jī)地改變一個(gè)串位的值。如對(duì)于二進(jìn)制串，即是將隨機(jī)選取的串位由1變?yōu)?或由0變?yōu)?.變異的概率通常是很小的，一般只有千分之幾。這個(gè)操作相對(duì)于復(fù)制和交叉操作而言，是處于相對(duì)次要的地位，其目的是為了防止丟失一些有用的遺傳因子，特別是當(dāng)種群中的個(gè)體，經(jīng)遺傳運(yùn)算可能使某些串位的值失去多樣性，從而可能失去檢驗(yàn)有用遺傳因子的機(jī)會(huì)，變異操作可以起到恢復(fù)串位多樣性的作用。對(duì)于本例，變異概率設(shè)取為0.001，則對(duì)于種群的總共20個(gè)串位，期望的變異串位數(shù)為20*0.001位=0.02位，所以本例中無串位值的改變。從表1和表2可以看出，在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。種群的平均適配度從293增至439，最大的適配度從575增至729，每經(jīng)過這樣的一次遺傳算法步驟，問題的解便朝著最優(yōu)解方向前進(jìn)了一步?？梢?，只要這個(gè)過程一直進(jìn)行下去，它將最終走向全局最優(yōu)解，而每一步的操作是非常簡(jiǎn)單的，而且對(duì)問題的依賴性很小以上就是遺傳算法的整個(gè)程序過程，經(jīng)過對(duì)遺傳算法的分析與探討，我們不難看出遺傳算法的復(fù)制操作、交叉操作和變異操作都是有意義的過程而且任何部分都不可或缺。其中：

復(fù)制過程可以看做遺傳算法求得最優(yōu)解的基礎(chǔ)

交叉過程可以看做遺傳算法求得最優(yōu)解的關(guān)鍵變異過程可以看做遺傳算法求得最優(yōu)解的保證

6.2.2遺傳算法的模式理論前面通過一個(gè)簡(jiǎn)單的例子說明了按照遺傳算法的操作步驟使得待尋優(yōu)問題的性能朝著不斷改進(jìn)的方向發(fā)展，下面將進(jìn)一步分析遺傳算法的工作機(jī)理。在上面的例子中，樣本串第1位的“1”使得適配度比較大，對(duì)于該例的函數(shù)及x的編碼方式很容易驗(yàn)證這一點(diǎn)。它說明某些子串模式在遺傳算法的運(yùn)行中起著關(guān)鍵的作用首位為“1”的子串可以表示成這樣的模式：1****，其中*是通配符，它既可代表“1”，也可代表“0”。該模式在遺傳算法的一代一代地運(yùn)行過程中不僅保留了下來，而且數(shù)量不斷增加。正式這種適配度高的模式不斷增加，才使得問題的性能不斷改進(jìn)。一般地，對(duì)于二進(jìn)制串串，在{0，1}字符串中間加入通配符“*”即可生成所有可能模式。因此用

{0，1，*}可以構(gòu)造出任意一種模式。稱一個(gè)模式與一個(gè)特定的串相匹配是指：該模式中的1與串中的1相匹配，模式中的0與串中的0相匹配，模式中的*可以匹配串中的0或1.舉例例如模式00*00匹配兩個(gè)串

{00000，00100}，模式*11*0匹配4個(gè)串

{01100，01110，11100，11110}?？梢钥闯?，定義模式的好處是較容易描述串的相似性對(duì)于前面例子中的5位字串，由于模式的每一位可取0、1、*，因此總共有3^5=243種模式。對(duì)于一般的問題，若串的基為k，長(zhǎng)度為l，則總共有（k+1)^l中模式，可見模式的數(shù)量要大于串的數(shù)量k^l。一般地，一個(gè)串中包含2^l種模式。例如串11