第二十三章現(xiàn)代優(yōu)化算法簡介分析

1、第二十三章現(xiàn)代優(yōu)化算法簡介1現(xiàn)代優(yōu)化算法簡介現(xiàn)代優(yōu)化算法是80年代初興起的啟發(fā)式算法。這些算法包括禁忌搜索(tabusearch),模擬退火(simulatedannealing),遺傳算法(geneticalgorithms),人工神經(jīng)網(wǎng)絡(luò)(neuralnetworks)。它們主要用于解決大量的實際應(yīng)用問題。目前，這些算法在理論和實際應(yīng)用方面得到了較大的發(fā)展。無論這些算法是怎樣產(chǎn)生的，它們有一個共同的目標(biāo)一求NP-hard組合優(yōu)化問題的全局最優(yōu)解。雖然有這些目標(biāo)，但NP-hard理論限制它們只能以啟發(fā)式的算法去求解實際問題。啟發(fā)式算法包含的算法很多，例如解決復(fù)雜優(yōu)化問題的蟻群算法(AntCo

2、lonyAlgorithms)o有些啟發(fā)式算法是根據(jù)實際問題而產(chǎn)生的，如解空間分解、解空間的限制等；另一類算法是集成算法，這些算法是諸多啟發(fā)式算法的合成?，F(xiàn)代優(yōu)化算法解決組合優(yōu)化問題，如TSP(TravelingSalesmanProblem)問題，QAP(QuadraticAssignmentProblem)問題，JSP(Job-shopSchedulingProblem)問題等效果很好。本章我們只介紹模擬退火算法，初步介紹一下蟻群算法，其它優(yōu)化算法可以參看相關(guān)的參考資料。2模擬退火算法算法簡介模擬退火算法得益于材料的統(tǒng)計力學(xué)的研究成果。統(tǒng)計力學(xué)表明材料中粒子的不同結(jié)構(gòu)對應(yīng)于粒子的不同能量水

3、平。在高溫條件下，粒子的能量較高，可以自由運動和重新排列。在低溫條件下，粒子能量較低。如果從高溫開始，非常緩慢地降溫(這個過程被稱為退火)，粒子就可以在每個溫度下達(dá)到熱平衡。當(dāng)系統(tǒng)完全被冷卻時，最終形成處于低能狀態(tài)的晶體。如果用粒子的能量定義材料的狀態(tài)，Metropolis算法用一個簡單的數(shù)學(xué)模型描述了退火過程。假設(shè)材料在狀態(tài)i之下的能量為E(i),那么材料在溫度T時從狀態(tài)i進(jìn)入狀態(tài)j就遵循如下規(guī)律：(1)如果E(j)E(i),接受該狀態(tài)被轉(zhuǎn)換。(2)如果E(j)E(i),則狀態(tài)轉(zhuǎn)換以如下概率被接受：E(i)E(j)eKT其中K是物理學(xué)中的波爾茲曼常數(shù)，T是材料溫度。在某一個特定溫度下，進(jìn)行了

4、充分的轉(zhuǎn)換之后，材料將達(dá)到熱平衡。這時材料處于狀態(tài)i的概率滿足波爾茲曼分布：Pt(x i)E( j)E(i)eKTeKTjS其中X表示材料當(dāng)前狀態(tài)的隨機(jī)變量，S表示狀態(tài)空間集合。顯然E(i)TimeKT|S|EJeKTS其中|S|表示集合度下降時，S中狀態(tài)的數(shù)量。這表明所有狀態(tài)在高溫下具有相同的概率。而當(dāng)溫E(i)EminTimoTmoe KTE(J) Emin e KT SE(i) Emi”e KTE(J) Emine KTSminlimT 0 e J Smin 1 | Smin | 0E(i) Emine ktE(J) EminKT其它E(J) Emin e KT J SminSminH中

5、EEminminE(j)且Smini|EEmin。JS上式表明當(dāng)溫度降至很低時，材料會以很大概率進(jìn)入最小能量狀態(tài)。假定我們要解決的問題是一個尋找最小值的優(yōu)化問題。將物理學(xué)中模擬退火的思想應(yīng)用于優(yōu)化問題就可以得到模擬退火尋優(yōu)方法?？紤]這樣一個組合優(yōu)化問題：優(yōu)化函數(shù)為F:xR,其中xS,它表示優(yōu)化問題的一個可行解，Ry|yR,y0,S表示函數(shù)的定義域。N(x)S表示x的一個鄰域集合。首先給定一個初始溫度解x N(x(0),是否接受To和該優(yōu)化問題的一個初始解x(0),并由x(0)生成下一個X作為一個新解P(x(0)x)1f(x) f(x(0)x(1)依賴于下面概率：若 f(x)f(x(0)換句話說

6、，如果生成的解其它x的函數(shù)值比前一個解的函數(shù)值更小，則接受 x(1) x作為f(x) f(x(0)一個新解。否則以概率 eTo接受X作為一個新解。泛泛地說，對于某一個溫度 Ti和該優(yōu)化問題的一個解 x(k),可以生成xo接受x 作為下一個新解x(k 1)的概率為：1P(x(k) x)f(x) f(x(k)若 f(x)f(x(k)(1)To其它在溫度工下，經(jīng)過很多次的轉(zhuǎn)移之后，降低溫度Ti ,得到Ti 1過程。因此整個優(yōu)化過程就是不斷尋找新解和緩慢降溫的交替過程。 題尋優(yōu)的結(jié)果。Ti。在Ti 1下重復(fù)上述 最終的解是對該問我們注意到，在每個 工下，所得到的一個新狀態(tài) x(k 1)完全依賴于前一個

7、狀態(tài)x(k),可以和前面的狀態(tài)x(0),x(k1)無關(guān)，因此這是一個馬爾可夫過程。使用馬爾可夫過程對上述模擬退火的步驟進(jìn)行分析，結(jié)果表明：從任何一個狀態(tài)x(k)生成x的概率，在N(x(k)中是均勻分布的，且新狀態(tài)x被接受的概率滿足式(1),那么經(jīng)過有限次的轉(zhuǎn)換，在溫度Ti下的平衡態(tài)xi的分布由下式給出:Pi (Ti)當(dāng)溫度T降為0時,ej Sxi的分布為：f (x。e Tf (xi)_ Ty(2)1* .P | Smin |0并且*Pi1xi Smin這說明如果溫度下降十分緩慢,若xiSmin其它而在每個溫度都有足夠多次的狀態(tài)轉(zhuǎn)移,使之在每一個溫度下達(dá)到熱平衡，則全局最優(yōu)解將以概率1被找到。因

8、此可以說模擬退火算法可以找到全局最優(yōu)解。在模擬退火算法中應(yīng)注意以下問題：(1)理論上，降溫過程要足夠緩慢，要使得在每一溫度下達(dá)到熱平衡。但在計算機(jī)實現(xiàn)中，如果降溫速度過緩，所得到的解的性能會較為令人滿意，但是算法會太慢，相對于簡單的搜索算法不具有明顯優(yōu)勢。如果降溫速度過快，很可能最終得不到全局最優(yōu)解。因此使用時要綜合考慮解的性能和算法速度，在兩者之間采取一種折衷。(2)要確定在每一溫度下狀態(tài)轉(zhuǎn)換的結(jié)束準(zhǔn)則。實際操作可以考慮當(dāng)連續(xù)m次的轉(zhuǎn)換過程沒有使?fàn)顟B(tài)發(fā)生變化時結(jié)束該溫度下的狀態(tài)轉(zhuǎn)換。最終溫度的確定可以提前定為一個較小的值Te,或連續(xù)幾個溫度下轉(zhuǎn)換過程沒有使?fàn)顟B(tài)發(fā)生變化算法就結(jié)束。(3)選擇初

9、始溫度和確定某個可行解的鄰域的方法也要恰當(dāng)。2.2應(yīng)用舉例例已知敵方100個目標(biāo)的經(jīng)度、緯度如下:經(jīng)度緯度經(jīng)度緯度經(jīng)度緯度經(jīng)度緯度53.712115.304651.17580.032246.325328.275330.33136.934856.543221.418810.819816.252922.789123.104510.158412.481920.105015.45621.94510.205726.495122.122131.48478.964026.241818.176044.035613.540128.983625.987938.472220.173128.269429.001132

10、.19105.869936.486329.72840.971828.147718.958624.663516.561823.614310.559715.117850.211110.29448.15199.532522.107518.55690.121518.872648.207716.888931.949917.63090.77320.465647.413423.778341.86713.566743.54743.906153.352426.725630.816513.459527.71335.070623.92227.630651.961222.851112.793815.73074.956

11、88.366921.505124.090915.254827.21116.20705.144249.243016.704417.116820.035434.168822.75719.44023.920011.581214.567752.11810.40889.555911.421924.45096.563426.721328.566737.584816.847435.66199.933324.46543.16440.77756.957614.470313.636819.866015.12243.16164.242818.524514.359858.684927.148539.516816.93

12、7156.508913.709052.521115.795738.43008.464851.818123.01598.998323.644050.115623.781613.79091.951034.057423.396023.06248.431919.98575.790240.880114.297858.828914.522918.66356.743652.842327.288039.949429.511447.509924.066410.112127.266228.781227.66598.083127.67059.155614.130453.79890.219933.64900.3980

13、1.349616.835949.98166.082819.363517.662236.954523.026515.732019.569711.511817.388444.039816.263539.713928.42036.990923.180438.339219.995024.654319.605736.998024.39924.15913.185340.140020.303023.98769.403041.108427.7149我方有一個基地，經(jīng)度和緯度為(70,40)。假設(shè)我方飛機(jī)的速度為1000公里/小時。我方派一架飛機(jī)從基地出發(fā)，偵察完敵方所有目標(biāo)，再返回原來的基地。在敵方每一目標(biāo)點

14、的偵察時間不計，求該架飛機(jī)所花費的時間(假設(shè)我方飛機(jī)巡航時間可以充分長)(這是一個旅行商問題。我們依次給基地編號為1,敵方目標(biāo)依次編號為2,3,101,最后我方基地再重復(fù)編號為102(這樣便于程序中計算)。距離矩陣D(dj)102102：其中dj表示表示i,j兩點的距離，i,j1,2,102,這里D為實對稱矩陣。則問題是求一個從點1出發(fā)，走遍所有中間點，到達(dá)點102的一個最短路徑。上面問題中給定的是地理坐標(biāo)(經(jīng)度和緯度)，我們必須求兩點間的實際距離。設(shè)A,B兩點的地理坐標(biāo)分別為(，y1)，(X2,y2),過A,B兩點的大圓的劣弧長即為兩點的實際距離。以地心為坐標(biāo)原點O,以赤道平面為XOY平面，

15、以0度經(jīng)線圈所在的平面為XOZ平面建立三維直角坐標(biāo)系。則A,B兩點的直角坐標(biāo)分別為：A(Rcosx1cosy1,Rsinx1cosy1,Rsiny1)B(Rcosx2cosy2,Rsinx2cosy2,Rsiny2)其中R6370為地球半徑。A,B兩點的實際距離Rarccos竺二OAOB化簡得dRarccoscos(x1x2)cosycosy2sinysiny2。求解的模擬退火算法描述如下：(1)解空間解空間S可表為1,2,101,102的所有固定起點和終點的循環(huán)排列集合，即S(1,102)|11,(2,101)為2,3,101的循環(huán)排列，102102其中每一個循環(huán)排列表示偵察100個目標(biāo)的一

16、個回路，ij表示在第i次偵察j點,初始解可選為(1,2,102),本文中我們使用MonteCarlo方法求得一個較好的初始解。(2)目標(biāo)函數(shù)此時的目標(biāo)函數(shù)為偵察所有目標(biāo)的路徑長度或稱代價函數(shù)。我們要求101minf(1,2,102)dii1i1而一次迭代由下列三步構(gòu)成：(3)新解的產(chǎn)生2變換法任選序號u,v(uv)交換u與v之間的順序，此時的新路徑為：1u1vv1u1uv11023變換法任選序號u,v和w，將u和v之間的路徑插到w之后，對應(yīng)的新路徑為(設(shè)uvw)1u1v1wuvw1102(4)代價函數(shù)差對于 2 變換法，路徑差可表示為f5)接受準(zhǔn)則P如果 f 0 ，路徑差可表示為(du1v d

17、uv1exp( f /T)則接受新的路徑。) (d du1 uf0f0否則， 以概率v v1exp( f /T) 接受新的路徑，即若exp(f/T)大于0至ij1之間的隨機(jī)數(shù)則接受。(6)降溫利用選定的降溫系數(shù)進(jìn)行降溫即：TT，得到新的溫度，這里我們?nèi)?.9999。(7)結(jié)束條件用選定的終止溫度e103,判斷退火過程是否結(jié)束。若Te,算法結(jié)束，輸出當(dāng)前狀態(tài)。我們編寫如下的matlab程序如下：clc,clearloadsj.txt%加載敵方100個目標(biāo)的數(shù)據(jù)，數(shù)據(jù)按照表格中的位置保存在純文本文件sj.txt中x=sj(:,1:2:8);x=x(:);y=sj(:,2:2:8);y=y(:);s

18、j=xy;d1=70,40;sj=d1;sj;d1;sj=sj*pi/180;%距離矩陣dd=zeros(102);fori=1:101forj=i+1:102temp=cos(sj(i,1)-sj(j,1)*cos(sj(i,2)*cos(sj(j,2)+sin(sj(i,2)*sin(sj(j,2);d(i,j)=6370*acos(temp);endendd=d+d;S0=;Sum=inf;rand(state,sum(clock);forj=1:1000S=11+randperm(100),102;temp=0;fori=1:101temp=temp+d(S(i),S(i+1);end

19、iftempSumS0=S;Sum=temp;endende=0.1A30;L=20000;at=0.999;T=1;%退火過程fork=1:L%產(chǎn)生新解c=2+floor(100*rand(1,2);c=sort(c);c1=c(1);c2=c(2);%計算代價函數(shù)值df=d(S0(c1-1),S0(c2)+d(S0(c1),S0(c2+1)-d(S0(c1-1),S0(c1)-d(S0(c2),S0(c2+1);%接受準(zhǔn)則ifdfrand(1)S0=S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102);Sum=Sum+df;endT=T*at;ifTebreak;end

20、end%輸出巡航路徑及路徑長度S0,Sum計算結(jié)果為44小時左右。其中的一個巡航路徑如下圖所示：3蟻群算法蟻群算法簡介蟻群是自然界中常見的一種生物，人們對螞蟻的關(guān)注大都是因為“蟻群搬家，天要下雨”之類的民諺。然而隨著近代仿生學(xué)的發(fā)展，這種似乎微不足道的小東西越來越多地受到學(xué)者們地關(guān)注。1991年意大利學(xué)者M(jìn).Dorigo等人首先提出了蟻群算法，人們開始了對蟻群的研究：相對弱小，功能并不強(qiáng)大的個體是如何完成復(fù)雜的工作的(如尋找到食物的最佳路徑并返回等)。在此基礎(chǔ)上一種很好的優(yōu)化算法逐步發(fā)展起來。蟻群算法的特點是模擬自然界中螞蟻的群體行為?？茖W(xué)家發(fā)現(xiàn)，蟻群總是能夠發(fā)現(xiàn)從蟻巢到食物源的最短路徑。經(jīng)研

21、究發(fā)現(xiàn)，螞蟻在行走過的路上留下一種揮發(fā)性的激素，螞蟻就是通過這種激素進(jìn)行信息交流。螞蟻趨向于走激素積累較多的路徑。找到最短路徑的螞蟻總是最早返回巢穴，從而在路上留下了較多的激素。由于最短路徑上積累了較多的激素，選擇這條路徑的螞蟻就會越來越多，到最后所有的螞蟻都會趨向于選擇這條最短路徑。基于螞蟻這種行為而提出的蟻群算法具有群體合作，正反饋選擇，并行計算等三大特點，并且可以根據(jù)需要為人工蟻加入前瞻、回溯等自然蟻所沒有的特點。在使用蟻群算法求解現(xiàn)實問題時，先生成具有一定數(shù)量螞蟻的蟻群，讓每一只螞蟻建立一個解或解的一部分，每只人工蟻從問題的初始狀態(tài)出發(fā)，根據(jù)“激素”濃度來選擇下一個要轉(zhuǎn)移到的狀態(tài)，直到

22、建立起一個解，每只螞蟻根據(jù)所找到的解的好壞程度在所經(jīng)過的狀態(tài)上釋放與解的質(zhì)量成正比例的“激素”。之后，每只螞蟻又開始新的求解過程，直到尋找到滿意解。為避免停滯現(xiàn)象，引入了激素更新機(jī)制。解決TSP問題的蟻群算法描述現(xiàn)以TSP問題的求解為例說明蟻群系統(tǒng)模型。首先引進(jìn)如下記號：n為城市的個數(shù)；m為蟻群中螞蟻的數(shù)量；dj為兩城市i和j之間距離；bi(t)為t時刻位于城市i的n螞蟻的個數(shù)，mbi(t)；j(t)為t時刻邊弧(i,j)的軌跡強(qiáng)度(即ij連線上殘留的i1信息量)，且設(shè)j(0)c(c為常數(shù))，i,j1,2,n,ij;j(t)為t時刻邊弧(i,j)的能見度，反映由城市i轉(zhuǎn)移到城市j的期望程度。根

23、據(jù)上述原理，螞蟻k(k1,2,m)在運動過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。與真實蟻群系統(tǒng)不同，人工蟻群系統(tǒng)具有一定的記憶功能。隨著時間的推移，以前留下的信息逐漸消逝，經(jīng)n個時刻，螞蟻完成一次循環(huán)，各路徑上信息量要作調(diào)整。由此得到下述的人工蟻群系統(tǒng)模型:1）設(shè)人工蟻群在并行地搜索TSP的解，并通過一種信息素做媒介相互通信，在每個結(jié)點上且和該結(jié)點相連的邊上以信息素量做搜索下一結(jié)點的試探依據(jù)，直到找到一個TSP問題的可行解。2）在時刻t人工蟻k由位置i轉(zhuǎn)移至位置j的轉(zhuǎn)移概率為ij （t） ij （t）Pik（t）iv（t）iv（t）v S0,其中參數(shù)為軌跡的相對重要性j Sj S0）;為能見

24、度的相對重要性(3)0); S為可行點集，即螞蟻 k下一步允許選擇的城市。分別反映了螞蟻在運動過程中所積累的信息及啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用。(4)3）當(dāng)m個人工蟻按（3）式找到了可行解，則將各邊的信息量用下式修改。即調(diào)整信息量的軌跡強(qiáng)度更新方程為j(t1)j(t)j,(0,1)mkijijk1其中ik為第k只螞蟻在本次循環(huán)中留在路徑（i,j）上的信息量；j為本次循環(huán)中路徑（i,j）上的信息量的增量；參數(shù)為軌跡的持久性；1為軌跡衰減度，表示信息消逝程度。對上述系統(tǒng)模型，采用人工蟻群方法求解的算法步驟可歸結(jié)為：step1：NC0（NC為迭代步數(shù)或搜索次數(shù)）；各j和j的初始化；將m個螞蟻置于n個頂點上。k ( k 1,2, ,m )step2：將各螞蟻的初