二維拋物型反問題的蟻群算法求解

[摘 要] 蟻群優化算法是一種新興的優化技術，它的思想來源于人工生命和演化計算理論。蟻群算法簡單容易實現、可調參數少，已經得到了廣泛研究和應用。本文提出了一種結合有限元方法求解偏微分方程反問題的蟻群優化算法，在對微分方程模型測試的數值模擬中都得到了較好的結果，體現了該算法的有效性、通用性和穩健性。

[關鍵詞] 數學物理 蟻群優化算法 求解

引言

數學物理反問題是一個新興的研究領域。有別于傳統的數學物理方程的定解問題（通常稱為正問題，它由給定的數學物理方程和相應的定解條件來求定解問題的解），反問題研究由解的部分已知信息來求定解問題中的某些未知量，如微分方程中的系數，定解問題的區域或者是某些定解條件。二維拋物型反問題是數學物理反問題中的一個重要方面，多年來人們已經為此進行了一系列的研究，提出了不少富有成效的求解方法，如最佳攝動量法，正則化方法等。但這些經典的方法一般都要求函數連續并且可微，大都使用了基于梯度信息的數學技巧，在接近最優解的時候，往往會出現所謂的鋸齒現象，收斂緩慢。因此傳統的優化方法并不適合于求解不可微函數以及高維函數的優化問題。近年來蓬勃發展起來的智能演化算法被廣泛應用于優化領域，其全局最優性、可并行性和高效性在函數優化中得到了廣泛的應用。1991年意大利學者Marco Dorigo及其導師Colorni提出了一種更簡單、更有效的智能演化算法——蟻群優化算法（簡稱ACD），是智能演化算法產生以來在算法方面取得的巨大進展，該算法在許多領域都取得了廣泛的應用。蟻群優化算法不僅能更快、更穩定地收斂到問題的全局最優解，而且它要比其他算法簡單得多。

本文在目前組合優化領域中頗有成效的蟻群算法思想的基礎上，提出了一種改進的求解反問題的連續型蟻群算法，對函數優化問題沒有任何可微甚至連續的要求。通過一系列測試，效果良好。

蟻群智能

昆蟲學家們在研究類似螞蟻這樣的視盲動物如何沿最佳路線從其巢穴到達事物源的過程中發現，螞蟻與螞蟻之間最重要的通信媒介就是它們在移動過程中所釋放的特有的分泌物——信息素。當一個孤立的螞蟻隨機移動時，它能檢測到其他同伴所釋放的信息素，并沿著該路線移動，同時又釋放自身的信息素，從而增強了該路線上的信息素數量。隨著越來越多的螞蟻通過該路線，一條最佳的路徑就會逐漸形成。蟻群智能是多螞蟻的聚集行為，信息素是該系統的標識，整個蟻群智能具有一些特點：非線性，涌現和自組織性；活性主體和并行性；正反饋和初值敏感；個體與環境及其他個體相互影響，相互作用；把宏觀與微觀有機地聯系在一起，引進了隨機因子。螞蟻選擇路徑是隨機的，只不過螞蟻選擇信息素濃度高的路徑的概率高于信息素濃度低的路徑。算法中隨機因子擴大了螞蟻的活動范圍，從而能夠使螞蟻接觸到更多的解。

求解函數優化問題的ACD算法

在新一代的智能型算法——蟻群算法中，盡管仍未能徹底解決收斂性問題，但至少對于求解一般函數優化問題而言，沒有對這些優化函數要求任何可微甚至連續的前提條件。

一個經典的帶約束函數優化問題可寫成如下形式：

用常規的罰函數將所有約束方程轉入目標函數中，這樣，在算法的具體搜索過程中可不必考慮約束是否滿足的問題，而直接通過對目標函數的評價，由罰函數來強制這種形式滿足。

對每個螞蟻i，定義其評價函數值為相應的目標函數值Zi并記 .

定義轉移概率：

其中，Ti為螞蟻i的鄰域（半徑為r）內的信息素數量，α，β為非負數。

算法中的轉移概率定義不同于其在組合優化路徑類問題中的實現，搜索過程將分兩部分來尋找最優解。

第一部分是將給定個數的螞蟻隨機地散布在解讀定義域內的等分區域的某處，可按以下方法生成：

rand是[0，1]之間的隨機數，并記錄具有最好評價函數值的精英螞蟻。

第二部分是按轉移概率移動個螞蟻，并嵌入鄰域搜索機制（按ΔZij的正負來決定是否作鄰域搜索），試圖尋找更好的解，然后按螞蟻信息素更新規則進行軌跡更新。

通過不斷地重復上述過程，使算法能夠找到問題的最優解，或較好的滿意解。求解函數優化問題的基本蟻群算法思想可簡述如下：

步驟1. 初始化：

nc←迭代次數；m←螞蟻個數；

對每個螞蟻 （較小的正常數）；

（外循環）

步驟2. 對每個螞蟻k：

在X的定義范圍內隨機生成一個解X(k)，并計算相應評價函數值；

Z*←當前最好的評價函數值，X*←對應Z*的X；

步驟3. 置s←1（內循環）

步驟4. 對每個螞蟻k：

按轉移概率Pkj將X（j ），；

（Q為單位螞蟻遺留的信息素數量）

以鄰域半徑r對X(k)作局部搜索，更新Z*和X*；

步驟5. s←s+1；

步驟6. 若s<預定次數≤nc（可自定），則轉移步驟4；

步驟7. 對每個螞蟻； ；

步驟8. r ← r ·99%；（按99%縮減，可自定縮減比例）

步驟9.count

步驟10. 輸出Z*和X*。

結 論

本文在基本的粒子群算法的基礎上，成功地與有限元方法相結合，在求解拋物型方程反問題上顯示了該算法的優越性，實驗結果表明，本文提出的算法對偏微分方程反問題均適用，該算法可以更快、更穩定地收斂到問題的全局最優解，而且該算法易懂，通用。

參考文獻：

[1]Kenneth Price， Rainer M Storn， Jouni A. Lampinen differential evolution: a practical approach to global optimization. Springer， 2004.

[2]吳志健，康立山，鄒秀芬.一種解函數優化問題的精英子空間演化算法[J].計算機應用，2003，23(2):13-14.

[3]陽明盛，羅長童.最優化原理、方法及求解軟件[M].北京:科學出版社，2006.

[4]龔純，王正林.MATLAB常用算法程序集[M].北京:電子工業出版社，2008.

[5]王正林，劉明.精通MATLAB7[M].北京:電子工業出版社，2006.

作者單位：西安交通大學城市學院 陜西西安