馬原響
( 華北水利水電大學(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 遺傳算法流程圖
遺傳算法(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)對問題進(jìn)行編碼。
(2)定義適應(yīng)度函數(shù)后,生成初始化群體。
(3)對于得到的群體選擇復(fù)制、交叉、變異操作,生成下一代種群。
(4)判斷算法是否滿足條件,如果不滿足停止條件,則返回繼續(xù)執(zhí)行步驟(3)。
(5)算法結(jié)束,獲得最優(yōu)解。
具體流程圖如圖1 所示。
文獻(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 蛙跳算法流程圖
混合蛙跳算法(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)化算法。
(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 所示。
文獻(xiàn)[7]代永強(qiáng)等人提出了一種基于改進(jìn)混合蛙跳算法的高維生物醫(yī)學(xué)數(shù)據(jù)特征選擇方法。該方法將混沌記憶權(quán)重因子和平衡分組策略引入基本混合蛙跳算法,在強(qiáng)化算法多樣性的同時(shí),維持了算法全局和局部尋優(yōu)之間的平衡,降低了算法陷入局部最優(yōu)的可能,進(jìn)一步提高了混合蛙跳算法特征選擇方法在特征空間的探索能力。
類似于以上幾種智能優(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)化算法。
以上主要介紹了三種在工程中應(yīng)用較為廣泛的智能優(yōu)化算法:遺傳算法、蟻群算法、蛙跳算法。同時(shí)列舉了幾乎近年來全部的智能優(yōu)化算法的名稱以備有需要的學(xué)者可以系統(tǒng)的了解智能優(yōu)化的各種算法,為其繼續(xù)深入學(xué)習(xí)該算法提供一些幫助。