智能優(yōu)化理論-第19章智能優(yōu)化方法的統(tǒng)一框架

第19章智能優(yōu)化方法的統(tǒng)一框架引言混沌優(yōu)化算法的迭代結(jié)構(gòu)遺傳算法的迭代結(jié)構(gòu)模擬退火算法的迭代結(jié)構(gòu)蟻群優(yōu)化算法的迭代結(jié)構(gòu)標(biāo)準(zhǔn)粒子群優(yōu)化算法的迭代結(jié)構(gòu)梯度下降法的迭代結(jié)構(gòu)復(fù)習(xí)思考題contents目錄01引言關(guān)于智能優(yōu)化方法的統(tǒng)一框架，目前多數(shù)研究都是針對進(jìn)化算法提出的。Eiben和Aarts等1995年提出一種通用搜索程序(GeneralSearchProcedure)，為描述遺傳算法、模擬退火算法、爬山法、深度優(yōu)先搜索和廣度優(yōu)先搜索等迭代搜索算法提供了一個(gè)統(tǒng)一框架，其中定義了7個(gè)要素。Eiben和Smith于2003年提出一種包含6個(gè)要素的通用框架，其中包括解的表示、解的評價(jià)、種群、父體選擇機(jī)制、重組和變異算子、選擇／替換機(jī)制。引言Taillard等通過對禁忌搜索、遺傳算法、蟻群算法等元啟發(fā)方法(Meta-heuristics)的分析發(fā)現(xiàn)，這些算法的實(shí)現(xiàn)非常相似，并提出一種叫做“適應(yīng)性記憶規(guī)劃”(AdaptiveMemoryProgramming，AMP)的統(tǒng)一算法框架。AMP框架通過記憶機(jī)制來構(gòu)造新解，通過改進(jìn)機(jī)制來搜索更優(yōu)解，并利用改進(jìn)的解產(chǎn)生的知識來更新記憶。Talbi從設(shè)計(jì)空間和實(shí)現(xiàn)空間兩個(gè)角度出發(fā)，提出一種混合算法的通用分類方法。引言引言010203劉波等從社會(huì)協(xié)作、自適應(yīng)和競爭3個(gè)層面為基于種群的元啟發(fā)式算法建立一種統(tǒng)一框架，并采用Markov鏈對統(tǒng)一算法模型進(jìn)行收斂性分析。辛斌等在對差分進(jìn)化算法和粒子群優(yōu)化算法的混合算法進(jìn)行全面綜述和分析的基礎(chǔ)上，提出一種包含母體算法關(guān)系、混合層次、操作順序、信息傳遞類型和傳遞信息類型5層次的通用混合策略分類法。把搜索優(yōu)化算法產(chǎn)生的解視為采樣點(diǎn)，那么搜索優(yōu)化算法可以視為一種迭代生成新的采樣點(diǎn)的過程，其中描述新采樣點(diǎn)生成方法的迭代算子或迭代函數(shù)就是最能反映算法本質(zhì)的要素。用G表示迭代算子或迭代函數(shù)，那么G的性質(zhì)就決定了算法的性質(zhì)。例如，如果G是確定性算子，那么迭代過程就是確定性的，相應(yīng)的算法就是確定性算法；如果G是隨機(jī)算子，那么迭代過程就是隨機(jī)性的，相應(yīng)的算法就是隨機(jī)性算法。對于G的分析而言，更重要的因素是它的實(shí)現(xiàn)所需利用的信息。引言02混沌優(yōu)化算法的迭代結(jié)構(gòu)混沌優(yōu)化算法的迭代結(jié)構(gòu)01混沌搜索過程的采樣只利用相鄰次序采樣的解信息，不包含評價(jià)值信息。02迭代過程包括兩個(gè)階段，第一階段是在整個(gè)搜索空間中隨機(jī)采樣，找到當(dāng)前最優(yōu)解的鄰域；03第二階段是在第一階段找到的當(dāng)前最優(yōu)解的鄰域內(nèi)執(zhí)行小范圍的混沌搜索。04搜索方法與第一階段無實(shí)質(zhì)性差異，故第二階段在縮小搜索范圍后仍然采用此式所示的迭代形式。03遺傳算法的迭代結(jié)構(gòu)經(jīng)典遺傳算法的迭代過程涉及交叉、變異和選擇3種算予。對于任何一個(gè)新的解（個(gè)體），用于產(chǎn)生該解的信息來自于上一代種群（父代）。父代個(gè)體參與選擇（復(fù)制）操作，然后隨機(jī)選擇的兩個(gè)個(gè)體執(zhí)行交叉操作，交叉后的個(gè)體繼續(xù)變異產(chǎn)生新解。遺傳算法的迭代結(jié)構(gòu)由于父代個(gè)體是隨機(jī)選擇的，每個(gè)個(gè)體都可能被選中，因此迭代算子利用的信息為<Xk-1，F(xiàn)(Xk-1)>。Xk-1不是單個(gè)解，而是第k-l代的所有解，而F(Xk-1)對應(yīng)于這些解的評價(jià)信息。如果分別用S、C、M表示選擇算子、交叉算子和變異算子，那么遺傳算法的迭代過程可以表示為如下形式：GAs是復(fù)合式算子，表示選擇、交叉和變異算子依次作用于上一代生成的解；X0為算法初始種群中的所有解；Pk包含種群規(guī)模、交叉概率和變異概率3個(gè)基本參數(shù)。遺傳算法的迭代結(jié)構(gòu)種群規(guī)模是一個(gè)特殊參數(shù)，是所有群搜索算法的共有參數(shù)。與一般參數(shù)不同，種群規(guī)模的變化會(huì)明顯改變迭代過程。由上式容易發(fā)現(xiàn)，遺傳算法的迭代中并未包含PSI，因?yàn)檫z傳算法不依賴于問題的特定信息。大多數(shù)智能優(yōu)化算法都具有這種特征，這是智能優(yōu)化算法具有較好通用性的重要原因之一。經(jīng)典遺傳算法采用固定參數(shù)，而參數(shù)自適應(yīng)遺傳算法采用參數(shù)動(dòng)態(tài)或適應(yīng)性調(diào)節(jié)策略。遺傳算法的迭代結(jié)構(gòu)04模擬退火算法的迭代結(jié)構(gòu)模擬退火算法的迭代結(jié)構(gòu)01在經(jīng)典模擬退火算法的迭代過程中，主要步驟包括產(chǎn)生新狀態(tài)和狀態(tài)更新。02產(chǎn)生新狀態(tài)依賴于狀態(tài)產(chǎn)生函數(shù)，通常在當(dāng)前狀態(tài)的鄰域結(jié)構(gòu)內(nèi)以一定概率方式生成。狀態(tài)更新依靠狀態(tài)接受函數(shù)，也以概率的方式給出，并且與溫度有關(guān)。03模擬退火算法的迭代結(jié)構(gòu)參數(shù)空間的迭代簡化為；為模擬退火算法的迭代算子；yk表示第k次迭代時(shí)的當(dāng)前狀態(tài)。分別以Tk和yk表示狀態(tài)產(chǎn)生函數(shù)和狀態(tài)接受函數(shù)，則模擬退火算法的迭代過程可以表示為如下形式：其中，Tk為第k次迭代時(shí)的溫度值，常見的溫度調(diào)控策略將Tk設(shè)為k的單調(diào)遞減函數(shù)或指數(shù)函數(shù)。y0=x0，x0為初始解。05蟻群優(yōu)化算法的迭代結(jié)構(gòu)蟻群優(yōu)化算法的4個(gè)主要參數(shù)構(gòu)成一個(gè)向量，通常這些參數(shù)采用固定設(shè)置。GACO為蟻群優(yōu)化算法的迭代算子，實(shí)質(zhì)上是一種基于概率模型進(jìn)行隨機(jī)采樣的算子，其中只包含生成算子，不包含選擇算子。算法采用的概率模型蘊(yùn)含了采樣過程中產(chǎn)生的所有解的信息（即SIk），這是因?yàn)槊恐晃浵佋诋a(chǎn)生新解的過程中都留下了“信息素”，信息量的更新公式中記憶了歷史信息，歷史采樣點(diǎn)對應(yīng)的適應(yīng)值等信息都蘊(yùn)含在概率模型中。由于揮發(fā)機(jī)制的作用（由揮發(fā)因子ρ控制），歷史信息對概率模型與新解產(chǎn)生過程的影響會(huì)逐漸衰退。蟻群優(yōu)化算法的迭代結(jié)構(gòu)06標(biāo)準(zhǔn)粒子群優(yōu)化算法的迭代結(jié)構(gòu)GPSO為粒子群優(yōu)化算法產(chǎn)生新解的迭代算子；SPB為更新粒子的個(gè)體最優(yōu)解的選擇算子；SLB為更新粒子的鄰域最優(yōu)解的選擇算子。xi,k為第k次迭伐時(shí)種群中第i個(gè)粒子的位置；為第i個(gè)粒子執(zhí)行第k次迭代時(shí)利用的解信息；pbi,k為到第k次迭代完成為止種群中第i個(gè)粒子找到的最優(yōu)解。lbi,k為到第k次迭代完成為止種群中第i個(gè)粒子所在的種群鄰域內(nèi)所有粒子找到的最優(yōu)解，如果種群鄰域覆蓋所有粒子，則lbi,k=gbk，gbk表示到第k次迭代完成為止所有粒子找到的最優(yōu)解。標(biāo)準(zhǔn)粒子群優(yōu)化算法的迭代結(jié)構(gòu)標(biāo)準(zhǔn)粒子群優(yōu)化算法的迭代結(jié)構(gòu)在經(jīng)典PSO算法中，所有粒子的鄰域都覆蓋了整個(gè)群體，因此lbi,k=gbk(?i∈{1,2，…，PS})。02由于慣性項(xiàng)的存在，每個(gè)粒子的位置歷史信息蘊(yùn)含在粒子速度中，因此PSO算法中的迭代算子隱含地運(yùn)用了這3種信息的歷史記錄。03由于慣性因子的作用，歷史信息的影響逐漸衰退。這一點(diǎn)與ACO的利用信息范圍特征非常相似。01標(biāo)準(zhǔn)粒子群優(yōu)化算法的迭代結(jié)構(gòu)01對于經(jīng)典PSO算法而言，其控制參數(shù)包括種群規(guī)模PS、慣性權(quán)重w、個(gè)體認(rèn)知因子c1和社會(huì)學(xué)習(xí)因子c2。02對于種群拓?fù)浣Y(jié)構(gòu)可變的PSO算法，我們可以用矩陣表示所有粒子的信息互聯(lián)關(guān)系。03種群拓?fù)湟彩荘SO算法的一個(gè)重要控制參數(shù)。07梯度下降法的迭代結(jié)構(gòu)010203梯度下降法不屬于智能優(yōu)化方法，但上述統(tǒng)一模型對數(shù)學(xué)規(guī)劃研究中的經(jīng)典方法同樣適用。在連續(xù)變量優(yōu)化研究中，梯度下降法是針對可微函數(shù)的一種經(jīng)典局部優(yōu)化方法。梯度下降法沿著目標(biāo)函數(shù)的負(fù)梯度方向搜索，因?yàn)槟繕?biāo)函數(shù)沿負(fù)梯度方向下降最快。梯度下降法的迭代結(jié)構(gòu)梯度下降法的迭代結(jié)構(gòu)式中，H(xk)為目標(biāo)函數(shù)在點(diǎn)xk處的Hessian矩陣。其迭代方式為式中，?f(xk)為目標(biāo)函數(shù)在點(diǎn)xk處的梯度；γk為正數(shù)，表示沿梯度方向的搜索步長。采用如下迭代方法與梯度下降法相比，NewtonRaphson方法還利用目標(biāo)函數(shù)的曲率信息使搜索方向更快地趨向局部最優(yōu)解。不同的梯度下降法往往采用不同的步長調(diào)節(jié)方法。例如，在…上述各種經(jīng)典迭代方法通常采用確定性的步長調(diào)節(jié)方法，但大多數(shù)方法都需要利用目標(biāo)函數(shù)的梯度信息或者對其進(jìn)行近似。梯度下降法或擬牛頓法的迭代結(jié)構(gòu)可以表示為：需要強(qiáng)調(diào)的是，如果梯度的計(jì)算直接利用顯式的梯度函數(shù)，則意味著算法利用了目標(biāo)函數(shù)的全局信息。由于Newton-Raphson方法對二階導(dǎo)數(shù)信息存在較強(qiáng)的依賴性，很多學(xué)者提出了近似方法以避免直接計(jì)算Hessian矩陣。梯度下降法的迭代結(jié)構(gòu)那么算法的迭代結(jié)構(gòu)應(yīng)表示為：顯然，無論梯度下降法還是擬牛頓法，都只適于局部搜索，而在多模態(tài)函數(shù)的優(yōu)化中，其收斂結(jié)果明顯依賴于初始解的位置。故