【文章內(nèi)容簡介】 6） 遺傳算法對(duì)于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至 10 是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因此應(yīng)用范圍較廣； （ 7） 遺傳算法具有并行計(jì)算的特點(diǎn)，因而可以通過大規(guī)模并行計(jì)算來提高計(jì)算速 度； （ 8） 遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化； （ 9） 遺傳算法計(jì)算簡單，功能強(qiáng)。 遺傳算法的優(yōu)化設(shè)計(jì) 遺傳算法的運(yùn)算過程 遺傳算法中最優(yōu)解的搜索過程也是模仿生物的進(jìn)化過程，通過染色體之間的交叉和染色體的變異來完成 [12]。通過所謂的遺傳算子 （ geic operators） 作用于群體 )(tP 中，進(jìn)行遺傳操作，從而得到新一代群體 )1( ?tP 。 遺傳算子包括選擇算子，交叉算子，變異算子。圖 是遺傳算法的運(yùn)算過程示意圖： 由該圖可以看出，使用上述三種遺傳算子（選擇算子，交叉算子，變異算子）的遺傳算法的主要運(yùn)算過程如下所述： 步驟一：初始化。 設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器 0??t ；設(shè)置最大進(jìn)化代數(shù) T ；隨機(jī)生成 M 個(gè)個(gè)體作為初始群體 )0(P ； 步驟二：個(gè)體評(píng)價(jià)。計(jì)算群體 )(tP 中各個(gè)個(gè)體的適應(yīng)度 ； 群體 P （ t ）選擇運(yùn)算交叉運(yùn)算變異運(yùn)算群體 P （ t + 1 ） 解碼解集合個(gè)體評(píng)價(jià)圖 3 . 1 遺傳算法運(yùn)算過程示意圖 11 步驟三：選擇運(yùn) 算。將選擇算子作用于群體 ； 步驟四：交叉運(yùn)算。將交叉算子作用于群體 ； 步驟五：變異運(yùn)算。將變異算子作用于群體。群體 )(tP 經(jīng)過選擇，交叉，變異運(yùn)算之后得到下一代群體 )1( ?tP ； 步驟六：終止條件判斷。若 Tt?? ，則： 1??? tt ，轉(zhuǎn)到步驟二；若 Tt? ，則以進(jìn)化過程中得到的具有最大適應(yīng)度的個(gè)體作為最優(yōu)解輸出，終止計(jì)算。 遺傳算法的構(gòu)成要素 （ 1） 染色體編碼方法。 基本遺傳算法使用固定長度的二進(jìn)制符號(hào)串兒來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集 {0,1}所組成的。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成。 （ 2） 個(gè)體適應(yīng)度評(píng)價(jià)。 基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正或零。至于，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理。 （ 3） 遺傳算子。 使用下述三種 遺傳算子： A. 選擇運(yùn)算使用比例選擇算子； B. 交叉運(yùn)算使用單點(diǎn)交叉算子； C．變異運(yùn)算使用基本位變異算子或均勻變異算子 。 （ 4） 基本遺傳算法的運(yùn)行參數(shù)。 基本遺傳算法有下述 4 個(gè)運(yùn)行參數(shù)需要提前設(shè)定： :群體大小。一般取為 20～ 100； :遺傳運(yùn)算終止進(jìn)化代數(shù)。一般取為 100～ 500； C. cp :交叉概率。一般取為 ～ ； D. mp :變異概率。一般取為 ～ 。 遺傳算法的應(yīng)用步驟 （ 1） 確定決策變量及其各種約束條件，即確定出個(gè)體的表現(xiàn)型 X 和問題的解 空間。 （ 2） 建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型（是求目標(biāo)函數(shù)的最大值還是最 小值？）及其數(shù)學(xué)描述形式或量化方法。 （ 3） 確定表示可行解的染色體編碼方法，也即確定出個(gè)體的基因型 X 及遺傳 12 算法的搜索空間。 （ 4） 確 定解碼方法，即確定出由個(gè)體基 因型 X 到個(gè)體表現(xiàn)型 X 的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法。 （ 5） 確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值 )(Xf 到個(gè)體 適應(yīng)度 )(XF 的轉(zhuǎn)換規(guī)則。 （ 6） 設(shè)計(jì)遺傳算子，即確定出選擇運(yùn)算，交叉運(yùn)算，變異運(yùn)算等遺傳算子的具 體操作方法。 （ 7） 確定遺傳算法的有關(guān)運(yùn)行參數(shù)， 如 M ,T , cp ， mp 等參數(shù)。 由上述構(gòu)造步驟可以看出，可行解的編碼方法，遺傳算子的設(shè)計(jì)是構(gòu)造遺傳算法時(shí)需要考慮的兩個(gè)主要問題，也是設(shè)計(jì)遺傳算法時(shí)的兩個(gè)關(guān)鍵步驟。對(duì)不同的優(yōu)化問題需要使用不同的編碼方法和不同操作的遺傳算子，它們與所求解的具體問題密切相關(guān)，因而對(duì)所求解的理解程度是遺傳算法應(yīng)用成功與否的關(guān)鍵。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問 題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科 [8]。下面是它的一些主要應(yīng)用領(lǐng)域： （ 1）函數(shù)優(yōu)化。函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機(jī)函數(shù)等。用這些幾何特性各具有特色的函數(shù)來評(píng)價(jià)遺傳算法的性能，更能反映算法的本質(zhì)效果。而對(duì)一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，而遺傳算法卻可以方便得到較好的結(jié) 果。 （ 2）組合優(yōu)化。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法是尋求最優(yōu)解的最佳工具之一。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題等方面得到成功的應(yīng)用。 （ 3）生產(chǎn)調(diào)度問題。生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也會(huì)因?yàn)楹喕喽骨蟮媒Y(jié)果與實(shí)際相差太遠(yuǎn)。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃等方面遺傳算法得到了有效的應(yīng)用。 （ 4）自動(dòng)控制。在自動(dòng)控制領(lǐng)域中很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示出了良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、基于遺傳算法的 PID 控制器等。 13 （ 5）圖象處理。圖象處理是計(jì)算機(jī)視覺中的一個(gè)重要研究領(lǐng)域。在圖象處理過程中，如掃描、特征提取、圖象分割等不可避免地會(huì)存在一些誤差，這些誤差會(huì)影響圖象處理效果。如何使其誤差變小，遺傳算法發(fā)揮了重要的作用。 14 第 4 章基于遺傳算法的 PID 整定 基于遺傳算法的 PID 參數(shù)整定優(yōu)點(diǎn) 目前 PID 參數(shù)的優(yōu)化方法有很多，如間接尋優(yōu)法，梯度法，爬山法等，而在熱工系統(tǒng)中單純形法、專家整定法則應(yīng)用較廣 [14]。雖然這些方法都具有良好的尋優(yōu)特性，但卻存在著一些弊端，單純形法對(duì)初值比較敏感容易陷入局部最優(yōu)化解，造成尋優(yōu)失敗。專家整定法則需要太多的經(jīng)驗(yàn)，不同目標(biāo)函數(shù)對(duì)應(yīng)不同的經(jīng)驗(yàn)，而整理知識(shí)庫則是一項(xiàng)長時(shí)間的工程。因此我們選取了遺傳算法來進(jìn)行參數(shù)尋優(yōu)。該方法是一種不需要任何初始信息并可以尋求全局最優(yōu)解的高效的優(yōu)化組合方 法。遺傳算法作為一種全局優(yōu)化算法，得到了越來越廣泛的應(yīng)用。近年來，它在控制上應(yīng)用日益增多。采用遺傳算法進(jìn)行 PID 三個(gè)參數(shù)的整定，具有以下優(yōu)點(diǎn)： （ 1） 與單純形法相比，遺傳算法同樣具有良好的尋優(yōu)特性，且克服了單純形法參數(shù)初值的敏感性。在初始條件選擇不當(dāng)?shù)那闆r下，遺傳算法在不需要給出調(diào)節(jié)器初始參數(shù)的情況下，仍能尋找到合適的參數(shù)，使控制目標(biāo)滿足要求。同時(shí)單純形答難以解決多值函數(shù)問題以及在多參數(shù)尋優(yōu)（如串級(jí)系統(tǒng)）中，容易造成尋優(yōu)失敗或時(shí)間過長，而遺傳算法的特性決定了它能很好地克服以上問題。 （ 2） 與專家整定法相比，它具有操作方 便、速度快的優(yōu)點(diǎn)，不需要復(fù)雜的規(guī)則，只通過字串進(jìn)行簡單的復(fù)制、交叉、變異，便可以達(dá)到尋優(yōu)。避免了專家整定法中前期大量的知識(shí)庫整理工作及大量的仿真實(shí)驗(yàn)。 （ 3） 遺傳算法是從許多點(diǎn)開始并行操作，在解空間進(jìn)行高效啟發(fā)式搜索，克服了從單點(diǎn)出發(fā)的弊端以及搜索的盲目性，從而使尋優(yōu)速度更快，避免了過早陷入局部最優(yōu)解。 （ 4） 遺傳算法不僅使用于單目標(biāo)尋優(yōu)，而且也使用于多目標(biāo)尋優(yōu)。根據(jù)不同的控制系統(tǒng)，針對(duì)一個(gè)或多個(gè)目標(biāo)，遺傳算法均能在規(guī)定的范圍內(nèi)尋找到合適的參數(shù)。 15 基于遺傳算法的 PID 整定的實(shí)現(xiàn) 編碼和解碼 我們把待尋 優(yōu)的參數(shù)用一個(gè)二進(jìn)制數(shù)來表示。若參數(shù) a的變化范圍為 [ mina ，maxa ] ,用 m 位二進(jìn)制數(shù) b來表示 ,則它們的關(guān)系為 : ),(1 m a xm i n2m i n aam baa ??? （ ） 將所有表示參數(shù)的二進(jìn)制數(shù)串接起來就組成了一個(gè)長的二進(jìn)制字串。該字串的每一位只有 0或 1兩種取值。該字串即為遺傳算法可以操作的對(duì)象。此過程為編碼。上述過程的反過程為解碼 。 初始種群的確定 適應(yīng)函數(shù)應(yīng)同目標(biāo)函數(shù)相關(guān) ,遺傳算法尋優(yōu)就是因?yàn)樾枰幊虂韺?shí)現(xiàn)各過程，所以采用計(jì)算機(jī)隨機(jī)產(chǎn)生初始種群，針對(duì)二進(jìn)制編碼而言，先產(chǎn)生 0～ 1 之間均分布的隨機(jī)數(shù)，然后規(guī)定產(chǎn)生的隨機(jī)數(shù) 0～ 之間代表 0， ～ 1 之間代表 1 。此外，考慮到計(jì)算的復(fù)雜程度來規(guī)定種群的大小。種群中字串的個(gè)數(shù)越大 , 其代表性越廣泛 , 最終進(jìn)化到最優(yōu)解的可能性越大 , 但勢必造成計(jì)算時(shí)間的增加。因此其個(gè)數(shù)一般選為 10 ～ 50。 適配函數(shù)的確定 一般的尋優(yōu)方法在約束條件下可以求得滿足條件的一組參數(shù)，在設(shè) 計(jì)中是從該組參數(shù)中尋找一個(gè)最好的。衡量一個(gè)控制系統(tǒng)的指標(biāo)有三個(gè)方面，即穩(wěn)定性、正確性和快速性。而上升時(shí)間反映了系統(tǒng)的快速性，上升時(shí)間越短，控制進(jìn)行的就越快，系統(tǒng)品質(zhì)也就越好。 如果單純追求系統(tǒng)的動(dòng)態(tài)特性，得到的參數(shù)很可能使控制信號(hào)過大，在實(shí)際應(yīng)用中會(huì)因系統(tǒng)中固有的飽和特性而導(dǎo)致系統(tǒng)不穩(wěn)定，為了防止控制能量過大，在目標(biāo)函數(shù)中加入控制量。因此為了使控制效果更好，我們給出了控制量、誤差和上升時(shí)間作為約束條件。因?yàn)檫m應(yīng)函數(shù)同目標(biāo)函數(shù)有關(guān)，所以目標(biāo)函數(shù)確定后，直接將其作為適配函數(shù)進(jìn)行參數(shù)尋優(yōu)，最優(yōu)的控制參數(shù)也就是在滿 足約束條件下使 )(xf 最大時(shí)， x 所對(duì)應(yīng)的控制器參數(shù)。 16 遺傳算子的確定 遺傳算法有三個(gè)算子 :選擇概率 sP ,交叉概率 cP 和變異概率 mP 。選擇概率 sP通過適配值來確定 ,這里不再贅講。交叉概率決定了交叉的次數(shù) , cP 過 小導(dǎo)致搜索停滯不前 。 而太大也會(huì)使高適配置的結(jié)構(gòu)被破壞掉。因此 , 交叉概率一般選取 ～ 之間。變異概率 mP 一般為 ～ ,太大會(huì)引起不穩(wěn)定 ,太小難以尋到全局最優(yōu)解。 遺傳算法的操作 首先利用適應(yīng)度比例法進(jìn)行復(fù)制。即通過適配函數(shù)求得適配值，進(jìn)而求每個(gè)串對(duì)應(yīng)的復(fù)制概率。復(fù)制概率與每代字串的個(gè)數(shù)的乘積為該串在下一代中應(yīng)復(fù)制的個(gè)數(shù)。復(fù)制概率大的在下一代中將有較多的子孫，相反則會(huì)淘汰。 其次進(jìn)行單點(diǎn)交叉，交叉概率為 cp ，從復(fù)制的成員中以 cp 的概率選取字串組成匹配池，而后對(duì)匹配池的成員隨機(jī)匹配，交叉的位置也是隨機(jī)確定的。 最后以概率 mp 進(jìn)行變異。假如每代有 15 個(gè)字串，每個(gè)字串 12 位，則共有15 12=180 個(gè)串位，期望的變異串位數(shù)為 180 ≈ 2（位），即每代中有兩個(gè)串位要由 1變?yōu)?0 或 0 變?yōu)?1。 初始種群通過復(fù)制、交叉及變異得到了新一代種群，該種群經(jīng)過解碼后代入適配函數(shù)，觀察是否滿結(jié)束條件，若不滿足，則重復(fù)以 上操作直到滿足為止。結(jié)束條件由具體問題所定，只要各目標(biāo)參數(shù)在規(guī)定范圍內(nèi)，則終止計(jì)算。以上操作過程可以用圖 來表示。 17 編 碼種 群 P （ t ）計(jì) 算 適 配 值解 碼滿 足 要 求尋 優(yōu) 結(jié) 束是否參 數(shù)圖 4 . 1 遺 傳 算 法 流 程 圖遺 傳 操 作（ 選 擇 、 交 叉 、 變 異 ）P （ t + 1 ） ＞ P （ t ） 利用遺傳算法優(yōu)化 PID 控制參數(shù)的具體步驟 （ 1） 確定每個(gè)參數(shù)的大致范圍和編碼長度，進(jìn)行編碼； （ 2） 隨機(jī)產(chǎn)生 n 個(gè)個(gè)體構(gòu)成初始種群 )(tP ； （ 3） 將種群中各個(gè)體解碼成對(duì)應(yīng)的參數(shù)值，用此參數(shù)求代價(jià)函數(shù) J 及適應(yīng)函數(shù)值 f ，取 Jf 1? ； （ 4） 應(yīng)用復(fù)制、交叉和變異算子對(duì)種群 )(tP 進(jìn)行操作，產(chǎn)生下一代種群)1(?tP ； （ 5） 重復(fù)步驟（ 3）和（ 4），直至參數(shù)收斂或達(dá)到預(yù)定的指標(biāo)。 基于遺傳算法的 PID 整定的程序設(shè)計(jì) 遺傳算法復(fù)制算子的實(shí)現(xiàn) 本文采用最簡單的輪盤賭選擇法，為選擇交配個(gè)體，需要進(jìn)行多輪操作，每一輪產(chǎn)生一個(gè) [0， 1]均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來確定 被選個(gè)體。Matlab 程序?qū)崿F(xiàn)如下： k=1。 for i=1:1:size for j=1:1:size If Ch_P(i)=Fi_S(j)amp。Ch_P(i)Fi_S(j+1) 18 Temp(k,:)=E_Code(IndexFi(j),:): k=k+1。 end end end 遺傳算法交叉算子的實(shí)現(xiàn) 交叉即基因重組，是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換、重組而生