一種函數優化的新算法

柯金霖　付宗濤

【摘 要】在多變量函數優化問題中，使用遺傳算法可能出現優化結果不收斂的問題。針對此問題本文提出了一種新的算法，它模仿的是落體碰撞的過程。此算法全局搜索能力較強，且具有強收斂性，可以解決其他算法在特定算例中出現的不收斂問題。

【關鍵詞】函數優化；落體碰撞算法；遺傳算法；收斂性

0 引言

利用遺傳算法進行優化時，其局部搜索能力較弱[1]，收斂性速度慢[2]是常見問題。在研究多變量函數優化時，常常會碰到不收斂的情況。針對這個問題，本文提出了一個優化算法——落體算法，該算法模擬落體碰撞過程。本文先介紹新算法的思路和原理，其次通過經典算法測試函數，對算法的正確性和效率性進行驗證；最后，通過對比展示新算法的特性以及優缺點。

1 落體碰撞算法優化

1.1 物理解釋

通常多變量函數存在非常多的峰值與谷值。函數優化的目的便是尋找最小或最大值的數值和對應自變量。若把函數的極大值和極小值視為“山峰”與“山谷”，則落體在重力和碰撞的作用下會自然趨近于最低點：自由落體過程中機械能守恒，高度不斷降低，速度不斷增加；而每次碰撞，由于存在機械能損耗，落體會逐漸靜止，停止于“谷”中。

1.2 主要參數

以上過程涉及幾個參數：

a）落體個數：即選取初始點，其參考標準是函數的“谷”的數目，如果定義域只有一個谷，理論上只需取一個點數。而實際情況較為復雜，可以采用試取的方式，選定初始點數進行計算，若是結果較好且基本不變化，則可基本認定試取數目得當，否則需要加大點個數；

b） 時間步長：當一次碰撞完成后，落體何時何地達到下一碰撞點，這個判斷過程采用的是以時間步長為參考的運動積累過程；

c） 碰撞次數：整個尋優過程中的碰撞次數，即算法的收斂性；

d） 重力加速度：決定碰撞速度的一個重要參數；

e）法向和切向速度恢復系數：每次碰撞過程中，速度的兩個方向分量的恢復系數，不宜小于0.9，否則碰撞會過早停止，但是亦不能太接近于1，否則會增加計算量。

f） “碰壁”和“觸地”：這兩個過程是算法核心步驟，而且必須要先判斷“碰壁”再判斷“觸地”。“碰壁”不是一次落體碰撞過程的結束，而只是中間過程，“觸地”才是一次落體碰撞過程結束。“碰壁”過程中可認為是完全彈性碰撞，不需要追究能量損耗的問題，可以把這個過程的恢復系數設為1。

1.3 算法測試

本文選取了三個測試函數編寫相應MATLAB程序來驗證其正確性[3]，并與遺傳算法進行對比。表1所列為測試結果的主要內容。

上述遺傳算法結果是利用MATLAB遺傳算法工具箱獲得，初始個數大部分采用默認，小部分則根據函數情況進行了調整。從上表可以看出，落體算法能收斂到最優解附近，但是收斂精度不一定夠高，而遺傳算法如果能夠收斂，則其收斂精度會好很多。但是從Schwefel函數看出，遺傳算法存在收斂到局部最優解的問題。

從表中還可以看出各個參數對運行結果的影響。

（1）點個數：通常情況下個體越多越容易得到全局最優解，但同時數目大小與運算耗時基本呈正比關系。Rastrigin Fuction和Hump Function函數中，個體數目為100，基本可以滿足結果收斂于最優解的要求。

（2）最大碰撞次數：從表中可以看出，Schwefe Function在50次碰撞左右，其收斂狀況就很好，其余兩例在150次后也趨向收斂。這是由于在后期的落體碰撞過程中，法向速度趨近于豎直方向，水平方向的運動較少。隨著碰撞速度的減小，落體過程的時間也在縮短，這代表程序耗時逐漸減少。

2 總結

落體算法的主要優點除了其有較好的全局搜索能力之外，還有就是其克服了收斂性問題。這些優點很好地彌補了很多優化方法。但是該算法也存在著缺點，主要為收斂精度不高和計算效率低兩個問題，有待后續進一步研究。

【參考文獻】

[1]Prügel-Bennett.A.：When a Genetic Algorithm Outperforms Hill-Climbing. Theoretical Computer Science.Vol. 320.（2004）135-153.

[2]王銀年.遺傳算法的研究與應用——基于3PM交叉算子的退火遺傳算法及應用.江南大學碩士論文.2009.

[3]陳杰，等.MATLAB寶典[M].北京：電子工業出版社，2010.

[責任編輯：朱麗娜]