各種優(yōu)化算法求解函數(shù)優(yōu)化問(wèn)題.doc

1、各種優(yōu)化算法求解函數(shù)優(yōu)化問(wèn)題.doc 各種優(yōu)化算法求解函數(shù)優(yōu)化問(wèn)題 1. 遺傳算法 的簡(jiǎn)單介紹及流程 1.1 遺傳算法的基本原理 遺傳算法( genetic algorithm ,簡(jiǎn)稱 ga) 是近年來(lái)迅速發(fā)展起來(lái)的一種全新的隨機(jī)搜索優(yōu)化算法。與傳統(tǒng)搜索算法不同,遺傳算法從一組隨機(jī)產(chǎn)生的初始解(稱為群體)開(kāi)始搜索。群體中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解,稱為染色體。這些染色體在后續(xù)迭代中不斷進(jìn)化,稱為遺傳。遺傳算法主要通過(guò)交叉、變異、選擇運(yùn)算實(shí)現(xiàn)。交叉或變異運(yùn)算生成下一代染色體,稱為后代。染色體的好壞用適應(yīng)度來(lái)衡量。根據(jù)適應(yīng)度的大小從上一代和后代中選擇一定數(shù)量的個(gè)體,作為下一代群體,再繼續(xù)進(jìn)化,這樣經(jīng)

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

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

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

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

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

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

8、動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 （ （2 ）tablet 函數(shù)測(cè)試種群變化圖(-100,100) 第1代種群動(dòng)態(tài)變化圖 第50代種群動(dòng)態(tài)變化圖 第100代種群動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 （ （3 ）rosenbrock 測(cè)試函數(shù)的種群動(dòng)態(tài)變化圖 第1代種群動(dòng)態(tài)變化圖 第50代種群動(dòng)態(tài)變化圖 第100代種群動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 (4) griewank函數(shù)種群動(dòng)態(tài)變化圖 第1代種群動(dòng)態(tài)變化圖 第50代種群動(dòng)態(tài)變化圖 第100代種群動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 名稱 最優(yōu)值 最差值 目標(biāo)平均值 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 從上面的實(shí)驗(yàn)結(jié)果中，我們可以發(fā)現(xiàn)遺傳算法在求解函數(shù)優(yōu)化問(wèn)題時(shí)，對(duì)于大部分測(cè)試函數(shù)，搜索速度都比較快，能很快收斂到最優(yōu)解上，獲得的最優(yōu)解也比較好，因此是一種比較有效的優(yōu)化算法。 2. 粒子群算法求解函數(shù)優(yōu)化問(wèn)題 2.1 粒子群算法介

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

11、nl n n u l x , 1 , , £ £ Î 和 un 分別表示第 n 維空間的上下邊界；當(dāng)前速度表示為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 次迭代的個(gè)體極值點(diǎn)位置和全局極值點(diǎn)位置。c1,c2 為常數(shù)，稱為學(xué)習(xí)因子，用來(lái)調(diào)節(jié)向 pi 和 pg 方向飛行的最大步長(zhǎng)；r1,r2 是（0，1）上均勻分布的隨機(jī)數(shù)；式（1）中第一部分是粒子上一步的速度，表明粒子目前的狀態(tài)；第二部分是粒子對(duì)本身的思考，是認(rèn)知部分，粒子通過(guò)對(duì)本身位置的思考來(lái)調(diào)整自己下一步的速度和位置，這樣可以是粒子有足夠強(qiáng)的全局搜索能力，避免陷入局部最??；第三部分表示粒子通過(guò)與其他粒子之間進(jìn)行信息交流來(lái)更新自己的下一步。 2.2 基本粒子群算法流程 （1）在初

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

14、群求解函數(shù)優(yōu)化問(wèn)題時(shí)，采用實(shí)數(shù)編碼來(lái)表示解空間內(nèi)的粒子的位置，開(kāi)始時(shí)隨機(jī)初始化n個(gè)二維解空間內(nèi)的數(shù)據(jù)點(diǎn)，這些數(shù)據(jù)點(diǎn)對(duì)應(yīng)了每個(gè)粒子的位置。粒子的速度也是隨機(jī)產(chǎn)生的，與粒子的位置的維數(shù)相同。 2.3.2 適應(yīng)度函數(shù) 這里用測(cè)試函數(shù)作為目標(biāo)函數(shù)來(lái)對(duì)算法進(jìn)行評(píng)價(jià)，把每個(gè)粒子的位置帶入測(cè)試函數(shù)，得到每個(gè)粒子的適應(yīng)值，然后分別與粒子的個(gè)體極值以及種群中所有粒子的全局極值進(jìn)行比較，如果比當(dāng)前的個(gè)體極值好，就更新這個(gè)個(gè)體的個(gè)體極值的位置pbestpop以及對(duì)應(yīng)的個(gè)體極值pbestfit，如果比上一代得到的全局極值好，則更新當(dāng)代的全局極值的位置gbestpop以及對(duì)應(yīng)的全局極值gbestfit。 2.4 標(biāo)準(zhǔn)粒

15、子群算法的幾種改進(jìn)方法 慣性權(quán)重法：慣性權(quán)重 w 是與前一次速度有關(guān)的一個(gè)比例因子，其速度更新方程為： ) ( ) ( *2 2 1 11 kikgkikikikix p r c x p r c v v - + - + =+w 用慣性權(quán)重來(lái)控制前面的速度對(duì)當(dāng)前速度的影響，較大的 w 可以加強(qiáng) pso 的全局搜索能力，而較小的 w 能加強(qiáng)局部搜索能力?；镜?pso 可以看作 w=1，因此在迭代后期缺少局部搜索能力。通常取 w 為0.8,1.2之間的數(shù)。 2.5 5 粒子群算法測(cè)試函數(shù)結(jié)果 2.5 .1 利用標(biāo)準(zhǔn) pso 算法對(duì)測(cè)試函數(shù)結(jié)果 根據(jù)粒子群求解函數(shù)優(yōu)化算法的流程，編寫程序pso.m文

16、件，然后用函數(shù)來(lái)測(cè)試算法的好壞優(yōu)劣。下表中列出了常用的幾個(gè)測(cè)試函數(shù)： 對(duì)上表中幾個(gè)測(cè)試函數(shù)用標(biāo)準(zhǔn)粒子群算法求最優(yōu)值，設(shè)定群體規(guī)模為 50，最大速度vmax=0.5，迭代次數(shù) n=200，學(xué)習(xí)因子 c1=c2=2，畫出種群的動(dòng)態(tài)變化圖。 （1 1 ） quadric 函數(shù)狀態(tài)變化圖( (- - 100,100) 第1代種群變化圖 第50代種群變化圖 第100代種群變化圖 第200代種群變化圖 （2 2） ）rastrigin 的測(cè)試函數(shù)( (- - 5.12,5.12) 第49代種群動(dòng)態(tài)變化圖 第99代種群動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 （3 3 ） tablet 函數(shù)( (- - 100

17、,100) 第49代種群動(dòng)態(tài)變化圖 第99代種群動(dòng)態(tài)變化圖 第200代種群動(dòng)態(tài)變化圖 從以上三個(gè)函數(shù)的種群動(dòng)態(tài)變化圖可以看出，粒子在200代的時(shí)候已經(jīng)將近收斂于一個(gè)點(diǎn)了。 （4 4 ）標(biāo)準(zhǔn) pso 算法測(cè)試函數(shù)得到的結(jié)果 名稱 最優(yōu)值 最差值 目標(biāo)平均值 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 用改進(jìn)的粒子群算法測(cè)試函數(shù)運(yùn)行結(jié)果 （1）用帶慣性權(quán)重的粒子群來(lái)求解函數(shù)的最小值， w 的值是隨機(jī)生成的(0,1)之間的數(shù)。下表就是測(cè)試結(jié)果： 名稱 最優(yōu)值 最差值 目標(biāo)平均值 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)用帶收縮因子的改進(jìn)粒子群算法測(cè)試函數(shù)，收縮因子 l 取(0,1)之間的隨機(jī)數(shù)。測(cè)試結(jié) 果如下： 名稱 最優(yōu)值 最差值 目標(biāo)平均值 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. 模擬退火算法求解 函數(shù)優(yōu)化 問(wèn)題 4.1 模擬退火算法的基本原理和算法描述 1982 年，kirkpatrick 等將退火思想引入組合優(yōu)化的領(lǐng)域，提出了一種求解大規(guī)模組合優(yōu)化問(wèn)題，特別是 np 完全組合優(yōu)化問(wèn)題的有效近似解的算法模擬退火算法（simulated annealing algorithm），簡(jiǎn)稱為 sa。 模擬退火算法是在某一初溫下，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳

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

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

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