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

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

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

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

總計 1170100.04.00 4

平均 293 25.0 1.00 1

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

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

A1=01101A2=11000

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

A1=01100

A2=11001

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

總計1754

平均439

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

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

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

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

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

{00000，00100}，模式*11*0匹配4個串

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