智能控制理論和方法-10遺傳算法的基本原理

1、遺傳算法簡(jiǎn)稱GA（Genetic Algorithms）是1962年由美國(guó)Michigan大學(xué)的Holland教授提出的模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。 遺傳算法是以達(dá)爾文的自然選擇學(xué)說(shuō)為基礎(chǔ)發(fā)展起來(lái)的。自然選擇學(xué)說(shuō)包括以下三個(gè)方面：,第10章 遺傳算法,10.1 遺傳算法的基本原理,（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個(gè)特征，物種

2、才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個(gè)體之間的差異，稱為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭(zhēng)和適者生存：具有適應(yīng)性變異的個(gè)體被保留下來(lái)，不具有適應(yīng)性變異的個(gè)體被淘汰，通過(guò)一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。,遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過(guò)遺傳中的復(fù)制、交叉及變異對(duì)個(gè)體

3、進(jìn)行篩選，使適適應(yīng)度高的個(gè)體被保留下來(lái)，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡(jiǎn)單，可并行處理，并能到全局最優(yōu)解。,遺傳算法的基本操作為：（1）復(fù)制（Reproduction Operator） 復(fù)制是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過(guò)程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。 復(fù)制操作可以通過(guò)隨機(jī)方

4、法來(lái)實(shí)現(xiàn)。首先產(chǎn)生0~1之間均勻分布的隨機(jī)數(shù)，若某串的復(fù)制概率為40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0.40~1.0之間時(shí)，該串被復(fù)制，否則被淘汰。,（2）交叉（Crossover Operator） 復(fù)制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進(jìn)化過(guò)程中的繁殖現(xiàn)象，通過(guò)兩個(gè)染色體的交換組合，來(lái)產(chǎn)生新的優(yōu)良品種。 交叉的過(guò)程為：在匹配池中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換點(diǎn)位置；交換雙親染色體交換點(diǎn)右邊

5、的部分，即可得到兩個(gè)新的染色體數(shù)字串。,交叉體現(xiàn)了自然界中信息交換的思想。交叉有一點(diǎn)交叉、多點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉。一點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，例：,（3）變異(Mutation Operator) 變異運(yùn)算用來(lái)模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號(hào)串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體

6、的某一個(gè)基因由1變?yōu)?，或由0變?yōu)?。,若只有選擇和交叉，而沒(méi)有變異，則無(wú)法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過(guò)程在早期就陷入局部解而進(jìn)入終止過(guò)程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。,10.2 遺傳算法的特點(diǎn),（1）遺傳算法是對(duì)參數(shù)的編碼進(jìn)行操作，而非對(duì)參數(shù)本身，這就是使得我們?cè)趦?yōu)化計(jì)算過(guò)程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化等機(jī)理；（2）遺傳算法同時(shí)

7、使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的迭代搜索過(guò)程，單個(gè)搜索點(diǎn)所提供的信息不多，搜索效率不高，有時(shí)甚至使搜索過(guò)程局限于局部最優(yōu)解而停滯不前。,遺傳算法從由很多個(gè)體組成的一個(gè)初始群體開(kāi)始最優(yōu)解的搜索過(guò)程，而不是從一個(gè)單一的個(gè)體開(kāi)始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標(biāo)函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且需要目標(biāo)函數(shù)的導(dǎo)

8、數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來(lái)的適應(yīng)度函數(shù)值，就可以確定進(jìn)一步的搜索方向和搜索范圍，無(wú)需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。,遺傳算法可應(yīng)用于目標(biāo)函數(shù)無(wú)法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問(wèn)題，以及組合優(yōu)化問(wèn)題等。（4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉、變異等運(yùn)算都是以一種概率的方式來(lái)進(jìn)行的，因而遺傳算法的搜索過(guò)程具有很好的靈活性。隨著進(jìn)化過(guò)程的進(jìn)行，遺傳算法新的群體會(huì)更多地產(chǎn)生出許多新的

9、優(yōu)良的個(gè)體。,（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索；（6）遺傳算法對(duì)于待尋優(yōu)的函數(shù)基本無(wú)限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因而應(yīng)用范圍較廣；（7）遺傳算法具有并行計(jì)算的特點(diǎn)，因而可通過(guò)大規(guī)模并行計(jì)算來(lái)提高計(jì)算速度，適合大規(guī)模復(fù)雜問(wèn)題的優(yōu)化。,10.3 遺傳算法的發(fā)展及應(yīng)用10.3.1 遺傳算法的發(fā)展,遺傳算法起

10、源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。早在20世紀(jì)40年代，就有學(xué)者開(kāi)始研究如何利用計(jì)算機(jī)進(jìn)行生物模擬的技術(shù)，他們從生物學(xué)的角度進(jìn)行了生物的進(jìn)化過(guò)程模擬、遺傳過(guò)程模擬等研究工作。進(jìn)入20世紀(jì)60年代，美國(guó)密歇根大學(xué)的Holland教授及其學(xué)生們受到這種生物模擬技術(shù)的啟發(fā)，創(chuàng)造出一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的自適應(yīng)概率優(yōu)化技術(shù)—遺傳算法。,以下是在遺傳算法發(fā)展進(jìn)程中一些關(guān)鍵人物所做出的主要貢獻(xiàn)：（1）J.H.Hol

11、land 20世紀(jì)70年代初，Holland教授提出了遺傳算法的基本定理—模式定理，從而奠定了遺傳算法的理論基礎(chǔ)。模式定理揭示了群體中優(yōu)良個(gè)體（較好的模式）的樣本數(shù)將以指數(shù)級(jí)規(guī)律增長(zhǎng)，從理論上保證了遺傳算法用于尋求最優(yōu)可行解的優(yōu)化過(guò)程。1975年，Holland出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專(zhuān)著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性》。20世紀(jì)80年代，Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)

12、習(xí)系統(tǒng)—分類(lèi)器系統(tǒng)，開(kāi)創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。,（3）K.A.De Jong 1975年，De Jong博士在其博士論文中結(jié)合模式定理進(jìn)行了大量純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹(shù)立了遺傳算法的工作框架。他推薦了在大多數(shù)優(yōu)化問(wèn)題中都較適用的遺傳算法的參數(shù)，建立了著名的De Jong五函數(shù)測(cè)試平臺(tái)，定義了評(píng)價(jià)遺傳算法性能的在線指標(biāo)和離線指標(biāo)。（4）D.J.Goldberg 1989年，G

13、oldberg出版了專(zhuān)著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》，該書(shū)全面地論述了遺傳算法的基本原理及其應(yīng)用，奠定了現(xiàn)代遺傳算法的科學(xué)基礎(chǔ)。,（2）J.D.Bagley 1967年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，并發(fā)表了遺傳算法應(yīng)用方面的第一篇論文。他發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個(gè)體編碼上使用了雙倍體的編碼方法。在遺傳算法的不同階段采用了不同的概率，從

14、而創(chuàng)立了自適應(yīng)遺傳算法的概念。,（5）L.Davis 1991年，Davis編輯出版了《遺傳算法手冊(cè)》一書(shū)，為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。（6）J.R.Koza 1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程的概念，并成功地將遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)和符號(hào)處理等方面。,10.3.1 遺傳算法的應(yīng)用（1）函數(shù)優(yōu)化。

15、 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。尤其是對(duì)非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。（2）組合優(yōu)化。 隨著問(wèn)題的增大，組合優(yōu)化問(wèn)題的搜索空間也急劇擴(kuò)大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等方面得到成功的應(yīng)用。,（3）生產(chǎn)調(diào)度問(wèn)題

16、 在很多情況下，采用建立數(shù)學(xué)模型的方法難以對(duì)生產(chǎn)調(diào)度問(wèn)題進(jìn)行精確求解。在現(xiàn)實(shí)生產(chǎn)中多采用一些經(jīng)驗(yàn)進(jìn)行調(diào)度。遺傳算法是解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車(chē)間調(diào)度、流水線生產(chǎn)車(chē)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。,（4）自動(dòng)控制。 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已經(jīng)在其中得到了初步的應(yīng)用。例如，利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參

17、數(shù)辨識(shí)、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等。,（5）機(jī)器人 例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理 遺傳算法可用于圖像處理過(guò)程中的掃描、特征提取、圖像分割等的優(yōu)化計(jì)算。目前遺傳算法已經(jīng)在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。,（7）人工生命 人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的

18、具有生物系統(tǒng)特有行為的人造系統(tǒng)。人工生命與遺傳算法有著密切的聯(lián)系，基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。遺傳算法為人工生命的研究提供了一個(gè)有效的工具。（8）遺傳編程 遺傳算法已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域的編程。,（9）機(jī)器學(xué)習(xí) 基于遺傳算法的機(jī)器學(xué)習(xí)在很多領(lǐng)域都得到了應(yīng)用。例如，采用遺傳算法實(shí)現(xiàn)模糊控制規(guī)則的優(yōu)化，可以改進(jìn)模糊系統(tǒng)的性能；遺傳算法可用于神經(jīng)網(wǎng)絡(luò)連

19、接權(quán)的調(diào)整和結(jié)構(gòu)的優(yōu)化；采用遺傳算法設(shè)計(jì)的分類(lèi)器系統(tǒng)可用于學(xué)習(xí)式多機(jī)器人路徑規(guī)劃。,10.4.1 遺傳算法的構(gòu)成要素（1）染色體編碼方法 基本遺傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)來(lái)表示群體中的個(gè)體，其等位基因是由二值符號(hào)集{0,1}所組成。初始個(gè)體基因值可用均勻分布的隨機(jī)值生成，如就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是18。,10.4 遺傳算法的優(yōu)化設(shè)計(jì),（2）個(gè)體適應(yīng)度評(píng)價(jià)：基本遺傳算法與個(gè)體適應(yīng)度成正比的概率

20、來(lái)決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的概率多少。為正確計(jì)算這個(gè)概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。因此，必須先確定由目標(biāo)函數(shù)值J到個(gè)體適應(yīng)度f(wàn)之間的轉(zhuǎn)換規(guī)則。,（3）遺傳算子：基本遺傳算法使用下述三種遺傳算子： ① 選擇運(yùn)算:使用比例選擇算子； ② 交叉運(yùn)算:使用單點(diǎn)交叉算子； ③ 變異運(yùn)算:使用基本位變異算子或均勻變異算子。,（4）基本遺傳算法的運(yùn)行參數(shù) 有下述4個(gè)運(yùn)行參數(shù)需要

21、提前設(shè)定： M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20~100； G：遺傳算法的終止進(jìn)化代數(shù)，一般取為100~500； Pc：交叉概率，一般取為0.4~0.99； Pm：變異概率，一般取為0.0001~0.1。,對(duì)于一個(gè)需要進(jìn)行優(yōu)化的實(shí)際問(wèn)題，一般可按下述步驟構(gòu)造遺傳算法： 第一步：確定決策變量及各種約束條件，即確定出個(gè)體的表現(xiàn)型X和問(wèn)題的解空間；

22、 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類(lèi)型及數(shù)學(xué)描述形式或量化方法； 第三步：確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型x及遺傳算法的搜索空間；,10.4.2 遺傳算法的應(yīng)用步驟,,第四步：確定解碼方法，即確定出由個(gè)體基因型x到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法； 第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則； 第六步：設(shè)計(jì)遺

23、傳算子，即確定選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即M,G,Pc,Pm等參數(shù)。,以上操作過(guò)程可以用圖10-1來(lái)表示。,,圖10-1 遺傳算法流程圖,利用遺傳算法求Rosenbrock函數(shù)的極大值,10.5 遺傳算法求函數(shù)極值,10.5.1 二進(jìn)制編碼遺傳算法求函數(shù)極大值 求解該問(wèn)題遺傳算法的構(gòu)造過(guò)程： （1）確定決策變量和約束條件

24、； （2）建立優(yōu)化模型； （3）確定編碼方法,用長(zhǎng)度為10位的二進(jìn)制編碼串來(lái)分別表示兩個(gè)決策變量x1,x2。10位二進(jìn)制編碼串可以表示從0到1023之間的1024個(gè)不同的數(shù)，故將x1,x2的定義域離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。 從離散點(diǎn)-2.048到離散點(diǎn)2.048 ，分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編

25、碼。,將x1,x2分別表示的兩個(gè)10位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對(duì)應(yīng)的關(guān)系。 例如： 表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10位表示x2。,（4）確定解碼方法：解碼時(shí)

26、需要將20位長(zhǎng)的二進(jìn)制編碼串切斷為兩個(gè)10位長(zhǎng)的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。 依據(jù)個(gè)體編碼方法和對(duì)定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為 例如，對(duì)個(gè)體,它由兩個(gè)代碼所組成 上述兩個(gè)代碼經(jīng)過(guò)解碼后，可得到兩個(gè)實(shí)際的值（5）確定個(gè)體評(píng)價(jià)方法：由于Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故可將個(gè)體的適應(yīng)

27、度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即,選個(gè)體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù) （6）設(shè)計(jì)遺傳算子：選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變異算子。 （7）確定遺傳算法的運(yùn)行參數(shù)：群體大小M=80，終止進(jìn)化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。 上述七個(gè)步驟構(gòu)成了用于求函數(shù)極大值的優(yōu)化計(jì)算基本遺傳算法。,采用上述方法進(jìn)行仿真，經(jīng)過(guò)100步迭代，最佳樣本

28、為即當(dāng) 時(shí)，Rosenbrock函數(shù)具有極大值，極大值為3905.9。 仿真程序：chap5_1.m,遺傳算法的優(yōu)化過(guò)程是目標(biāo)函數(shù)J和適應(yīng)度函數(shù)F的變化過(guò)程。 由仿真結(jié)果可知，隨著進(jìn)化過(guò)程的進(jìn)行，群體中適應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體會(huì)越來(lái)越多，并且它們都集中在所求問(wèn)題的最優(yōu)點(diǎn)附近，從而

29、搜索到問(wèn)題的最優(yōu)解。,10.5.2 實(shí)數(shù)編碼遺傳算法求函數(shù)極大值 求解該問(wèn)題遺傳算法的構(gòu)造過(guò)程：（1）確定決策變量和約束條件；（2）建立優(yōu)化模型；（3）確定編碼方法：用2個(gè)實(shí)數(shù)分別表示兩個(gè)決策變量，分別將的定義域離散化為從離散點(diǎn)-2.048到離散點(diǎn)2.048的Size個(gè)實(shí)數(shù)。,（4）確定個(gè)體評(píng)價(jià)方法： 個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即 選個(gè)體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù),（5）設(shè)計(jì)遺傳算子：選擇運(yùn)算使

30、用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變異算子。（6）確定遺傳算法的運(yùn)行參數(shù)：群體大小M=500，終止進(jìn)化代數(shù)G=200，交叉概率Pc=0.90，采用自適應(yīng)變異概率即變異概率與適應(yīng)度有關(guān)，適應(yīng)度越小，變異概率越大。,上述六個(gè)步驟構(gòu)成了用于求函數(shù)Rosenbrock極大值的優(yōu)化計(jì)算的實(shí)數(shù)編碼遺傳算法。 十進(jìn)制編碼求函數(shù)Rosenbrock極大值。仿真程序見(jiàn)chap10_2.m。 仿真程序經(jīng)過(guò)200步迭代

31、，最佳樣本為即當(dāng) ， 時(shí)，函數(shù)具有極大值，極大值為3880.3。,10.6 基于遺傳算法優(yōu)化的RBF網(wǎng)絡(luò)逼近,10.6.1 遺傳算法優(yōu)化原理 在7.3節(jié)的RBF網(wǎng)絡(luò)逼近算法中，網(wǎng)絡(luò)權(quán)值、高斯函數(shù)的中心矢量和基寬向量的初值難以確定，如果這些參數(shù)選擇不當(dāng)，會(huì)造成逼近精度的下降甚至RBF網(wǎng)絡(luò)的發(fā)散。采用遺傳算法可實(shí)現(xiàn)RBF網(wǎng)絡(luò)參數(shù)的優(yōu)化。,為獲取滿意的逼近精度，采用誤差絕對(duì)值指標(biāo)作為

32、參數(shù)選擇的最小目標(biāo)函數(shù)。 式中， 為逼近的總步驟， 為第 步RBF網(wǎng)絡(luò)的逼近誤差。 在應(yīng)用遺傳算法時(shí)，為了避免參數(shù)選取范圍過(guò)大，可以先按經(jīng)驗(yàn)選取一組參數(shù)，然后再在這組參數(shù)的周?chē)眠z傳算法進(jìn)行設(shè)計(jì)，從而大大減少初始尋優(yōu)的盲目性，節(jié)約計(jì)算量。,10.6.2 仿真實(shí)例 使用RBF網(wǎng)絡(luò)逼近下列對(duì)象：,在RBF網(wǎng)絡(luò)中，網(wǎng)絡(luò)輸入信號(hào)為2個(gè)，即和

33、 ，網(wǎng)絡(luò)初始權(quán)值及高斯函數(shù)參數(shù)初始值通過(guò)遺傳算法優(yōu)化而得。,遺傳算法優(yōu)化程序?yàn)閏hap10_3a.m，取逼近總步驟為，每一步的逼近誤差由chap10_3b.m求得。采用二進(jìn)制編碼方式，用長(zhǎng)度為10位的二進(jìn)制編碼串來(lái)分別表示向量b、c和w中的每個(gè)值。,遺傳算法優(yōu)化中，取樣本個(gè)數(shù)為Size=30，交叉概率為Pc=0.60，采用自適應(yīng)變異概率，即適應(yīng)度越小，變異概率越大，取變異概率為 取用于優(yōu)化的RBF網(wǎng)絡(luò)結(jié)構(gòu)為2-3-

34、1，網(wǎng)絡(luò)權(quán)值wj的取值范圍為[-1,+1]，高斯函數(shù)基寬向量的取值范圍為[0.1,3.0]，高斯函數(shù)中心矢量的取值范圍為[-3,+3]。取則共有12個(gè)參數(shù)需要優(yōu)化。,,經(jīng)過(guò)150代遺傳算法進(jìn)化，優(yōu)化后的結(jié)果為： p=[2.7732，2.6343，2.2630，1.8680， -0.0616，-0.7126，-0.3959，2.2669， -1.4047，-0.3099，0.7478，-0.3353]。 則R

35、BF網(wǎng)絡(luò)高斯基函數(shù)參數(shù)的初始值及權(quán)值的初始值為:,RBF網(wǎng)絡(luò)遺傳算法優(yōu)化程序包括三部分，即遺傳算法優(yōu)化程序chap10_3a.m、RBF網(wǎng)絡(luò)逼近函數(shù)程序chap10_3b.m和RBF網(wǎng)絡(luò)逼近測(cè)試程序chap10_3c.m。,10.8 基于遺傳算法的TSP問(wèn)題優(yōu)化 在第8.5節(jié)已經(jīng)對(duì)旅行商問(wèn)題進(jìn)行了描述。遺傳算法由于其全局搜索的特點(diǎn)，在解決TSP問(wèn)題中有明顯的優(yōu)勢(shì)。 10.8.1 TSP問(wèn)題的編碼

36、 設(shè) 是由城市i和城市j之間的距離組成的距離矩陣，旅行商問(wèn)題就是求出一條通過(guò)所有城市且每個(gè)城市只通過(guò)一次的具有最短距離的回路。,,在旅行商問(wèn)題的各種求解方法中，描述旅行路線的方法主要有如下兩種：（1）巡回旅行路線經(jīng)過(guò)的連接兩個(gè)城市的路線的順序排列；（2）巡回旅行路線所經(jīng)過(guò)的各個(gè)城市的順序排列。大多數(shù)求解旅行商問(wèn)題的遺傳算法是以后者為描述方法的，它們大多采用所遍歷城市的順序來(lái)表示各個(gè)個(gè)體的編碼串，其等位基

37、因?yàn)镹個(gè)整數(shù)值或N個(gè)記號(hào)。 以城市的遍歷次序作為遺傳算法的編碼，目標(biāo)函數(shù)取路徑長(zhǎng)度。在群體初始化、交叉操作和變異操作中考慮TSP問(wèn)題的合法性約束條件（即對(duì)所有的城市做到不重不漏）。,10.8.2 TSP問(wèn)題的遺傳算法設(shè)計(jì) 采用遺傳算法進(jìn)行路徑優(yōu)化，分為以下幾步： 第一步：參數(shù)編碼和初始群體設(shè)定 一般來(lái)說(shuō)遺傳算法對(duì)解空間的編碼大多采用二進(jìn)制編碼形式，但對(duì)于TSP一類(lèi)

38、排序問(wèn)題，采用對(duì)訪問(wèn)城市序列進(jìn)行排列組合的方法編碼，即某個(gè)巡回路徑的染色體個(gè)體是該巡回路徑的城市序列。 針對(duì)TSP問(wèn)題，編碼規(guī)則通常是N取進(jìn)制編碼，即每個(gè)基因僅從1到N的整數(shù)里面取一個(gè)值，每個(gè)個(gè)體的長(zhǎng)度為N，N為城市總數(shù)。定義一個(gè)s行t列的pop矩陣來(lái)表示群體，t為城市個(gè)數(shù)N+1，即N+1，s為樣本中個(gè)體數(shù)目。針對(duì)30個(gè)城市的TSP問(wèn)題，t取值31，,即矩陣每一行的前30個(gè)元素表示經(jīng)過(guò)的城市編號(hào)，最后一個(gè)元素表示經(jīng)過(guò)

39、這些城市要走的距離。 參數(shù)編碼和初始群體設(shè)定程序?yàn)椋?pop=zeros(s,t); for i=1:s pop(i,1:t-1)=randperm(t-1); end 第二步：計(jì)算路徑長(zhǎng)度的函數(shù)設(shè)計(jì) 在TSP的求解中，用距離的總和作為適應(yīng)度函數(shù)，來(lái)衡量求解結(jié)果是否最優(yōu)。將POP矩陣中每一

40、行表示經(jīng)過(guò)的距離的最后一個(gè)元素作為路徑長(zhǎng)度。,兩個(gè)城市m和n間的距離為： 用于計(jì)算路徑長(zhǎng)度的程序?yàn)閏hap10_1dis.m。 通過(guò)樣本的路徑長(zhǎng)度可以得到目標(biāo)函數(shù)和自適應(yīng)度函數(shù)。根據(jù)t的定義，兩兩城市組合數(shù)共有t-2組，則目標(biāo)函數(shù)為：自適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)，即：

41、 （10.18）,,,,第三步：計(jì)算選擇算子 選擇就是從群體中選擇優(yōu)勝個(gè)體、淘汰劣質(zhì)個(gè)體的操作，它是建立在群體中個(gè)體適應(yīng)度評(píng)估基礎(chǔ)上。仿真中采用最優(yōu)保存方法，即將群體中適應(yīng)度最大的c個(gè)個(gè)體直接替換適應(yīng)度最小的c個(gè)個(gè)體。選擇算子函數(shù)為chap10_7select.m。仿真中，取 。 第四步：計(jì)算交叉算子 交叉算子在遺傳算法中起著核心的作用，

42、它是指將個(gè)體進(jìn)行兩兩配對(duì)，并以交叉概率將配對(duì)的父代個(gè)體加以替換重組而生成新個(gè)體的操作。仿真中，取 。有序交叉法實(shí)現(xiàn)的步驟是:,,,有序交叉法實(shí)現(xiàn)的步驟是:步驟 1 隨機(jī)選取兩個(gè)交叉點(diǎn)crosspoint(1)和crosspoint(2)；步驟 2 兩后代先分別按對(duì)應(yīng)位置復(fù)制雙親X1和X2匹配段中的兩個(gè)子串A1和B1；步驟 3 在對(duì)應(yīng)位置交換雙親匹配段以外的城市，如果交換后，后代X1中的某一城市a與子串中

43、A1的城市重復(fù)，則將該城市取代子串B1與A1中的城市a具有相同位置的新城市，直到與子串A1中的城市均不重復(fù)為止，對(duì)后代X2也采用同樣方法，如圖10-15所示：,圖10-15 有序交叉算子 從圖10-15可知，有序交叉算子能夠有效地繼承雙親的部分基因成分，達(dá)到了進(jìn)化過(guò)程中的遺傳功能，使該算法并不是盲目搜索，而是趨向于使群體具有更多的優(yōu)良基因，最后實(shí)現(xiàn)尋優(yōu)的目的。交叉算子函數(shù)為chap10_7corss.m,第五步：計(jì)算變異

44、算子 變異操作是以變異概率 對(duì)群體中個(gè)體串某些基因位上的基因值作變動(dòng)，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則，仍保留父代染色體。仿真中，取 。 這里采用倒置變異法：假設(shè)當(dāng)前個(gè)體X為(1 3 7 4 8 0 5 9 6 2 )，如果當(dāng)前隨機(jī)概率值< ，則隨機(jī)選擇來(lái)自同一個(gè)體的兩個(gè)點(diǎn)mutatepoint(1)和mutatepoint(

45、2)，然后倒置該兩個(gè)點(diǎn)的中間部分，產(chǎn)生新的個(gè)體。例如，假設(shè)隨機(jī)選擇個(gè)體X的兩個(gè)點(diǎn)“7”和“9”，則倒置該兩個(gè)點(diǎn)的中間部分，即將“4805”變?yōu)椤?084”，產(chǎn)生新的個(gè)體X為(1 3 7 5 0 8 4 9 6 2)。變異算子函數(shù)為chap10_7mutate.m。,,,,10.8.3 仿真實(shí)例 以8個(gè)城市的路徑優(yōu)化為例，其城市路徑坐標(biāo)保存在路徑e:\ljkmb\的程序cities8.txt中。遺傳算法參數(shù)設(shè)定為：群

46、體中個(gè)體數(shù)目 ，交叉概率 ，變異概率 。通過(guò)改變進(jìn)化代數(shù)為K，觀察不同進(jìn)化代數(shù)下路徑的優(yōu)化情況，仿真結(jié)果見(jiàn)圖10-16和圖10-17所示，經(jīng)過(guò)1000次進(jìn)化，城市組合路徑達(dá)到最小。最短路程為2.8937 仿真過(guò)程表明，在20次仿真實(shí)驗(yàn)中，有15次可收斂到最優(yōu)解。,,,,圖10-16 進(jìn)化代次數(shù)為300時(shí)的軌跡，距離L= 3.4173,圖10-17 進(jìn)化代次