之前做特征選擇，實(shí)現(xiàn)過(guò)基于群智能算法進(jìn)行最優(yōu)化的搜索，看過(guò)一些群智能優(yōu)化算法的論文，在此做一下總結(jié)。

　　在生活或者工作中存在各種各樣的最優(yōu)化問(wèn)題，比如每個(gè)企業(yè)和個(gè)人都要考慮的一個(gè)問(wèn)題“在一定成本下，如何使利潤(rùn)最大化”等。最優(yōu)化方法是一種數(shù)學(xué)方法，它是研究在給定約束之下如何尋求某些因素(的量)，以使某一(或某些)指標(biāo)達(dá)到最優(yōu)的一些學(xué)科的總稱。

　　工程設(shè)計(jì)中最優(yōu)化問(wèn)題（optimalization problem）的一般提法是要選擇一組參數(shù)（變量），在滿足一系列有關(guān)的限制條件（約束）下，使設(shè)計(jì)指標(biāo)（目標(biāo)）達(dá)到最優(yōu)值。因此，最優(yōu)化問(wèn)題通?？梢员硎緸閿?shù)學(xué)規(guī)劃形式的問(wèn)題。進(jìn)行工程優(yōu)化設(shè)計(jì)時(shí)，應(yīng)將工程設(shè)計(jì)問(wèn)題用上述形式表示成數(shù)學(xué)問(wèn)題，再用最優(yōu)化的方法求解。這項(xiàng)工作就是建立優(yōu)化設(shè)計(jì)的數(shù)學(xué)模型。

　　
　　最優(yōu)化問(wèn)題分為函數(shù)優(yōu)化問(wèn)題和組合優(yōu)化問(wèn)題兩大類，其中函數(shù)優(yōu)化的對(duì)象是一定區(qū)間的連續(xù)變量，而組合優(yōu)化的對(duì)象則是解空間中的離散狀態(tài)。其中典型的組合優(yōu)化問(wèn)題有旅行商(Traveling salesman problem,TSP)問(wèn)題、加工調(diào)度問(wèn)題(Scheduling problem,如Flow-shop,Job-shop)、0-1背包問(wèn)題(Knapsack problem)、裝箱問(wèn)題(Bin packing problem)、圖著色問(wèn)題(Graph coloring problem)、聚類問(wèn)題(Clustering problem)等。

最優(yōu)化算法

根據(jù)自己對(duì)最優(yōu)化的理解，采用最優(yōu)化算法解決實(shí)際問(wèn)題主要分為下列兩步：

建立數(shù)學(xué)模型。對(duì)可行方案進(jìn)行編碼（變量），約束條件以及目標(biāo)函數(shù)的構(gòu)造。
最優(yōu)值的搜索策略。在可行解（約束條件下）搜索最優(yōu)解的方法，有窮舉、隨機(jī)和啟發(fā)式搜索方法。

最優(yōu)化算法有三要素：變量（Decision Variable）、約束條件（Constraints）和目標(biāo)函數(shù)（Objective function）。最優(yōu)化算法，其實(shí)就是一種搜索過(guò)程或規(guī)則，它是基于某種思想和機(jī)制，通過(guò)一定的途徑或規(guī)則來(lái)得到滿足用戶要求的問(wèn)題的解。

優(yōu)化問(wèn)題相關(guān)算法有如下分類：

精確算法(絕對(duì)最優(yōu)解)

精確算法包括線性規(guī)劃、動(dòng)態(tài)規(guī)劃、整數(shù)規(guī)劃和分支定界法等運(yùn)籌學(xué)中的傳統(tǒng)算法，其算法計(jì)算復(fù)雜性一般很大，只適合于求解小規(guī)模問(wèn)題，在工程中往往不實(shí)用。

啟發(fā)式算法（近似算法）

　　啟發(fā)式方法指人在解決問(wèn)題時(shí)所采取的一種根據(jù)經(jīng)驗(yàn)規(guī)則進(jìn)行發(fā)現(xiàn)的方法。其特點(diǎn)是在解決問(wèn)題時(shí),利用過(guò)去的經(jīng)驗(yàn),選擇已經(jīng)行之有效的方法，而不是系統(tǒng)地、以確定的步驟去尋求答案。

領(lǐng)域搜索算法。從任一解出發(fā)，對(duì)其領(lǐng)域的不斷搜索和當(dāng)前解的替換來(lái)實(shí)現(xiàn)優(yōu)化。根據(jù)搜索行為，它又可分為局部搜索法和指導(dǎo)性搜索法。

局部領(lǐng)域搜索法（也稱爬山法）。以局部?jī)?yōu)化策略在當(dāng)前解的領(lǐng)域中貪婪搜索，如只接受優(yōu)于當(dāng)前解的狀態(tài)作為下一當(dāng)前解的爬山法；接受當(dāng)前鄰域中的最好解作為下一當(dāng)前解的最陡下降法等。

指導(dǎo)性搜索法。利用一些指導(dǎo)規(guī)則來(lái)指導(dǎo)整個(gè)解空間中優(yōu)良解的探索，如SA、GA、EP、ES和TS等.

個(gè)體啟發(fā)（尋找相對(duì)最優(yōu)）

特點(diǎn)：每次輸出的是相同的。從一個(gè)解開(kāi)始，尋找最優(yōu)，易陷入局部最優(yōu)。

爬山算法

算法思想：從當(dāng)前的節(jié)點(diǎn)開(kāi)始，和周圍的鄰居節(jié)點(diǎn)的值進(jìn)行比較。如果當(dāng)前節(jié)點(diǎn)是最大的，那么返回當(dāng)前節(jié)點(diǎn)，作為最大值(即山峰最高點(diǎn))；反之就用最高的鄰居節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)，從而實(shí)現(xiàn)向山峰的高處攀爬的目的。

其實(shí)就是，在初始值的附近，找到最大的一個(gè)。

優(yōu)點(diǎn)

容易理解，容易實(shí)現(xiàn)，具有較強(qiáng)的通用性；
局部開(kāi)發(fā)能力強(qiáng)，收斂速度很快

缺點(diǎn)

全局開(kāi)發(fā)能力弱，只能搜索到局部最優(yōu)解；
搜索結(jié)果完全依賴于初始解和鄰域的映射關(guān)系。

禁忌算法(Tabu Search，TS)

基本思想：基于爬山算法的改進(jìn)，標(biāo)記已經(jīng)解得的局部最優(yōu)解或求解過(guò)程，并在進(jìn)一步的迭代中避開(kāi)這些局部最優(yōu)解或求解過(guò)程。局部搜索的缺點(diǎn)在于，太過(guò)于對(duì)某一局 大專欄 最優(yōu)化算法——常見(jiàn)優(yōu)化算法分類及總結(jié)部區(qū)域以及其鄰域的搜索，導(dǎo)致一葉障目。為了找到全局最優(yōu)解，禁忌搜索就是對(duì)于找到的一部分局部最優(yōu)解，有意識(shí)地避開(kāi)它，從而或得更多的搜索區(qū)域

特點(diǎn)：

避免在搜索過(guò)程中的循環(huán)
只進(jìn)不退的原則,通過(guò)禁忌表實(shí)現(xiàn)
不以局部最優(yōu)作為停止準(zhǔn)則
鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能

禁忌表：用于防止搜索出現(xiàn)循環(huán)

記錄前若干步走過(guò)的點(diǎn)、方向或目標(biāo)值，禁止返回
表是動(dòng)態(tài)更新的
表的長(zhǎng)度稱為Tabu-Size

禁忌表的主要指標(biāo)（兩項(xiàng)指標(biāo)）

禁忌對(duì)象：禁忌表中被禁的那些變化元素
禁忌長(zhǎng)度：禁忌的步數(shù)

禁忌對(duì)象（三種變化）

以狀態(tài)本身或者狀態(tài)的變化作為禁忌對(duì)象
以狀態(tài)分量以及分量的變化作為禁忌對(duì)象
采用類似的等高線做法，以目標(biāo)值變化作為禁忌對(duì)象

禁忌長(zhǎng)度:可以是一個(gè)固定的常數(shù)(T=c),也可以是動(dòng)態(tài)變化的，可按照某種規(guī)則或公式在區(qū)間內(nèi)變化。

禁忌長(zhǎng)度過(guò)短，一旦陷入局部最優(yōu)點(diǎn)，出現(xiàn)循環(huán)無(wú)法跳出；
禁忌長(zhǎng)度過(guò)長(zhǎng)，候選解全部被禁忌，造成計(jì)算時(shí)間較大，也可能造成計(jì)算無(wú)法繼續(xù)下去。

參考：

禁忌搜索算法(Tabu Search)
禁忌搜索算法詳解

貪婪算法

從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。

基本都要先排序，從排序的開(kāi)始那個(gè)依次判斷，符合就留下不符合就去掉。

模擬退火(simulated annealing，SA)

模擬退火算法作為局部搜索算法的擴(kuò)展，在每一次修改模型的過(guò)程中，隨機(jī)產(chǎn)生一個(gè)新的狀態(tài)模型，然后以一定的概率選擇鄰域中能量值大的狀態(tài)．這種接受新模型的方式使其成為一種全局最優(yōu)算法，并得到理論證明和實(shí)際應(yīng)用的驗(yàn)證．SA雖然在尋優(yōu)能力上不容置疑，但它是以嚴(yán)密的退火計(jì)劃為保證的，具體地講，就是足夠高的初始溫度、緩慢的退火速度、大量的迭代次數(shù)及同一溫度下足夠的擾動(dòng)次數(shù)。

用兔子的故事來(lái)說(shuō)：兔子喝醉了。他隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝他踏過(guò)的最高方向跳去。這就是模擬退火。

其實(shí)就是，先用初始值進(jìn)行隨機(jī)更新，記錄每次更新的值，最后取歷史記錄中最大的值。

參考：模擬退火算法

群體智能（全局最優(yōu)）

類別：

粒子群算法(PSO)
蟻群算法(ACO)
人工蜂群算法(ABC)
人工魚群算法(AFSA)
混洗蛙跳算法(SFLA)
煙花算法(FWA)
細(xì)菌覓食優(yōu)化(BFO)
螢火蟲(chóng)算法(FA)

特點(diǎn)：

全局尋優(yōu)
每次的解都不同
時(shí)間較長(zhǎng)

智能計(jì)算包括：

進(jìn)化算法（EC），如遺傳算法。
模糊邏輯
群智能(SI)算法
人工免疫系統(tǒng)(AIS)
人工神經(jīng)網(wǎng)絡(luò)(ANN)

參考：

最優(yōu)化問(wèn)題及其分類
遺傳算法
《MATLAB神經(jīng)網(wǎng)絡(luò)30個(gè)案例分析》的13個(gè)案例中的GA優(yōu)化SVM參數(shù)
手把手教你實(shí)現(xiàn)SVM算法（一）
遺傳算法學(xué)習(xí)筆記（一）：常用的選擇策略
粒子群算法介紹（講解的很清晰，將PSO的算法原理、算法特點(diǎn)以及參數(shù)的設(shè)置）
群體智能簡(jiǎn)介ppt（粒子群和人工蟻群優(yōu)化）
優(yōu)化算法分類

總結(jié)

以上是生活随笔為你收集整理的最优化算法——常见优化算法分类及总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。