基于混沌技術的連續禁忌搜索算法研究

摘要:將混沌技術與加強連續禁忌搜索算法(ECTS)相結合，利用混沌的隨機性和遍歷性，結合ECTS算法的快速性，提出一種混合最優化搜索算法——混沌加強連續禁忌搜索算法(CECTS)。通過應用Benchmark函數對CECTS算法進行測試表明，CECTS相對于ECTS算法能夠提高尋優的成功率，減少目標函數的計算量，是一種比較適合工程優化問題的優化方法。

關鍵詞:混沌; 加強連續禁忌搜索; 連續系統; 優化

中圖分類號:TP18文獻標志碼:A

文章編號:1001－3695(2008)02－0411－03

禁忌搜索(tabu search，TS)算法的思想最早由Glover[1]提出，它是對局部領域搜索的一種擴展。TS算法最重要的思想是標記對應已搜索到的局部最優解的一些對象，并在進一步的迭代搜索中盡量避開這些對象，從而保證對不同的有效搜索途徑的探索。TS算法已經成功應用于組合優化問題[2]，但其在連續系統優化中的應用還不多。文獻[3]提出了連續禁忌搜索算法(CTS)。與隨機搜索算法(RS)和模擬退火算法(SA)相比，CTS算法具有一定的優越性。但該算法采用分散化搜索來尋找最優解，增加了尋優計算量，并且CTS的尋優成功率不能得到保證。

為解決CTS算法的上述問題，文獻[4]采用分散化搜索和集中化搜索相結合的方式，提出了加強連續禁忌搜索算法(ECTS)。測試表明，在同樣的條件下，ECTS與CTS相比需要更少的目標函數計算量，并且尋優成功率明顯提高。但是ECTS算法還存在一些問題:a)領域隨機數的產生方法不能實現遍歷性;b)最有希望區的搜索方法容易錯過更好的希望區。文獻[5]在原ECTS的基礎上進行了一定的改進，提高了獲得最有希望區的可能性，但仍存在不能實現遍歷的問題。

1ECTS算法的介紹

1.1ECTS的實現方法

ECTS是一種解決連續優化問題的算法。它主要由五部分組成(圖1)[4]，即參數設置#65380;分散化搜索#65380;最有希望區的識別#65380;集中化搜索#65380;最佳點的輸出。其中第二#65380;三#65380;四部分為三個核心步驟。

ECTS算法首先進行參數的設置，這包括禁忌表和希望表的大小#65380;禁忌球和希望球的半徑等。之后在整個搜索空間內產生一定數量的隨機數，計算有希望區接收閾值，選擇其中的最佳解為當前解，并將其加入禁忌表。

分散化搜索用于確定有希望區的列表，在以當前最佳解為中心的超立方體中產生一定數量的領域解。為了避免迂回搜索，屬于禁忌表的領域解將被清除，選擇剩余領域解中的最佳解為當前解，并將其加入禁忌表;同時對當前最佳解進行希望區的檢測(檢測方法參見文獻[4])。如果滿足希望區的接受條件，則更新希望表。重復執行上述過程，直到滿足在一定迭代步數內未發現新的希望區為止。至此結束分散化搜索。

最有希望區搜索針對分散化搜索所產生的每一個有希望解執行“產生領域解#65380;選取最佳解”的搜索過程;然后用最佳領域解替換有希望解(僅在領域解優于有希望解時執行)，而當整個希望表被掃描后，算法將移去最不重要的有希望區。上述過程重復進行，直到只有一個有希望區域存在，即最有希望區。

集中化搜索應用CTS算法在最有希望區內進行集中化搜索，直到滿足一定的終止準則。

1.2ECTS算法的問題

文獻[4]對ECTS算法進行了測試，并與其他算法進行了對比，表明ECTS具有一定的優越性。但是，通過對ECTS算法執行過程的分析，發現該算法存在以下問題:

a)領域隨機數的產生方法存在不能實現遍歷性的問題。ECTS算法在初始化階段，有希望區接收閾值的計算采用隨機方式在整個搜索空間內產生一定數量的采樣點，接受閾值取為這些采樣點的目標函數值的平均值。這種方法所產生的采樣點只具有隨機性，而不具有遍歷性，這使得所產生的接收閾值或者偏大，或者偏小。對于極小值問題，偏小將可能錯過最有希望區;偏大則會增加搜索計算量。同時，在進行領域隨機數的產生時，ECTS算法同樣存在上述問題，即產生領域隨機數的方式不能實現均勻遍歷性。這將降低搜索效率，增加反復的搜索過程。

b)ECTS算法中最有希望區的搜索采用先確定全部有希望區，然后再進行最有希望區搜索。該方式存在一個問題:如果定義域范圍較大，則希望表的大小必須很大，同時在之后的最有希望區的搜索中將增加計算量。

為解決此問題，文獻[5]采用在搜索有希望區的同時搜索最有希望區的方式。這樣不但可以節省有希望區的存儲空間，而且可以提高最有希望區的準確定位能力。本文依舊采用文獻[4]的隨機數產生方式，第一個問題仍然存在。

2CECTS算法

2.1混沌隨機序列產生方法的改進

混沌是非線性系統所獨有且廣泛存在的一種非周期的運動形式，表現出介于規則與隨機之間的一種行為。其具有精致的內在結構，能把系統的運動吸引并束縛在特定的范圍內，按其自身規律不重復遍歷所有狀態。這里選用最常用的混沌映射——logistic映射[6]:

圖2是logistic映射的概率密度分布圖。從圖中可以看出，概率密度分布是中間稀#65380;邊緣密，而且密度函數在(0，1)區間內是以0.5為中心對稱的。

鑒于logistic混沌映射的特點，為了能夠得到均勻分布的混沌隨機分布，從而提高CECTS算法的全局搜索能力，本文對上述混沌隨機序列的產生方式進行了改進。下面僅以一維混沌隨機序列的產生方法加以介紹，多維混沌隨機序列的產生方法類似。其具體步驟如下:

a)初始化參數。下邊界LB=0;上邊界UB=1;混沌隨機數產生的次數為Nset，通過測試Nset取為3時能夠達到較好的均勻分布效果;邊界的遞減比例系數為Ld，根據logistic映射的概率密度分布函數，本文取為0.2;設定初始循環次數N=1;初始混沌隨機序列長度為LN。

b)在區間(0，1)內隨機產生混沌隨機序列的初始值x0(不動點0.25#65380;0.5#65380;0.75除外)。

c)應用logistic映射進行迭代操作，產生長度為LN的混沌隨機數序列x，并將其存儲于序列X中。

d)應用式(3)更新上下邊界值，即

f)判斷是否滿足N

g)輸出混沌隨機序列X，結束算法。

圖3為應用文獻[4]的方法產生的二維隨機序列分布圖(圖3(a))與應用上述混沌隨機序列產生方法生成的二維隨機序列分布圖(圖3(b))的對比。可以看出，在同樣的條件下，應用本文方法實現的隨機序列較文獻[4]的方法更具遍歷性。

2.2CECTS算法的實現

圖4為CECTS算法的基本流程。其主要由三部分組成，即初始化#65380;分散化搜索及集中化搜索。CECTS算法是在ECTS算法的基礎上發展起來的。由于篇幅所限，下面僅就CECTS算法相對ECTS算法的幾點不同加以說明。

a)有希望區的接收閾值采用混沌技術產生的隨機數進行計算，利用混沌技術的遍歷性。使得有希望區初始接收閾值相對ECTS算法準確，提高有希望區的準確定位能力。

b)領域解的產生方式亦采用混沌技術在超立方體內產生隨機數。這樣增加了領域解的遍歷性，提高了搜索能力。

c)最有希望區的搜索移入分散化搜索中，在搜索有希望區的同時搜索最有希望區。該方法可以縮小希望表的大小，減少搜索的計算量和存儲量，提高計算效率。CECTS算法最有希望區搜索的步驟為:在每次接受一個有希望區的同時，應用混沌技術在該區內產生隨機數，并計算該區的最佳目標函數值;在當前的希望列表中，選擇最佳目標函數值最大的希望區為最有希望區。

3CECTS算法的性能測試

為驗證CECTS算法的性能，本研究應用標準測試函數Benchmark[4]對算法進行測試。為了能夠與ECTS算法進行對比，測試采用與文獻[4]相同的測試條件及性能評價函數，即評價函數取為對每一測試函數以不同的初始值分別計算100次的尋優成功率#65380;目標函數平均計算次數及平均誤差(具體的定義參見文獻[4])。 所選用的Benchmark測試函數如下:

測試函數的全局最小值點如表2所示。表3為應用上述測試函數對CECTS算法進行測試的結果與文獻[4]中ECTS測試結果的對比。從對比結果可以看出，CECTS相對ECTS具有相當或更高的尋優成功率，這主要是因為采用了混沌隨機數產生方式，增加了最有希望區的定位能力，從而提高了尋優成功率。從目標函數的平均計算次數的對比可以看出，除了測試函數R2#65380;Z2#65380;Z10外，其余的測試函數的平均計算次數明顯減少，提高了搜索效率。CECTS算法所達到的平均誤差與ECTS算法基本一致，這主要是在集中搜索階段，兩者采用了相同的搜索方法，可以采用基于梯度的算法進行集中搜索[5]，以減少平均誤差，獲得更好的優化精度。

4結束語

禁忌搜索算法(TS)是對局部領域搜索的一種擴展，其已經成功應用于組合優化問題，但在連續系統優化中的應用還不多。本文將混沌技術與加強連續禁忌搜索算法(ECTS)相結合，利用混沌的隨機性和遍歷性，并結合ECTS算法的快速性，提出一種混合最優化搜索算法——混沌加強連續禁忌搜索算法(CECTS)。通過應用benchmark函數對CECTS算法進行測試，結果表明:CECTS算法相對于ECTS算法能夠提高尋優的成功率，減少目標函數的計算量，是一種比較適合工程優化問題的優化方法。

參考文獻:

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

[2]PASQUALE C， STEFANO G. A tabu search approach for scheduling Hazmat shipments[J]. Computers Operations Research， 2006，34(5):1328－1350.

[3]SIARRY P， BERTHIAU G. Fitting of tabu search to optimize functions of continuous variables[J]. International Journal for Numerical Methods in Engineering， 1997，40(13):2449－2457.

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

[5]TEH Y S， RANGAIAH G P. Tabu search for global optimization of continuous functions with application to phase equilibrium calculations[J]. Computers Chemical Engineering， 2003，27(11):1665－1679.

[6]黃潤生，黃浩.混沌及其應用[M].武漢:武漢大學出版社，2005.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”