1、各種優化算法求解函數優化問題.doc 各種優化算法求解函數優化問題 1. 遺傳算法 的簡單介紹及流程 1.1 遺傳算法的基本原理 遺傳算法( genetic algorithm ,簡稱 ga) 是近年來迅速發展起來的一種全新的隨機搜索優化算法。與傳統搜索算法不同,遺傳算法從一組隨機產生的初始解(稱為群體)開始搜索。群體中的每個個體是問題的一個解,稱為染色體。這些染色體在后續迭代中不斷進化,稱為遺傳。遺傳算法主要通過交叉、變異、選擇運算實現。交叉或變異運算生成下一代染色體,稱為后代。染色體的好壞用適應度來衡量。根據適應度的大小從上一代和后代中選擇一定數量的個體,作為下一代群體,再繼續進化,這樣經

2、過若干代之后,算法收斂于最好的染色體,它很可能就是問題的最優解或次優解。遺傳算法中使用適應度這個概念來度量群體中的各個個體在優化計算中有可能達到最優解的優良程度。度量個體適應度的函數稱為適應度函數。適應度函數的定義一般與具體求解問題有關。 1.2 遺傳算法的流程 第一步：確定決策變量及各種約束條件，即確定出個體的表現型x和問題的解空間； 第二步：確定出目標函數的類型，即求目標函數的最大值還是最小值，以及其數學描述形式或量化方法，建立其優化模型； 第三步：確定表示可行解的染色體編碼方法，即確定出個體的基因型x和遺傳算法的搜索空間。 第四步：確定解碼方法，即確定出個體的基因型x和個體的表現型x的對

3、應關系或轉換方法； 第五步：確定個體時候適應度的量化評價方法，即確定出由目標函數f(x)值到個體適應度f(x)的轉換規則； 第六步：設計遺傳算子，即確定出選擇運算、交叉運算、變異運算等遺傳算子的具體操作方法； 第七步：確定出遺傳算法的運行參數，即確定出遺傳算法的m、t、pc、pm等參數。 1.3 遺傳算法求解函數優化問題 中的參數分析 目前，函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能評價的常用范例。對于函數優化中求解實數型變量的問題，一般采用動態編碼和實數編碼的方法來提高其搜索效率，所以是求解各類函數優化問題比較適合的算法。 1.3 .1 編碼方案 在用遺傳算法求解函數優化問題時

4、，把解空間中的數據點都映射到遺傳中對應的基因型數據，采用二進制編碼，在給定函數的變量上下界和編碼精度內，求得單個變量的編碼長度l ，然后隨機生成一些固定長度為 l 的二進制數作為作為初始種群。 1.3.2 適應度函數 先用解碼函數將二進制代碼轉換為解空間中的數據，把數據帶入測試函數中，得到種群中每個個體的適應值，然后以種群中函數值取得最大值的個體的函數值與每個個體的函數值之差，再與最大函數值的n倍(假設種群粒子數為n)和種群中所有個體的函數值之和的比值，得到每個個體的適應度。如果求函數最小值問題，則適應度值越大其函數值越小。 1.3.3 選擇算子 遺傳算法最常用的選擇策略就是正比選擇策略，即每

5、個個體被選中進行遺傳運算的概率為該個體的適應值和群體中所有個體適應值總和的比例。對于個體i，其適應度值為f i ，種群規模為np，則該個體的選擇概率可以表示為 å=npiiiiffp1 得到選擇概率后，采用旋輪法來實現選擇操作，令 pp 0 =0 å=ijj ipp pp1 共轉輪 np 次，每次轉輪時，隨機產生 ) 1 , 0 ( ukÎ x ，當 k ipp x £-1pp i ,則選擇個體 i。適應度越高的個體的選擇概率越大，越容易被選擇參與交叉變異運算。 1.3.4 交叉 算子 在遺傳算法中，最常用的交叉策略就是單點交叉和雙切點交叉。在這個算法中

6、，先從種群中隨機選擇兩個要進行交叉的個體，然后隨機生成一個數據點，對兩個父串中對應位的數值進行交換，得到兩個字串。 1.3.5 變異算子 變異是在種群中按照變異概率p m 任選若干基因位改變其位值，對于0-1編碼來說，就是反轉位值。在這個算法中，先在父串中隨機生成一個數，如果這個數對應的位值為0，則將它變為1；如果這個數上的位值為1，則將它變為0. 1.4 遺傳算法求解函數優化問題流程 step 1：初始化選擇、交叉、變異概率，設置初始代數和最大迭代次數，隨機生成若干個初始個體構成初始種群； step 2：利用解碼函數將初始種群的二進制編碼轉化為解空間中便于計算的數據，然后用測試函數以及適應度

7、函數求得每個個體的適應度。 step 3：采用輪盤賭選擇種群中的個體進行遺傳運算； step 4：對種群中的個體進行交叉，變異運算，產生下一代新的種群。 step 5：如果當前的迭代次數達到設置的最大迭代次數，則算法停止，進行step 6；若未達到最大迭代次數，則轉入step 2. step 6：保存種群中每一代的選擇函數值最小個體作為最優個體，并保存其對應的函數值。 1.5 測試函數運行結果 及算法參數對結果影響分析 1.5.1 各種函數測試結果 （1 1 ） quadric 函數 狀種群動態 變化圖( (- - 100,100) 第1代種群動態變化圖 第50代種群動態變化圖 第100代種群

8、動態變化圖 第200代種群動態變化圖 （ （2 ）tablet 函數測試種群變化圖(-100,100) 第1代種群動態變化圖 第50代種群動態變化圖 第100代種群動態變化圖 第200代種群動態變化圖 （ （3 ）rosenbrock 測試函數的種群動態變化圖 第1代種群動態變化圖 第50代種群動態變化圖 第100代種群動態變化圖 第200代種群動態變化圖 (4) griewank函數種群動態變化圖 第1代種群動態變化圖 第50代種群動態變化圖 第100代種群動態變化圖 第200代種群動態變化圖 名稱 最優值 最差值 目標平均值 tablet 2.2737e-009 0.2951 0.0015

9、 quadric 3.7719e-005 29.7138 1.7039 rosenbrock 1.7771e-007 3.8917 0.4625 griewank 0.0235 1.6926 0.0281 rastrigin 3.0273e-006 2.1965 0.0487 schaffers 2.0231e-010 1.0e-003* 0.9379 0.1470 從上面的實驗結果中，我們可以發現遺傳算法在求解函數優化問題時，對于大部分測試函數，搜索速度都比較快，能很快收斂到最優解上，獲得的最優解也比較好，因此是一種比較有效的優化算法。 2. 粒子群算法求解函數優化問題 2.1 粒子群算法介

10、紹 粒子群算法是一種基于迭代的優化方法。進行優化時，粒子在一個 n 維空間中搜索，每個粒子的位置對應于問題的一個解，粒子通過不斷調整自己的位置來搜索新解。每個粒子根據自己的飛行經驗和其他粒子的飛行經驗來調整自己的飛行。每個粒子在飛行過程所經歷的最好位置，就是粒子本身找到的最優解，稱為個體極值（p best ）;整個種群所經歷過的最好位置，就是整個群體目前找到的最優解，稱為全局極值（g best ）。每個粒子都通過上述兩個極值不斷更新自己，從而產生新一代群體。 設粒子的群體規模為 n，粒子當前的位置表示為 ) , ,., , (2 1 knknk k kix x x x x = ， n n nk

11、nl n n u l x , 1 , , £ £ Î 和 un 分別表示第 n 維空間的上下邊界；當前速度表示為kiknknk kiv v v v v ), ,., ,., (1= 被鉗位在最大值 ) ,., ,., (max, max, 1 max, maxknknk kv v v v = 和最小值) ,. ,. (m i n, m i n, 1 m i n, m i nknknk kv v v v = 之間，粒子的速度和位置更新方程如式（1）和式（2）所示： ) ( ) (2 2 1 11 kikgkikikikix p r c x p r c v v - +

12、 - + =+ （1） 1 1 + + =kikikiv x x （2） 其中，kgkip p , 分別表示粒子第 k 次迭代的個體極值點位置和全局極值點位置。c1,c2 為常數，稱為學習因子，用來調節向 pi 和 pg 方向飛行的最大步長；r1,r2 是（0，1）上均勻分布的隨機數；式（1）中第一部分是粒子上一步的速度，表明粒子目前的狀態；第二部分是粒子對本身的思考，是認知部分，粒子通過對本身位置的思考來調整自己下一步的速度和位置，這樣可以是粒子有足夠強的全局搜索能力，避免陷入局部最?。坏谌糠直硎玖Ｗ油ㄟ^與其他粒子之間進行信息交流來更新自己的下一步。 2.2 基本粒子群算法流程 （1）在初

13、始化范圍內，對粒子群進行隨機初始化，包括隨機位置和速度。 （2）計算每個粒子的適應值。 （3）對于每個粒子，將其適應值與所經歷過的最好位置的適應值進行比較，如果更好則將其作為粒子的個體歷史最優值，用當前位置更新個體歷史最好位置 （4）對每個粒子，將其歷史最優適應值與群體內或鄰域內所經歷的最好位置的適應值進行比較，若更好，則將其作為當前的全局最好位置。 （5）根據上面公式（1）和（2）更新粒子的速度和位置。 （6）若未達到終止條件，則進行步驟（2）。 一般將終止條件設定為一個足夠好的適應值或達到一個預設的最大迭代次數。 2.3 粒子群算法求解函數優化問題的參數分析 2.3.1 編碼方法 在用粒子

14、群求解函數優化問題時，采用實數編碼來表示解空間內的粒子的位置，開始時隨機初始化n個二維解空間內的數據點，這些數據點對應了每個粒子的位置。粒子的速度也是隨機產生的，與粒子的位置的維數相同。 2.3.2 適應度函數 這里用測試函數作為目標函數來對算法進行評價，把每個粒子的位置帶入測試函數，得到每個粒子的適應值，然后分別與粒子的個體極值以及種群中所有粒子的全局極值進行比較，如果比當前的個體極值好，就更新這個個體的個體極值的位置pbestpop以及對應的個體極值pbestfit，如果比上一代得到的全局極值好，則更新當代的全局極值的位置gbestpop以及對應的全局極值gbestfit。 2.4 標準粒

15、子群算法的幾種改進方法 慣性權重法：慣性權重 w 是與前一次速度有關的一個比例因子，其速度更新方程為： ) ( ) ( *2 2 1 11 kikgkikikikix p r c x p r c v v - + - + =+w 用慣性權重來控制前面的速度對當前速度的影響，較大的 w 可以加強 pso 的全局搜索能力，而較小的 w 能加強局部搜索能力。基本的 pso 可以看作 w=1，因此在迭代后期缺少局部搜索能力。通常取 w 為0.8,1.2之間的數。 2.5 5 粒子群算法測試函數結果 2.5 .1 利用標準 pso 算法對測試函數結果 根據粒子群求解函數優化算法的流程，編寫程序pso.m文

16、件，然后用函數來測試算法的好壞優劣。下表中列出了常用的幾個測試函數： 對上表中幾個測試函數用標準粒子群算法求最優值，設定群體規模為 50，最大速度vmax=0.5，迭代次數 n=200，學習因子 c1=c2=2，畫出種群的動態變化圖。 （1 1 ） quadric 函數狀態變化圖( (- - 100,100) 第1代種群變化圖 第50代種群變化圖 第100代種群變化圖 第200代種群變化圖 （2 2） ）rastrigin 的測試函數( (- - 5.12,5.12) 第49代種群動態變化圖 第99代種群動態變化圖 第200代種群動態變化圖 （3 3 ） tablet 函數( (- - 100

17、,100) 第49代種群動態變化圖 第99代種群動態變化圖 第200代種群動態變化圖 從以上三個函數的種群動態變化圖可以看出，粒子在200代的時候已經將近收斂于一個點了。 （4 4 ）標準 pso 算法測試函數得到的結果 名稱 最優值 最差值 目標平均值 tablet 6.9977e-010 0.0935 5.8828e-004 quadric 9.7719e-010 0.5134 0.0090 rosenbrock 1.1286e-008 2.0589e-007 0.0024 griewank 9.0223e-008 3.8537e-007 0.0051 rastrigin 2.0283e-

18、008 0.0874 0.0026 schaffers 5.6037e-009 8.4428e-006 8.8449e-007 2.4.2 用改進的粒子群算法測試函數運行結果 （1）用帶慣性權重的粒子群來求解函數的最小值， w 的值是隨機生成的(0,1)之間的數。下表就是測試結果： 名稱 最優值 最差值 目標平均值 tablet 2.9455e-010 0.0266 6.6766e-004 quadric 1.5761e-009 1.2119 0.0117 rosenbrock 1.4386-012 0.02568 0.02641 griewank 1.9839e-009 4.2095e-00

19、4 3.4790e-004 rastrigin 3.0255e-006 0.5047 0.0044 schaffers 2.3281e-007 1.1189e-006 4.1312e-005 (2)用帶收縮因子的改進粒子群算法測試函數，收縮因子 l 取(0,1)之間的隨機數。測試結 果如下： 名稱 最優值 最差值 目標平均值 tablet 1.0901e-005 2.3877 0.0192 quadric 1.2824e-006 1.7284e-005 9.2941e-004 rosenbrock 0.04891-004 0.0532-002 0.06364 griewank 1.5922e-

20、004 0.2197 0.0079 rastrigin 8.2416e-006 2.5299e-004 0.0106 schaffers 1.1029e-006 1.0096e-005 1.4717e-004 4. 模擬退火算法求解 函數優化 問題 4.1 模擬退火算法的基本原理和算法描述 1982 年，kirkpatrick 等將退火思想引入組合優化的領域，提出了一種求解大規模組合優化問題，特別是 np 完全組合優化問題的有效近似解的算法模擬退火算法（simulated annealing algorithm），簡稱為 sa。 模擬退火算法是在某一初溫下，伴隨溫度參數的不斷下降，結合概率突跳

21、特性在解空間中隨機尋找目標函數的全局最優解，在局部優解處能概率性地跳出并最終趨于全局最優。 基于 metropolis 接受準則的優化過程，可避免搜索過程陷于局部極小，并最終趨于問題的全局最優解。 模擬退火算法包括四個要素： （1）系統狀態(configuration)：即在某一個溫度下，系統產生的初始解，并當作目前的現行解。 (2)搜尋法則(search rule)：在退火的過程中，由目前系統狀態經由隨機擾動而產生變化跳至另一種狀態。一般而言，sa 較常用的有梯度搜尋法(gradient type) 和迭代改善法。 (3)成本函數(cost function)：用來衡量某一系統狀態下之能量函

22、數。 (4)退火程序(annealing process)：退火程序中包含的參數有初始溫度、降溫機制、冷卻率和終止溫度。在退火的過程中，在溫度高的時候，雖然是較差的目標值，但有可能被接受當成目前的目標值，但隨著溫度慢慢的降低，接受較差目標值的幾率逐漸降低。 4.2 模 模 擬退火算法求解 函數優化 問題算法分析 4.2.1 解空間 模擬退火算法的解空間是隨機生成若干個固定上下界的二維數據點，這里采用實數編 碼，這些數據點在迭代的過程中會不斷移動來尋找最優值。 4.2.2 目標函數 這里用測試函數作為目標函數來對算法進行評價，把每個粒子的位置帶入測試函數，得到每個粒子的適應值，在退火的過程中不斷

23、尋優，粒子不斷更新自己的位置，通過適應值大小的比較來尋找最優值。 4.2.3 算法流程 第 1 步：初始化：初始溫度 t，設定終止溫度 t 0 和馬爾科夫鏈長度 l，初始化每個粒子的位置。 第 2 步：用測試函數計算每個粒子的適應值。 第 3 步：對 k=1,l 做第 4 步至第 7 步； 第 4 步：對于初始的粒子位置和適應值進行隨機擾動，產生新解 s。 第 5 步：計算增量 t d =c（s）-c(s),其中 c(s)為適應度函數。 第 6 步：若 t d 0 則接受 s作為新的當前解，否則以概率 exp(- t d /t)接受 s作為當前粒子新的位置。 第 7 步： 如果滿足終止條件則輸出當前解作為最優解，結束程序。終止條件通常取為連續若干個新解都沒有被接