1、計量經濟學遺傳算法第1頁，共45頁，2022年，5月20日，7點13分，星期三 遺傳算法簡稱GA（Genetic Algorithms）是1962年由美國Michigan大學的Holland教授提出的模擬自然界遺傳機制和生物進化論而成的一種并行隨機搜索最優化方法。 遺傳算法是以達爾文的自然選擇學說為基礎發展起來的。自然選擇學說包括以下三個方面：一、遺傳算法的基本原理第2頁，共45頁，2022年，5月20日，7點13分，星期三（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個特征，物種才能穩定存在。（2）變異：親代和子代之間以及子代的不同個體

2、之間的差異，稱為變異。變異是隨機發生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應性變異的個體被保留下來，不具有適應性變異的個體被淘汰，通過一代代的生存環境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變為新的物種。第3頁，共45頁，2022年，5月20日，7點13分，星期三 遺傳算法將“優勝劣汰，適者生存”的生物進化原理引入優化參數形成的編碼串聯群體中，按所選擇的適應度函數并通過遺傳中的復制、交叉及變異對個體進行篩選，使適適應度高的個體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優于上一代。這樣周而復始，群體中個體適應度不斷提高，直到滿足一定的條件。遺傳

3、算法的算法簡單，可并行處理，并能到全局最優解。第4頁，共45頁，2022年，5月20日，7點13分，星期三遺傳算法的基本操作為：（1）復制（Reproduction Operator） 復制是從一個舊種群中選擇生命力強的個體位串產生新種群的過程。具有高適應度的位串更有可能在下一代中產生一個或多個子孫。 復制操作可以通過隨機方法來實現。首先產生01之間均勻分布的隨機數，若某串的復制概率為40%，則當產生的隨機數在0.401.0之間時，該串被復制，否則被淘汰。第5頁，共45頁，2022年，5月20日，7點13分，星期三（2）交叉（Crossover Operator） 復制操作能從舊種群中選擇出優

4、秀者，但不能創造新的染色體。而交叉模擬了生物進化過程中的繁殖現象，通過兩個染色體的交換組合，來產生新的優良品種。 交叉的過程為：在匹配池中任選兩個染色體，隨機選擇一點或多點交換點位置；交換雙親染色體交換點右邊的部分，即可得到兩個新的染色體數字串。第6頁，共45頁，2022年，5月20日，7點13分，星期三 交叉體現了自然界中信息交換的思想。交叉有一點交叉、多點交叉、還有一致交叉、順序交叉和周期交叉。一點交叉是最基本的方法，應用較廣。它是指染色體切斷點有一處，例：第7頁，共45頁，2022年，5月20日，7點13分，星期三（3）變異(Mutation Operator) 變異運算用來模擬生物在自

5、然的遺傳環境中由于各種偶然因素引起的基因突變，它以很小的概率隨機地改變遺傳基因（表示染色體的符號串的某一位）的值。在染色體以二進制編碼的系統中，它隨機地將染色體的某一個基因由1變為0，或由0變為1。第8頁，共45頁，2022年，5月20日，7點13分，星期三 若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質量。為了在盡可能大的空間中獲得質量較高的優化解，必須采用變異操作。第9頁，共45頁，2022年，5月20日，7點13分，星期三二、 遺傳算法的特點 （1）遺傳算法是對參數的編碼進行操作，而非對參數本身，這就是使得

6、我們在優化計算過程中可以借鑒生物學中染色體和基因等概念，模仿自然界中生物的遺傳和進化等機理；（2）遺傳算法同時使用多個搜索點的搜索信息。傳統的優化方法往往是從解空間的單個初始點開始最優解的迭代搜索過程，單個搜索點所提供的信息不多，搜索效率不高，有時甚至使搜索過程局限于局部最優解而停滯不前。第10頁，共45頁，2022年，5月20日，7點13分，星期三 遺傳算法從由很多個體組成的一個初始群體開始最優解的搜索過程，而不是從一個單一的個體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。（3）遺傳算法直接以目標函數作為搜索信息。傳統的優化算法不僅需要利用目標函數值，而且需要目

7、標函數的導數值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標函數值變換來的適應度函數值，就可以確定進一步的搜索方向和搜索范圍，無需目標函數的導數值等其他一些輔助信息。第11頁，共45頁，2022年，5月20日，7點13分，星期三 遺傳算法可應用于目標函數無法求導數或導數不存在的函數的優化問題，以及組合優化問題等。（4）遺傳算法使用概率搜索技術。遺傳算法的選擇、交叉、變異等運算都是以一種概率的方式來進行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進化過程的進行，遺傳算法新的群體會更多地產生出許多新的優良的個體。第12頁，共45頁，2022年，5月20日，7點13分，星期三（5）遺傳算法在

8、解空間進行高效啟發式搜索，而非盲目地窮舉或完全隨機搜索；（6）遺傳算法對于待尋優的函數基本無限制，它既不要求函數連續，也不要求函數可微，既可以是數學解析式所表示的顯函數，又可以是映射矩陣甚至是神經網絡的隱函數，因而應用范圍較廣；（7）遺傳算法具有并行計算的特點，因而可通過大規模并行計算來提高計算速度，適合大規模復雜問題的優化。 第13頁，共45頁，2022年，5月20日，7點13分，星期三三、 遺傳算法的應用領域（1）函數優化。 函數優化是遺傳算法的經典應用領域，也是遺傳算法進行性能評價的常用算例。尤其是對非線性、多模型、多目標的函數優化問題，采用其他優化方法較難求解，而遺傳算法卻可以得到較好

9、的結果。第14頁，共45頁，2022年，5月20日，7點13分，星期三（2）組合優化。 隨著問題的增大，組合優化問題的搜索空間也急劇擴大，采用傳統的優化方法很難得到最優解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。第15頁，共45頁，2022年，5月20日，7點13分，星期三（3）生產調度問題 在很多情況下，采用建立數學模型的方法難以對生產調度問題進行精確求解。在現實生產中多采用一些經驗進行調度。遺傳算法是解決復雜調度問題的有效工具，在單件生產車間調度、流水線生產車間調度、生產規劃、任務分配等方面遺傳算法都得到

10、了有效的應用。第16頁，共45頁，2022年，5月20日，7點13分，星期三（4）自動控制。 在自動控制領域中有很多與優化相關的問題需要求解，遺傳算法已經在其中得到了初步的應用。例如，利用遺傳算法進行控制器參數的優化、基于遺傳算法的模糊控制規則的學習、基于遺傳算法的參數辨識、基于遺傳算法的神經網絡結構的優化和權值學習等。第17頁，共45頁，2022年，5月20日，7點13分，星期三（5）機器人 例如，遺傳算法已經在移動機器人路徑規劃、關節機器人運動軌跡規劃、機器人結構優化和行為協調等方面得到研究和應用。（6）圖像處理 遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優化計算。目前遺傳

11、算法已經在模式識別、圖像恢復、圖像邊緣特征提取等方面得到了應用。第18頁，共45頁，2022年，5月20日，7點13分，星期三4.1 遺傳算法的構成要素（1）染色體編碼方法 基本遺傳算法使用固定長度的二進制符號來表示群體中的個體，其等位基因是由二值符號集0,1所組成。初始個體基因值可用均勻分布的隨機值生成，如就可表示一個個體，該個體的染色體長度是18。四、 遺傳算法的優化設計第19頁，共45頁，2022年，5月20日，7點13分，星期三（2）個體適應度評價：基本遺傳算法與個體適應度成正比的概率來決定當前群體中每個個體遺傳到下一代群體中的概率多少。為正確計算這個概率，要求所有個體的適應度必須為正

12、數或零。因此，必須先確定由目標函數值J到個體適應度f之間的轉換規則。第20頁，共45頁，2022年，5月20日，7點13分，星期三（3）遺傳算子：基本遺傳算法使用下述三種遺傳算子： 選擇運算:使用比例選擇算子； 交叉運算:使用單點交叉算子； 變異運算:使用基本位變異算子或均勻變異算子。第21頁，共45頁，2022年，5月20日，7點13分，星期三（4）基本遺傳算法的運行參數 有下述4個運行參數需要提前設定：M：群體大小，即群體中所含個體的數量，一般取為20100；G：遺傳算法的終止進化代數，一般取為100500；Pc：交叉概率，一般取為0.40.99；Pm：變異概率，一般取為0.00010.1

13、。第22頁，共45頁，2022年，5月20日，7點13分，星期三一般可按下述步驟構造遺傳算法：第一步：確定決策變量及各種約束條件，即確定出個體的表現型X和問題的解空間；第二步：建立優化模型，即確定出目標函數的類型及數學描述形式或量化方法；4.2 遺傳算法的應用步驟第23頁，共45頁，2022年，5月20日，7點13分，星期三第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型x及遺傳算法的搜索空間；第四步：確定解碼方法，即確定出由個體基因型x到個體表現型X的對應關系或轉換方法；第五步：確定個體適應度的量化評價方法，即確定出由目標函數值到個體適應度的轉換規則；第六步：設計遺傳算子，即確定

14、選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法。第七步：確定遺傳算法的有關運行參數，即M,G,Pc,Pm等參數。第24頁，共45頁，2022年，5月20日，7點13分，星期三以上操作過程可以用圖1來表示。 圖1 遺傳算法流程圖 第25頁，共45頁，2022年，5月20日，7點13分，星期三利用遺傳算法求Rosenbrock函數的極大值五、 遺傳算法求函數極值第26頁，共45頁，2022年，5月20日，7點13分，星期三5.1 二進制編碼遺傳算法求函數極大值 求解該問題遺傳算法的構造過程：（1）確定決策變量和約束條件；（2）建立優化模型；（3）確定編碼方法 第27頁，共45頁，2022年，

15、5月20日，7點13分，星期三 用長度為10位的二進制編碼串來分別表示兩個決策變量x1,x2。10位二進制編碼串可以表示從0到1023之間的1024個不同的數，故將x1,x2的定義域離散化為1023個均等的區域，包括兩個端點在內共有1024個不同的離散點。 從離散點-2.048到離散點2.048 ，分別對應于從0000000000(0)到1111111111(1023)之間的二進制編碼。第28頁，共45頁，2022年，5月20日，7點13分，星期三 將x1,x2分別表示的兩個10位長的二進制編碼串連接在一起，組成一個20位長的二進制編碼串，它就構成了這個函數優化問題的染色體編碼方法。使用這種編

16、碼方法，解空間和遺傳算法的搜索空間就具有一一對應的關系。例如： 表示一個個體的基因型，其中前10位表示x1，后10位表示x2。第29頁，共45頁，2022年，5月20日，7點13分，星期三（4）確定解碼方法：解碼時需要將20位長的二進制編碼串切斷為兩個10位長的二進制編碼串，然后分別將它們轉換為對應的十進制整數代碼，分別記為y1和y2。 依據個體編碼方法和對定義域的離散化方法可知，將代碼y轉換為變量x的解碼公式為 例如，對個體第30頁，共45頁，2022年，5月20日，7點13分，星期三 它由兩個代碼所組成 上述兩個代碼經過解碼后，可得到兩個實際的值（5）確定個體評價方法：由于Rosenbro

17、ck函數的值域總是非負的，并且優化目標是求函數的最大值，故可將個體的適應度直接取為對應的目標函數值，即第31頁，共45頁，2022年，5月20日，7點13分，星期三選個體適應度的倒數作為目標函數（6）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（7）確定遺傳算法的運行參數：群體大小M=80，終止進化代數G=100，交叉概率Pc=0.60，變異概率Pm=0.10。 上述七個步驟構成了用于求函數極大值的優化計算基本遺傳算法。第32頁，共45頁，2022年，5月20日，7點13分，星期三 采用上述方法進行仿真，經過100步迭代，最佳樣本為即當 時，R

18、osenbrock函數具有極大值，極大值為3905.9。第33頁，共45頁，2022年，5月20日，7點13分，星期三 遺傳算法的優化過程是目標函數J和適應度函數F的變化過程。 由仿真結果可知，隨著進化過程的進行，群體中適應度較低的一些個體被逐漸淘汰掉，而適應度較高的一些個體會越來越多，并且它們都集中在所求問題的最優點附近，從而搜索到問題的最優解。第34頁，共45頁，2022年，5月20日，7點13分，星期三5.2 實數編碼遺傳算法求函數極大值求解該問題遺傳算法的構造過程：（1）確定決策變量和約束條件；（2）建立優化模型；（3）確定編碼方法：用2個實數分別表示兩個決策變量，分別將的定義域離散化

19、為從離散點-2.048到離散點2.048的Size個實數。第35頁，共45頁，2022年，5月20日，7點13分，星期三（4）確定個體評價方法： 個體的適應度直接取為對應的目標函數值，即 選個體適應度的倒數作為目標函數 第36頁，共45頁，2022年，5月20日，7點13分，星期三（5）設計遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子。（6）確定遺傳算法的運行參數：群體大小M=500，終止進化代數G=200，交叉概率Pc=0.90，采用自適應變異概率即變異概率與適應度有關，適應度越小，變異概率越大。 第37頁，共45頁，2022年，5月20日，7點1

20、3分，星期三 上述六個步驟構成了用于求函數Rosenbrock極大值的優化計算的實數編碼遺傳算法。 十進制編碼求函數Rosenbrock極大值。仿真程序見chap10_2.m。 仿真程序經過200步迭代，最佳樣本為即當 ， 時，函數具有極大值，極大值為3880.3。第38頁，共45頁，2022年，5月20日，7點13分，星期三六、 基于遺傳算法優化的RBF網絡逼近6.1 遺傳算法優化原理 在7.3節的RBF網絡逼近算法中，網絡權值、高斯函數的中心矢量和基寬向量的初值難以確定，如果這些參數選擇不當，會造成逼近精度的下降甚至RBF網絡的發散。采用遺傳算法可實現RBF網絡參數的優化。第39頁，共45頁，2022年，5月20日，7點13分，星期三 為獲取滿意的逼近精度，采用誤差絕對值指標作為參數選擇的最小目標函數。 式中， 為逼近的總步驟， 為第 步RBF網絡的逼近誤差。 在應用遺傳算法時，為了避免參數選取范圍過大，可以先按經驗選取一組參數，然后再在這組參數的周圍利用遺傳算法進行設計，從而大大減少初始尋優的盲目性，節約計算量。第40頁，共45頁，2022年，5月20日，7點13分，星期三6.2 仿真實例 使用RBF網絡逼近下列對象：