1、1引言 在復雜系統的優化計算過程中，傳統的確定性算法（如梯度法、共軛梯度法、牛頓法、擬牛頓法等）往往容易陷入局部極值點（如下圖）。為了有效地進行全局搜索，得到問題的全局最優解或次優解，人們受自然界、或具體問題的啟發提出了一些啟發式的隨機優化算法。 模擬退火算法； 遺傳算法等進化計算方法； 神經網絡算法； 蟻群算法等等。第1頁/共57頁2一、模擬退火算法 模擬退火算法最早由Metropolis于1953年提出，1983年Kirkpatrick等將其應用于優化問題。 1. 算法步驟 (1) 給定初溫t=t0，隨機產生初始狀態X(1)，令k=0; (2) Repeat (2.1) Repeat (2

2、.1.1) 產生新的狀態X(2) =Generate (X(1); (2.1.2) if random0,1min1,expC(X(1)-C(X(2)/tk X(1) = X(2); /這里C(X(1)為狀態X(1)的目標函數值 (2.2) Until 抽樣穩定準則滿足 (2.3) 退溫tk+1=update(tk),并令k=k+1; (3) Until 算法終止準則滿足; (4) 輸出結果第2頁/共57頁3一、模擬退火算法 2、 三函數、二準則（新狀態產生函數，新狀態接受函數，退溫函數，抽樣穩定準則和退火結束準則） 新狀態產生函數：通常用領域函數，并且盡可能使候選解遍布全部解空間。 狀態接受

3、函數：通常用概率的方式給出，遵循以下三原則： 1）在固定溫度下，接受使目標函數值下降的候選解的概率要大于使用目標函數值上升的候選解的概率； 2）隨著溫度的下降，接受使目標函數值上升的解的概率要逐漸減少； 3）當溫度趨于零時，只能接受目標函數值下降的解。 模擬退火算法通常采用min1,expC(X(1)-C(X(2)/tk作為狀態接受函數。第3頁/共57頁4一、模擬退火算法 退溫函數：tk+1k+1=tk k (01); 抽樣穩定規則：通常有三種方法: 1) 檢驗目標函數的均值是否穩定; 2) 連續若干步的目標值變化較小; 3) 按一定的步數抽樣. 退火結束準則：三種方法： 1) 設置終止溫度;

4、 2) 設置外循環迭代次數; 3) 算法搜索到的最優值連續若干步保持不變。第4頁/共57頁5二、勢能曲面變平算法 1. 勢能曲面變平（ELP）算法描述(1)(1)(1)(, )(, )(, )EtE XtkH XtX(1) 給定一個初始狀態給定一個初始狀態X(1)，令，令t=1，初始化直方圖函數，初始化直方圖函數 H(E, t)，設置溫度，設置溫度T，計算，計算E(X(1),t)，令最優解，令最優解 E= E(X(1),t)，計算，計算 ；(2) 更新當前狀態X(1)，產生新的狀態X（2）Generate(X(1)；(3) 計算 和 ，令(2)(, )E Xt(2)( (), )H EtX(2

5、)(2)(2)(, )(, )(, )EtE XtkH XtX(4) 如果 ，則接受X(2)，判斷E(X(2)E?(2)(1)(, )(, )E XtE Xt第5頁/共57頁6二、勢能曲面變平算法 若是，則令E= E(X(2), t)； 否則按下式決定是否接受X(2) ： random(0,1)106，則停止迭代，輸出E；否則， 令t=t+1，轉(2). 2. 對算法的理解 關鍵是：通過增加懲罰項，對目標函數進行修改，盡量避免重復訪問曾經訪問過的狀態。(1)(2)(, )(, )/BEtEtTkXX第6頁/共57頁7二、勢能曲面變平算法 3. 對算法的改進 1）提出好的狀態更新機制： 怎樣產生

6、新的狀態？最好具有搜索整個狀態空間的能力。具體來說： 可以針對具體問題提出一些啟發式策略； 或考慮與遺傳算法相結合； 或采用與禁忌搜索相結合的方法。 2）局部搜索：一旦產生一個新的狀態，就用某一確定性的算法（如梯度法）進一步搜索該狀態附近目標函數值更低的狀態。 3）將退溫機制加入算法 4）增加補充搜索過程：即以搜索到的最優解為初始狀態，再次執行勢能曲面變平法，或進行局部搜索。第7頁/共57頁8三、吸引盤填充算法 吸引盤填充算法是勢能曲面變平法與梯度法的結合。 1. 自適應步長的梯度算法 X2=X1-E(X1)h 其中h是自適應步長。第8頁/共57頁9三、吸引盤填充算法 2. 吸引盤填充(Bas

7、in Filling, BF)算法 BF算法是一種將隨機算法（ELP）與確定性算法（如梯度法）很好地結合起來的混合算法，其中隨機算法ELP用來進行全局搜索，提高采樣的多樣性和跳出局部極值點，梯度法則用來進行局部搜索，以便快速得到全局最優或新的能量更低的狀態。BF算法是一種高性能的全局優化方法。第9頁/共57頁10四. 應用：圓形packing問題 1. 問題提法 問題1：給定一個大小確定的圓形閉區域，以及M個可互不重疊地放進圓形區域中的小圓，這些小圓的半徑分別為R1, R2, , RM，問如何將這些小圓互不重疊地放進圓形區域中? 問題2：給定M個半徑分別是R1,R2,RM的小圓，問如何將這M個

8、小圓擺放在直角坐標系平面上，使得所有M個小圓形成的包絡圓(即圓形閉區域)的面積最小？ 11:1M22ijijij22iiMiMinimizeRSubjecttoxxyyRRxyRRi, jM第10頁/共57頁11四. 圓形packing問題 一個實例：第11頁/共57頁12四. 圓形packing問題 一個實例的布局結果第12頁/共57頁13四. 圓形packing問題 2. 問題背景 圓形Packing問題是NP難度問題，在玻璃、鋼板、木材、紙張和制衣等工程領域中有著廣泛的應用，在這些工程應用領域中人們常常遇到圓形物體的裁剪、下料及裝運問題。從實際應用的角度出發，人們開始尋找快速的近似啟發式

9、求解算法。 3. 研究現狀 Hifi和Hallah提出了動態、自適應二階段局部搜索算法。（Hifi M, MHallah R. European Journal of Operational Research, 2007） 此后，他們進一步改進該算法，提出了一個基于自適應和從頭開始策略的三階段近似求解算法（Hifi M, MHallah R. Computational Optimization and Applications, 2008 ）。 第13頁/共57頁14四. 圓形packing問題 Akeb 等給出了自適應的集束搜索算法（Akeb H. Hifi M, MHallah R. C

10、omputers and Operations Research, 2008 ) 在國內，黃文奇等提出了求解不等圓Packing問題的高效的擬物擬人算法。(Wang HQ, Huang WQ, Zhang QA, Xu DM. European Journal of Operational Research, 2002; Huang WQ, Kang Y. Annals of Operations Research 2004 Huang WQ, Li Y, Li CM, Xu RC. Computers and Operations Research, 2006 ) 張德富等將禁忌搜索算法與模

11、擬退火算法相結合，提出了圓形Packing問題的混合算法。(Zhang DF, Deng AS. Computers and Operations Research, 2008 ) 呂志鵬等將PERM算法與占角穴度算法相結合得到了求解圓形Packing問題的PERM算法。(L ZP, Huang WQ. Computers and Operations Research, 2008 ) 第14頁/共57頁15四. 圓形packing問題 4. 問題1的轉換 將所有給定的圓想象為光滑的具有彈性的圓餅；將圓形區域想象為一個圓形彈性容器，則M個小圓和圓形區域構成的系統的勢能為： 這里 表示第i個圓與

12、第j個圓之間的嵌入深度。 這樣，問題1轉化為優化問題： min E(X)，即要求求狀態X*使得E(X*)=0。 1=11( )MM2i,jijiE Xd+= +=邋, i jd第15頁/共57頁16四. 圓形packing問題第16頁/共57頁17四. 圓形packing問題 5. 實驗結果 測試集1（任意圓情況，14個算例中有9個得到新的世界紀錄）第17頁/共57頁18四. 圓形packing問題 測試集2（等圓情況，10個算例中有7個達到世界紀錄）第18頁/共57頁19四. 圓形packing問題 測試集3（不等圓情況）： 12個算例中有3個得到新的世界記錄。第19頁/共57頁203. 圓

13、形packing問題 350個圓的布局結果。第20頁/共57頁21五、禁忌搜索算法 （一）禁忌搜索（Tabu Search, 或Taboo Search, 簡記為TS）由Glover（1986年）提出。禁忌搜索最重要的思想是：標記已搜索到的局部最優的一些對象，并在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止），從而保證對不同的有效搜索途徑的探索。第21頁/共57頁22五、禁忌搜索算法 基本過程是：給定一個當前解（初始解）和一種鄰域，然后在當前解的鄰域中確定若干候選解；若最佳候選解對應的目標值優于“best so far”狀態，則忽視其禁忌特性，用其替換當前解和“best so far”狀

14、態，并將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則在候選解中選擇非禁忌的最佳狀態為新的當前解，而無視它與當前解的優劣，同時將相應的對象加入禁忌表，并修改禁忌表中各對象的任期；如此重復上述迭代搜索過程，直到滿足停止準則。第22頁/共57頁23五、禁忌搜索算法 （二）簡單禁忌搜索算法的步驟：（1）給定算法參數，隨機產生初始解x，置禁忌表為空。（2）判斷算法終止條件是否滿足？若是，則結束算法并輸出優化結果；否則，繼續以下步驟。（3）利用當前解x的鄰域函數產生其所有（或若干）鄰域解，并從中確定若干候選解。（4）對候選解判斷藐視準則是否滿足？若成立，則用滿足藐視準則的最佳

15、狀態y替換x成為新的當前解，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換“best so far”狀態，并修改禁忌表中各對象的任期，然后轉步驟（6）；否則，繼續以下步驟。（5）判斷候選解對應的各狀態的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時修改禁忌表中各對象的任期。（6）轉步驟（2）。第23頁/共57頁24五、禁忌搜索算法 （三）禁忌搜索的關鍵參數和操作 （1）初始解和適配值函數； （2）鄰域結構和禁忌對象； （3）候選解選擇； （4）禁忌表及其長度； （5）藐視準則； （6）其中搜索和分散搜索策略； （7）終止準則。 其中，鄰域函數是基于局部鄰域

16、搜索的思想，用于實現鄰域搜索；禁忌表和禁忌對象的設置，體現了算法避免迂回搜索的特點；藐視準則，則是對優良狀態的獎勵，它是對禁忌策略的一種放松。第24頁/共57頁25五、禁忌搜索算法 1、適配值函數 可以將目標函數直接作為適配值函數。也可以將目標函數的變形作為適配值函數，譬如對極小值問題可將狀態的適配值f(x)定義為M-c(x)或e-c(x)，其中M為一個足夠大正數，c(x)為目標值。 2、禁忌對象 所謂禁忌對象就是被置入禁忌表中的那些變化元素，而禁忌的目標則是為了盡量避免迂回搜索而多搜索一些有效的搜索途徑。通常，禁忌對象可選取狀態本身或狀態分量或適配值的變化等。第25頁/共57頁26五、禁忌搜

17、索算法(1) 以狀態本身或其變化作為禁忌對象是最簡單、最容易理解的途徑。具體而言，當狀態由x變化到狀態y時，將狀態y(或x-y的變化)視為禁忌對象，從而在一定條件下禁止了y(或x-y的變化)的再度出現。(2) 狀態的變化包含了狀態分量的變化，因此以狀態分量的變化為禁忌對象將擴大禁忌的范圍，并可減少相應的計算量。(3) 以適配值或其變化為禁忌對象。此時可將處于同一適配值的狀態視為相同狀態，該策略在函數優化中經常采用。第26頁/共57頁27五、禁忌搜索算法 3、禁忌長度和候選解 禁忌長度和候選解的大小是影響TS算法性能的兩個關鍵參數。所謂禁忌長度，即禁忌對象在不考慮藐視準則情況下不允許被選取的最大

18、次數（即對象在禁忌表中的任期），對象只有當其任期為0時才被解禁。禁忌長度t可以是固定的某個數（如t=3）；也可以是動態變化的，如根據搜索性能和問題特性設定禁忌長度的變化區間（如3,10等），而禁忌長度則可按照某種原則或公式在其區間內變化。 一般而言，當算法的性能動態下降較大時，說明算法當前的搜索能力比較強，也可能當前解附近極小解形成的“波谷”較深，從而可設置較大的禁忌長度來延續當前的搜索行為。第27頁/共57頁28五、禁忌搜索算法 候選解集則通常是當前狀態的領域解集的一個子集。在算法的構造和計算過程中，一方面要求計算量和存儲量盡量少，這就要求禁忌長度和候選解集盡量小；但是，禁忌長度過短將造成搜

19、索的循環，候選解集過小容易造成早熟收斂，即陷入局部極小。因此可以確定性或隨機性地在部分鄰域解中選取候選解，具體數據大小則可視問題特性和對算法的要求而定。第28頁/共57頁29五、禁忌搜索算法 4、藐視準則 在禁忌搜索算法中，可能會出現候選解全部禁忌，或者存在一個優于“best so far”狀態的禁忌候選解，此時藐視準則將使某些狀態解禁，以實現更高效的優化性能。下面是幾種常用的藐視準則。 （1）基于適配值的準則。若某個禁忌候選解的適配值優于”best so far”狀態，則解禁候選解為當前狀態和新的”best so far”狀態。 （2）基于搜索方向的準則。若禁忌對象上次被禁忌時使得適配值有所

20、改善，并且目前該禁忌對象對應的候選解的適配值優于當前解，則對該禁忌對象解禁。 （3）基于解鎖準則。若候選解均被禁忌，且不存在優于”best so far”狀態的候選解，則對候選解中最佳的候選解進行解禁，以繼續搜索。第29頁/共57頁30五、禁忌搜索算法 5、禁忌頻率 記憶禁忌頻率（或次數）是對禁忌屬性的一種補充，可放寬選擇決策對象的范圍。譬如，如果某個適配值頻繁出現，則可以推測算法陷入某種循環或某個極小點，或者說現有算法參數難以有助于發掘更好的狀態，進而適當對算法結構或參數作修改。 6、終止準則 （1）給定最大迭代步數。 （2）設定某個對象的最大禁忌頻率。即，若某個狀態、適配值等對象的禁忌頻率

21、超過某一閥值，則終止算法，其中也包括最佳適配值連續若干步保持不變的情況。 （3）設定適配值的偏離幅度。首先估計問題的下限，一旦算法中最佳適配值與下限的偏離值小于某規定幅度時，則終止搜索。第30頁/共57頁31六、遺傳算法 （一）遺傳算法(Genetic algorithm, GA) 遺傳算法是Holland于1975年受生物進化論的啟發而提出的。它將問題的求解表示為“染色體”的適者生存過程，通過“染色體”群的一代代不斷進化，包括復制、交叉和變異等操作，最終收斂到“最適應環境”的個體，從而求得問題的最優解或滿意解。第31頁/共57頁32六、遺傳算法 （二）遺傳算法的主要步驟：（1）隨機產生一組初

22、始個體，構成初始種群，并評價每個個體的適配值。（2）判斷算法收斂準則是否滿足。若滿足則輸出搜索結果；否則執行以下步驟。（3）根據適配值大小以一定方式執行復制操作。（4）按照交叉概率pc執行交叉操作。如random0,1pc（5）按照變異概率pm執行變異操作。如 random0,1pm（6）返回步驟（2）。第32頁/共57頁33六、遺傳算法第33頁/共57頁34六、遺傳算法 （三）算法關鍵參數與操作的設計 1、編碼 編碼就是將問題的解用一種碼來表示，從而將問題的狀態空間與GA的碼空間相對應。函數優化中，不同的碼長和碼制，對問題求解的精度和效率有很大影響。二進制編碼將問題的解用一個二進制串來表示，

23、十進制編碼將問題的解用一個十進制串來表示。而實數編碼將問題的解用一個實數來表示，實數編碼解決了編碼對算法精度和存儲量的影響，也便利于優化中引入問題的相關信息，它在高維復雜優化問題中得到廣泛應用。第34頁/共57頁35六、遺傳算法 2、適配值函數f(X)：如取f(X)=M-c(X)或1/(1+c(X)，其中M為大數，c(X)為目標函數值。 3、遺傳算子 復制操作是為了避免有效基因的損失，使高性能的個體得以更大的概率生存，從而提高全局收斂性和計算效率。最常用的方法是比例復制（如輪盤賭）和基于排名的復制。 交叉操作用于組合出新的個體，在解空間中進行有效的搜索，同時降低對有效模式的破壞概率。二進制編碼

24、中，單點交叉隨機確定一個交叉位置，然后對換相應的字串；多點交叉隨機確定多個交叉位置，然后對換相應的子串。12,niiiiiiuuuuuu第35頁/共57頁36六、遺傳算法 如：父串為(1011001)，(0010110)若單點交叉位置為4，則后代為(1011110)，(0010001)；若多點交叉位置為2，5，則后代為(1010101)，(0011010)。十進制編碼一樣處理。對于實數編碼則可采用算術交叉，即 =ax1+(1-a)x2， =ax2+(1-a)x1，其中a(0,1), x1,x2為父代個體， 和 為后代個體。 變異操作有利于增加種群的多樣性，克服交叉操作產生的后代適配值沒有達到最

25、優且不再進化而早熟收斂的缺陷。二進制或十進制編碼中通常采用替換式變異，即用另一種基因替換某位置原先的基因；實數編碼中通常采用擾動式變異，即對原先個體附加一定機制的擾動來實現變異。1x2x1x2x第36頁/共57頁37六、遺傳算法 4、算法參數 種群數目是影響算法優化性能的因素之一。通常，種群太小則不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題的可行解；種群太大時盡管可增加優化信息以阻止早熟收斂的發生，但無疑會增加計算量，從而使收斂時間太長。 交叉概率用于控制交叉操作的頻率。概率太大時，種群的更新很快，進而會使高適配值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而使搜索停滯不前。

26、 變異操作是加大種群多樣性的重要因素。通常一個較低的變異率足以防止整個群體中任一位置的基因一直保持不變。第37頁/共57頁38六、遺傳算法 5、算法的終止條件 最常用的終止條件就是事先給定一個最大進化步數，或者是判斷最佳優化值是否連續若干步沒有明顯變化。 總之，目前實際應用遺傳算法時，許多環節一般還只是憑經驗解決，盡管提出了許多針對各個環節進行的一些改進的遺傳算法：如對于復制操作，DeJong提出了回放和無回放式隨機采樣復制策略等；在交叉操作方面，Goldberg提出了部分匹配交叉算子等；在變異操作方面，一些學者提出了自適應變異、多級變異等操作；在函數優化方面，Goldberg引入分享思想將解

27、空間分成若干子空間，然后在子空間中產生子群體成員分別進行優化。此外還有人提出了基于小生境的遺傳算法，以及免疫遺傳算法等等。但GA的效率還有待于進一步研究。第38頁/共57頁39一些優化計算軟件 SNOPT（大規模線性、二次和非線性規劃）；MINOS（線性和非線性規劃）；LANCELOT(無約束最優化、非線性最小二乘、邊界約束最優化和一般約束最優化問題)； MINPACK(非線性方程組和非線性最小二乘問題)； PROC NLP(無約束最優化、非線性最小二乘、線性約束最優化、二次規劃和一般約束最優化問題)；CONOPT（非線性規劃）；FSQP（非線性規劃和極小極大問題）；GRG2（非線性規劃)；L

28、INDO（線性、二次和混合整數規劃）；LSSOL（最小二乘和二次規劃）；NLPJOB（非線性多目標規劃）； OPTPACK（約束和無約束最優化）；PETS（解非線性方程組和無約束問題的并行算法）；QPOPT（線性和二次規劃）；SQOPT（大規模線性和凸二次規劃）；SPRNLP（稀疏最小二乘,稀疏和稠密非線性規劃）；SYSFIT（非線性方程組的參數估計）；TENSOLVE（非線性方程組和最小二乘）等。第39頁/共57頁40七、支持向量機 1 支持向量機的基本思想 對于線性可分數據，隨機產生一個超平面并移動它，直到訓練集中屬于不同類別的樣本點正好位于該超平面的兩側。顯然，這種方法能夠解決線性分類問

29、題，但不能保證產生的超平面是最優的。 支持向量機建立的分類超平面能夠在保證分類精度的同時，使超平面兩側的空白區域最大化，從而實現對線性可分問題的最優分類 。第40頁/共57頁41七、支持向量機 1.1 最優超平面的概念 考慮P個線性可分樣本 對于任一輸入樣本Xp，其期望輸出為d p = ，分別代表兩類的類別標識。用于分類的超平面方程為：1122(,),(,),(,),(,)ppPPX dX dXdXd10(1)TWXb0,10,1TppTppWbdXWbdX 當當式中，X為輸入向量，W為權值向量，b為偏置，則有第41頁/共57頁42七、支持向量機 由式（1）定義的超平面與最近的樣本點之間的間隔

30、稱為分離邊緣，用 表示，支持向量機的目標是找到一個使分離邊緣最大的超平面，即最優超平面。如下圖：最優超平面支持向量第42頁/共57頁43七、支持向量機 假設最優超平面的方程為： 則樣本空間中任一點X到最優超平面的距離為： 從而有判別函數，g(X)=r|W0|= W0TXb0 將判別函數歸一化，使所有樣本滿足：000TXWb000TXWbrW00001,11,11,2,(2)TppTppWbdXpPWbdX 當當第43頁/共57頁44七、支持向量機 則對于離最優超平面最近的特殊樣本Xs滿足|g(Xs )|=1，稱為支持向量。 （2）式可表示為： 從支持向量到最優超平面的代數距離為：()1,1,2

31、,(3)pTpbpPdW X0001,1,W()1,1,WsssssdXgXrWdX 在最優超平面的正面在最優超平面的負面第44頁/共57頁45七、支持向量機 因此，兩類之間的間隔可用分離邊緣表示為： （4）式表明，要使分離邊緣最大化等價于使權值向量的范數 |W| 最小化。因此，滿足（3）式的條件且使 |W| 最小的分類超平面就是最優超平面。02(4)W第45頁/共57頁46七、支持向量機 1.2 最優超平面的構建 建立最優線性分類超平面問題可以表示成如下的約束優化問題。采用Lagrange系數方法解決此約束最優化問題，引入Lagrange函數211min()(5)22. .()11,2,Tp

32、TpWWW WstdW XbpP11(, , )()1(6)2min(, , )PTpTpppL W bW WdW XbL W b求第46頁/共57頁47七、支持向量機L(, ,)L(, ,)L(, ,)000W bW bW bWb令得：11(7)0()1()PppppPpppTppWd XdW Xb d 支持向量將（6）式展開：111111(, , )21212PPPTTpppppppppPTTppPTppL W bW WWd Xd bW WW WW W 第47頁/共57頁48七、支持向量機 將（7）式代入上式，則問題轉化為：1111max( )()2PPPp TjpjppjppjQXXd d 設Q（ )的最優解為010200,pP則最優超平面的權向量為：0001PpppppppWd Xd X所有支持向量最優分類判斷