隨機(jī)算法介紹課件

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

=Generate(X(1));(2.1.2)ifrandom[0,1]≤min{1,exp[C(X(1))-C(X(2))]/tk}X(1)=X(2);//這里C(X(1))為狀態(tài)X(1)的目標(biāo)函數(shù)值(2.2)Until抽樣穩(wěn)定準(zhǔn)則滿足(2.3)退溫tk+1=update(tk),并令k=k+1;(3)Until算法終止準(zhǔn)則滿足;(4)輸出結(jié)果3一、模擬退火算法③退溫函數(shù)：tk+1=λtk(0<λ<1);④抽樣穩(wěn)定規(guī)則：通常有三種方法:1)檢驗?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定;2)連續(xù)若干步的目標(biāo)值變化較小;3)按一定的步數(shù)抽樣.⑤退火結(jié)束準(zhǔn)則：三種方法：

1)設(shè)置終止溫度;2)設(shè)置外循環(huán)迭代次數(shù);3)算法搜索到的最優(yōu)值連續(xù)若干步保持不變。5二、勢能曲面變平算法1.勢能曲面變平（ELP）算法描述給定一個初始狀態(tài)X(1)，令t=1，初始化直方圖函數(shù)

H(E,t)，設(shè)置溫度T，計算E(X(1),t)，令最優(yōu)解

E’=

E(X(1),t)，計算；(2)更新當(dāng)前狀態(tài)X(1)，產(chǎn)生新的狀態(tài)X（2）＝Generate(X(1))；(3)計算和，令(4)如果，則接受X(2)，判斷E(X(2))<E’?6二、勢能曲面變平算法若是，則令E’=E(X(2),t)；否則按下式?jīng)Q定是否接受X(2)：random(0,1)<exp若X(2)被接受，則令X(1)=X(2),轉(zhuǎn)步驟(5)；否則恢復(fù)狀態(tài)X(1)，轉(zhuǎn)步驟(2).(5)如果t>106，則停止迭代，輸出E’；否則，令t=t+1，轉(zhuǎn)(2).2.對算法的理解關(guān)鍵是：通過增加懲罰項，對目標(biāo)函數(shù)進(jìn)行修改，盡量避免重復(fù)訪問曾經(jīng)訪問過的狀態(tài)。7三、吸引盤填充算法吸引盤填充算法是勢能曲面變平法與梯度法的結(jié)合。1.自適應(yīng)步長的梯度算法X2=X1-▽E(X1)?h其中h是自適應(yīng)步長。9三、吸引盤填充算法2.吸引盤填充(BasinFilling,BF)算法BF算法是一種將隨機(jī)算法（ELP）與確定性算法（如梯度法）很好地結(jié)合起來的混合算法，其中隨機(jī)算法ELP用來進(jìn)行全局搜索，提高采樣的多樣性和跳出局部極值點，梯度法則用來進(jìn)行局部搜索，以便快速得到全局最優(yōu)或新的能量更低的狀態(tài)。BF算法是一種高性能的全局優(yōu)化方法。10四.應(yīng)用：圓形packing問題1.問題提法問題1：給定一個大小確定的圓形閉區(qū)域，以及M個可互不重疊地放進(jìn)圓形區(qū)域中的小圓，這些小圓的半徑分別為R1,R2,…,RM，問如何將這些小圓互不重疊地放進(jìn)圓形區(qū)域中?問題2：給定M個半徑分別是R1,R2,…,RM的小圓，問如何將這M個小圓擺放在直角坐標(biāo)系平面上，使得所有M個小圓形成的包絡(luò)圓(即圓形閉區(qū)域)的面積最小？

11四.圓形packing問題一個實例的布局結(jié)果13四.圓形packing問題2.問題背景圓形Packing問題是NP難度問題，在玻璃、鋼板、木材、紙張和制衣等工程領(lǐng)域中有著廣泛的應(yīng)用，在這些工程應(yīng)用領(lǐng)域中人們常常遇到圓形物體的裁剪、下料及裝運問題。從實際應(yīng)用的角度出發(fā)，人們開始尋找快速的近似啟發(fā)式求解算法。3.研究現(xiàn)狀Hifi和Hallah提出了動態(tài)、自適應(yīng)二階段局部搜索算法。（HifiM,M’HallahR.

EuropeanJournalofOperationalResearch,2007）此后，他們進(jìn)一步改進(jìn)該算法，提出了一個基于自適應(yīng)和從頭開始策略的三階段近似求解算法（HifiM,M’HallahR.

ComputationalOptimizationandApplications,2008

）。

14四.圓形packing問題Akeb等給出了自適應(yīng)的集束搜索算法（AkebH.HifiM,M’HallahR.

ComputersandOperationsResearch,2008

)在國內(nèi)，黃文奇等提出了求解不等圓Packing問題的高效的擬物擬人算法。(WangHQ,HuangWQ,ZhangQA,XuDM.

EuropeanJournalofOperationalResearch,2002;HuangWQ,KangY.AnnalsofOperationsResearch

2004

HuangWQ,LiY,LiCM,XuRC.

ComputersandOperationsResearch,2006

)張德富等將禁忌搜索算法與模擬退火算法相結(jié)合，提出了圓形Packing問題的混合算法。(ZhangDF,DengAS.

ComputersandOperationsResearch,2008

)呂志鵬等將PERM算法與占角穴度算法相結(jié)合得到了求解圓形Packing問題的PERM算法。(LüZP,HuangWQ.

ComputersandOperationsResearch,2008

)15四.圓形packing問題17四.圓形packing問題5.實驗結(jié)果測試集1（任意圓情況，14個算例中有9個得到新的世界紀(jì)錄）18四.圓形packing問題測試集2（等圓情況，10個算例中有7個達(dá)到世界紀(jì)錄）193.圓形packing問題350個圓的布局結(jié)果。21五、禁忌搜索算法（一）禁忌搜索（TabuSearch,或TabooSearch,簡記為TS）由Glover（1986年）提出。禁忌搜索最重要的思想是：標(biāo)記已搜索到的局部最優(yōu)的一些對象，并在進(jìn)一步的迭代搜索中盡量避開這些對象（而不是絕對禁止），從而保證對不同的有效搜索途徑的探索。22五、禁忌搜索算法基本過程是：給定一個當(dāng)前解（初始解）和一種鄰域，然后在當(dāng)前解的鄰域中確定若干候選解；若最佳候選解對應(yīng)的目標(biāo)值優(yōu)于“bestsofar”狀態(tài)，則忽視其禁忌特性，用其替換當(dāng)前解和“bestsofar”狀態(tài)，并將相應(yīng)的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則在候選解中選擇非禁忌的最佳狀態(tài)為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時將相應(yīng)的對象加入禁忌表，并修改禁忌表中各對象的任期；如此重復(fù)上述迭代搜索過程，直到滿足停止準(zhǔn)則。23五、禁忌搜索算法（三）禁忌搜索的關(guān)鍵參數(shù)和操作

（1）初始解和適配值函數(shù)；（2）鄰域結(jié)構(gòu)和禁忌對象；（3）候選解選擇；（4）禁忌表及其長度；（5）藐視準(zhǔn)則；（6）其中搜索和分散搜索策略；（7）終止準(zhǔn)則。其中，鄰域函數(shù)是基于局部鄰域搜索的思想，用于實現(xiàn)鄰域搜索；禁忌表和禁忌對象的設(shè)置，體現(xiàn)了算法避免迂回搜索的特點；藐視準(zhǔn)則，則是對優(yōu)良狀態(tài)的獎勵，它是對禁忌策略的一種放松。25五、禁忌搜索算法1、適配值函數(shù)

可以將目標(biāo)函數(shù)直接作為適配值函數(shù)。也可以將目標(biāo)函數(shù)的變形作為適配值函數(shù)，譬如對極小值問題可將狀態(tài)的適配值f(x)定義為M-c(x)或e-c(x)，其中M為一個足夠大正數(shù)，c(x)為目標(biāo)值。2、禁忌對象所謂禁忌對象就是被置入禁忌表中的那些變化元素，而禁忌的目標(biāo)則是為了盡量避免迂回搜索而多搜索一些有效的搜索途徑。通常，禁忌對象可選取狀態(tài)本身或狀態(tài)分量或適配值的變化等。26五、禁忌搜索算法

候選解集則通常是當(dāng)前狀態(tài)的領(lǐng)域解集的一個子集。在算法的構(gòu)造和計算過程中，一方面要求計算量和存儲量盡量少，這就要求禁忌長度和候選解集盡量??；但是，禁忌長度過短將造成搜索的循環(huán)，候選解集過小容易造成早熟收斂，即陷入局部極小。因此可以確定性或隨機(jī)性地在部分鄰域解中選取候選解，具體數(shù)據(jù)大小則可視問題特性和對算法的要求而定。29五、禁忌搜索算法4、藐視準(zhǔn)則在禁忌搜索算法中，可能會出現(xiàn)候選解全部禁忌，或者存在一個優(yōu)于“bestsofar”狀態(tài)的禁忌候選解，此時藐視準(zhǔn)則將使某些狀態(tài)解禁，以實現(xiàn)更高效的優(yōu)化性能。下面是幾種常用的藐視準(zhǔn)則。（1）基于適配值的準(zhǔn)則。若某個禁忌候選解的適配值優(yōu)于”bestsofar”狀態(tài)，則解禁候選解為當(dāng)前狀態(tài)和新的”bestsofar”狀態(tài)。（2）基于搜索方向的準(zhǔn)則。若禁忌對象上次被禁忌時使得適配值有所改善，并且目前該禁忌對象對應(yīng)的候選解的適配值優(yōu)于當(dāng)前解，則對該禁忌對象解禁。（3）基于解鎖準(zhǔn)則。若候選解均被禁忌，且不存在優(yōu)于”bestsofar”狀態(tài)的候選解，則對候選解中最佳的候選解進(jìn)行解禁，以繼續(xù)搜索。30五、禁忌搜索算法5、禁忌頻率

記憶禁忌頻率（或次數(shù)）是對禁忌屬性的一種補(bǔ)充，可放寬選擇決策對象的范圍。譬如，如果某個適配值頻繁出現(xiàn)，則可以推測算法陷入某種循環(huán)或某個極小點，或者說現(xiàn)有算法參數(shù)難以有助于發(fā)掘更好的狀態(tài)，進(jìn)而適當(dāng)對算法結(jié)構(gòu)或參數(shù)作修改。6、終止準(zhǔn)則

（1）給定最大迭代步數(shù)。（2）設(shè)定某個對象的最大禁忌頻率。即，若某個狀態(tài)、適配值等對象的禁忌頻率超過某一閥值，則終止算法，其中也包括最佳適配值連續(xù)若干步保持不變的情況。（3）設(shè)定適配值的偏離幅度。首先估計問題的下限，一旦算法中最佳適配值與下限的偏離值小于某規(guī)定幅度時，則終止搜索。31六、遺傳算法（一）遺傳算法(Geneticalgorithm,GA)遺傳算法是Holland于1975年受生物進(jìn)化論的啟發(fā)而提出的。它將問題的求解表示為“染色體”的適者生存過程，通過“染色體”群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解或滿意解。32六、遺傳算法（二）遺傳算法的主要步驟：（1）隨機(jī)產(chǎn)生一組初始個體，構(gòu)成初始種群，并評價每個個體的適配值。（2）判斷算法收斂準(zhǔn)則是否滿足。若滿足則輸出搜索結(jié)果；否則執(zhí)行以下步驟。（3）根據(jù)適配值大小以一定方式執(zhí)行復(fù)制操作。（4）按照交叉概率pc執(zhí)行交叉操作。如random[0,1]<pc（5）按照變異概率pm執(zhí)行變異操作。如random[0,1]<pm（6）返回步驟（2）。33六、遺傳算法34六、遺傳算法（三）算法關(guān)鍵參數(shù)與操作的設(shè)計1、編碼編碼就是將問題的解用一種碼來表示，從而將問題的狀態(tài)空間與GA的碼空間相對應(yīng)。函數(shù)優(yōu)化中，不同的碼長和碼制，對問題求解的精度和效率有很大影響。二進(jìn)制編碼將問題的解用一個二進(jìn)制串來表示，十進(jìn)制編碼將問題的解用一個十進(jìn)制串來表示。而實數(shù)編碼將問題的解用一個實數(shù)來表示，實數(shù)編碼解決了編碼對算法精度和存儲量的影響，也便利于優(yōu)化中引入問題的相關(guān)信息，它在高維復(fù)雜優(yōu)化問題中得到廣泛應(yīng)用。35六、遺傳算法2、適配值函數(shù)f(X)：如取f(X)=M-c(X)或1/(1+c(X))，其中M為大數(shù)，c(X)為目標(biāo)函數(shù)值。3、遺傳算子復(fù)制操作是為了避免有效基因的損失，使高性能的個體得以更大的概率生存，從而提高全局收斂性和計算效率。最常用的方法是比例復(fù)制（如輪盤賭）和基于排名的復(fù)制。交叉操作用于組合出新的個體，在解空間中進(jìn)行有效的搜索，同時降低對有效模式的破壞概率。二進(jìn)制編碼中，單點交叉隨機(jī)確定一個交叉位置，然后對換相應(yīng)的字串；多點交叉隨機(jī)確定多個交叉位置，然后對換相應(yīng)的子串。36六、遺傳算法如：父串為{(1011001)，(0010110)}若單點交叉位置為4，則后代為{(1011110)，(0010001)}；若多點交叉位置為2，5，則后代為{(1010101)，(0011010)}。十進(jìn)制編碼一樣處理。對于實數(shù)編碼則可采用算術(shù)交叉，即=ax1+(1-a)x2，=ax2+(1-a)x1，其中a∈(0,1),x1,x2為父代個體，和為后代個體。變異操作有利于增加種群的多樣性，克服交叉操作產(chǎn)生的后代適配值沒有達(dá)到最優(yōu)且不再進(jìn)化而早熟收斂的缺陷。二進(jìn)制或十進(jìn)制編碼中通常采用替換式變異，即用另一種基因替換某位置原先的基因；實數(shù)編碼中通常采用擾動式變異，即對原先個體附加一定機(jī)制的擾動來實現(xiàn)變異。37六、遺傳算法4、算法參數(shù)種群數(shù)目是影響算法優(yōu)化性能的因素之一。通常，種群太小則不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題的可行解；種群太大時盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長。交叉概率用于控制交叉操作的頻率。概率太大時，種群的更新很快，進(jìn)而會使高適配值的個體很快被破壞掉；概率太小時，交叉操作很少進(jìn)行，從而使搜索停滯不前。變異操作是加大種群多樣性的重要因素。通常一個較低的變異率足以防止整個群體中任一位置的基因一直保持不變。38六、遺傳算法5、算法的終止條件最常用的終止條件就是事先給定一個最大進(jìn)化步數(shù)，或者是判斷最佳優(yōu)化值是否連續(xù)若干步?jīng)]有明顯變化?？傊?，目前實際應(yīng)用遺傳算法時，許多環(huán)節(jié)一般還只是憑經(jīng)驗解決，盡管提出了許多針對各個環(huán)節(jié)進(jìn)行的一些改進(jìn)的遺傳算法：如對于復(fù)制操作，DeJong提出了回放和無回放式隨機(jī)采樣復(fù)制策略等；在交叉操作方面，Goldberg提出了部分匹配交叉算子等；在變異操作方面，一些學(xué)者提出了自適應(yīng)變異、多級變異等操作；在函數(shù)優(yōu)化方面，Goldberg引入分享思想將解空間分成若干子空間，然后在子空間中產(chǎn)生子群體成員分別進(jìn)行優(yōu)化。此外還有人提出了基于小生境的遺傳算法，以及免疫遺傳算法等等。但GA的效率還有待于進(jìn)一步研究。39一些優(yōu)化計算軟件SNOPT（大規(guī)模線性、二次和非線性規(guī)劃）；MINOS（線性和非線性規(guī)劃）；LANCELOT(無約束最優(yōu)化、非線性最小二乘、邊界約束最優(yōu)化和一般約束最優(yōu)化問題)；MINPACK(非線性方程組和非線性最小二乘問題)；PROCNLP(無約束最優(yōu)化、非線性最小二乘、線性約束最優(yōu)化、二次規(guī)劃和一般約束最優(yōu)化問題)；CONOPT（非線性規(guī)劃）；FSQP（非線性規(guī)劃和極小極大問題）；GRG2（非線性規(guī)劃)；LINDO（線性、二次和混合整數(shù)規(guī)劃）；LSSOL（最小二乘和二次規(guī)劃）；NLPJOB（非線性多目標(biāo)規(guī)劃）；OPTPACK（約束和無約束最優(yōu)化）；PETS（解非線性方程組和無約束問題的并行算法）；QPOPT（線性和二次規(guī)劃）；SQOPT（大規(guī)模線性和凸二次規(guī)劃）；SPRNLP（稀疏最小二乘,稀疏和稠密非線性規(guī)劃）；SYSFIT（非線性方程組的參數(shù)估計）；TENSOLVE（非線性方程組和最小二乘）等。40七、支持向量機(jī)§1支持向量機(jī)的基本思想對于線性可分?jǐn)?shù)據(jù)，隨機(jī)產(chǎn)生一個超平面并移動它，直到訓(xùn)練集中屬于不同類別的樣本點正好位于該超平面的兩側(cè)。顯然，這種方法能夠解決線性分類問題，但不能保證產(chǎn)生的超平面是最優(yōu)的。支持向量機(jī)建立的分類超平面能夠在保證分類精度的同時，使超平面兩側(cè)的空白區(qū)域最大化，從而實現(xiàn)對線性可分問題的最優(yōu)分類。41七、支持向量機(jī)§1.1最優(yōu)超平面的概念考慮P個線性可分樣本對于任一輸入樣本Xp，其期望輸出為dp

=，分別代表兩類的類別標(biāo)識。用于分類的超平面方程為：式中，X為輸入向量，W為權(quán)值向量，b為偏置，則有42七、支持向量機(jī)由式（1）定義的超平面與最近的樣本點之間的間隔稱為分離邊緣，用表示，支持向量機(jī)的目標(biāo)是找到一個使分離邊緣最大的超平面，即最優(yōu)超平面。如下圖：最優(yōu)超平面支持向量43七、支持向量機(jī)假設(shè)最優(yōu)超平面的方程為：則樣本空間中任一點X到最優(yōu)超平面的距離為：從而有判別函數(shù)，g(X)=r||W0||=W0TX＋b0將判別函數(shù)歸一化，使所有樣本滿足：44七、支持向量機(jī)則對于離最優(yōu)超平面最近的特殊樣本Xs滿足|g(Xs)|=1，稱為支持向量。

（2）式可表示為：從支持向量到最優(yōu)超平面的代數(shù)距離為：45七、支持向量機(jī)因此，兩類之間的間隔可用分離邊緣表示為：

（4）式表明，要使分離邊緣最大化等價于使權(quán)值向量的范數(shù)||W||最小化。因此，滿足（3）式的條件且使||W||最小的分類超平面就是最優(yōu)超平面。46七、支持向量機(jī)§1.2最優(yōu)超平面的構(gòu)建建立最優(yōu)線性分類超平面問題可以表示成如下的約束優(yōu)化問題。采用Lagrange系數(shù)方法解