一種全局優(yōu)化的兩階段算法

張玉芬，王永軍

（1.河北大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北保定 071002；

2.東方地球物理公司研究院數(shù)據(jù)處理中心，河北涿州 072751）

一種全局優(yōu)化的兩階段算法

張玉芬1，王永軍2

（1.河北大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北保定 071002；

2.東方地球物理公司研究院數(shù)據(jù)處理中心，河北涿州 072751）

為了提高算法的有效性，利用梯度算法和粒子群算法獨(dú)立的運(yùn)行機(jī)制，采用驅(qū)趕技術(shù)和重新初始化部分群體的技術(shù)，提出了一種基于梯度下降法和粒子群算法的兩階段優(yōu)化算法，并對新算法進(jìn)行了理論分析和數(shù)值仿真.數(shù)值結(jié)果顯示新算法比單純梯度算法有更好的全局優(yōu)化能力，比單純粒子群算法有更快的收斂速度和更高的精度.新算法求解質(zhì)量更高，運(yùn)行更穩(wěn)定.

全局優(yōu)化；兩階段算法；梯度算法；粒子群算法

全局優(yōu)化問題廣泛應(yīng)用于金融模型、網(wǎng)絡(luò)交通、圖像處理、集成電路設(shè)計(jì)、分子生物學(xué)、數(shù)據(jù)庫、物流配送系統(tǒng)設(shè)計(jì)中.因?yàn)檫@些優(yōu)化問題存在多個不同于全局最優(yōu)解的局部最優(yōu)解，所以傳統(tǒng)的非線性規(guī)劃中的局部優(yōu)化方法不能有效地處理這類問題.而且，隨著科學(xué)的發(fā)展，工程中遇到的優(yōu)化問題的規(guī)模越來越大、復(fù)雜性越來越高，這使得全局優(yōu)化問題的求解變得更加困難.全局優(yōu)化問題的難以解決阻滯了許多學(xué)科的發(fā)展，因而全局優(yōu)化方法的研究顯得尤為重要.

梯度類算法是一種確定性的局部優(yōu)化方法，它能夠快速高效地找到臨近初始點(diǎn)的局部最優(yōu)值.常見的算法有最速下降法、牛頓法、擬牛頓法、共軛梯度方法等.它們已經(jīng)廣泛地應(yīng)用于許多領(lǐng)域［1－5］.此類算法的主要缺點(diǎn)是對初始點(diǎn)的嚴(yán)重依賴性、目標(biāo)函數(shù)和約束區(qū)域的拓?fù)浣Y(jié)構(gòu)的嚴(yán)格要求性.

粒子群算法是一種群體智能優(yōu)化方法［1］，在粒子群算法中，群體中的一個粒子根據(jù)它本身找到的最優(yōu)位置以及整個群體當(dāng)前為止找到的最優(yōu)位置，來不斷地調(diào)整它本身的位置.算法的核心思想是用當(dāng)前最好的已知的位置來引導(dǎo)群體朝搜索空間的最優(yōu)位置移動.粒子群算法設(shè)計(jì)簡單，參數(shù)少，容易實(shí)現(xiàn)，且表現(xiàn)出了較好的局部跳躍性，已經(jīng)被應(yīng)用到許多領(lǐng)域.但算法有時搜索到的只是局部解，找到高精度的解需要較長的運(yùn)行時間，解決大規(guī)模優(yōu)化問題至今還沒有涉及.

文獻(xiàn)［2］提出了一種把梯度信息混合到粒子的速度更新公式中加快算法收斂的方法.這種方法沒有使用現(xiàn)存的梯度算法的有效性和群體搜索中找到的最優(yōu)信息.過于強(qiáng)調(diào)啟發(fā)，而改變了傳統(tǒng)粒子群算法的核心思想.文獻(xiàn)［6］提出了一種基于梯度方法和動態(tài)隧道法的混合技術(shù)（用GRDT表示）來解決全局優(yōu)化問題.在GRDT方法中，梯度用來加快局部搜索，動態(tài)方程用來尋找好的初始點(diǎn).但是，該方法需要多次積分動態(tài)方程，對高維函數(shù)耗時較多，填充函數(shù)法和隧道法中的參數(shù)較難調(diào)節(jié).

1 兩階段算法

1.1 算法原理

不同于一般意義下的進(jìn)化算法，即局部搜索限制在進(jìn)化算法的框架內(nèi)，本文設(shè)計(jì)了一種新的混和算法.在新算法中，粒子群按照其獨(dú)有的進(jìn)化機(jī)制演化，而梯度算法使用目標(biāo)函數(shù)的梯度信息進(jìn)行獨(dú)立的搜索.粒子群算法起著全局搜索的作用，而梯度搜索起著局部探測的作用.從而把2種算法混合為一個兩階段方法，發(fā)揮出它們各自的優(yōu)點(diǎn)以解決復(fù)雜函數(shù)的優(yōu)化問題是本文的核心思想所在.具體而言，第1步，從可行域中隨機(jī)產(chǎn)生的一點(diǎn)出發(fā)，使用梯度算法得到目標(biāo)函數(shù)的一個局部最優(yōu)點(diǎn).其次，以得到的最優(yōu)點(diǎn)為均值，使用高斯分布函數(shù)初始化粒子群.然后，在最大的迭代次數(shù)內(nèi)，運(yùn)用粒子群算法找到一個更好的點(diǎn).以找到的點(diǎn)作為初始點(diǎn)，回到第1步，重新開始梯度搜索.

另外，為了利用算法已經(jīng)得到的最優(yōu)值信息（所有已經(jīng)找到的局部最優(yōu)點(diǎn)）防止群體早熟現(xiàn)象，把一種驅(qū)趕群體技巧［7］以及部分初始化群體方法加入到新算法中.驅(qū)趕技術(shù)利用當(dāng)前點(diǎn)與已經(jīng)找到的局部最優(yōu)點(diǎn)之間的距離，建立起一種屏障，使得新產(chǎn)生的點(diǎn)不要落到已經(jīng)找到的局部最優(yōu)點(diǎn)太近的范圍內(nèi)，這可以使粒子向著更有希望的區(qū)域飛行，同時避免重復(fù)搜索.文獻(xiàn)［7］已經(jīng)證明了此方法可以有效地加快群智能算法的收斂.部分初始化群體方法是在群體搜索不能取得全局進(jìn)展時，使用均勻分布函數(shù)產(chǎn)生的部分群體代替當(dāng)前群體中同等規(guī)模的較差個體的一種做法.

1.2 算法步驟

假設(shè)群體規(guī)模是NP，n是問題的規(guī)模，M是一個隨機(jī)生成的數(shù)值，M∈｛1，2，…，NP｝.本文使用的驅(qū)趕技術(shù)見算法1，更多的信息可以參考文獻(xiàn)［5］.本文使用的部分初始化群體技術(shù)執(zhí)行如下：根據(jù)當(dāng)前群體的適應(yīng)值進(jìn)行排序，在可行域中按均勻分布隨機(jī)產(chǎn)生M個樣本點(diǎn)，執(zhí)行驅(qū)趕技術(shù)，然后代替當(dāng)前群體中M個較差的個體，其余NP－M個個體保留在群體中，進(jìn)而形成同等規(guī)模的新群體.新群體繼續(xù)執(zhí)行粒子群算法搜索.新算法記做GRPSO（gradient based particle swarm optimization method），見算法2.

算法1 驅(qū)趕技術(shù)［5］

步驟0.輸入算法找到的極小點(diǎn)集S＊＝｛X＊j（j＝1，2，…，m）｝，這里的m是找到的極小點(diǎn)的個數(shù).給定小生境的半徑rij與驅(qū)趕因子mij.

步驟1.對群體中的每一個粒子Xi，i＝1，2，…，NP.

步驟1a.計(jì)算距離d ij＝｜X i－X＊j｜j＝1，2，m.

步驟1b.對集合S＊中的每一個元素X＊j，j＝1，2，…，m.

如果d ij＜rij，那么令Zij＝（X i－X＊j）／d ij.然后置X i＝Xi＋Pij Z ij.

步驟2.輸出群體Xi，i＝1，2，…，NP.

算法2 提出的新算法（GRPSO）

步驟0.隨機(jī)生成可行域中的初始點(diǎn)X0，并置局部搜索計(jì)數(shù)器k＝0.給定粒子群內(nèi)部的最大迭代次數(shù)Smax和計(jì)數(shù)器Npso＝1、調(diào)用粒子群算法的最大次數(shù)SSmax.設(shè)最優(yōu)點(diǎn)集合S＊＝Φ.

步驟1.（局部搜索）從Xk出發(fā)，應(yīng)用梯度下降法找到可行域中的1個極小點(diǎn)X＊k，同時保留到集合S＊中.

步驟2.（使用粒子群算法的全局搜索）

步驟2a.根據(jù)高斯分布，以X＊k為均值，在可行域中初始化群體，并找出最好個體gbest.若f（X＊k）＜f（gbest），令gbest＝X＊k，k＝1轉(zhuǎn)步驟1.否則，令gbest＝X＊k，計(jì)數(shù)器SS＝1，轉(zhuǎn)入步驟2b.

步驟2b.當(dāng)最大迭代次數(shù)Smax沒有達(dá)到時

1）更新pbest，如果當(dāng)前個體適應(yīng)值好于f（pbest），i＝1，2，…，NP.

2）更新gbest，如果當(dāng)前群體中的最優(yōu)個體適應(yīng)值好于f（gbest）.

3）如果f（gbest）＜f（X＊k），令X＊k＝gbest，結(jié)束循環(huán).

4）根據(jù)速度更新公式（1）和位置更新公式（2）更新群體的速度和位置.

5）把當(dāng)前群體和極小點(diǎn)集S＊作為輸入集，執(zhí)行算法1的驅(qū)趕技術(shù)（Algorithm 1）.然后，令Npso＝Npso＋1.

步驟2c.如果gbest＝X＊k，SS＝SS＋1.

如果SS＞SSmax，停止計(jì)算并輸出gbest＝X＊k.否則，重新初始化M∈｛1，2，…，NP｝個粒子，并執(zhí)行算法1的驅(qū)趕技術(shù)，保證此M個粒子遠(yuǎn)離找到的局部最優(yōu)點(diǎn).令Npso＝＋1，轉(zhuǎn)入步驟2b.否則，令X＊k＋1＝gbest，k＝k＋1，轉(zhuǎn)入步驟1.

2 實(shí)驗(yàn)結(jié)果與分析

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

用文獻(xiàn)［3］中已經(jīng)被GRDT測試過的10個函數(shù)來檢驗(yàn)新算法的優(yōu)化性能.首先，把函數(shù)值的計(jì)算次數(shù)設(shè)定為2 100，比較最終解的質(zhì)量，數(shù)值結(jié)果見表1.用新算法GRPSO對10個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行優(yōu)化，把運(yùn)算的結(jié)果與其他的算法，如GRDT（梯度算法和動態(tài)隧道法的混合方法［3］）、HGPSO（混合粒子群算法［6］）和專門設(shè)計(jì)處理高維函數(shù)的GRADSA（混合梯度和模擬退火技術(shù)的算法［4］）做比較.由于解的質(zhì)量、收斂速度（計(jì)算機(jī)的CPU時間或目標(biāo)函數(shù)值的計(jì)算次數(shù)）、算法的尋優(yōu)成功率是衡量算法優(yōu)劣的主要標(biāo)準(zhǔn)，對10個復(fù)雜函數(shù)［3］的20次獨(dú)立運(yùn)行后這幾個指標(biāo)的平均結(jié)果總結(jié)如表1.然后，在給定的最大函數(shù)值計(jì)算次數(shù)下，比較算法找到給定精度的解的成功率，數(shù)值結(jié)果見表2和3.

表1 新算法、GRDT以及其他的文獻(xiàn)找到的函數(shù)最優(yōu)值Tab.1 Optimal value of functions by the new algorithm，GRDT method and other algorithms in bibliography

表2 新算法和其他文獻(xiàn)提到算法的函數(shù)值平均計(jì)算次數(shù)Tab.2 Average numbers of functions by the new algorithm and other algorithms in bibliographies

表3 新算法和HGPSO方法的成功率Tab.3 Rate of success in computation by the new algorithm and HGPSO method

2.2 結(jié)果分析

從表1可以看出，GRPSO可以找到所有測試函數(shù)的最優(yōu)值，其結(jié)果接近理論上的分析值.與GRDT和其他文獻(xiàn)報道的結(jié)果相比，新算法找到的結(jié)果更好一些，比如函數(shù)H3和SH是2個典型的例子.

從表2和3可以看到，新算法HGPSO運(yùn)行效果更好，盡管它們都是基于梯度搜索的混PSO算法.同時，數(shù)值結(jié)果意味著在同樣給定的計(jì)算時間內(nèi)，新算法可以得到比GRPSO更高精度的解.說明兩階段的獨(dú)立搜索更有助于各個算法發(fā)揮其基本功能.

從表2可以看出，根據(jù)函數(shù)值的計(jì)算次數(shù)，新算法優(yōu)化性能高于GRDT和HGPSO方法，尤其對于GP和H3函數(shù)的優(yōu)化效果更明顯.與其他典型方法如PRS（純隨機(jī)搜索）、MS（多起點(diǎn)方法）、SA1（基于微分方程的模擬退火方法）、SA2（基本模擬退火方法）、TS（禁忌搜索）、TA（樹退火）和TT（信賴方法TRUST）相比，新算法的計(jì)算量大大降低.

總之，梯度算法幫助新算法加快局部收斂，并找到高精度的解.加入了驅(qū)趕技術(shù)和部分初始化群體的粒子群算法增加了群體多樣性，防止了群體早熟，進(jìn)而使新算法能有效地跳出局部最優(yōu).所有這些顯示新算法對低維的復(fù)雜函數(shù)優(yōu)化效果好.

3 結(jié)論

提出了一種基于梯度算法和粒子群算法的兩階段混和算法.從有效的局部搜索（使用梯度算法）開始，然后借助進(jìn)化算法（采用粒子群算法）的全局跳躍性質(zhì)探索更有希望區(qū)域，為局部搜索找到更好的出發(fā)點(diǎn).尋找高精度的解由局部搜索完成，因而省卻了演化算法的進(jìn)化時間，粒子群算法的全局搜索信息得以利用.不同于一般框架下的演化算法，該算法有效地利用了梯度算法和粒子群算法獨(dú)立的運(yùn)行機(jī)制.另外，新算法中采用了驅(qū)趕技術(shù)和重新初始化部分群體的技術(shù).數(shù)值結(jié)果顯示新算法比單純梯度算法有更好的全局優(yōu)化能力，比單純粒子群算法有更快的收斂速度、解的精度.

［1］KENNEDY J，EBERHART R C.Particle swarm optimization［Z］.Proceedings of IEEE International Conference on Neural Networks，Perth Australia，1995.

［2］ROY C P，SINGH Y P，CHANSARKAR R A.Hybridization of gradient descent algorithms with dynamic tunneling methods for global optimization［J］.IEEE T Syst Man Cy，2000，30（3）：384－390.

［3］NOEL M M，JANNETT T C.Simulation of a new hybrid particle swarm optimization algorithm［J］.System Symposium，2004，32（4）：150－153.

［4］SUGANTHAN P N.Particle swarm optimiser with neighbourhood operator［Z］.Proceedings of the IEEE Congress on Evolutionary Computation，Piscataway，NJ，1999.

［5］PARSOPOULOS K E，VRAHATIS M N.On the computation of all global optimizers through particles warm optimization［J］.IEEE Trans on Evolutionary Computation，2004，8（3）：211－224.

［6］劉星寶，蔡自興，王勇.用于全局優(yōu)化問題的混合免疫進(jìn)化算法［J］.西安電子科技大學(xué)學(xué)報，2010，37（5）：971－980.

LIU Xingbao，CAI Zixing，WANG Yong.Hybrid immune evolutionary algorithm for global optimization problems［J］.Journal of Xidian University，2010，37（5）：971－980.

［7］路克中，王汝傳，章家順.最優(yōu)化問題全局尋優(yōu)的PSO－BFGS混合算法［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（5）：17－19.

LU Kezhong，WANG Ruchuan，ZHANG Jiashun.PSO－BFGS algorithm of global optimum for optimization problems［J］.Application Research of Computers，2007，24（5）：17－19.

A two－phase algorithm for global optimization

ZHANG Yu－fen1，WANG Yong－jun2
（1.College of Mathematics and Computer Science，Hebei University，Baoding 071002，China；2.Date Processing Center，Geophysical Prospecting Research Institute，Zhuozhou 072751，China）

To enhance effectiveness of algorithm，on the basis of analyzing the independent operating mechanism of both gradient algorithm and particle swarm algorithm，a two－phase optimization algorithm based on gradient descent and particle swarm algorithm is presented；it adopts the driving technique and the re－initialization technique of part of population.Then，the theoretical analysis and numerical simulation about the new algorithm are made.The numerical simulation shows this new algorithm has better global optimization ability than the gradient algorithm，and it has faster convergences speed and lighter solution accuracy than particle swarm algorithm.This new algorithm produces a lighter quality solution and has more stable operation.

global optimization；two－phase algorithm；gradient algorithm；particle swarm op timization

O241.3

A

1000－1565（2012）02－0207－05

2011－09－11

河北省軟科學(xué)研究計(jì)劃項(xiàng)目（11457250）；河北省自然科學(xué)基金資助項(xiàng)目（F2009000236）

張玉芬（1964－），女，河北肅寧人，河北大學(xué)副教授，主要從事不確定信息處理方向研究.E－mail：happy6002＿cn＠sina.com

孟素蘭）