智能優化算法的比較與改進

王夢蘭

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

關鍵詞：智能優化算法 個體行為 群體智能

智能優化算法概述

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

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

1、禁忌搜索算法

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

2、模擬退火算法

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

3、遺傳算法

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

4、蟻群算法

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

5、粒子群算法

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

智能優化算法的本質與比較

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

遺傳算法、蟻群算法、粒子群算法等屬于基于群體智能的算法，這些算法通過模擬群體生物之間信息交換、信息共享以及學習機制，通過迭代逐步選出優質解。基于群體智能的算法又分為兩類，一類是基于個體編碼結構的智能算法，另一類是基于個體與群體行為特征的智能算法。遺傳算法、螞蟻算法等屬于基于個體編碼結構的智能算法，這類算法以選優解的編碼結構為基礎，通過交換、變異與信息素標記即共享來重組個體編碼，換言之，這類算法假定選優解的部分編碼結構必優，通過重組優質解的部分編碼結構能夠找到群體優質解。粒子群算法屬于基于個體與群體行為特征的智能算法，粒子群算法以個體與群體行為特征向量即飛行方向向量來調整個體行為，最終達到個體行為與群體行為的協調統一，從而得到優質解。

智能優化算法的改進

智能優化算法的改進主要從以下兩個方面來改進：

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

總結

本文通過幾種常用的智能優化算法的基本思想的介紹，概括了智能優化算法的本質特征與區別，并提出了改進的方向，角度獨特，觀點新穎，對智能優化算法的研究具有一定的啟發性。

（作者單位： 國防信息學院）