柯金霖 付宗濤
【摘 要】在多變量函數優(yōu)化問題中,使用遺傳算法可能出現(xiàn)優(yōu)化結果不收斂的問題。針對此問題本文提出了一種新的算法,它模仿的是落體碰撞的過程。此算法全局搜索能力較強,且具有強收斂性,可以解決其他算法在特定算例中出現(xiàn)的不收斂問題。
【關鍵詞】函數優(yōu)化;落體碰撞算法;遺傳算法;收斂性
0 引言
利用遺傳算法進行優(yōu)化時,其局部搜索能力較弱[1],收斂性速度慢[2]是常見問題。在研究多變量函數優(yōu)化時,常常會碰到不收斂的情況。針對這個問題,本文提出了一個優(yōu)化算法——落體算法,該算法模擬落體碰撞過程。本文先介紹新算法的思路和原理,其次通過經典算法測試函數,對算法的正確性和效率性進行驗證;最后,通過對比展示新算法的特性以及優(yōu)缺點。
1 落體碰撞算法優(yōu)化
1.1 物理解釋
通常多變量函數存在非常多的峰值與谷值。函數優(yōu)化的目的便是尋找最小或最大值的數值和對應自變量。若把函數的極大值和極小值視為“山峰”與“山谷”,則落體在重力和碰撞的作用下會自然趨近于最低點:自由落體過程中機械能守恒,高度不斷降低,速度不斷增加;而每次碰撞,由于存在機械能損耗,落體會逐漸靜止,停止于“谷”中。
1.2 主要參數
以上過程涉及幾個參數:
a)落體個數:即選取初始點,其參考標準是函數的“谷”的數目,如果定義域只有一個谷,理論上只需取一個點數。而實際情況較為復雜,可以采用試取的方式,選定初始點數進行計算,若是結果較好且基本不變化,則可基本認定試取數目得當,否則需要加大點個數;
b) 時間步長:當一次碰撞完成后,落體何時何地達到下一碰撞點,這個判斷過程采用的是以時間步長為參考的運動積累過程;
c) 碰撞次數:整個尋優(yōu)過程中的碰撞次數,即算法的收斂性;
d) 重力加速度:決定碰撞速度的一個重要參數;
e)法向和切向速度恢復系數:每次碰撞過程中,速度的兩個方向分量的恢復系數,不宜小于0.9,否則碰撞會過早停止,但是亦不能太接近于1,否則會增加計算量。
f) “碰壁”和“觸地”:這兩個過程是算法核心步驟,而且必須要先判斷“碰壁”再判斷“觸地”?!芭霰凇辈皇且淮温潴w碰撞過程的結束,而只是中間過程,“觸地”才是一次落體碰撞過程結束。“碰壁”過程中可認為是完全彈性碰撞,不需要追究能量損耗的問題,可以把這個過程的恢復系數設為1。
1.3 算法測試
本文選取了三個測試函數編寫相應MATLAB程序來驗證其正確性[3],并與遺傳算法進行對比。表1所列為測試結果的主要內容。
上述遺傳算法結果是利用MATLAB遺傳算法工具箱獲得,初始個數大部分采用默認,小部分則根據函數情況進行了調整。從上表可以看出,落體算法能收斂到最優(yōu)解附近,但是收斂精度不一定夠高,而遺傳算法如果能夠收斂,則其收斂精度會好很多。但是從Schwefel函數看出,遺傳算法存在收斂到局部最優(yōu)解的問題。
從表中還可以看出各個參數對運行結果的影響。
(1)點個數:通常情況下個體越多越容易得到全局最優(yōu)解,但同時數目大小與運算耗時基本呈正比關系。Rastrigin Fuction和Hump Function函數中,個體數目為100,基本可以滿足結果收斂于最優(yōu)解的要求。
(2)最大碰撞次數:從表中可以看出,Schwefe Function在50次碰撞左右,其收斂狀況就很好,其余兩例在150次后也趨向收斂。這是由于在后期的落體碰撞過程中,法向速度趨近于豎直方向,水平方向的運動較少。隨著碰撞速度的減小,落體過程的時間也在縮短,這代表程序耗時逐漸減少。
2 總結
落體算法的主要優(yōu)點除了其有較好的全局搜索能力之外,還有就是其克服了收斂性問題。這些優(yōu)點很好地彌補了很多優(yōu)化方法。但是該算法也存在著缺點,主要為收斂精度不高和計算效率低兩個問題,有待后續(xù)進一步研究。
【參考文獻】
[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].北京:電子工業(yè)出版社,2010.
[責任編輯:朱麗娜]