第8章

智能優(yōu)化算法辨識8.1遺傳算法基本原理8.1遺傳算法基本原理遺傳算法簡稱GA（GeneticAlgorithms）是1962年由美國Michigan大學的Holland教授提出的模擬自然界遺傳機制和生物進化論而成的一種并行隨機搜索最優(yōu)化方法。遺傳算法是以達爾文的自然選擇學說為基礎發(fā)展起來的。自然選擇學說包括以下三個方面：8.1.1遺傳算法的基本操作8.1遺傳算法基本原理（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個體之間的差異，稱為變異。變異是隨機發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應性變異的個體被保留下來，不具有適應性變異的個體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。8.1.1遺傳算法的基本操作8.1遺傳算法基本原理8.1.1遺傳算法的基本操作遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應度函數(shù)并通過遺傳中的復制、交叉及變異對個體進行篩選，使適適應度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復始，群體中個體適應度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。8.1遺傳算法基本原理8.1.1遺傳算法的基本操作遺傳算法的基本操作為：（1）復制（ReproductionOperator）復制是從一個舊種群中選擇生命力強的個體位串產(chǎn)生新種群的過程。具有高適應度的位串更有可能在下一代中產(chǎn)生一個或多個子孫。復制操作可以通過隨機方法來實現(xiàn)。首先產(chǎn)生0~1之間均勻分布的隨機數(shù)，若某串的復制概率為40%，則當產(chǎn)生的隨機數(shù)在0.40~1.0之間時，該串被復制，否則被淘汰。8.1遺傳算法基本原理8.1.1遺傳算法的基本操作（2）交叉（CrossoverOperator）復制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進化過程中的繁殖現(xiàn)象，通過兩個染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。交叉的過程為：在匹配池中任選兩個染色體，隨機選擇一點或多點交換點位置；交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數(shù)字串。8.1遺傳算法基本原理8.1.1遺傳算法的基本操作交叉體現(xiàn)了自然界中信息交換的思想。交叉有一點交叉、多點交叉、還有一致交叉、順序交叉和周期交叉。一點交叉是最基本的方法，應用較廣。它是指染色體切斷點有一處，例：8.1遺傳算法基本原理8.1.1遺傳算法的基本操作（3）變異(MutationOperator)變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機地改變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進制編碼的系統(tǒng)中，它隨機地將染色體的某一個基因由1變?yōu)?，或由0變?yōu)?。8.1遺傳算法基本原理8.1.1遺傳算法的基本操作若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。8.1遺傳算法基本原理8.1.2遺傳算法的特點（1）遺傳算法是對參數(shù)的編碼進行操作，而非對參數(shù)本身，這就是使得我們在優(yōu)化計算過程中可以借鑒生物學中染色體和基因等概念，模仿自然界中生物的遺傳和進化等機理；8.1遺傳算法基本原理8.1.2遺傳算法的特點（2）遺傳算法同時使用多個搜索點的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個初始點開始最優(yōu)解的迭代搜索過程，單個搜索點所提供的信息不多，搜索效率不高，有時甚至使搜索過程局限于局部最優(yōu)解而停滯不前。8.1遺傳算法基本原理8.1.2遺傳算法的特點遺傳算法從由很多個體組成的一個初始群體開始最優(yōu)解的搜索過程，而不是從一個單一的個體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標函數(shù)值，而且需要目標函數(shù)的導數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數(shù)值變換來的適應度函數(shù)值，就可以確定進一步的搜索方向和搜索范圍，無需目標函數(shù)的導數(shù)值等其他一些輔助信息。8.1遺傳算法基本原理8.1.2遺傳算法的特點遺傳算法可應用于目標函數(shù)無法求導數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等。（4）遺傳算法使用概率搜索技術。遺傳算法的選擇、交叉、變異等運算都是以一種概率的方式來進行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進化過程的進行，遺傳算法新的群體會更多地產(chǎn)生出許多新的優(yōu)良的個體。8.1遺傳算法基本原理8.1.2遺傳算法的特點（5）遺傳算法在解空間進行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機搜索；（6）遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡的隱函數(shù)，因而應用范圍較廣；（7）遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度，適合大規(guī)模復雜問題的優(yōu)化。8.1遺傳算法基本原理8.1.3遺傳算法的應用領域（1）函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是遺傳算法進行性能評價的常用算例。尤其是對非線性、多模型、多目標的函數(shù)優(yōu)化問題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。8.1遺傳算法基本原理8.1.3遺傳算法的應用領域（2）組合優(yōu)化隨著問題的增大，組合優(yōu)化問題的搜索空間也急劇擴大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。8.1遺傳算法基本原理8.1.3遺傳算法的應用領域（3）生產(chǎn)調(diào)度問題在很多情況下，采用建立數(shù)學模型的方法難以對生產(chǎn)調(diào)度問題進行精確求解。在現(xiàn)實生產(chǎn)中多采用一些經(jīng)驗進行調(diào)度。遺傳算法是解決復雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務分配等方面遺傳算法都得到了有效的應用。8.1遺傳算法基本原理8.1.3遺傳算法的應用領域（4）控制系統(tǒng)在自動控制領域中有很多與優(yōu)化相關的問題需要求解，遺傳算法已經(jīng)在其中得到了初步的應用。例如，利用遺傳算法進行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學習、基于遺傳算法的參數(shù)辨識、基于遺傳算法的神經(jīng)網(wǎng)絡結(jié)構(gòu)的優(yōu)化和權(quán)值學習等。8.1遺傳算法基本原理8.1.3遺傳算法的應用領域（5）機器人例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)劃、機器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應用。（6）圖像處理遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優(yōu)化計算。目前遺傳算法已經(jīng)在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計（1）染色體編碼方法基本遺傳算法使用固定長度的二進制符號來表示群體中的個體，其等位基因是由二值符號集{0,1}所組成。初始個體基因值可用均勻分布的隨機值生成，如個體X=100111001000101101就可表示一個個體，該個體的染色體長度是18。1、遺傳算法的構(gòu)成要素8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計（2）個體適應度評價基本遺傳算法與個體適應度成正比的概率來決定當前群體中每個個體遺傳到下一代群體中的概率多少。為正確計算這個概率，要求所有個體的適應度必須為正數(shù)或零。因此，必須先確定由目標函數(shù)值J到個體適應度f之間的轉(zhuǎn)換規(guī)則。1、遺傳算法的構(gòu)成要素8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計1、遺傳算法的構(gòu)成要素（3）遺傳算子：基本遺傳算法使用下述三種遺傳算子：①選擇運算：使用比例選擇算子；②交叉運算：使用單點交叉算子；③變異運算：使用基本位變異算子或均勻變異算子。8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計1、遺傳算法的構(gòu)成要素（4）基本遺傳算法的運行參數(shù)有下述4個運行參數(shù)需要提前設定：M：群體大小，即群體中所含個體的數(shù)量，一般取為20~100；G：遺傳算法的終止進化代數(shù)，一般取為100~500；Pc：交叉概率，一般取為0.4~0.99；Pm：變異概率，一般取為0.0001~0.1。8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計2、遺傳算法的應用步驟對于一個需要進行優(yōu)化的實際問題，一般可按下述步驟構(gòu)造遺傳算法：第一步：確定決策變量及各種約束條件，即確定出個體的表現(xiàn)型X和問題的解空間；第二步：建立優(yōu)化模型，即確定出目標函數(shù)的類型及數(shù)學描述形式或量化方法；8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計2、遺傳算法的應用步驟第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型x及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個體基因型x到個體表現(xiàn)型X的對應關系或轉(zhuǎn)換方法；第五步：確定個體適應度的量化評價方法，即確定出由目標函數(shù)值到個體適應度的轉(zhuǎn)換規(guī)則；8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計2、遺傳算法的應用步驟第六步：設計遺傳算子，即確定選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。第七步：確定遺傳算法的有關運行參數(shù)，即M,G,Pc,Pm等參數(shù)。8.1遺傳算法基本原理8.1.4遺傳算法的優(yōu)化設計以上操作過程可以用圖1來表示。參數(shù)編碼種群1計算適配值滿足要求遺傳操作種群2解碼尋優(yōu)結(jié)束種群1>種群2復制交叉變異是否圖1遺傳算法流程圖8.2遺傳算法求函數(shù)極大值劉金琨8.2遺傳算法求函數(shù)極大值利用遺傳算法求Rosenbrock函數(shù)的極大值8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值求解該問題遺傳算法的構(gòu)造過程：確定決策變量和約束條件01建立優(yōu)化模型02確定編碼方法038.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值用長度為10位的二進制編碼串來分別表示兩個決策變量x1,x2。10位二進制編碼串可以表示從0到1023之間的1024個不同的數(shù)，故將x1,x2的定義域離散化為1023個均等的區(qū)域，包括兩個端點在內(nèi)共有1024個不同的離散點。從離散點-2.048到離散點2.048，分別對應于0000000000(0)到1111111111(1023)之間的二進制編碼。8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值將x1,x2分別表示的兩個10位長的二進制編碼串連接在一起，組成一個20位長的二進制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應的關系。例如：x:00001101111101110001表示一個個體的基因型，其中前10位表示x1，后10位表示x2。8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值（4）確定解碼方法：解碼時需要將20位長的二進制編碼串切斷為兩個10位長的二進制編碼串，然后分別將它們轉(zhuǎn)換為對應的十進制整數(shù)代碼，分別記為y1和y2。依據(jù)個體編碼方法和對定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為例如，對個體x：000011011111011100018.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值它由兩個代碼所組成上述兩個代碼經(jīng)過解碼后，可得到兩個實際的值（5）確定個體評價方法：由于Rosenbrock函數(shù)的值域總是非負的，并且優(yōu)化目標是求函數(shù)的最大值，故可將個體的適應度直接取為對應的函數(shù)值，即8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值選個體適應度的倒數(shù)作為目標函數(shù)（6）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（7）確定遺傳算法的運行參數(shù)：群體大小M=80，終止進化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。上述七個步驟構(gòu)成了用于求函數(shù)極大值的優(yōu)化計算基本遺傳算法。8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值采用上述方法進行仿真，經(jīng)過100步迭代，最佳樣本為即當X1=-2.0480,X2=-2.0480時，Rosenbrock函數(shù)具有極大值，極大值為3905.9。仿真程序見chap8_1.m

8.2遺傳算法求函數(shù)極大值8.2.1二進制編碼遺傳算法求函數(shù)極大值遺傳算法的優(yōu)化過程是目標函數(shù)J和適應度函數(shù)F的變化過程。由仿真結(jié)果可知，隨著進化過程的進行，群體中適應度較低的一些個體被逐漸淘汰掉，而適應度較高的一些個體會越來越多，并且它們都集中在所求問題的最優(yōu)點附近，從而搜索到問題的最優(yōu)解。8.2遺傳算法求函數(shù)極大值8.2.2實數(shù)編碼遺傳算法求函數(shù)極大值求解該問題遺傳算法的構(gòu)造過程：（1）確定決策變量和約束條件；（2）建立優(yōu)化模型；（3）確定編碼方法：用2個實數(shù)分別表示兩個決策變量，分別將的定義域離散化為從離散點-2.048到離散點2.048的Size個實數(shù)。8.2遺傳算法求函數(shù)極大值8.2.2實數(shù)編碼遺傳算法求函數(shù)極大值求解該問題遺傳算法的構(gòu)造過程：（4）確定個體評價方法：個體的適應度直接取為對應的函數(shù)值，即選個體適應度的倒數(shù)作為目標函數(shù)8.2遺傳算法求函數(shù)極大值8.2.2實數(shù)編碼遺傳算法求函數(shù)極大值求解該問題遺傳算法的構(gòu)造過程：（5）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（6）確定遺傳算法的運行參數(shù)：群體大小M=500，終止進化代數(shù)G=200，交叉概率Pc=0.90，采用自適應變異概率即變異概率與適應度有關，適應度越小，變異概率越大。8.2遺傳算法求函數(shù)極大值8.2.2實數(shù)編碼遺傳算法求函數(shù)極大值上述六個步驟構(gòu)成了用于求函數(shù)Rosenbrock極大值的優(yōu)化計算的實數(shù)編碼遺傳算法。十進制編碼求函數(shù)Rosenbrock極大值。仿真程序見chap8_2.m。仿真程序經(jīng)過200步迭代，最佳樣本為即當X2=-2.044,X1=-2.0438時，函數(shù)具有極大值，極大值為3880.3?？梢姡捎脤崝?shù)編碼的遺傳算法求解效率不如二進制編碼。8.3粒子群算法劉金琨8.3粒子群算法粒子群算法，也稱粒子群優(yōu)化算法(ParticleSwarmOptimization)，縮寫為PSO。粒子群優(yōu)化算法是一種進化計算技術，1995年由Eberhart博士和Kennedy博士提出，該算法源于對鳥群捕食的行為研究，是近年來迅速發(fā)展的一種新的進化算法。8.3粒子群算法最早的PSO是模擬鳥群覓食行為而發(fā)展起來的一種基于群體協(xié)作的隨機搜索算法，讓一群鳥在空間里自由飛翔覓食，每個鳥都能記住它曾經(jīng)飛過最高的位置，然后就隨機的靠近那個位置，不同的鳥之間可以互相交流，它們都盡量靠近整個鳥群中曾經(jīng)飛過的最高點，這樣，經(jīng)過一段時間就可以找到近似的最高點。8.3粒子群算法PSO算法屬于進化算法的一種，和遺傳算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，沒有遺傳算法的“交叉”和“變異”操作，通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術界的重視，并且在解決實際問題中展示了其優(yōu)越性。目前已廣泛應用于函數(shù)優(yōu)化、系統(tǒng)辨識、模糊控制等應用領域。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法從這種模型中得到啟示并用于解決優(yōu)化問題。PSO算法中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應度值，適應度值越大越好。每個粒子還有一個速度決定他們飛行的方向和距離，粒子們追隨當前的最優(yōu)粒子在解空間中搜索。8.3粒子群算法8.3.1粒子群算法基本原理PSO算法首先初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個"極值"來更新自己的位置。第一個極值是粒子本身所找到的最優(yōu)解，這個解叫做個體極值。另一個極值是整個種群目前找到的最優(yōu)解，這個極值稱為全局極值。8.3粒子群算法8.3.1粒子群算法基本原理粒子群基本算法速度更新位置更新8.3粒子群算法8.3.2參數(shù)設置

8.3粒子群算法8.3.2參數(shù)設置a)粒子數(shù)：一般取20-40，對于比較難的問題,粒子數(shù)可以取到100或200；b)最大速度Vmax：決定粒子在一個循環(huán)中最大的移動距離，通常小于粒子的范圍寬度。較大的Vmax可以保證粒子種群的全局搜索能力，較小的Vmax則粒子種群的局部搜索能力加強；c)學習因子：c1和c2通?？稍O定為2.0。c1為局部學習因子，c2為全局學習因子，c2一般取大些。8.3粒子群算法8.3.2參數(shù)設置d)慣性權(quán)重：一個大的慣性權(quán)值有利于展開全局尋優(yōu)，而一個小的慣性權(quán)值有利于局部尋優(yōu)。當粒子的最大速度Vmax很小時，使用接近于1的慣性權(quán)重。當Vmax不是很小時，使用權(quán)重ω=0.8較好。8.3粒子群算法8.3.2參數(shù)設置還可使用時變權(quán)重。如果在迭代過程中采用線性遞減慣性權(quán)值，則粒子群算法在開始時具有良好的全局搜索性能，能夠迅速定位到接近全局最優(yōu)點的區(qū)域，而在后期具有良好的局部搜索性能，能夠精確的得到全局最優(yōu)解。經(jīng)驗表明，慣性權(quán)重采用從0.90線性遞減到0.10的策略，會獲得比較好的算法性能；中止條件：最大循環(huán)數(shù)或最小誤差要求。8.3粒子群算法8.3.3算法流程（1）初始化：設定參數(shù)運動范圍，設定學習因子

c1、c2

，最大進化代數(shù)G，kg表示當前的進化代數(shù)。在一個D維參數(shù)的搜索解空間中，粒子組成的種群規(guī)模大小為Size，每個粒子代表解空間的一個候選解，其中第i個粒子在整個解空間的位置表示為Xi，速度表示為Vi。第i個粒子從初始到當前迭代次數(shù)搜索產(chǎn)生的最優(yōu)解，個體極值Pi，整個種群目前的最優(yōu)解為BestS。隨機產(chǎn)生Size個粒子，隨機產(chǎn)生初始種群的位置矩陣和速度矩陣。8.3粒子群算法8.3.3算法流程

8.3粒子群算法8.3.3算法流程（3）更新粒子的速度和位置，產(chǎn)生新種群，并對粒子的速度和位置進行越界檢查，為避免算法陷入局部最優(yōu)解，加入一個局部自適應變異算子進行調(diào)整。(8.25)(8.26)其中kg=1,2…G

，i=1,2…Size

，r1

和

r2為0到1的隨機數(shù)，c1為局部學習因子，c2

為全局學習因子，一般取

c2大些。8.3粒子群算法8.3.3算法流程（4）比較粒子的當前適應值f(Xi)和自身歷史最優(yōu)值Pi，如果f(Xi)

優(yōu)于Pi，則置f(Xi)為當前值，并更新粒子位置。（5）比較粒子當前適應值f(Xi)與種群最優(yōu)值BestS，如果f(Xi)優(yōu)于BestS，則置f(Xi)為當前值，更新種群全局最優(yōu)值。（6）檢查結(jié)束條件，若滿足，則結(jié)束尋優(yōu)；否則kg=kg+1，轉(zhuǎn)至（3）。結(jié)束條件為尋優(yōu)達到最大進化代數(shù)，或評價值小于給定精度。8.3粒子群算法圖PSO的算法流程圖8.3.3算法流程開始初始化種群和設置參數(shù)調(diào)用適應度子函數(shù)，計算個體適應度值初始化個體最優(yōu)和全局最優(yōu)更新粒子位置和速度產(chǎn)生新種群調(diào)用適應度子函數(shù)，計算個體適應度值更新個體最優(yōu)和全局最優(yōu)達到代數(shù)要求？輸出優(yōu)化結(jié)果結(jié)束NY8.4基于粒子群算法的函數(shù)優(yōu)化劉金琨

全局粒子群算法中，每個粒子的速度的更新是根據(jù)粒子自己歷史最優(yōu)值Pi和粒子群體全局最優(yōu)值Pg。為了避免陷入局部極小，可采用局部粒子群算法，每個粒子速度更新根據(jù)粒子自己歷史最優(yōu)值Pi和粒子鄰域內(nèi)粒子的最優(yōu)值Plocal。圖8-16環(huán)形鄰域法

根據(jù)取鄰域的方式的不同，局部粒子群算法有很多不同的實現(xiàn)方法。本節(jié)采用最簡單的環(huán)形鄰域法，如圖8-16所示。以8個粒子為例說明局部粒子群算法，如下圖所示。在每次進行速度和位置更新時，粒子1追蹤1、2、8三個粒子中的最優(yōu)個體，粒子2追蹤1、2、3三個粒子中的最優(yōu)個體，依次類推。仿真中，求解某個粒子鄰域中的最優(yōu)個體是由函數(shù)chap8_3lbest.m來完成。

采用實數(shù)編碼求函數(shù)極大值，用2個實數(shù)分別表示兩個決策變量x1，x2，分別將x1，x2

的定義域離散化為從離散點-2.048到離散點2.048的Size個實數(shù)。個體的適應度直接取為對應的目標函數(shù)值，越大越好。即取適應度函數(shù)為F(x)=f(x1,x2)。在粒子群算法仿真中，取粒子群個數(shù)為Size=30，最大迭代次數(shù)G=100，粒子運動最大速度為Vmax=1.0，即速度范圍為[-1,1]。學習因子取c1=1.3，c2=1.7，采用線性遞減的慣性權(quán)重，慣性權(quán)重采用從0.90線性遞減到0.10的策略。根據(jù)M的不同可采用不同的粒子群算法。取M=2，采用局部粒子群算法。按式(8.8)和式(8.9)更新粒子的速度和位置，產(chǎn)生新種群。經(jīng)過100步迭代，最佳樣本為BestS=[-2.048,-2.048]，函數(shù)具有極大值，極大值為3905.9。適應度函數(shù)F的變化過程如圖8-17所示，由仿真可見，隨著迭代過程的進行，粒子群通過追蹤自身極值和局部極值，不斷更新自身的速度和位置，從而找到全局最優(yōu)解。通過采用局部粒子群算法，增強了算法的局部搜索能力，有效地避免了陷入局部最優(yōu)解，仿真結(jié)果表明正確率在95%以上。圖8-17適應度函數(shù)的變化過程粒子群優(yōu)化程序：包括以下三個部分。主程序:chap8_3.m局部最優(yōu)排序函數(shù)：chap8_3lbest.m函數(shù)計算程序：chap8_3func.m1238.5基于粒子群算法的非線性系統(tǒng)參數(shù)辨識劉金琨以下面三個例子為例，說明粒子群算法在非線性系統(tǒng)中的參數(shù)辨識中的應用。01辨識非線性靜態(tài)模型一、辨識非線性靜態(tài)模型

一、辨識非線性靜態(tài)模型首先運行模型測試程序chap8_4.m，對象的輸入樣本區(qū)間為[-44]之間，步長為0.10，由式（8.10）計算樣本輸出值，共有81對輸入輸出樣本對。一、辨識非線性靜態(tài)模型將待辨識的參數(shù)向量記為X，取樣本個數(shù)為Size=200，最大迭代次數(shù)G=200，采用實數(shù)編碼，四個參數(shù)的搜索范圍均為[0,5]。粒子運動最大速度為Vmax=1.0，即速度范圍為[-1,1]。學習因子取c1=1.3,c2=1.7，采用線性遞減的慣性權(quán)重，慣性權(quán)重采用從0.90線性遞減到0.10的策略。目標函數(shù)的倒數(shù)作為粒子群的適應度函數(shù)。將辨識誤差指標直接作為粒子的目標函數(shù)，越小越好。一、辨識非線性靜態(tài)模型

一、辨識非線性靜態(tài)模型圖8-9辨識誤差函數(shù)的優(yōu)化過程一、辨識非線性靜態(tài)模型仿真程序模型測試程序：chap8_4.m辨識程序粒子群算法辨識程序:chap8_5.m目標函數(shù)計算程序：chap8_5obj.m1202辨識非線性動態(tài)模型二、辨識非線性動態(tài)模型

二、辨識非線性動態(tài)模型

二、辨識非線性動態(tài)模型首先運行模型測試程序chap8_6.m，對象的輸入信號取偽隨機二進制序列（PRBS）為輸入，如圖8-10所示，從而得到用于辨識的模型測試數(shù)據(jù)。二、辨識非線性動態(tài)模型

二、辨識非線性動態(tài)模型

二、辨識非線性動態(tài)模型圖8-10M序列信號二、辨識非線性動態(tài)模型圖8-11辨識誤差函數(shù)的變化過程二、辨識非線性動態(tài)模型仿真程序模型測試程序模型測試主程序：chap8_6.m偽隨機二進制序列產(chǎn)生程序：chap8_6prbs.m辨識程序粒子群算法辨識程序:chap8_7.m目標函數(shù)計算程序：chap8_7obj.m128.6差分進化算法及其參數(shù)辨識劉金琨差分進化算法簡介差分進化（DifferentialEvolution，DE）算法是模擬自然界生物種群以“優(yōu)勝劣汰、適者生存”為原則的進化發(fā)展規(guī)律而形成的一種隨機啟發(fā)式搜索算法，是一種新興的進化計算技術。它于1995年由RainerStorn和KennethPrice提出。由于其簡單易用、穩(wěn)健性好以及強大的全局搜索能力，使得差分進化算法已在多個領域取得成功。差分進化算法簡介差分進化算法保留了基于種群的全局搜索策略，采用實數(shù)編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復雜性。同時，差分進化算法特有的記憶能力使其可以動態(tài)跟蹤當前的搜索情況，以調(diào)整其搜索策略，具有較強的全局收斂能力和魯棒性,且不需要借助問題的特征信息，適于求解一些利用常規(guī)的數(shù)學規(guī)劃方法所無法求解的復雜環(huán)境中的優(yōu)化問題。采用差分進化算法可實現(xiàn)復雜系統(tǒng)的參數(shù)辨識。差分進化算法簡介實驗結(jié)果表明，差分進化算法的性能優(yōu)于粒子群算法和其它進化算法，該算法已成為一種求解非線性、不可微、多極值和高維的復雜函數(shù)的一種有效和魯棒的方法。標準差分進化算法01差分進化算法的基本流程02差分進化算法的參數(shù)設置03差分進化算法的函數(shù)優(yōu)化04目錄CONTENTS01標準差分進化算法一、標準差分進化算法差分進化算法是基于群體智能理論的優(yōu)化算法，通過群體內(nèi)個體間的合作與競爭產(chǎn)生的群體智能指導優(yōu)化搜索。它保留了基于種群的全局搜索策略，采用實數(shù)編碼、基于差分的簡單變異操作和一對一的競爭生存策略，降低了遺傳操作的復雜性，同時它特有的記憶能力使其可以動態(tài)跟蹤當前的搜索情況已調(diào)整其搜索策略。具有較強的全局收斂能力和魯棒性。差分進化算法的主要優(yōu)點可以總結(jié)為以下三點：待定參數(shù)少；不易陷入局部最優(yōu)；收斂速度快。一、標準差分進化算法

差分進化算法根據(jù)父代個體間的差分矢量進行變異、交叉和選擇操作，其基本思想是從某一隨機產(chǎn)生的初始群體開始，通過把種群中任意兩個個體的向量差加權(quán)后按一定的規(guī)則與第三個個體求和來產(chǎn)生新個體，然后將新個體與當代種群中某個預先決定的個體相比較，如果新個體的適應度值優(yōu)于與之相比較的個體的適應度值，則在下一代中就用新個體取代舊個體，否則舊個體仍保存下來，通過不斷地迭代運算，保留優(yōu)良個體，淘汰劣質(zhì)個體，引導搜索過程向最優(yōu)解逼近。一、標準差分進化算法在優(yōu)化設計中，差分進化算法與傳統(tǒng)的優(yōu)化方法相比，具有以下主要特點：

差分進化算法從一個群體即多個點而不是從一個點開始搜索，這是它能以較大的概率找到整體最優(yōu)解的主要原因；

差分進化算法的進化準則是基于適應性信息的，無須借助其它輔助性信息（如要求函數(shù)可導或連續(xù)），大大地擴展了其應用范圍；

差分進化算法具有內(nèi)在的并行性，這使得它非常適用于大規(guī)模并行分布處理，減小時間成本開銷；

差分進化算法采用概率轉(zhuǎn)移規(guī)則，不需要確定性的規(guī)則。123402差分進化算法的基本流程二、差分進化算法的基本流程差分進化算法是基于實數(shù)編碼的進化算法，整體結(jié)構(gòu)上與其它進化算法類似，由變異、交叉和選擇三個基本操作構(gòu)成。標準差分進化算法主要包括以下4個步驟：1.生成初始群體

二、差分進化算法的基本流程2.變異操作

二、差分進化算法的基本流程2.變異操作

二、差分進化算法的基本流程3.交叉操作

二、差分進化算法的基本流程4.選擇操作

二、差分進化算法的基本流程圖8-12差分進化基本運算流程03差分進化算法的參數(shù)設置三、差分進化算法的參數(shù)設置對于進化算法而言，為了取得理想的結(jié)果，需要對差分進化算法的各參數(shù)進行合理的設置。針對不同的優(yōu)化問題，參數(shù)的設置往往也是不同的。另外，為了使差分進化算法的收斂速度得到提高，學者們針對差分進化算法的核心部分—變異向量的構(gòu)造形式提出了多種的擴展模式，以適應更廣泛的優(yōu)化問題。三、差分進化算法的參數(shù)設置差分進化算法的運行參數(shù)主要有：縮放因子F，交叉因子CR

，群體規(guī)模M和最大進化代數(shù)G

。變異因子F是控制種群多樣性和收斂性的重要參數(shù)。一般在[0,2]之間取值。變異因子F值較小時，群體的差異度減小，進化過程不易跳出局部極值，可能會導致種群過早收斂的問題。變異因子F值較大時，雖然容易跳出局部極值，但是收斂速度會減慢。一般可選在F=0.3-0.6。1.變異因子F三、差分進化算法的參數(shù)設置2.交叉因子CR交叉因子CR可控制個體參數(shù)的各維對交叉的參與程度，以及全局與局部搜索能力的平衡，一般在[0,1]之間。交叉因子CR越小，種群多樣性減小，容易受騙，過早收斂。CR越大，收斂速度越大。但過大可能導致收斂變慢，因為擾動大于了群體差異度。根據(jù)文獻一般應選在[0.6,0.9]之間。

CR越大，F(xiàn)越小，種群收斂逐漸加速，但隨著交叉因子CR的增大，收斂對變異因子F的敏感度逐漸提高。三、差分進化算法的參數(shù)設置3.群體規(guī)模群體所