基于多樣性和局部優(yōu)化能力協(xié)同優(yōu)化的引力搜索算法

基于多樣性和局部優(yōu)化能力協(xié)同優(yōu)化的引力搜索算法

1改進的gsa算法該算法是一種發(fā)展算法，是對整個搜索空間問題的全局搜索方法。研究證明,GSA的全局搜索能力明顯優(yōu)于粒子群優(yōu)化算法在算法改進方面,文獻[10]對GSA引入反饋策略,均衡優(yōu)化了算法全局與局部搜索能力,文獻[11]在GSA中引入了三角范數(shù)算子,進一步提高了算法的全局搜索能力。文獻[12]對GSA的記憶性進行改進,提出記憶改進GSA(MemoryGravitationalSearchAlgorithm,MGSA),在一定程度上改善了GSA的局部搜索能力。研究發(fā)現(xiàn),以往的算法改進主要針對GSA算法的全局與局部搜索能力,但GSA在搜索過程中,每個粒子都向質(zhì)量大的粒子靠近,在這種方式下,由于多樣性的失去,粒子群易在全局近優(yōu)點的吸引下陷入局部最優(yōu),發(fā)生早熟收斂。在引力搜索算法中添加局部優(yōu)化策略和保持多樣性策略,從而在保留強大全局搜索能力與加強局部搜索能力的同時,更可以保持種群多樣性,避免早熟現(xiàn)象的發(fā)生。本文提出了在引力搜索算法中添加多樣性和局部優(yōu)化策略的方法。主要在粒子進化公式中引入粒子群算法2引力函數(shù)的引入引力搜索算法是近年來提出的用于解決優(yōu)化問題的啟發(fā)式算法,和其他現(xiàn)有的著名啟發(fā)式優(yōu)化算法相比,引力搜索算法具有更好的全局搜索能力和更快的收斂能力引力搜索算法中粒子的初始位置是隨機生成的。假設一個由N個粒子組成的粒子群在D維的搜索空間以一定的速度飛行,定義第i個粒子的位置為:X根據(jù)牛頓萬有引力定律,在第d維空間上第j個粒子對第i個粒子的作用力可以定義為:其中,M其中,fit在求解目標函數(shù)最大值問題時,best(t)和worst(t)定義如下:值得指出的是,引力系數(shù)G(t)決定了GSA算法的性能,搜索開始時就應對引力系數(shù)G(t)初始化,G(t)值隨著時間逐步減小,從而控制搜索精度。G(t)是關于初始值G其中,G通過在作用力F其中,kbest是一個隨著時間增加而減少的線性函數(shù)。一開始的值為搜索空間中粒子總數(shù),表示所有粒子相互間都有作用力,這樣就增加了粒子的全局搜索能力,避免陷入局部最優(yōu);隨著迭代過程的進行,應逐步增加粒子的局部搜索能力,故kbest值線性減少,最終值應為1,此時只有一個慣性質(zhì)量最大的粒子i作用于其他粒子。依據(jù)粒子所受作用力公式,若粒子慣性質(zhì)量為M基于萬有引力定律的搜索策略,粒子i在下一時刻的速度和位置的進化公式為:其中,rand3引入搜索方法的引入3.1快速更新技術(shù)基于群體的啟發(fā)式算法有2個共同點:探索與開發(fā)其中,L為搜索空間最長對角線長度;根據(jù)迭代過程中粒子群不同的多樣性選擇不同的速度更新方式。當diversity(N)≥d當diversity(N)≤d其中,rand3.2利用拉普拉斯反變換與四因素耦合的算法對于上述提出的改進的引力搜索算法可引入微分方程對其進行描述,采用控制理論對其搜索能力進行分析其中,τ為區(qū)間(0,1)間隨機選取的常數(shù)?，F(xiàn)將式(15)分別代入式(11)、式(13)可得:以式(16)為例進行分析,分解可以得到:其中,V(1)對于V由此可得:利用微分方程根據(jù)控制理論得到系統(tǒng)傳遞函數(shù),利用拉普拉斯反變換可得又因為τ∈(0,1),則:因此,參數(shù)選擇只要滿足而對于式(17),算法分析如式(16)。只要參數(shù)選擇滿足條件,系統(tǒng)就可以獲得振蕩環(huán)節(jié)。與采用一階微分方程描述的慣性環(huán)節(jié)相比,采用二階微分方程描述的振蕩環(huán)節(jié)能夠使粒子在全局最優(yōu)位置和局部最優(yōu)位置附近進行幅度由大到小的搜索,大大提高粒子速度的利用率和算法的全局與局部搜索能力。改進算法的流程如圖1所示。4全局搜索性能分析為驗證本文算法的有效性,選用以下4個測試函數(shù)進行測試,如表1所示。為更好地驗證多樣性與局部優(yōu)化能力改進的GSA(DiversityandLocalOptimizationGSA,DLOGSA)算法的優(yōu)越性,同時采用標準GSA(StandardGSA,SGSA)和MGSA對上述4個函數(shù)進行尋優(yōu)。采用WindowsXP為實驗仿真平臺,Matlab2010b版本進行仿真模擬。粒子種群數(shù)目設為50,每個算法獨立運行20次,最大迭代次數(shù)設置為1000,表1中n取30。按引力系數(shù)式(5),G對于每個測試函數(shù),每種算法分別獨立運行20次,表2給出了20次實驗后3種算法對每個測試函數(shù)的優(yōu)化結(jié)果的平均值、中間值和標準方差。Sphere是簡單的單峰值函數(shù),只有一個全局最優(yōu)解,SGSA、MGSA和DLOGSA在搜索過程中都可快速收斂至最優(yōu)值,不會陷入局部最優(yōu)。如圖2所示,3種算法的過程曲線較為相似,在迭代過程中始終保持著較快的收斂速度。但DLOGSA算法優(yōu)化結(jié)果從迭代開始就明顯優(yōu)于SGSA和MGSA,迭代快結(jié)束時DLOGSA算法收斂速度加快,獲得了良好的收斂效果。Noise函數(shù)是含有高斯噪聲的4次函數(shù),不考慮噪聲影響時,函數(shù)具有全局最小值f(0,0,…,0)=0。從圖3可以看出,在這個測試函數(shù)中,MGSA在前100次迭代中優(yōu)化結(jié)果明顯大于SGSA和DLOGSA,在100次~200次迭代過程中3種函數(shù)都快速收斂,很快收斂到最優(yōu)值,但在測試函數(shù)200次迭代過程以后SGSA和MGSA就陷入早熟收斂。相比較而言,DLOGSA在200次迭代以后仍進化振蕩向下,進一步收斂,最終找到最優(yōu)結(jié)果,其優(yōu)化結(jié)果明顯優(yōu)于SGSA和MGSA。Rastrigin函數(shù)是一個多峰值函數(shù),本次仿真模擬中選取30個維數(shù),故該測試函數(shù)是多峰高維函數(shù)。如圖4所示,在整個優(yōu)化的過程中,DLOGSA在迭代過程中一直保持很快的收斂速度,DLOGSA算法的優(yōu)化結(jié)果也明顯優(yōu)于SGSA和MGSA。SGSA和MGSA收斂過程類似,在迭代200次左右就陷入局部最優(yōu),表現(xiàn)為進化曲線平直,而DLOGSA持續(xù)進化振蕩向下。該結(jié)果表明對于這類復雜函數(shù),DLOGSA算法具有優(yōu)越性,這在于在進化過程中不僅有吸引操作更有排斥操作在起作用,很好地保持了種群的多樣性,避免函數(shù)陷入早熟收斂。Griewank函數(shù)是典型的多模態(tài)函數(shù),具有大量局部極值,可以很好地檢驗算法的全局搜索性能。如圖5所示,對于SGSA算法的改進并未影響SGSA原有的良好全局搜索性能。迭代之初,3種算法性能接近,在迭代100次~200次之間,DLOGSA的收斂速度就明顯快于SGSA和MGSA,而在迭代200次~300次之間,SGSA已收斂到局部最優(yōu)值,DLOGSA和MGSA仍持續(xù)振蕩向下,進一步收斂,最終DLOGSA優(yōu)化結(jié)果仍優(yōu)于MGSA。5改進的粒子群算法搜索粒子的研究本文在引力搜索算法的基礎上,提出一種改進對種群多樣性和粒子局部搜索能力的方法。針對引力搜索算法中粒子局部搜索能力弱和種群易陷入早熟收斂的情況,引入粒子群算法中的局部搜索思想和細菌趨化理論,使得粒子在進行速度更新時,對歷史最優(yōu)位置