智能優(yōu)化算法簡述

馬原響

（ 華北水利水電大學(xué) 土木與交通學(xué)院，河南 鄭州450011）

隨著科學(xué)的發(fā)展，人們逐漸提出了許多優(yōu)化算法并由此形成了系統(tǒng)的優(yōu)化理論。但由于這些傳統(tǒng)的優(yōu)化算法在解決大型的工程問題上存在一定的局限性，所以自二十世紀(jì)80 年代以來，出現(xiàn)了一些比較新穎的優(yōu)化算法，例如遺傳算法、混合蛙跳算法等，這些算法都有一個(gè)共同點(diǎn)就是通過模擬或揭示某些自然現(xiàn)象或者過程從而得到高速發(fā)展，這些算法都有其獨(dú)特的優(yōu)點(diǎn)和機(jī)制，引起了國內(nèi)外學(xué)者的廣泛重視，也因此掀起了一股研究優(yōu)化算法的熱潮，到目前為止這些算法已經(jīng)在廣泛的工程領(lǐng)域得到了應(yīng)用。

圖1 遺傳算法流程圖

1 遺傳算法

遺傳算法（Genetic Algorithm，GA）是美國MIChigen 大學(xué)的Holland 教授[1]在受到達(dá)爾文進(jìn)化論啟發(fā)而創(chuàng)造的一種智能優(yōu)化算法，這個(gè)算法按照類似生物界自然選擇（selection）、變異（mutation）和雜交（crossover）等自然進(jìn)化方式，通過種群之間的“適者生存”原則，提高種群的平均適應(yīng)度，然后利用適應(yīng)度函數(shù)來引導(dǎo)種群進(jìn)化的方向，由此可以得到最優(yōu)個(gè)體所代表的問題解并逐漸逼近問題的全局最優(yōu)解。目前遺傳算法以及其改進(jìn)算法已經(jīng)廣泛應(yīng)用于函數(shù)優(yōu)化、生產(chǎn)調(diào)度、自動(dòng)控制、圖像處理、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域。

1.1 遺傳算法基本步驟

（1）對問題進(jìn)行編碼。

（2）定義適應(yīng)度函數(shù)后，生成初始化群體。

（3）對于得到的群體選擇復(fù)制、交叉、變異操作，生成下一代種群。

（4）判斷算法是否滿足條件，如果不滿足停止條件，則返回繼續(xù)執(zhí)行步驟（3）。

（5）算法結(jié)束，獲得最優(yōu)解。

具體流程圖如圖1 所示。

1.2 遺傳算法的改進(jìn)

文獻(xiàn)[2-3]武兆慧，田東平等，模擬退火法的思想運(yùn)用于遺傳算法，將兩者的優(yōu)點(diǎn)進(jìn)行整合合，形成了模擬退火遺傳算法，在迷糊控制等方面展現(xiàn)出了其巨大的優(yōu)點(diǎn)。

文獻(xiàn)[4-5]田東平、黃聰明提出了基于小生境的遺傳算法，這種改進(jìn)的遺傳算法具有多樣性解，收斂速度以及全局尋優(yōu)的優(yōu)點(diǎn)，對于求解復(fù)雜多峰的函數(shù)優(yōu)化問題有突出的優(yōu)點(diǎn)。

2 混合蛙跳算法

圖2 蛙跳算法流程圖

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）是Muzaffar Eusuf 和Kevin Lansey[6]在2003 年提出的一種基于青蛙群體的協(xié)同搜索方法。這個(gè)算法的思想來源于基因的傳承，它顯著特點(diǎn)就是可以進(jìn)行局部搜索與全局信息混合的協(xié)同搜索。通過大量的仿真測試可以證明，混合蛙跳算法在解決高維、病態(tài)、多局部極值等函數(shù)問題方面具有一定的優(yōu)越性，是一種行之有效的優(yōu)化算法。

2.1 蛙跳算法的具體步驟

（1）初始化。設(shè)置合適的子種群個(gè)數(shù)和每個(gè)子種群的青蛙個(gè)數(shù)。

（2）生成一個(gè)虛擬種群規(guī)模為。d 為維變量，表示每一個(gè)青蛙的當(dāng)前位置，對于優(yōu)化問題則表示解空間的一個(gè)候選解。

（3）對青蛙劃分等級，按照適應(yīng)度大小降序排列個(gè)體。

（4）將青蛙循環(huán)分組生成子種群。

（5）在每個(gè)子種群里進(jìn)行局部進(jìn)化，以使個(gè)體的位置得到改善。

（6）執(zhí)行混合運(yùn)算。當(dāng)子種群循環(huán)一定次數(shù)之后，將青蛙重新排列，更新位置最佳的青蛙。

（7）檢查終止條件，若迭代終止條件滿足，停止算法輸出結(jié)果；否則程序返回Step3 繼續(xù)執(zhí)行。

具體流程如圖2 所示。

2.2 蛙跳算法的改進(jìn)

文獻(xiàn)[7]代永強(qiáng)等人提出了一種基于改進(jìn)混合蛙跳算法的高維生物醫(yī)學(xué)數(shù)據(jù)特征選擇方法。該方法將混沌記憶權(quán)重因子和平衡分組策略引入基本混合蛙跳算法，在強(qiáng)化算法多樣性的同時(shí)，維持了算法全局和局部尋優(yōu)之間的平衡，降低了算法陷入局部最優(yōu)的可能，進(jìn)一步提高了混合蛙跳算法特征選擇方法在特征空間的探索能力。

3 其他智能算法

類似于以上幾種智能優(yōu)化算法，新興的智能算法還有很多，在這里不再具體敘述其基本原理以及優(yōu)缺點(diǎn)只列舉出各個(gè)算法的名稱。

（1）進(jìn)化算法，（2）禁忌算法，（3）粒子群算法，（4）人工魚群算法，（5）量子遺傳算法，（6）人工蜂群算法，（7）混沌優(yōu)化算法，（8）人工免疫算法，（9）細(xì)菌覓食算法，（10）貓群算法，（11）神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法，（12）混合優(yōu)化算法。

4 結(jié)論

以上主要介紹了三種在工程中應(yīng)用較為廣泛的智能優(yōu)化算法：遺傳算法、蟻群算法、蛙跳算法。同時(shí)列舉了幾乎近年來全部的智能優(yōu)化算法的名稱以備有需要的學(xué)者可以系統(tǒng)的了解智能優(yōu)化的各種算法，為其繼續(xù)深入學(xué)習(xí)該算法提供一些幫助。