【正文】 遺傳算法的模式定理 遺傳算法的基礎(chǔ)理論是圖式定理。例如： x x0 x x 1H ? 是一個圖式。圖式中 第 1 位數(shù)字和最后位數(shù)字間的距離稱為圖式的長度，并用 )(H? 表示。 常州工學(xué)院畢業(yè)設(shè)計論文 13 (3)Holland 圖式定理 低階，短長度的圖式在群體遺傳過程中將會按指數(shù)規(guī)律增加。 遺傳算法這種處理能力稱為隱含并行性 (Implicit Parallelism)。 Holland 首先用模式定理解釋了遺傳算法的搜索行為，從而在一定程度上奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)。 模式是描述種群中任意編碼 (染色體 )之間相似 性的一組符號串，由 0， 1和通配符 ‘ *’ 任意組合而成。遺傳算法正是利用種群中包含的眾多模式及其染色體符號串之間的相似性信息進(jìn)行啟發(fā)式搜索和求解問 題的。種群中定義長度短、確定位數(shù)少和適應(yīng)度高的模式為組塊， GA 的運(yùn)算實際上是對組塊的操作。 許多學(xué)者對模式理論進(jìn)行了推廣和改進(jìn)， Bertoni 和 Dorigo 給出了處理有效模式的表達(dá)式，指出每代遺傳會產(chǎn)生多少新模式是衡量遺傳算法的一個重要因素；惲為民和席裕庚給出了每代至少產(chǎn)生新模式的表達(dá)式。 標(biāo)準(zhǔn)遺傳算法的結(jié)構(gòu)、特點和應(yīng) 用關(guān)鍵 遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。 在遺傳算法中 ,上述幾個特征以一種特殊的方式組合在一起：遺傳算法基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。 遺傳算法將問題的求解表示成“染色體”，一般用二進(jìn)制 碼串表示，解的特定集合稱為“種群”，解中的變量稱為“基因”。這樣一代一代不斷進(jìn)化，最后收斂到一個最適應(yīng)環(huán)境的個體上，從而求得問題的最優(yōu)解。適應(yīng)值度量為群體中可能的確定長度的 字符串指定一個適應(yīng)值，它通常是問題本身所包含的，適應(yīng)值函數(shù)必須有能力計 算搜索空間中每個確定長度的特征串的適應(yīng)值 。停止準(zhǔn)則有兩種 :輸出解達(dá)到滿意程度或進(jìn)化已達(dá)到指定最大代數(shù)。遺傳算法的一般過程可以分為初始化、選擇、交叉和變異四個組成部分。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實現(xiàn)并行化。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。 (4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。遺傳算法利用進(jìn)化過程獲得的信息自 行組織搜索時，硬度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。一般把問題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。 2．適應(yīng)函數(shù)的確定 適應(yīng)函數(shù) (fitness function)也稱對象函數(shù) (object function)，這是問題求解品質(zhì)的測量函數(shù)；往往也稱為問題的“環(huán)境”。 3．遺傳 算法自身參數(shù)設(shè)定 遺傳算法自身參數(shù)有 3個，即群體大小 n、交叉概率 cP 和 變異概率 mP 。一般 6030n ?? 。一般取 ??cP 。一般取 ~?mP 。 常州工學(xué)院畢業(yè)設(shè)計論文 17 第 4 章 基于遺傳算法的 PID 參數(shù)整定 Matlab 簡介 Matlab 是一種開放式軟件，經(jīng)過一定的程序可以將開發(fā)的優(yōu)秀的應(yīng)用程序集加入到 Matlab 工具的行列。這樣，許多領(lǐng)域前沿的研究者和科學(xué)家都可以將自己的成果集成到 Matlab 中，被全人類繼承和利用。例如：信號處理工具箱、圖象處理工具箱、通信處理工具箱、優(yōu)化 工具箱、遺傳算法工具箱等，而且這些工具箱還在不斷的擴(kuò)展中。它語法規(guī)則簡單，貼近人的思維方式，用它編程可以直接調(diào)用所需庫函數(shù)，編程效率高，程序簡練，猶如在一張演算紙上排列公式和求解問題，因此被稱為“演算紙式”的科學(xué)工程算法語言。在 Matlab 環(huán)境中，有超過 500 種的數(shù)學(xué)、統(tǒng)計、科學(xué)及工程方面的函數(shù)可供使用，而且使用簡單快捷。 。研究人員在完成科學(xué)性或工程性文章時，可以用 Matlab 制作高質(zhì)量的圖形，從而寫出圖文并茂的文章。除了內(nèi)部函數(shù)外，所有 Matlab 主包文件和各工具包都是可讀可改的源文件 ，用戶可以檢查算法、修改現(xiàn)有函數(shù)，甚至加入自己的函數(shù)、構(gòu)成新的工具包，使 Matlab 擁有適合用戶的環(huán)境。由于 Matlab 的開放性，許多領(lǐng)域的專家都為 Matlab 編寫了各種程序工具箱。 Matlab 主要由 Matlab 主程序、 Matlab 工具箱 (Toolbox)和 SIMULINK 動態(tài)系統(tǒng)仿真三大部分組成。工具箱實際就是用 Matlab 的基本語句編寫的各種子程序集和函數(shù)庫，用于解決某一方面的特定問題，實現(xiàn)某一類的新算法。同時，因為這個優(yōu)化問題有三個參數(shù)需要同時優(yōu)化，屬于多參數(shù)優(yōu)化問題，所以本文使用了多參數(shù)級聯(lián)編碼方法，即將 pK ， iT ， dT 分別編碼后，再將三個編碼首尾串聯(lián)組成整個個體編碼。 在遺傳算法中主要的遺傳操作包括選擇，交叉和變異三個基本算子，其基本流程圖如圖 41 所示： 常州工學(xué)院畢業(yè)設(shè)計論文 19 圖 41 標(biāo)準(zhǔn)遺傳算法流程圖 本章小結(jié) 本章重點介紹了 Matlab 軟件的歷史和該軟件所具有的特點，另外對于遺傳算法PID 控制的參數(shù)整定設(shè)計進(jìn)行一個整體藍(lán)圖的設(shè)計，提出了幾點設(shè)計的關(guān)鍵，為接下來仿真提供了很明確的方向。其中，適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大，適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小。 fi_Size=(Oderfi/fi_sum)*Size。 kk=1。 kk=kk+1。對于問題求解的方面來講，就是選擇出和最優(yōu)解比較接近的中間解。交叉時，可以執(zhí)行單點交叉和多點交叉。具體的 Matlab 仿真如下： pc=。 常州工學(xué)院畢業(yè)設(shè)計論文 21 for i=1:2:(Size1) temp=rand。 TempE(i+1,j)=E(i,j)。 變異運(yùn)算用來模擬生物在大自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，現(xiàn)象，它是以很小的概率隨機(jī)的改變遺傳基因的數(shù)值，所以，為了在盡可能大的空間中獲得質(zhì)量比較高的優(yōu)化解，必須采用變異的過程。 pm=[1:1:Size]*()/Size。 pm=。 if pmtemp if TempE(i,j)==0 TempE(i,j)=1。 end end end end 常州工學(xué)院畢業(yè)設(shè)計論文 22 Guarantee TempE(Size,:) TempE(Size,:)=BestS。 通過以上的步驟，就可以完成遺傳算法的實現(xiàn)。 基于二進(jìn)制的遺傳算法的 PID 仿真 已知被控對象的二階傳遞函數(shù)為 sssG 50400)( 2 ?? 運(yùn)行 Matlab 軟件，創(chuàng)建 m 文件并寫入程序，然后運(yùn)行進(jìn)行仿真。 程序按照標(biāo)準(zhǔn)遺傳算法進(jìn)行運(yùn)算，程序開始先對遺傳算法有關(guān)參數(shù)進(jìn)行設(shè)定，如：最大迭代數(shù)設(shè)置為 20（最大進(jìn)化代數(shù)）、樣本個數(shù)為 30（種群大?。徊娓怕剩?cP ）為 ，變異概率（ mP ）為 。如圖 52所示： 圖 52采用隨機(jī)數(shù)函數(shù)和 round 函數(shù)雙精度形式 接著就是計算適值，如圖 53所示： 常州工學(xué)院畢業(yè)設(shè)計論文 23 圖 53 計算適值 程序運(yùn)行后，會對計算結(jié)果進(jìn)行從小到大的排序，即是找出當(dāng)前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體。用迄今為止的最佳個體替換掉當(dāng)前群體中的最差個體。到此，計算出適值為 ，也就是 PID 控制器要整定參數(shù)的最優(yōu)個體。 復(fù)制 可以 使高適應(yīng)值個體以較高概率出現(xiàn)在新群體中 ，從而復(fù)制是通過概率選擇的方法實現(xiàn)的，高適應(yīng)值的個體趨于在下一代中 生存；低適應(yīng)值的個體趨于在下一代中被淘汰。但是應(yīng)該看到，復(fù)制所帶來的另一個不利的方面，即對某些適應(yīng)值突變的個體，復(fù)制可能使它們在下一代中過多地重復(fù)出現(xiàn)。這種缺點在遺傳算法中是通過交叉和變異來改善的。雜交是遺傳算法中一個至關(guān)重要的概念。雜交也可是多點雜交，如對上例進(jìn)行 5 位雜交，則串 1和串2中只 交換第 4 和第 5位。交叉過程和結(jié)果如圖 5圖 55和圖 56所示： 常州工學(xué)院畢業(yè)設(shè)計論文 24 圖 54 遺傳算法交叉過程 1 圖 55 遺傳算法交叉過程 2 圖 56 遺傳算法交叉結(jié)果 變異是對串中某些位進(jìn)行求反的操作。通過試驗發(fā)現(xiàn)，這樣的變異同樣能產(chǎn)生較好的效果。整個程序就真正的實現(xiàn)了遺傳算法的整個運(yùn)算過程，同時也做到了對 PID 控制器的參數(shù)整定。故整個 PID 控制器參數(shù)整定在遺傳算法中得到最優(yōu)的效果。 常州工學(xué)院畢業(yè)設(shè)計論文 27 基于實數(shù)制的遺傳算法 PID 仿真 被控對象為二階傳遞函數(shù) sssG 50400)( 2 ?? 采樣時間設(shè)為 1ms，輸入信號為一個單位階躍信號。到此，計算出適值為 ，也就是 PID 控制器要整定參數(shù)的最優(yōu)個體 如圖 512所示： 圖 512 計算適值 在應(yīng)用遺傳算法的時候，為了避免參數(shù)的選取范圍過大，可以先按經(jīng)驗選取一組參數(shù)，然后在在這組參數(shù)的周圍利用遺傳算法進(jìn)行設(shè)計，從而大大減少初始尋優(yōu)的盲目性，較小計算量。 常州工學(xué)院畢業(yè)設(shè)計論文 28 圖 513 交叉過程 1 圖 514 交叉過程 2 圖 515 交叉的結(jié)果 交叉即是雜交，是兩個串互相交換某一對應(yīng)段中的對應(yīng)位的值的操作。因為雜交能產(chǎn)生適應(yīng)值更高的新個體，使搜索進(jìn)入更高一層。這樣有可能保存高適應(yīng)值串（或模式）的特征。 交叉過程結(jié)束之后，就要進(jìn)行變異的過程，如下圖 51圖 517 所示。圖 516和圖 517充分的反映了這個過程，最終得到變異結(jié)果如圖 518 所示。 圖 519 代階函數(shù)值 J 的優(yōu)化過程 常州工學(xué)院畢業(yè)設(shè)計論文 31 圖 520 整定后的 PID 階躍響應(yīng) 從圖中可以看到， 在第六十代的時候參數(shù)整定優(yōu)化達(dá)至比較理想的狀態(tài)，第六十代以后的 整 定結(jié)果都 比較一致。 本章小結(jié) 本章節(jié)，我注重研究了遺傳算法三大關(guān)鍵步驟：選擇、交叉和變異，并對其進(jìn)行仿真說明。 通過本次基于遺傳算法的 PID 參數(shù)整定的 Matlab 仿真，實驗結(jié)果顯示，在 PID控制器參數(shù)整定中結(jié)合遺傳算法，使得通常交叉概率取值較大，變異概率取值較小，而且在整個搜索過程中，交叉和變異概率保持不變。 常州工學(xué)院畢業(yè)設(shè)計論文 32 結(jié)論 本文是通過 Matlab 仿真主要實現(xiàn)在 PID 參數(shù)整定過程中，將遺傳算法的“優(yōu)勝劣汰、適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串連的群體中，按照所選擇的適配值函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個體進(jìn)行篩選，使得適配值高的個體被保留下來，組成新的群體，新的群體又繼承了上一代的信息，又優(yōu)于上一代，這樣群體中的個體的適應(yīng)度不斷提高，從而得到全局最優(yōu)解。 實驗結(jié)果顯示，通常交叉概率取值較大，變異概率取值較小，而且在整個搜索過程中，交叉和變異概率保持不變。較小的變異率又不能有效地使群體擺脫超平面，從而起不到維持樣本空間多樣性的目的。如何充分發(fā)揮遺傳算法尋優(yōu)的強(qiáng)大優(yōu)勢，在線獲得系統(tǒng)的輸入輸出響應(yīng)，并及時完成參數(shù)優(yōu)化，使遺傳算法真正在控制領(lǐng)域得以實際應(yīng)用，這應(yīng)是我們下一步要研究的。 1999. ，張井崗，趙志誠 .多變量系統(tǒng)的 PID控制器設(shè)計 [J].信息與控制， 2020,37（ 3）： 316~321. ，孫樹棟，彭炎午 .并行遺傳算法的研究評述 .南昌航空工業(yè)學(xué)院學(xué)報， 1998，（ 2）： 84~88. ,張興華 ,李緯 . 基于差分進(jìn)化算法的 PID 優(yōu)化設(shè)計 [D]. 南京工業(yè)大學(xué)自動化學(xué)院 ,江蘇南京 2020. ,韓濮 . 基于神經(jīng)網(wǎng)絡(luò)的 PID 參數(shù)優(yōu)化方法研究 . 華北電力大學(xué)動力系保定 [D],2020. 常州工學(xué)院畢業(yè)設(shè)計論文 35 Grossberg. How is a moving target continuously tracked behind occluding cover In ( Ed． ) ， High level motion Processing: Computational， neurobiological，and psychophysical Perspectives［ J］ .Cambridge， MA: MIT Press， － 52． 常州工學(xué)院畢業(yè)設(shè)計論文 36 致謝 本設(shè)計能圓滿完成是在我的導(dǎo)師張燕紅的細(xì)心指導(dǎo)下進(jìn)行的，在每次遇到問題時老師不辭辛苦的講解才使得我的設(shè)計順利的進(jìn)