智能優(yōu)化算法的比較與改進(jìn)

王夢(mèng)蘭

摘要：本文闡述了幾種常用智能優(yōu)化算法的基本思想，概括了它們的本質(zhì)特征，對(duì)智能優(yōu)化算法進(jìn)行了分類，并指出了智能優(yōu)化算法的改進(jìn)方向。

關(guān)鍵詞：智能優(yōu)化算法 個(gè)體行為 群體智能

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

傳統(tǒng)優(yōu)化算法本質(zhì)上是全局搜索算法，即通過搜索整個(gè)解空間來找到問題的最優(yōu)解。為了加快算法的搜索速度或減少運(yùn)行時(shí)計(jì)算空間的耗費(fèi)，傳統(tǒng)優(yōu)化算法往往需要充分利用目標(biāo)函數(shù)的解析性質(zhì)以及約束空間的幾何特征，逐步縮小搜索空間，最終完成整個(gè)解空間的搜索，從而找到最優(yōu)解。但隨著問題越來越復(fù)雜，規(guī)模越來越大，傳統(tǒng)優(yōu)化算法已經(jīng)不能在可以接受的時(shí)間內(nèi)找到最優(yōu)解。這里求解時(shí)間與最優(yōu)解是一對(duì)矛盾，為了解決這一矛盾，有些研究者提出了一類新的解決方法，它們不以尋找問題的最優(yōu)解為目的，而是追求在有限的時(shí)間內(nèi)找到滿足需要的解即可。這類方法往往借鑒了人類解決復(fù)雜問題的技巧以及生物體的本能，能夠?qū)?fù)雜的求解過程簡(jiǎn)單化，從而表現(xiàn)出“智能”的特征，因此被稱為“智能算法”。常用的智能優(yōu)化算法有：遺傳算法、禁忌搜索算法、模擬退火算法、蟻群算法、粒子群算法等。

智能優(yōu)化算法按群體規(guī)模大小可以簡(jiǎn)單分為兩類：基于個(gè)體行為的算法與基于群體智能的算法。其中，禁忌搜索算法、模擬退火算法等屬于基于個(gè)體行為的智能算法；遺傳算法、蟻群算法、粒子群算法、免疫算法、細(xì)菌覓食算法、人工魚群算法、Memetic算法、捕食搜索算法等屬于基于群體智能的算法。

1、禁忌搜索算法

人類的行為具有記憶性，即對(duì)過去行為的記憶往往對(duì)眼下及未來的行為具有指引性，所謂“吃一塹，長(zhǎng)一智”，“一朝被蛇咬，三年怕井繩”講的就是這個(gè)道理。禁忌就是禁止重復(fù)前面的工作，類似人類的記憶行為。禁忌搜索算法為了避免局部鄰域搜索陷入局部最優(yōu)解，引入禁忌表來記錄已經(jīng)搜索過的局部最優(yōu)解，在下一次搜索中，不再有選擇地搜索這些點(diǎn)，以此來跳出局部最優(yōu)解。同時(shí)，禁忌搜索算法還引入“破禁”或特赦的思想，當(dāng)被禁忌的解優(yōu)于歷史最優(yōu)解，會(huì)被解禁。此外，禁忌表的長(zhǎng)度類似人類的遺忘周期，當(dāng)禁忌表填滿禁忌對(duì)象時(shí)，新進(jìn)的禁忌對(duì)象會(huì)擠出最早進(jìn)入禁忌表中的對(duì)象，算法下一次搜索就可以重新選擇被解禁的對(duì)象。

2、模擬退火算法

模擬退火算法本質(zhì)上是一種概率搜索算法，算法每次迭代都以一定的概率選擇搜索鄰域外的解，即算法總能以一定的概率跳出局部最優(yōu)解，如果這個(gè)解優(yōu)于歷史最優(yōu)解，算法會(huì)集中在這個(gè)解的附近搜索，直到以一定的概率找到更好的解。模擬退火算法類似人類的隨機(jī)漫步行為以及固體物體的退火過程。該算法將固體的退火過程與優(yōu)化問題的求解過程有機(jī)的結(jié)合起來，因此被稱為模擬退火算法。算法運(yùn)行時(shí)從某一較高初溫開始，結(jié)合具有概率突跳特性的Metropolis抽樣策略在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，伴隨溫度參數(shù)的不斷下降重復(fù)抽樣過程，最終得到問題的近似最優(yōu)解。模擬退火算法理論上屬于全局最優(yōu)算法，但實(shí)際中只需在一定的時(shí)間內(nèi)找到近似解即可。

3、遺傳算法

遺傳算法模擬生物進(jìn)化和生命遺傳的過程，將問題的解編碼成基因串，通過選擇、交叉、變異三個(gè)遺傳算子，完成種群的繁衍、進(jìn)化。其本質(zhì)是一種通過交換機(jī)制，重組基因串的概率搜索算法。由于遺傳算法滲透了“優(yōu)勝劣汰、適者生存”的遺傳和進(jìn)化思想，至今仍是應(yīng)用最廣泛也是最為成功的算法。

4、蟻群算法

蟻群算法是通過模仿螞蟻覓食行為而設(shè)計(jì)出來的一種智能優(yōu)化算法。單個(gè)螞蟻的行為極其簡(jiǎn)單，談不上智能，但由螞蟻個(gè)體組成的蟻群能夠協(xié)助合作，總能找到一條從蟻巢到食物源的最短路，其行為表現(xiàn)出高度的智能。研究發(fā)現(xiàn)，螞蟻個(gè)體之間通過一種稱之為信息素的物質(zhì)進(jìn)行信息傳遞，即螞蟻個(gè)體之間能夠共享信息，從而能夠相互協(xié)作，完成復(fù)雜的任務(wù)。螞蟻在覓食過程中，能夠在它所經(jīng)過的路徑上留下信息素，而且能夠感知信息素的存在及其強(qiáng)度，從而指導(dǎo)自己朝著信息素強(qiáng)度高的方向移動(dòng)。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來的螞蟻選擇該路徑的概率就越大。蟻群個(gè)體之間就是通過這種信息的交流、共享機(jī)制，從而達(dá)到尋找食物的目的。人類野外尋找路徑以及在陌生領(lǐng)域內(nèi)探索研究，與蟻群個(gè)體之間通過信息的交流、共享，完成食物的搜索一樣，具有相同的本質(zhì)特征。后來者總是沿著前人開辟的道路前進(jìn)，只有某條路不能再前行了，人們才會(huì)去開辟新的道路。所謂“世上本沒有路，走的人多了，也就成了路”，講的就是信息共享的道理。但正反饋機(jī)制既是蟻群算法的優(yōu)點(diǎn)，也是其缺點(diǎn)，蟻群算法很容易出現(xiàn)停滯現(xiàn)象。當(dāng)局部最優(yōu)解路徑上的信息素強(qiáng)度較強(qiáng)時(shí)，正反饋機(jī)制會(huì)繼續(xù)放大這條路徑上的信息素強(qiáng)度，從而使得算法很快陷入局部最優(yōu)解。這時(shí)，正反饋機(jī)制就不再是“正反饋”，而是“負(fù)反饋”了，這與“羊群效應(yīng)”或“盲從現(xiàn)象”是類似的了。

5、粒子群算法

粒子群優(yōu)化算法是模擬鳥類遷徙行為而設(shè)計(jì)出來的一種智能算法，最早由Kenney與Eberhart于1995年提出。鳥類在遷徙途中總能根據(jù)自身的位置以及周圍同伴的位置調(diào)整飛行方向，因此整個(gè)鳥群能夠保持完美的飛行陣型，這種充滿美學(xué)的行為背后是鳥類個(gè)體之間相互學(xué)習(xí)的機(jī)制發(fā)揮了作用的結(jié)果。粒子群優(yōu)化算法正是借鑒這種學(xué)習(xí)機(jī)制，微粒個(gè)體通過記住自身歷史最好解以及群體的歷史最優(yōu)解，并結(jié)合自身的位置隨時(shí)調(diào)整飛行方向，從而經(jīng)過一段時(shí)間就能飛向最優(yōu)解。PSO后來經(jīng)過多次的改進(jìn)，去除了原來算法中一些無關(guān)的或冗余的變量，又加入了一些隨機(jī)變化的量，使得鳥群的運(yùn)動(dòng)更象是空間微粒的運(yùn)動(dòng)，所以稱之為微粒群算法。

智能優(yōu)化算法的本質(zhì)與比較

禁忌搜索算法和模擬退火算法都是基于個(gè)體行為的智能優(yōu)化算法。禁忌搜索算法通過禁忌表記錄局部歷史最優(yōu)解，本質(zhì)上類似人類的記憶行為，而模擬退火算法通過隨機(jī)選擇來跳出局部最優(yōu)解，本質(zhì)上類似人類的隨機(jī)漫步行為。人類行為兼具記憶性與隨機(jī)性兩種特征，即對(duì)過去行為的記憶往往對(duì)眼下及未來的行為具有指引性，這往往是確定性的，而人類行為還具有隨機(jī)性的特征，即人類行為往往還是偶發(fā)的、不可琢磨的、隨機(jī)的。

遺傳算法、蟻群算法、粒子群算法等屬于基于群體智能的算法，這些算法通過模擬群體生物之間信息交換、信息共享以及學(xué)習(xí)機(jī)制，通過迭代逐步選出優(yōu)質(zhì)解?；谌后w智能的算法又分為兩類，一類是基于個(gè)體編碼結(jié)構(gòu)的智能算法，另一類是基于個(gè)體與群體行為特征的智能算法。遺傳算法、螞蟻算法等屬于基于個(gè)體編碼結(jié)構(gòu)的智能算法，這類算法以選優(yōu)解的編碼結(jié)構(gòu)為基礎(chǔ)，通過交換、變異與信息素標(biāo)記即共享來重組個(gè)體編碼，換言之，這類算法假定選優(yōu)解的部分編碼結(jié)構(gòu)必優(yōu)，通過重組優(yōu)質(zhì)解的部分編碼結(jié)構(gòu)能夠找到群體優(yōu)質(zhì)解。粒子群算法屬于基于個(gè)體與群體行為特征的智能算法，粒子群算法以個(gè)體與群體行為特征向量即飛行方向向量來調(diào)整個(gè)體行為，最終達(dá)到個(gè)體行為與群體行為的協(xié)調(diào)統(tǒng)一，從而得到優(yōu)質(zhì)解。

智能優(yōu)化算法的改進(jìn)

智能優(yōu)化算法的改進(jìn)主要從以下兩個(gè)方面來改進(jìn)：

一是算法融合，即在一種算法中通過融合其他算法的優(yōu)點(diǎn)來改進(jìn)。算法融合主要有兩種方式，一種是在基于群體智能的算法中通過融合個(gè)體行為的隨機(jī)或記憶特征來改進(jìn)，另一種是在基于個(gè)體行為特征的智能算法中引入群體特征如并行機(jī)制來改進(jìn)。二是模仿自然界生物的行為特征創(chuàng)立新型智能優(yōu)化算法，如捕食搜索算法、人工魚群算法、細(xì)菌覓食算法、免疫算法、Memetic算法等。

總結(jié)

本文通過幾種常用的智能優(yōu)化算法的基本思想的介紹，概括了智能優(yōu)化算法的本質(zhì)特征與區(qū)別，并提出了改進(jìn)的方向，角度獨(dú)特，觀點(diǎn)新穎，對(duì)智能優(yōu)化算法的研究具有一定的啟發(fā)性。

（作者單位： 國(guó)防信息學(xué)院）