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

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

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

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

4、充分的轉換之后，材料將達到熱平衡。這時材料處于狀態(tài)i的概率滿足波爾茲曼分布：Pt(x i)E( j)E(i)eKTeKTjS其中X表示材料當前狀態(tài)的隨機變量，S表示狀態(tài)空間集合。顯然E(i)TimeKT|S|EJeKTS其中|S|表示集合度下降時，S中狀態(tài)的數量。這表明所有狀態(tài)在高溫下具有相同的概率。而當溫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上式表明當溫度降至很低時，材料會以很大概率進入最小能量狀態(tài)。假定我們要解決的問題是一個尋找最小值的優(yōu)化問題。將物理學中模擬退火的思想應用于優(yōu)化問題就可以得到模擬退火尋優(yōu)方法?？紤]這樣一個組合優(yōu)化問題：優(yōu)化函數為F:xR,其中xS,它表示優(yōu)化問題的一個可行解，Ry|yR,y0,S表示函數的定義域。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的函數值比前一個解的函數值更小，則接受 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其它在溫度工下，經過很多次的轉移之后，降低溫度Ti ,得到Ti 1過程。因此整個優(yōu)化過程就是不斷尋找新解和緩慢降溫的交替過程。 題尋優(yōu)的結果。Ti。在Ti 1下重復上述 最終的解是對該問我們注意到，在每個 工下，所得到的一個新狀態(tài) x(k 1)完全依賴于前一個

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

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

9、始溫度和確定某個可行解的鄰域的方法也要恰當。2.2應用舉例例已知敵方100個目標的經度、緯度如下:經度緯度經度緯度經度緯度經度緯度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我方有一個基地，經度和緯度為(70,40)。假設我方飛機的速度為1000公里/小時。我方派一架飛機從基地出發(fā)，偵察完敵方所有目標，再返回原來的基地。在敵方每一目標點

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

15、以0度經線圈所在的平面為XOZ平面建立三維直角坐標系。則A,B兩點的直角坐標分別為：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個目標的一

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

17、uv1exp( f /T)則接受新的路徑。) (d du1 uf0f0否則， 以概率v v1exp( f /T) 接受新的路徑，即若exp(f/T)大于0至ij1之間的隨機數則接受。(6)降溫利用選定的降溫系數進行降溫即：TT，得到新的溫度，這里我們取0.9999。(7)結束條件用選定的終止溫度e103,判斷退火過程是否結束。若Te,算法結束，輸出當前狀態(tài)。我們編寫如下的matlab程序如下：clc,clearloadsj.txt%加載敵方100個目標的數據，數據按照表格中的位置保存在純文本文件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%產生新解c=2+floor(100*rand(1,2);c=sort(c);c1=c(1);c2=c(2);%計算代價函數值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);%接受準則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計算結果為44小時左右。其中的一個巡航路徑如下圖所示：3蟻群算法蟻群算法簡介蟻群是自然界中常見的一種生物，人們對螞蟻的關注大都是因為“蟻群搬家，天要下雨”之類的民諺。然而隨著近代仿生學的發(fā)展，這種似乎微不足道的小東西越來越多地受到學者們地關注。1991年意大利學者M.Dorigo等人首先提出了蟻群算法，人們開始了對蟻群的研究：相對弱小，功能并不強大的個體是如何完成復雜的工作的(如尋找到食物的最佳路徑并返回等)。在此基礎上一種很好的優(yōu)化算法逐步發(fā)展起來。蟻群算法的特點是模擬自然界中螞蟻的群體行為。科學家發(fā)現，蟻群總是能夠發(fā)現從蟻巢到食物源的最短路徑。經研

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

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

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

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