一種函數(shù)優(yōu)化的新算法

柯金霖　付宗濤

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

【關(guān)鍵詞】函數(shù)優(yōu)化；落體碰撞算法；遺傳算法；收斂性

0 引言

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

1 落體碰撞算法優(yōu)化

1.1 物理解釋

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

1.2 主要參數(shù)

以上過程涉及幾個(gè)參數(shù)：

a）落體個(gè)數(shù)：即選取初始點(diǎn)，其參考標(biāo)準(zhǔn)是函數(shù)的“谷”的數(shù)目，如果定義域只有一個(gè)谷，理論上只需取一個(gè)點(diǎn)數(shù)。而實(shí)際情況較為復(fù)雜，可以采用試取的方式，選定初始點(diǎn)數(shù)進(jìn)行計(jì)算，若是結(jié)果較好且基本不變化，則可基本認(rèn)定試取數(shù)目得當(dāng)，否則需要加大點(diǎn)個(gè)數(shù)；

b） 時(shí)間步長：當(dāng)一次碰撞完成后，落體何時(shí)何地達(dá)到下一碰撞點(diǎn)，這個(gè)判斷過程采用的是以時(shí)間步長為參考的運(yùn)動(dòng)積累過程；

c） 碰撞次數(shù)：整個(gè)尋優(yōu)過程中的碰撞次數(shù)，即算法的收斂性；

d） 重力加速度：決定碰撞速度的一個(gè)重要參數(shù)；

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

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

1.3 算法測(cè)試

本文選取了三個(gè)測(cè)試函數(shù)編寫相應(yīng)MATLAB程序來驗(yàn)證其正確性[3]，并與遺傳算法進(jìn)行對(duì)比。表1所列為測(cè)試結(jié)果的主要內(nèi)容。

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

從表中還可以看出各個(gè)參數(shù)對(duì)運(yùn)行結(jié)果的影響。

（1）點(diǎn)個(gè)數(shù)：通常情況下個(gè)體越多越容易得到全局最優(yōu)解，但同時(shí)數(shù)目大小與運(yùn)算耗時(shí)基本呈正比關(guān)系。Rastrigin Fuction和Hump Function函數(shù)中，個(gè)體數(shù)目為100，基本可以滿足結(jié)果收斂于最優(yōu)解的要求。

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

2 總結(jié)

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

【參考文獻(xiàn)】

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

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

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

[責(zé)任編輯：朱麗娜]