基于分區和分層搜索的并行粒子群算法
2009-01-01 00:00:00龔燕蔣玉明張培頌
計算機應用研究 2009年5期
（四川大學 計算機學院 成都 610065）
摘 要：為提高粒子群優化算法在優化問題中的效率，提出了并行粒子群優化算法(SLPSO)。其基本思想是并行機制+解空間壓縮+分層搜索。主要工作包括：搜索空間劃分為n個區，由n個子群并行搜索，將搜索結果最好的作為指定的搜索空間，即將搜索空間縮小到原解空間的(1/n)；提出了粒子群兩層劃分模型，底層利于擴大搜索范圍，上層利于全局精細搜索。在四個基準函數上的優化實驗表明，新方法比經典的IPPSO并行粒子群算法在解的精度上提高了80.37%。
關鍵詞：并行粒子群算法； 分區； 分層搜索
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2009)05-1670-03
Parallel particle swarm optimization algorithmbased on spacedivision and layered search
GONG Yan JIANG Yuming ZHANG Peisong
(College of Computer Science Sichuan University Chengdu 610065 China)
Abstract:To improve the efficiency of particle swarm optimization this paper proposed a novel parallel particle swarm optimization algorithm(SLPSO).The basic idea is parallel mechanism and spacedivision and layered search. The main contributions include divided whole search space into n sub ares. For certain generations let the best sub areabe the search space. This shrinked the search space to the solution space. Proposed two layers partition of particles the lower andtopper work well for global and local search respectively. By experiments on four benchmark functions shows that the new algorithm increases precision by 80.37% compared with IPPSO.
Key words：parallel particle swarm optimization; spacedivision; layered search
粒子群優化算法(PSO)由Kennedy等人[1，2]提出，能有效解決復雜優化任務[3]。但PSO在接近最優解時搜索速度低，且很難得到精確最優解。為解決上述問題，需增加粒子群的粒子數，或減弱粒子對全局最優點的追逐。增加粒子數將導致算法計算復雜度增高，而減弱粒子對全局最優點的追逐又存在算法不易收斂的缺點。并行粒子群算法[4]可以減小粒子間的相互干擾，擴大搜索范圍；對于大規模的多變量求解具有重要的意義[5]，可以提高解的速度和質量。但是現有的并行粒子群算法采用的信息共享方式與PSO在本質上是一樣的[6]，不能從根本上解決PSO早熟問題。為此，本文提出了并行粒子群的改進算法。
1 傳統概念和算法
PSO算法與其他演化算法相似，根據對環境的適應度將群體中的個體移動到好的區域。不同于其他演化算法，PSO不對個體使用演化算子，而將個體看做D維搜索空間中無體積的粒子，在搜索空間中以一定的速度飛行。
在D維空間，第i個粒子被描述為Xi=(xi1，xi2，…，xiD)；每個粒子迄今所經歷的個體最優位置描述為Pi=(pi1，pi2，…，piD)；整個粒子群搜索到的最優位置為Pg=(pg1，pg2，…，pgD)。加上慣性權重因子[7]，粒子狀態更新策略為
v(t+1)id=wv(t)id+c1r1(pid-x(t)id)+c2r2(pgd-x(t)id)(1)
x(t+1)id=x(t)id+v(t+1)id(2)
其中:w為慣性權重；c1、c2為學習因子，一般取值為2；r1、r2為分布在(0，1)間的隨機數；v(t)id表示第i個粒子在第t次迭代時在第d維上的速度；pid表示第i個粒子的歷史最優位置在第d維上的坐標；pgd表示整個粒子群中最優粒子在第d維上的坐標。
文獻[8]提出了一種基于島嶼模型的并行粒子群算法(IPPSO)。IPPSO將整個粒子群劃分為多子群體，每個子群體在各自群內進行全局PSO搜索，在子群內對每個粒子適應度進行計算和評價，產生群內最佳粒子。子群全體演化采用一個獨立的子進程來完成，各子進程利用集中遷移策略，周期性地將島內最佳粒子發給主進程，集中形成主群。主進程則選出主群中全局最佳粒子廣播給子進程，迫使子群體進行全局最優演化。
2 分區和分層搜索
IPPSO搜索策略是將粒子群分成幾個子群，然后各個子群各自在問題解空間的完整空間內搜索，一直到算法結束。實際上，隨著粒子群的搜索，解空間范圍應該慢慢縮小，不應該仍然在整個解空間搜索。
2.1 基于分區的思想
PSO的整個搜索過程中，個體導向因子（即式(1)的第二部分）起探測作用，全局導向因子（即式(1)的第三部分）起開拓作用[9]。探測是指在問題空間中開辟新的搜索域去試探全局最優解；而開拓是指將搜索集中到有希望的候選解，使搜索迅速定位到最優解以提高收斂速度。PSO前期側重探測(全局搜索)，后期側重開拓(局部搜索)有利于算法提高性能[10]。
數據結構中的折半查找法給了很好的啟示。折半法在查找時，先將要找的查找空間分成兩半，確定要找的數在哪一半，這樣就將查找空間縮小到原來的1/2，然后又將定下的查找空間分成兩半，一直到算法結束。
類似于折半查找算法，分區的基本思想是并行機制結合搜索空間的壓縮，將初始的搜索空間劃分為n個區，由n個子群并行搜索，每隔一定代數，將其中搜索結果最好的一個區作為指定的搜索空間，這樣就將搜索空間縮小到原解空間的1/n，然后對其再進行分區搜索，又將壓縮到原始解空間的1/n2，直到將解空間壓縮到足夠小。
同時產生了一個新的問題，即如何確定某一個子搜索空間是整個解空間的最優解空間。本文將每個子群固定在周期t內，得到平均適應度值作為評價標準，在該周期內的平均適應度值最高的某一個子群所在的搜索空間將作為下個周期搜索的空間。
為避免遺漏掉出現在邊界上的最優解，每次要將最佳解空間擴充邊緣（10%左右），然后作為下個周期的搜索空間。算法1描述了這一過程。
算法1 分區搜索的函數形式
search()
{arrange every division of solution space to a particle swarm;
//主進程將解空間的劃分分派到各個群
for every particle swarm//每個群對應一個子進程
{while (maximum iterations is not attained)
{initialize all particles;//將粒子隨機散落在解空間
calculate fitness value;//計算適應度}
calculate average of fitness as referee strategy;
//計算適應度的平均值}
send average of fitness to main process;
//各子進程將各自平均適應值傳送給主進程
select excellent subspace of solution from divisions of solution space;
//選擇最優區域
set the excellent subspace with small extension as new solution space;
//將最優區域的邊緣微微擴展并作為新的解空間 }
2.2 分層搜索技術
為了改善PSO和IPPSO局部搜索能力差的缺點，本文提出了分層搜索(layered search)的思想。PSO算法局部搜索能力差的原因是在開始階段搜索較大的解空間，然后才在較好解的鄰域內精細搜索。為了提高算法的精細搜索能力，使得算法的任何階段都能同時進行探索和開拓，采用兩層搜索，將整個粒子群劃分為S個子群體。前S-1個粒子群作為底層在各自的進程上相互獨立地搜索解空間以擴大搜索范圍；第S個粒子群作為上層總是追隨全局最優解進行精細搜索以加快收斂，改進PSO和IPPSO局部搜索能力差的缺點。算法2描述了這一過程。
算法2 基于分層搜索的函數形式
convergence()
{arrange the final best subspace of solution to all particle swarms;
while (maximum iterations or minimum error criteria is not attained)
{for every paticle swarm
{initialize all particles;//各子群初始化，優化群的速度較小
calculate fitness value;//計算適應度
particle fly;//微粒飛翔，微粒運動}
if (the time of transference has arrived)；
{attain best fitness of every particle swarm;
//子進程將最優適應度傳送給主進程
select best solution;//選擇最優的解
set the best solution to all particle as group best solution;
//將最優解廣播到子進程
if (the best of group changed) { //當群體最優發生變更時
optimized particle follow; } //優化群緊隨}}}
2.3 分區和分層搜索
算法2描述的分層搜索算法主要是為了局部精細搜索。因此，在前期進行了分區搜索，壓縮解空間，后期應該采用分層搜索來進行局部精細搜索。其過程如算法3所示。
算法3 基于分區和分層搜索的并行粒子群算法
(SLPSO)
{search();//前期分區搜索，可一次或多次迭代
convergence();//后期分層搜索
output result;//輸出結果}
在前期進行四次分區搜索以后，解空間已經足夠小，接下來后期就可以進行分層搜索。
3 分區和分層搜索實驗
3.1 實驗條件和參數設置
實驗平臺為JDK1.5多線程來模擬多進程。每個子群用一個線程實現。采用四個無約束優化標準測試函數，即Sphere、Rosenbrock、Griewank、Rastrigrin，維數均為10，分別采用PSO、IPPSO、SLPSO進行實驗，并進行比較，如表1所示。
表1 標準測試函數
名稱表達式最大速度搜索空間維數/d最小值位置
Sphere∑di=1x2i(0.9)d(-100，100)d10(0)d
Rosenbrock∑d-1i=1[100(xi+1-x2i)2+(xi-1)2](1.1)d(-100，100)d10(1)d
Griewank1/4000∑di=1x2-i ∏di=1 cos(xi/i1/2)+1(6.6)d(-600，600)d10(0)d
Rastrigrin∑di=1[x2i-10 cos(2πx2i)+10](0.06)d(-5.12，5.12)d10(0)d
為了提高可比性，三種算法取同樣的參數，粒子總數均為80，演化代數為1 000。IPPSO和SLPSO取相同的參數，將粒子分成四個子群，每個子群20個粒子，各子群線程都是每隔20代向主線程傳送群內最佳粒子。PSO、IPPSO、SLPSO的慣性權重w的取值一樣，從0.9線性遞減至0.4，學習因子c1、c2均為2。
3.2 驗證分區搜索的有效性
對四個測試函數的原始解空間分別進行了四輪迭代搜索，每輪搜索的周期是150代，以驗證分區搜索的可行性。搜索后生成的新的解空間如表2所示。
表2 原始解空間經過1~4次分區搜索(擴充邊緣)后形成的新的解空間
目標函數最小值位置原始解空間第1次第2次第3次第4次
Sphere(0)d(-100，100)
(-5.0，55.0)d(-6.5，11.5)d(-2.95，2.45)d(-1.24，0.38)d
(-55.0，5.0)d(-11.5，6.5)d(-2.45，2.95)d(-0.38，1.24)d
Rosenbrock(1)d(-100，100)(-5.0，55.0)d(-6.5，11.5)d(-2.45，2.95)d(0.11，1.73)d
Griewank(0)d(-600，600)
(330.0，30.0)d(-69.0，39.0)d(-17.7，14.7)d(-2.31，7.4)d
(30.0，330.0)d(-39.0，69.0)d(-14.7，17.7)d(-7.4，2.3)d
Rastrigrin(0)d(-10，10)
(-5.5，0.5)d(-1.15，0.65)d(-0.30，0.24)d(-0.04，0.12)d
(-0.5，5.5)d(-0.65，1.15)d(-0.25，0.29)d(-0.12，0.04)d
由表2可以看出，解空間成幾何級別地進行壓縮，而且得到新的解空間包含了最優坐標，即壓縮后解空間沒有出現錯誤。因此可以說明分區搜索是有效的。
3.3 比較幾種算法的收斂精度
對三種算法重復運行50次，迭代數為1 000，結果如表3所示。
總的來說，IPPSO比PSO的精度有所提高；SLPSO所得的解的精度比IPPSO大幅度提高了80.37%以上。同時，SLPSO所得的解的精度又比PSO提高了81.16%以上。
表3 PSO、IPPSO、SLPSO三種算法實驗結果比較
目標函數
PSOIPPSOSLPSO
平均值方差平均值方差平均值方差
Sphere2.314 30.170 82.175 20.149 90.003 12.334 4E7
Rosenbrock75.36311 25451.047 44967.153 94.923 52.134 5
Griewank0.402 40.006 00.386 20.006 20.075 80.001 9
Rastrigrin9.149 316.465 710.609 822.282 03.025 3E47.843 9
3.4 比較幾種算法的收斂成功率
以最大迭代數為2 000和確定的精度為算法結束的條件，運行算法50次。表4給出的實驗結果表明：SLPSO較IPPSO的成功率均提高了10倍以上。
表4 確定精度后PSO、IPPSO、SLPSO三種算法的
迭代代數及成功率
目標函數要求達到的精度
平均迭代次數成功率/%
PSOIPPSOSLPSOPSOIPPSOSLPSO
Sphere1.0e-19878961 0307.013.0100.0
Rosenbrock1.01 4561 3941 1913.06.078.0
Griewank1.0e-11 2351 05699421.035.099.0
Rastrigrin1.09541 0987689.07.0100.0
4 結束語
SLPSO通過前期的分區搜索，能成幾何型的壓縮解空間，后期通過分層搜索精細搜索，對算法的性能提高起了很大的作用。實驗結果表明該算法收斂速度和成功率提高較大。
參考文獻：
［1］KENNEDY J EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. 1995: 1942-1948.
[2]KENNEDY J EBERHART R C. A new optimizer using particle swarm theory[C]//Proc of the 6th International Symp on Micromachine. 1995: 39-43.
[3]PARSOPOULOS K E VRAHATIS M N. On the computation of all global minimizers through particle swarm optimization[J]. IEEE Trans on Evolutionary Computation 2004，8(3):211-224.
[4]SCHUTTE J F ，FREGLY B J. A parallel particle swarm optimizer[C]//Proc of the 5th World Congress of Structural and Multidisciplinary Optimization. 2003:19-23.
[5]樊治平，胡國奮.區間數多屬性決策的一種目標規劃方法[J]．管理工程學報，2000，14(4): 50-53.
[6]趙勇，岳繼光. 一種新的求解復雜函數優化問題的并行粒子群算法[J]. 計算機工程與應用，2005，41(16):58-60.
[7]SHI Y EBERHART R. A modified particle swarm optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation(ICEC’98). 1998:69-73.
[8]黃芳，樊曉平.基于島嶼群體模型的并行粒子群優化算法[J]. 控制與決策，2006，21(2):175-179.
[9]TRELEA I C. The particle swarm optimization algorithm: convergence analysis and parameter selection[J]. Information Processing Letters，2003，85(6):317-325.
[10]SHI Y EBERHART R. Empirical study of particle swarm optimization[C]//Proc of International Conference on Evolutionary Computation. Washington: IEEE Press 1999.
