一種新的自適應(yīng)動(dòng)態(tài)網(wǎng)格優(yōu)化算法

于　干, 周紅志

(阜陽(yáng)師范學(xué)院 信息工程學(xué)院，安徽 阜陽(yáng) 236041)

?

一種新的自適應(yīng)動(dòng)態(tài)網(wǎng)格優(yōu)化算法

于干, 周紅志

(阜陽(yáng)師范學(xué)院 信息工程學(xué)院，安徽 阜陽(yáng) 236041)

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

關(guān)鍵詞：動(dòng)態(tài)網(wǎng)格優(yōu)化算法；收斂程度；隨機(jī)因子；有效性

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

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

1自適應(yīng)動(dòng)態(tài)網(wǎng)格優(yōu)化算法(AD-GEA)

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

圖1　GEA算法搜索過(guò)程

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

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

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

(1)算法從第一代設(shè)定幾個(gè)網(wǎng)格點(diǎn)作為目前較好適應(yīng)點(diǎn)，到以后每代產(chǎn)生幾個(gè)最好適應(yīng)點(diǎn)，算法都是圍繞設(shè)定好的幾個(gè)較好網(wǎng)格點(diǎn)周圍展開(kāi)搜索過(guò)程，這使得算法能夠朝著潛在的最優(yōu)解方向進(jìn)行搜索.因此，算法不會(huì)盲目搜索，可以說(shuō)這種搜索過(guò)程是一種確定性的搜索過(guò)程.

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

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

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

1.2自適應(yīng)動(dòng)態(tài)網(wǎng)格優(yōu)化算法實(shí)現(xiàn)技術(shù)

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

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

Nlen=w(t)Plen;

(1)

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

(2)

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

1.3自適應(yīng)動(dòng)態(tài)網(wǎng)格優(yōu)化算法流程

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

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

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

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

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

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

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

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

2仿真實(shí)驗(yàn)

2.1實(shí)驗(yàn)函數(shù)

為對(duì)本文算法的思想進(jìn)行有效性的驗(yàn)證，本文測(cè)試了MP(MovingPeak)問(wèn)題[6](由Branke提出)，函數(shù)形式如下:

(3)

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

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

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

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

函數(shù)的維數(shù)、峰每次變化所移動(dòng)的距離及函數(shù)峰的個(gè)數(shù)均是MP函數(shù)的決定性參數(shù).因此，AD-GEA的實(shí)驗(yàn)將主要在這幾個(gè)方面與文獻(xiàn)[3-6]中所提到的GEA、SOS、AD-CPSO算法進(jìn)行比較.

2.2實(shí)驗(yàn)結(jié)果

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

表1　實(shí)驗(yàn)函數(shù)的所有初始化參數(shù)

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

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

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

3結(jié)語(yǔ)

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

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

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

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

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

[參考文獻(xiàn)]

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

[2]于干，李長(zhǎng)河，康立山.一種新的基于網(wǎng)格的函數(shù)優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，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]任圓圓,劉培玉,薛素芝.一種新的自適應(yīng)動(dòng)態(tài)文化粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2013,30(11):3240-3243.

[5]于干，康立山.基于網(wǎng)格的一種新的動(dòng)態(tài)演化算法[J].計(jì)算機(jī)應(yīng)用，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.

[責(zé)任編輯馬云彤]

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

中圖分類號(hào)：TP393.028

文獻(xiàn)標(biāo)志碼：A

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

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

收稿日期：2015-04-30

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