于　干, 周紅志

(阜陽師范學院 信息工程學院，安徽 阜陽 236041)

?

一種新的自適應動態(tài)網格優(yōu)化算法

于干, 周紅志

(阜陽師范學院 信息工程學院，安徽 阜陽 236041)

摘要：針對動態(tài)網格優(yōu)化算法(GEA)收斂速度較快，收斂精度不夠理想，特別是解決多峰函數有可能會錯過全局最優(yōu)解的缺陷，提出了一種新的自適應動態(tài)網格優(yōu)化算法.通過評估早熟收斂程度，將早熟收斂程度、函數的峰值與步長的變化聯(lián)系起來，加入1個隨機因子用以調整搜索范圍，從而提高了算法的尋優(yōu)效率.通過對典型的MP問題的測試，并與其他的動態(tài)優(yōu)化算法比較，證明了算法的有效性.

關鍵詞：動態(tài)網格優(yōu)化算法；收斂程度；隨機因子；有效性

動態(tài)網格優(yōu)化算法(Gridding Evolutionary Algorithm，GEA)[1]是2007年由于干等人提出的一種基于網格節(jié)點的快速收斂算法.網格算法[2]的這種基于搜索網格節(jié)點的技術具有很強的定向搜索能力，主要體現為：算法能夠按照設計好的搜索技術總是搜索當前幾個較好的方向，這項技術能夠保證算法不局限于只圍繞一個點搜索，從而陷入局部最優(yōu)，因此理論上它每次運行都能找到函數的全局最優(yōu)解.

但網格優(yōu)化算法的定向搜索特性在一定程度上限制了算法本身的隨機性，優(yōu)化結果的優(yōu)劣很大程度上依賴于研究者給出的定向搜索信息，即所設置的一些參數如：演化步長、每代設定的較優(yōu)解個數、每代搜索的網格點個數等.研究者通過對文獻[3-4]的研究，借助其研究成果，設計了一種具有自適應能力的動態(tài)網格優(yōu)化算法.本文提出的改進網格優(yōu)化算法同傳統(tǒng)的網格算法的主要不同在于：算法的自調節(jié)、自適應能力，也就是在不改變算法的定性特性的前提下，增加了算法的隨機性，同時在種群初始化時也采用隨機初始化方法.改進后的算法通過實驗與文獻[3-5]的研究結果進行比較，驗證了算法的有效性.

1自適應動態(tài)網格優(yōu)化算法(AD-GEA)

GEA的基本思想是：首先以待求解的函數變量區(qū)域的中心位置點為中心，依據設定好的步長值(步長值的初始值設置為函數變量區(qū)域長度的一半，標記為perlength)，根據函數的維數，將變量區(qū)域劃分網格；依據適應值函數計算網格上各個網格節(jié)點的適應值，再統(tǒng)計適應值較好的幾個點作為下一代演化的父代種群(較好點的個數需要根據函數的維數設定，一般設為4～8)；將步長值減少(一般減為原步長值的一半)，以新的步長分別在上一代保存的較好點的周圍劃分網格，分別計算每個網格上各個網格節(jié)點的函數值，分別找出幾個較好個體暫存到較好個體集中，待所有網格點周圍的較好個體搜索完成之后，篩選出較好的幾個網格點作為下一代搜索種群；在新的搜索種群個體周圍進行下一代的搜索.直到停止條件滿足.

圖1　GEA算法搜索過程

圖1演示了GEA算法的搜索過程，算法每代只存放一個較好點.其中第一次以變量區(qū)間中心點為中心劃網格，計算網格上所有網格點的函數值(空心圓點、中間的紅色矩形點)，第一次找到的較好點假定為紅色矩形點；第二次以紅色矩形點為中心，以原步長的一般值再次劃網格，計算網格上所有網格點的函數值(空心矩形點、紅色圓點)，本次找到的較好點假定為紅色圓形點；將步長再次減半，以紅色圓形點為中心劃分網格，計算、找出較好點假定為紅色菱形點.依次搜索下去直到滿足停止條件.

1.1網格優(yōu)化算法特點及收斂性分析

從算法思想的描述可以得出算法的幾個特性：

(1)算法從第一代設定幾個網格點作為目前較好適應點，到以后每代產生幾個最好適應點，算法都是圍繞設定好的幾個較好網格點周圍展開搜索過程，這使得算法能夠朝著潛在的最優(yōu)解方向進行搜索.因此，算法不會盲目搜索，可以說這種搜索過程是一種確定性的搜索過程.

(2)每代設定好幾個較好個體作為搜索的中心，且搜索每個較好個體以后都需要按照一定的規(guī)則在這個較好點的周圍再篩選出幾個較好的點暫存起來.當所有較好點按照此過程完成搜索以后，將所有暫存的較好解組合在一起篩選找出最好的幾個點用于下一代搜索.這樣保證了整個算法的搜索過程不會陷入到某一個最好點的局部搜索，避免了局部最優(yōu)問題.

(3)算法的演化搜索過程中步長的設定一般都將步長逐次減半，也就是在當前搜索過程中在每個最好點的周圍進行網格劃分時所依據的步長為上一代所用步長值的1/2，在測試實驗中函數的變量區(qū)域一般都不是很大.因此，在設置初始步長時通常設置為每維變量的區(qū)間范圍的一半，通過這種快速的收縮過程使得算法能夠很快地收斂到要搜索的函數全局最優(yōu)解.

綜上，網格優(yōu)化算法具有：定向性、不易陷入局部最優(yōu)、快速收斂等特性.

1.2自適應動態(tài)網格優(yōu)化算法實現技術

基本網格優(yōu)化算法依據步長快速變化而達到收斂目標，但這種技術也存在兩個明顯的缺陷：a)實際搜索過程中復雜的非線性行為在快速收斂的過程中，得不到有效的反映，導致收斂精度不夠理想;b)網格優(yōu)化算法每代都是圍繞在設定好的幾個較好解周圍進行搜索，這種搜索過程解決單峰函數效果很好，但解決多峰函數有可能會錯過全局最優(yōu)解,因此它對于復雜問題的適應能力和調節(jié)能力都十分有限.

基于以上兩個問題，本文在參考文獻[3-4]中的自適應策略基礎上，提出了一種動態(tài)隨機調整策略，將早熟收斂程度、函數的峰值與步長的變化聯(lián)系起來.基本思想是：解決單峰函數時，步長的變化依據早熟收斂程度設定.如果收斂程度較快，步長變化需慢些，以增加網格搜索范圍，反之按照步長減半處理；解決多峰函數時步長變化依照單峰函數變化策略的同時增加1個隨機因子.基本思想是將步長的變化與搜索過程的早熟收斂程度的指標聯(lián)系起來，具體可按照下面公式進行：假設當前步長設為：Plen，下一代步長設為Nlen:

Nlen=w(t)Plen;

(1)

w(t)=1-(1+e-p)-1

(2)

式中，p為隨機因子用于評價算法的收斂程度，p越小說明算法越趨于收斂.w(t)為步長變化權重值，由公式(2)看以看出，算法的步長變化權重值在(0，1)內變化，當p減小時(即算法趨于收斂)w(t)則增加，也就是擴大搜索范圍，反之則減小.w(t)描述了在第t代的步長變化相對收斂速度的影響，w(t)取值大小可以調節(jié)GEA算法全局尋優(yōu)能力與局部尋優(yōu)能力，w(t)值較大，全局尋優(yōu)能力強，局部搜索能力弱;反之，則全局尋優(yōu)能力弱，局部尋優(yōu)能力增強.恰當的w(t)可以提高算法性能，提高尋優(yōu)能力，同時減少迭代次數.當GEA處于收斂狀態(tài)時，需要增加搜索步長，從而增強GEA的全局尋優(yōu)能力;當GEA處于全局搜索狀態(tài)時，需要減小搜索步長，從而增強算法局部尋優(yōu)能力.當早熟收斂程度的指標減小時，w(t)相應增加，增強了全局搜索能力；相反增大時，w(t)值將隨之減小，增加局部搜索能力.

1.3自適應動態(tài)網格優(yōu)化算法流程

綜合以上基本原理，本文算法的基本流程如下：

a)種群初始化:在函數變量區(qū)間內隨機產生M個點，通過研究證明M取值與函數的維數有關，當維數較低時M取值范圍為5～10，當維數較高時M取值范圍為20～50.具體做法是(以n維函數為例)：在函數變量區(qū)間內對任1個xi隨意取值，形成1個點(x1,x2,x3，…,xn),作為當代搜索種群中的1個個體.然后按照此方法產生搜索種群的其他M-1個個體，M個種群個體必須包含函數變量區(qū)域中心點個體，形成初始種群Gen[M]；

b)設定初始步長:Pleni為函數變量xi區(qū)間長度值的一半；

c)在Gen[M]每個個體Mi周圍分別實現：以當前步長Pleni為依據在每個變量區(qū)間上劃分網格，任意一個變量都有xi，xi±Pleni，xi±2*Pleni等5種可能取值，然后所有xi可能取值在一起，隨機的組合形成一組(x1,x2,x3，…,xn)，統(tǒng)計這些點的函數適應值，比較后選出n個較好的點(n值一般取3～5)，放入較好種群Betterpoint[n*M]中；

d)產生下一代演化種群個體集：在步驟c完成的基礎上，在Betterpoint[n*M]中選出M個適應值較好點，從而得到BestPoint[M]作為下一代種群Gen[M]；

e)計算算法的收斂程度:BestPoint[M]中M個點的函數適應值最優(yōu)解與實際最優(yōu)解的的差值作為計算依據，當差值小于0.001時，p值取較小值取值范圍為(0～0.5)，反之p取較大值取值范圍為(0.5～1.0)；

f)計算下一代步長：利用公式(1)、(2)計算出下一代步長Plen；

g)演化搜索過程終止判定：若滿足算法終止條件則停止搜索過程；如不滿足則轉至步驟b.通常算法的終止條件設置為：演化代數滿足要求或BestPoint[M]所有個體的適應值最大差值<=0.000 01.

2仿真實驗

2.1實驗函數

為對本文算法的思想進行有效性的驗證，本文測試了MP(MovingPeak)問題[6](由Branke提出)，函數形式如下:

(3)

式中，X(t)、Wi(t)、Hi(t)分別表示時刻t時峰i的位置、寬度和高度，峰的個數用m表示，n代表函數的維數，函數問題的一個解用X=(x1,x2,x3，…,xn)表示，每個解X的適應值為F(X，t).Hi(t)、Wi(t)和X(t)的變化過程為：

Hi(t)=Hi(t-1)+α·β

Wi(t)=Wi(t-1)+β·δ

α和β分別表示與函數的高度和寬度相關的懲罰因子，σ是一個用于增加函數隨機性的高斯變量，同時為了控制峰的變化方向增加了一個隨機矢量V.

函數的維數、峰每次變化所移動的距離及函數峰的個數均是MP函數的決定性參數.因此，AD-GEA的實驗將主要在這幾個方面與文獻[3-6]中所提到的GEA、SOS、AD-CPSO算法進行比較.

2.2實驗結果

表1給出了在本文的實驗中函數的所有初始化參數.其中f是函數變化的頻率,A表示函數自變量變化范圍，H表示峰高的變化范圍，W表示峰寬的變化范圍,I表示所有峰的初始化高度，M為所有實驗中測試函數的變化次數.

表1　實驗函數的所有初始化參數

表2　峰移距離S不同,GEA和SOS算法所得到的平均誤差值

表3　峰數n不同時,GEA和SOS算法所得到的平均誤差值

上述實驗結果(表2、表3)表明：在解決動態(tài)函數優(yōu)化問題方面，AD-GEA能夠很好地解決動態(tài)函數優(yōu)化問題,無論是演化代數還是誤差值均明顯好于文獻[3-6]中所提到的GEA、SOS、AD-CPSO算法.特別是在求解低維數的優(yōu)化函數時,GEA的快速收斂性和精確性優(yōu)勢更加明顯.

3結語

針對GEA算法收斂速度較快，收斂精度不夠理想，特別是解決多峰函數有可能會錯過全局最優(yōu)解的缺陷，本文提出了一種新的自適應動態(tài)網格優(yōu)化算法.通過評估早熟收斂程度，將算法的搜索過程與收斂程度結合起來，加入一隨機因子用以調整搜索范圍，從而提高了算法的尋優(yōu)效率.

自適應動態(tài)網格優(yōu)化算法和別的優(yōu)化算法相比，具備以下不同點：

1)算法并不是記憶存儲過的所有有效信息，它只是將當前一代比較有效的結果用于下一代的優(yōu)化；

2)算法并不是在這個優(yōu)化空間不停地搜索，而是將搜索空間劃分成多個區(qū)域，依據當前的優(yōu)化信息在最優(yōu)希望的區(qū)域進行搜索.

需要指出的是，本文算法在解決多維、高峰函數優(yōu)化問題時，如何進一步減少每代搜索的個體個數，將是下一步研究的重點.

[參考文獻]

[1]吳亞麗,徐麗青.一種基于粒子群算法的改進多目標優(yōu)化算法[J].控制與決策,2012,27(8)：1127-1132.

[2]于干，李長河，康立山.一種新的基于網格的函數優(yōu)化算法[J].計算機應用，2007，27(7)：1760-1759.

[3]WANG YS,AI JB，SHI YJ，et al.Cultural- based particle swarm optimization algorithm[J].Journal of Dalian University of Technology,2007,47(4):539-544.

[4]任圓圓,劉培玉,薛素芝.一種新的自適應動態(tài)文化粒子群優(yōu)化算法[J].計算機應用研究，2013,30(11):3240-3243.

[5]于干，康立山.基于網格的一種新的動態(tài)演化算法[J].計算機應用，2008，28(2)：319-322.

[6]BRANKEJ,KAUFLERT,SCHMIDTC,et al.A multipopulation approach to dynamic optimization problems[C]∥Adaptive Computingin DesignandManufacturing.NewYork:Springer-Verlag,2000:299-308.

[責任編輯馬云彤]

A New Adaptive Dynamic Gridding Evolutionary Algorithm

YU Gan， ZHOU Hong-zhi

( School of Information Engineering, Fuyang Teachers College, Fuyang 236041, China )

Abstract：In view of the shortage of fast convergence speed of optimization algorithm for dynamic Gridding Evolutionary Algorithm (GEA), unsatisfactory convergence precision and especially the defect in missing the global optimal solution when solving multimodal function, a new optimization algorithm for adaptive dynamic gridding was proposed in this paper. It improves the optimization efficiency of the algorithm by evaluating the degree of premature convergence, linking the degree of premature convergence and the change of peak and step of function and adding a random factor to adjust the search scope. It proves the effectiveness of the algorithm through the tests on the typical MP problem and comparisons with other dynamic optimization algorithms.

Key words：dynamic gridding evolutionary algorithm; convergence degree; random factor; effectiveness

中圖分類號：TP393.028

文獻標志碼：A

作者簡介：于干(1982—)，男，安徽亳州人，阜陽師范學院信息工程學院講師，碩士，主要從事智能計算與智能優(yōu)化研究.

基金項目：安徽省自然科學一般項目(2014FXSK01)；安徽省自然科學項目(2015FXTZK03)

收稿日期：2015-04-30

文章編號：1008-5564(2016)01-0048-04