基于仿生理論的幾種優化算法綜述

摘 要：簡要介紹了目前比較流行的三種新型仿生優化算法，即人工魚群算法、免疫算法和禁忌搜索算法，就這些算法的特點和異同進行了分析，并對它們的發展進行了進一步的闡述，提出了今后的研究方向。

關鍵詞：優化算法；人工魚群算法；免疫算法；禁忌搜索算法

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2009)06-2032-03

doi:10.3969/j.issn.1001-3695.2009.06.009

Overview of some optimization algorithm based on bionic theory

LI Xue-mei1，2，ZHANG Su-qin1

(1.Dept. of Computer Science Technology， Tsinghua University， Beijing 100084， China；2.Dept. of Information Engineering， College of Engineering， Shanxi University， Taiyuan 030013， China)

Abstract:The article surveyed three new-style bionic optimization algorithms， artificial fish-swarm algorithm， immune algorithm， and tabu search algorithm.Discussed their characteristics， similarities， differences， and development， at last pointed out the direction of researching.

Key words:optimization algorithm; artificial fish-swarm algorithm; immune algorithm; tabu search algorithm

20世紀50年代中期創立了仿生學，人們從生物進化的機理中受到啟發，提出了許多用于解決復雜優化問題的新方法，如近年來提出的人工魚群算法、免疫算法、禁忌搜索算法等， 取得了一系列較好的實驗結果。

人工魚群算法^[1]在對動物群體智能行為研究的基礎上提出一種新型仿生優化算法，根據在一片水域中，魚往往能自行或尾隨其他魚找到營養物質多的地方，因而魚生存數目最多的地方一般就是本水域中營養物質最多的地方這一特點，構造人工魚來模仿魚群的覓食、聚群及追尾行為，從而實現尋優。

免疫算法是基于生物免疫系統基本機制，模仿了人體的免疫系統，是生物免疫抗體產生記憶學習機理的產物，這方面的研究是從20世紀80年代中期的免疫學研究發展而來的。90年代初，Bersini H等人^[2]首次使用人工免疫算法來解決優化問題。

禁忌搜索算法最早是由Glover^[3]提出的，它是一種局部搜索的擴展，模擬人類具有記憶功能的尋優特征。該算法通過局部領域搜索機制和相應的禁忌準則來避免重復迂回搜索，并通過期望準則來釋放一些被禁忌的優良個體，進而保證多樣化的有效搜索，以此來最終實現全局優化。

1 三種算法的基本思想

1.1 人工魚群算法

魚群典型的行為描述如下：

a）覓食行為。一般情況下，魚在水中隨機地自由游動，當發現食物時，則會向食物逐漸增多的方向快速游去。 

b）聚群行為。魚在游動過程中，為保證自身的生存和躲避危害，會自然地聚集成群。魚聚群時遵守的規則有：分隔規則，盡量避免與鄰近伙伴過于擁擠；對準規則，盡量與鄰近伙伴的平均方向一致；內聚規則，盡量朝鄰近伙伴中心移動。 

c）追尾行為。當魚群中的一條或幾條魚發現食物時，鄰近的伙伴會尾隨其快速到達食物點。

d）隨機行為。隨機選擇當前狀態以外的另一個狀態，目的就是想擴大搜索范圍， 有利于跳出局部極值。

e）約束行為。在尋優過程中，由于聚群行為、隨機行為等操作，可能出現不是可行解的情況，這時需要加入相應的約束條件來調整，使它們由無效狀態變為可行解。 

f）公告板。算法中設立一個公告板來記錄最優狀態。每條人工魚在行動一次后就將自身當前狀態與公告板進行比較，如優于公告板則用自身狀態取代公告板狀態。

g）移動策略。根據所要解決的問題性質，對人工魚當前所處的環境進行評價，從而選擇一種合適的行為策略。可以按照進步最快的原則或進步即可的原則來選擇，例如先進行聚群行為，如果沒有進步再進行追尾行為，如果還沒有進步則進行覓食行為，依然沒有進步就進行隨機行為。

人工魚群算法的基本步驟如下：

a）產生初始化魚群。設置初始公告板最優人工魚狀態記錄為空，在搜索域內隨機產生N個人工魚個體，組成初始群體。

b）公告板賦初值。分別計算各人工魚狀態的食物濃度，選擇最大食物濃度的人工魚個體狀態記錄到公告板內。

c）行為選擇。各人工魚分別模擬聚群和追尾行為，缺省為覓食行為，然后選擇最優的作為實際執行行為。

d）公告板。各人工魚每行動一次，則與公告板記錄進行比較，若優于公告板記錄，則以當前最優的記錄替換公告板記錄。

e）條件判斷。判斷公告板最優人工魚狀態連續不變化或變化極少的迭代次數是否已達到預設的連續不變化的最大值，若是執行下一步；否則執行g）。

f）隨機行為。隨機選擇當前公告板狀態以外的另一個狀態，形成新的魚群，然后執行d）。

g）終止條件判斷。判斷是否滿足終止條件，若不能滿足終止條件，則轉向c)，進行下一步魚群優化過程；若滿足終止條件繼續以下步驟。

h）算法結束。當前公告板中的記錄即為問題的最佳解，輸出公告板記錄，算法終止。

1.2 免疫算法

為了掌握和充分利用免疫系統的強大防御能力，基礎醫學對免疫系統的各種優良特性和機理進行了深入細致的研究并取得了重大成果。生物免疫系統是一個具有防御能力的高效信息處理系統，已經得到人們的普遍認可。研究表明，當病菌侵入時，免疫系統首先要識別這一抗原，才能產生對應的抗體消滅它。面對大量不同種類的抗原，免疫系統必須先識別再消滅，這就是免疫系統識別多樣性的特性。免疫算法正是基于這種生物免疫系統的基本機制開發形成，它模仿了免疫系統中抗體與抗原識別、結合及抗體產生的過程，并利用免疫系統的多樣性和記憶機理抽象得到。在用免疫算法求解優化問題時，滿足約束條件的最優解即是抗原；候選解即是抗體，用親和力來描述抗體與抗原間的匹配程度。其基本步驟如下：

a）定義抗原。輸入問題的目標函數和約束條件，作為免疫算法的抗原。

b）產生初始抗體群體。將抗體的群體定義為問題的解，抗體與抗原之間的親和力對應問題解的評估，即親和力越高，說明解越好。

c）計算親和力。計算抗體與抗原之間的親和力，將與抗原最高有親和力的抗體作為記憶細胞保留在記憶細胞庫中，以替換親和力較低的抗體。

d）克隆選擇。與抗原有較大親和力的抗體優先得到繁殖，抑制濃度過高的抗體（避免局部最佳解），淘汰低親和力的抗體。為了獲得多樣性（追求最佳解），抗體在克隆時經歷變異。在克隆選擇中，抗體促進和克隆刪除對應優化解的促進與非優化解的刪除等。

e）評估新的抗體群體。若不能滿足終止條件，則轉向c），重新開始；否則，當前的抗體群體即為問題的最佳解。

在使用免疫算法解決問題時，一般各步驟有對應形式。抗原對應要解決問題數據輸入，如目標、約束；抗體對應問題解，如優化問題的最優解；親和力對應解的評估、結合強度的評估；克隆選擇對應優化解促進、非優化解的刪除等；新抗體產生對應優化解的出現等。對應內容因解決問題對象不同而內容各異。

1.3 禁忌搜索算法

禁忌搜索算法是一種局部搜索修正算法，模擬人類具有記憶功能的尋優特征。其基本思想是假設給出一個解和一個鄰域，首先在這一鄰域中找出一個最好的局部解作為ans，令當前最優解ans^=ans；然后再在這個當前解的鄰域中搜索最好的局部解ans′。但是，這個最好解有可能與前一次的相同。為了避免這種循環現象，設置一個記憶近期操作的禁忌表，如果當前操作是記錄在禁忌表中的操作，那么這一操作將被禁止；否則用ans′代替ans。此時ans′點的目標函數值可能劣于ans點的目標函數值，所以禁忌搜索算法可以接受劣解，但是對于那些特別有意義的操作，如改善了目前找到的最優解，可以運用期望準則進行解禁，以便迅速找到更好的解。

該算法的基本步驟如下：

a）給定算法參數，隨機產生初始解x，置禁忌表為空。

b）判斷算法終止條件是否滿足。若是，則結束并輸出優化結果；否則，繼續以下步驟。

c）利用當前解x的鄰域函數產生其所有（或若干）鄰域解，并從中確定若干候選解。

d）對候選解判斷藐視準則是否滿足。若滿足，則用滿足藐視準則的最佳狀態y替代x成為新的當前解，即x=y，并用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換最優狀態，然后轉f)；否則，繼續以下步驟。

e）判斷候選解對應各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。

f）轉步驟b）。

2 三種算法的特點與異同

2.1 三種算法的特點

人工魚群算法主要是利用了魚的覓食、聚群和追尾行為，從構造單條魚的底層行為做起，通過魚群中各個個體的局部尋優從而以全局最優值在群體中突現出來為目的。該算法具有良好的克服局部極值取得全局極值的能力，并且算法中只使用目標函數的函數值，無須其梯度值等特殊信息，對搜索空間具有一定的自適應能力。算法對初值無要求，對各參數的選擇也不敏感。但該算法僅僅獲取的是系統的滿意解域，對于精確解的獲取還需要進行適當的改進，所以又有一些改進的算法被研究出來。

免疫算法的主要特點是分布式、自適應學習和采用并行算法。它模仿了人體的免疫系統，即為了有效地提供防御功能，必須具有識別能力，將自己的分子和細胞與抗原區分開，除此之外還需要有記憶功能。根據這些特點，免疫算法是在記憶單元基礎上進行，所以能夠確保快速收斂于全局最優解；它有計算親和力的程序，從而保證了算法的多樣性；通過促進或抑制抗體的產生，體現了免疫反應的自我調節功能。

禁忌搜索算法的特點是采用了禁忌技術。禁忌就是禁止重復前面的工作，它避免了局部鄰域搜索陷入局部最優的主要不足，用一個禁忌表記錄下已經到達過的局部最優點，在下一次搜索中，就利用禁忌表中的信息不再或有選擇地搜索這些點，以跳出局部最優。禁忌搜索算法具有靈活的記憶功能和藐視準則，并且在搜索過程中可以接受劣解，所以具有較強的“爬山”能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局解的概率。禁忌搜索算法是一種局部搜索能力很強的全局迭代尋優算法。

2.2 三種算法的比較分析

1）相同點

a）三種算法都是隨機搜索算法，其搜索過程具有非確定性，都是利用仿生理論的記憶機制加強局部搜索或抑制早熟收斂，從而使算法快速收斂到全局最優解。例如人工魚群算法的公告板、免疫算法的記憶細胞庫和禁忌搜索算法的禁忌表就是這個作用，所以它們都具有避免陷入局部最優以收斂于全局最優(或次優) 的能力。

b）三種算法都是從由多個個體所組成的初始種群起始的種群空間中的迭代過程，其搜索過程的每一步利用了種群中各個體所提供的信息，這些信息可避免一些不必要搜索的點或區域，提高了搜索效率，在更大程度上避免了陷入局部極值。 

c）三種算法的魯棒性都較強。由于仿生優化算法不依賴于優化問題本身的嚴格數學性質和所求解本身的結構特征，在求解不同問題時，只需對基本算法模型稍加修改，便可以應用于其他問題。

d）三種算法都具有并行性，易于并行實現。仿生優化算法的并行性主要表現在：（a）仿生計算是內在并行的，即仿生優化算法本身非常適合大規模并行；（b）演化計算的內含并行性，這使得仿生計算能以較少的計算獲得較大的收益。

e）三種算法都很容易與多種啟發式算法結合，以改善算法的性能。

2)不同點

人工魚群優化算法具有良好的克服局部極值、取得全局極值的能力，使用靈活，收斂速度快。但是解決離散優化問題時，該算法具有保持探索與開發平衡的能力較差和算法運行后期搜索盲目性較大等缺點，影響了該算法搜索的質量和效率。

免疫算法雖然能很好地獲得全局最優解，并具有較快的收斂速度，但需要用戶設置的參數較多，使算法對問題的依賴性較強、泛化能力較差；其智能性也沒有其他幾種仿生算法高，改進起來較其他仿生算法麻煩一些。

禁忌搜索算法雖然算法結構簡單、迭代次數少、到達最優點的效率較高，但它的最大缺陷是對于初始解具有較強的依賴性。一個較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個較差的初始解則會降低禁忌搜索的收斂速度，搜索到的解也相對較差；此外， 迭代搜索過程是串行的，僅是單一狀態的移動，而非并行搜索。

2.3 三種算法的實例

下面通過一個典型的旅行商問題（traveling salesman problem，TSP）對這三個算法的性能作一些簡要的闡述。

李曉磊等人^[13]對TSP進行求解時得出的結論是人工魚群算法具有較快的收斂速度，但隨著問題規模的擴大其尋優的精度會有所降低。周輝等人^[14]對TSP進行求解，得出的結論是免疫算法具有較好的全局搜索能力，是全局收斂的，在解決小規模問題時優勢明顯。賀一等人^[15]對TSP進行求解，得出的結論是禁忌搜索算法的尋優下降過程非常快，在實際工作中若只滿足于求出滿意解，即亞優解，則該算法將是一個強有力的搜索工具，但它最大的缺點就是上面提到的解的質量與初始解有關，而且當求解大規模TSP時運行效率低。

從以上實例運算得出的結論來看，這三種算法在解決TSP時得出了比較理想的結果，但也都存在著隨著問題規模的擴大而精度下降的問題，很難準確地說出哪種算法更具優勢。所以它們雖然在目前的一些應用中已表現出相當好的性能，但其研究都還處于初級階段，不論理論還是應用都尚未成熟。表1給出了這三種算法到目前為止的研究現狀。縱觀近年來的研究成果，試圖使用單一的方法求解TSP的研究在減少，而使用多種方法結合，互相取長補短的研究比較多，也必將成為今后研究的主流。

3 結束語

上面就模擬自然現象和人類思維的三種仿生隨機優化算法進行了論述，這三種算法存在著共性和差異，但它們都能很好地解決以往傳統的數學方法很難解決的智能優化問題，目前已成為一個研究解決實際問題的熱點。但這三種算法各有其優缺點，往往只用一種算法來解決問題有一定的局限性，所以現在又有很多算法是將仿生算法的兩種或兩種以上綜合起來應用到實際工作中去，已經有一些國內外學者作了一些有益的嘗試，并收到了很好的效果。總之，仿生優化算法的研究還處于初步發展研究階段，但隨著對其研究的深入以及與其他智能方法相結合，必將成為智能優化、智能控制、模式識別、數據挖掘和計算機安全等領域研究應用的有力工具。

參考文獻：

［1］李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，2002，22(11)：32-38.

[2]BERSINI H，VARELA F.Hints for adaptive problem solving leaned from immune network[M].Berlin， Heidelberg:Springer-Verlag，1991：343-354.

[3]GLOVER F.Tabu search: part Ⅰ[J].ORSA Journal on Computing，1989，1(3):190-206.

[4]GLOVER F.Tabu search:partⅡ[J].ORSA Journal on Computing，1990，2(1):4-32.

[5]李濤.計算機免疫學[M].北京:電子工業出版社，2004.

[6]肖人彬，曹鵬彬，劉勇.工程免疫計算[M].北京：科學出版社，2007.

[7]李茂軍，羅安，童調生.人工免疫算法及其應用研究[J].控制理論與應用，2004，21（2）:153-157.

[8]HOFMEYR S A，FORREST S.Immunity by design:an artificial immune system[C]//Proc of GECCO’99.San Francisco: Morgan Kaufmann Publishers，1999:1289-1296.

[9]莫宏偉.人工免疫系統原理與應用[M].哈爾濱:哈爾濱工業大學出版社，2002.

[10]CHELOUAH R，SIARRY P.Tabu search applied to global optimization[J].European Journal of Operational Research，2000，123(2):256-270.

[11]FRANZE F，SPECIALE N.A tabu-search-based algorithm for continuo multiminima problems[J].International Journal for Numerical Methods in Engineering，2001，50(3):665-680.

[12]孫艷豐，戴春榮.幾種隨機搜索算法的比較研究[J].系統工程與電子技術，1998，20(2)：43-47.

[13]李曉磊，路飛，田國會，等.組合優化問題的人工魚群算法應用[J].山東大學學報，2004，34(5)：64-67.

[14]周輝，李NC05A，胡佳慶，等.旅行商問題的免疫算法[J].長沙電力學院學報：自然科學版，2003，18（2）：16-20.

[15]賀一，劉光遠.禁忌搜索算法求解旅行商問題研究[J].西南師范大學學報，2002，27（3）：341-345.

[16]GAMBOA D，REGO C，GLOVER F.Data structures and ejection chains for solving large-scale traveling salesman problems[J].European Journal of Operational Research，2005，160(1):154-171.

[17]劉于江，喻澤峰.一種求解旅行商問題的禁忌搜索算法[J].江西理工大學學報，2006，27（4）：38-40.

[18]ALISANTOSO D，KHOO L P，JIANG P Y.An immune algorithm approach to the scheduling of a flexible PCB flow shop[J].Advanced Manufuring Technology，2003，22(11-12):819-827.

[19]WANG Dong-dong， ZHOU Yong-quan， CAO Dun-qian. Artificial fish-school algorithm for solving nonlinear equations[J].Journal of Information Computational Science，2007，4(1):255-264.

[20]計明軍. 若干隨機性全局優化算法的研究[D]. 大連：大連理工大學研究生院，2004.