馮 勇 郭 軍 徐紅艷 付瀟瑩

(遼寧大學(xué)信息學(xué)院 沈陽 110036)

一種基于解空間分割的并行遺傳算法

馮 勇 郭 軍 徐紅艷 付瀟瑩

(遼寧大學(xué)信息學(xué)院 沈陽 110036)

遺傳算法是一種常用于NP問題中尋求近似最優(yōu)解的優(yōu)化方法,已被廣泛應(yīng)用于國防、科研、經(jīng)濟(jì)管理、工程建設(shè)等重要領(lǐng)域,但其求解過程中常出現(xiàn)過早收斂于局部最優(yōu)解、計算復(fù)雜度高等問題。針對這些問題,論文首先給出一種基于解空間分割的并行處理機(jī)制,通過對問題解空間的分割實現(xiàn)求解最優(yōu)化問題的并行化處理;然后將該機(jī)制引入到遺傳算法中,提出了一種基于解空間分割的并行遺傳算法;最后,經(jīng)實驗對比表明論文所提算法在并行化處理方面具有良好的線性加速比,同時證明在克服過早收斂于局部最優(yōu)解方面要優(yōu)于標(biāo)準(zhǔn)遺傳算法和粗粒度并行遺傳算法。

解空間分割; 并行化; 遺傳算法; 線性加速比; 優(yōu)化

Class Number TP183

1 引言

遺傳算法作為一種經(jīng)典的求解復(fù)雜問題最優(yōu)解的算法,在電網(wǎng)規(guī)劃、生產(chǎn)調(diào)度、復(fù)雜網(wǎng)絡(luò)分析等領(lǐng)域得到廣泛應(yīng)用[1～3]。由于標(biāo)準(zhǔn)遺傳算法[4]是串行算法,存在運(yùn)行時間長、易陷入局部最優(yōu)解的弊端,為更好滿足當(dāng)今大規(guī)模計算的應(yīng)用需求,往往需要對標(biāo)準(zhǔn)遺傳算法進(jìn)行并行化改進(jìn)。其中,粗粒度并行遺傳算法[5]是應(yīng)用最為廣泛的一種并行遺傳算法,具備線性加速比[6],在全局搜索上優(yōu)于標(biāo)準(zhǔn)遺傳算法,有抑制早熟收斂的效能[7]。為進(jìn)一步提升粗粒度并行遺傳算法的性能,眾多學(xué)者對其進(jìn)行改進(jìn),具有代表性的成果有:胡玉蘭等提出子種群規(guī)模動態(tài)可變,子種群間按照其競爭能力進(jìn)行遷移[8];龔雪晶等提出進(jìn)化過程中動態(tài)調(diào)整各遺傳參數(shù)和遺傳算子,并針對自適應(yīng)調(diào)整過程中帶來的負(fù)載失衡加入了相應(yīng)的遷移策略[9];嚴(yán)曉明提出對遷移算子進(jìn)行改進(jìn),用公共池的方式來代替各子種群間個體遷移時的拓?fù)浣Y(jié)構(gòu)[10]。這些改進(jìn)在不同程度上提升了算法的性能,但以犧牲算法復(fù)雜度為代價,需要預(yù)設(shè)子種群數(shù)、種群間個體遷移的拓?fù)漤樞?、個體遷移數(shù)及個體遷移時機(jī)等參數(shù)。這些參數(shù)中子種群數(shù)的劃分直接影響粗粒度并行遺傳算法求解效率,而由于該參數(shù)的設(shè)置與求解問題有關(guān),故該參數(shù)難以直接設(shè)定[7]。并且,這些改進(jìn)算法在克服過早收斂于局部最優(yōu)解方面仍需要進(jìn)一步的提升。

針對以上問題,本文首先給出了基于解空間分割的并行處理機(jī)制,然后將該機(jī)制引入到標(biāo)準(zhǔn)遺傳算法中,形成了一種基于解空間分割的并行遺傳算法?；诮饪臻g分割的并行處理機(jī)制分為三階段:第一階段是對優(yōu)化問題的解空間進(jìn)行分割;第二階段是在不同的子空間上分別對目標(biāo)函數(shù)進(jìn)行求解;第三階段是對不同子空間的解匯總選出最優(yōu)解作為全局解。該機(jī)制設(shè)計簡單、便于實現(xiàn),沒有過多的預(yù)設(shè)值,對于最優(yōu)化問題的求解具有很好的普適性。采用基于解空間分割機(jī)制的并行遺傳算法在初始化時對運(yùn)算參數(shù)進(jìn)行預(yù)設(shè)定,然后對問題解空間進(jìn)行分割。分割后子任務(wù)在其解空間內(nèi)進(jìn)行最優(yōu)化求解。最后,將各子任務(wù)得出的解匯總,從中選出全局最優(yōu)解。經(jīng)實驗對比分析,本文所給算法模型簡單,沒有過多的參數(shù)設(shè)定,在并行化處理上具有良好的線性加速比,在克服過早收斂于局部最優(yōu)解方面優(yōu)于標(biāo)準(zhǔn)遺傳算法和粗粒度并行遺傳算法。

2 基于解空間分割的并行處理機(jī)制

本文提出的基于解空間分割的并行處理機(jī)制是將分而治之的思想引入到對優(yōu)化問題的求解中。該機(jī)制將處理過程分為分割、運(yùn)算、匯總?cè)齻€階段,具體描述如下:

1) 分割階段。對解空間進(jìn)行劃分,設(shè)待優(yōu)化的問題共有m個自變量,即X1,X2,…,Xm,整體解空間S為m個自變量構(gòu)成的m維空間,解空間的維度為自變量數(shù)。將整體解空間S進(jìn)行等分分割成n份不同子空間{S1,S2,…,Sn}。

2) 運(yùn)算階段。將分割后的子空間{S1,S2,…,Sn}分別作為各子任務(wù){(diào)K1,K2,…,Kn}的解空間,劃分后的子空間數(shù)即為子任務(wù)數(shù),子任務(wù)為最小的計算單元,各子任務(wù){(diào)K1,K2,…,Kn}分別在其所在的解空間{S1,S2,…,Sn}中對目標(biāo)函數(shù)F(X1,X2,…,Xm)進(jìn)行尋優(yōu)運(yùn)算,得出各子任務(wù){(diào)K1,K2,…,Kn}的最優(yōu)解,對應(yīng)的最優(yōu)目標(biāo)函數(shù)值為{A1,A2,…,An}。各子任務(wù)的尋優(yōu)過程是完全獨(dú)立的,子任務(wù)在各自的解空間中對優(yōu)化問題求解。

3) 匯總階段。從各子任務(wù)的解中選擇最優(yōu)解,將所有子任務(wù){(diào)K1,K2,…,Kn}運(yùn)算得出的函數(shù)值{A1,A2,…,An}進(jìn)行匯總,從運(yùn)算結(jié)果{A1,A2,…,An}中選出最優(yōu)目標(biāo)函數(shù)值A(chǔ)x作為整體的最優(yōu)目標(biāo)函數(shù)值,Ax所對應(yīng)的解(x1,x2,…,xm)為整體解空間中的最優(yōu)解。

基于解空間分割的并行處理機(jī)制的工作流程如圖1所示。

圖1 基于解空間分割的并行處理機(jī)制的工作流程

3 基于解空間分割的并行遺傳算法

3.1 算法理論分析

根據(jù)文獻(xiàn)[11～12]可知選擇算子采用精英選擇法,即每一代選擇的時候最優(yōu)個體淘汰掉最差個體的遺傳算法收斂到全局最優(yōu)點(diǎn)。優(yōu)化問題中函數(shù)的解空間S是所有解的集合,將其分割成n份不同子空間{S1,S2,…,Sn},即S為各子空間的并集,目標(biāo)函數(shù)值是解空間中的解關(guān)于目標(biāo)函數(shù)的映射,由集合論可知各子集的最優(yōu)解的集合中的最優(yōu)解必為整體解空間的最優(yōu)解。

文獻(xiàn)[13]提出了模式理論,文獻(xiàn)[14]在模式理論的基礎(chǔ)上定義了區(qū)間分割,綜上可得采用解空間分割的并行處理機(jī)制的帶有精英選擇的遺傳算法必然收斂到全局最優(yōu)解。對標(biāo)準(zhǔn)遺傳算法進(jìn)行性能分析可知在固定迭代次數(shù)下其運(yùn)算的時間復(fù)雜度為關(guān)于個體數(shù)N的O(N)。對解空間進(jìn)行K等分分割,若每個子空間的個體數(shù)為N/K,可知各子群的運(yùn)算時間均為原運(yùn)算時間的1/K,從而達(dá)到線性加速。

3.2 算法思想

基于解空間分割的并行遺傳算法相較于標(biāo)準(zhǔn)遺傳算法,增加了子空間劃分個數(shù)和各子空間個體數(shù)兩個參數(shù),在算法運(yùn)行之前需要對這兩個參數(shù)進(jìn)行設(shè)定。首先,按照要求的精度選擇總體樣本個數(shù),再按照子空間占總體空間的比例為每個子群分配個體。一般來說,種群劃分?jǐn)?shù)越多整體并行性越好,對克服過早收斂于局部最優(yōu)解的效果也越好,但是隨著劃分?jǐn)?shù)的急劇增加會使子群的個體數(shù)急劇下降從而不利于對子空間的求解,而增加子群個體數(shù)又勢必降低算法的并行性,所以在實際運(yùn)算中劃分后的子群個體數(shù)可以在按比例劃分的基礎(chǔ)上做適當(dāng)?shù)脑黾硬⑦m當(dāng)?shù)脑黾拥螖?shù)。另外,為保證每個子群獨(dú)立尋優(yōu)的可行性要求每個子群的個體數(shù)不能過少,根據(jù)Reeves[15]提出的最小規(guī)模理論在此規(guī)定各子群內(nèi)的個體數(shù)不少于20。

3.3 算法描述

采用基于解空間分割的并行處理機(jī)制對遺傳算法進(jìn)行改進(jìn)后,算法的具體運(yùn)行步驟如下:

Step1 在基本遺傳算法的基礎(chǔ)上對初始參數(shù)進(jìn)行設(shè)定。

Step2 分割階段,將整體解空間S等分為n份,子種群個體數(shù)為整體個體數(shù)的n等分,如式(1)所示:

Cut:S→{S1,S2,…,Sn}

(1)

Step3 運(yùn)算階段,子任務(wù)隨機(jī)產(chǎn)生初始種群(二進(jìn)制),各子任務(wù)按遺傳算法工作流程在各自的解空間上獨(dú)立運(yùn)行。如式(2)所示:

Compute:K1:A1=maxF(X1,X2,…,Xm)X1,X2,…,Xm∈S1

K2:A2=maxF(X1,X2,…,Xm)X1,X2,…,Xm∈S2

…

Kn:An=maxF(X1,X2,…,Xm)X1,X2,…,Xm∈Sn

(2)

Step4 匯總階段,將各子種群運(yùn)行結(jié)束后的求解結(jié)果匯總,從中選出最優(yōu)值,其對應(yīng)的解即為全局最優(yōu)解,如式(3)所示:

Join:choose(A1,A2,…,An)→AxAx∈{A1,A2,…,An}Ax=F(x1,x2,…,xm) (x1,x2,…,xm)∈Sx

(3)

3.4 算法示例

為更好地說明算法的運(yùn)行,這里給出具體示例。如果一個遺傳算法的目標(biāo)函數(shù)的搜索域是在二維空間中,即目標(biāo)函數(shù)的自變量為X、Y,目標(biāo)函數(shù)F(X,Y)=X2+Y2為關(guān)于X、Y的復(fù)雜函數(shù)。本例設(shè)種群個體數(shù)M為200、進(jìn)化代數(shù)T為300、交叉概率Pc為0.6、變異概率Pm為0.01。對整體解空間即X、Y的范圍進(jìn)行4等份分割,每個子空間中的個體數(shù)為50。假設(shè)解空間為0≤X≤10,0≤Y≤10,將X、Y的范圍空間進(jìn)行4等份分割后,即分割后的4個子任務(wù){(diào)K1,K2,K3,K4}的搜索空間{S1,S2,S3,S4}如式(4)所示:

S1∈{0≤X≤5,0≤Y≤5}

S2∈{0≤X≤5,5≤Y≤10}

S3∈{5≤X≤10,0≤Y≤5}

S4∈{0≤X≤10,5≤Y≤10}

(4)

各子空間由不同的子群并行進(jìn)行搜索,每個子群采用基本遺傳算法獨(dú)立運(yùn)算。各子任務(wù)的最優(yōu)目標(biāo)函數(shù)值{A1,A2,A3,A4}分別為50、125、125、200,從中選出最優(yōu)目標(biāo)函數(shù)值,即A4作為全局的最優(yōu)目標(biāo)函數(shù)值,其所對應(yīng)的解X4=10、Y4=10作為全局最優(yōu)解。

4 實驗分析

4.1 實驗環(huán)境

本文所提改進(jìn)算法取Schaffer測試函數(shù)為目標(biāo)函數(shù),其函數(shù)表達(dá)如式(5)所示:

-5≤x1,x2≤5

max(F)=1

(5)

圖2為Schaffer測試函數(shù)的三維立體圖,從中可看出該函數(shù)有無窮個局部極大點(diǎn),其中只有一個點(diǎn)為全局最大點(diǎn),最大值為1。

圖2 Schaffer測試函數(shù)的三維立體圖

本文中所用的實驗預(yù)設(shè)參數(shù)為:種群個體M為200、進(jìn)化代數(shù)T為300、交叉概率Pc為0.6、變異概率Pm為0.01,選擇策略采用精英法,交叉為單點(diǎn)交叉,實驗的結(jié)果為1000次重復(fù)實驗的平均值,精度為0.0001。粗粒度并行遺傳算法子種群個數(shù)分別取4、9、16、25,遷移操作采用環(huán)狀拓?fù)?遷移規(guī)模為4的最佳→最差準(zhǔn)則,遷移間隔為5的定周期遷移策略?；诮饪臻g的并行遺傳算法分別將解空間分割為4、9、16、25等分。實驗環(huán)境為局域網(wǎng)中25臺裝有Ubuntu14.04 64位操作系統(tǒng),CPU為Intel I5 4250型號的計算機(jī)作為計算節(jié)點(diǎn)組成的分布式計算集群。編程語言為Python2.7。

4.2 實驗結(jié)果

在上述實驗環(huán)境下,對Schaffer函數(shù)進(jìn)行最優(yōu)化求解,實驗結(jié)果如下:

1) 標(biāo)準(zhǔn)遺傳算法、粗粒度并行遺傳算法的運(yùn)行用時如表1所示。

表1 標(biāo)準(zhǔn)遺傳算法與粗粒度并行遺傳算法的運(yùn)行用時

2) 標(biāo)準(zhǔn)遺傳算法、基于解空間分割的并行遺傳算法的運(yùn)行用時如表2所示。

表2 標(biāo)準(zhǔn)遺傳算法與基于解空間分割的并行遺傳算法的運(yùn)行用時

經(jīng)計算后,得到的解情況如下:

1) 標(biāo)準(zhǔn)遺傳算法最終解為0.9917。

2) 粗粒度并行遺傳算法的最終解如表3所示。

表3 粗粒度并行遺傳算法的最終解

3) 基于解空間分割的并行遺傳算法最終解如表4所示。

表4 基于解空間分割的并行遺傳算法最終解

4.3 結(jié)果分析

在并行性能方面,與標(biāo)準(zhǔn)遺傳算法對比,可以看出改進(jìn)算法具有很好的并行性能,可以達(dá)到良好的線性加速比。

在計算性能方面,粗粒度的并行遺傳算法在克服過早收斂于局部最優(yōu)解方面優(yōu)于標(biāo)準(zhǔn)遺傳算法,改進(jìn)算法在空間分割為4等分、9等分和25等分時最優(yōu)解的求解效果優(yōu)于其他算法。9等分和25等分時求解的最優(yōu)解在精度上可以近似認(rèn)為已到達(dá)實際最優(yōu)解,16等分時效果要稍差于粗粒度遺傳算法但仍然優(yōu)于標(biāo)準(zhǔn)遺傳算法,由此可見基于解空間分割的并行遺傳算法在并行化和克服局部最優(yōu)解方面相對于傳統(tǒng)的串并行遺傳算法確有提升,但不同的分割方式對求解效果有一定的影響,在具體的解空間劃分方式及子群個體分配上仍需要進(jìn)一步的深入研究和完善。

對實驗中各算法的計算性能進(jìn)行分析,粗粒度并行遺傳算法采用子種群劃分及種群間個體遷移,增加了全局的搜索能力,對比基本遺傳算法減少了未成熟收斂的可能性。但是各子種群都是在整體解域空間中進(jìn)行求解,存在重復(fù)求解的問題,同時各子種群具有更少的個體數(shù),解空間的范圍和解的精度并沒有改變,這樣必然導(dǎo)致子種群更容易陷入局部最優(yōu)解。保證種群多樣性的個體遷移,可能會使陷入局部最優(yōu)解的子種群的個體遷移到其他子種群,使被遷移入的子種群受到污染并造成其加快早熟。子種群數(shù)不同會得到不同的求解效果,但是最好的子種群數(shù)無法直觀地確定,只能經(jīng)過多次實驗確定。

改進(jìn)算法中子種群完全獨(dú)立運(yùn)行,不存在個體遷移帶來的污染問題,同時對潛在的最優(yōu)解具有保護(hù)作用。各子種群采用的是不同的子解域空間,各子種群的個體數(shù)量為整體個體數(shù)按其子空間占整體解空間的比例劃分,可以減少由于子種群個體數(shù)量的減少帶來的子種群早熟可能性。解空間的劃分可以很好避免導(dǎo)致早熟的高適應(yīng)度個體對整體求解效果的影響,使最優(yōu)解所在的子空間減少非全局最優(yōu)解的高適應(yīng)度個體的存在。

5 結(jié)語

為提升并行遺傳算法的性能及克服過早收斂問題,本文提出了一種基于解空間分割的并行處理機(jī)制,并在此基礎(chǔ)上給出了一種基于解空間分割的并行遺傳算法,改進(jìn)算法對問題解空間進(jìn)行分割,使分割后的子任務(wù)在其解空間內(nèi)進(jìn)行最優(yōu)化求解,將各子任務(wù)得出的解匯總,從中選出全局最優(yōu)解。最后,經(jīng)實驗分析表明本文所提算法設(shè)計簡單、便于實現(xiàn)、沒有過多的參數(shù)設(shè)定,在并行化處理方面具有良好的線性加速比,同時在克服過早收斂于局部最優(yōu)解方面要優(yōu)于標(biāo)準(zhǔn)遺傳算法和粗粒度并行遺傳算法。

[1] 黃慧,顧波.改進(jìn)遺傳算法在電網(wǎng)規(guī)劃中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制,2012,40(22):65-67. HUANG Hui, GUO Bo. Application of improved genetic algorithm in power network planning[J]. Power System Protection and Control,2012,40(22):65-67.

[2] 張國輝,高亮,李培根,等.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J].機(jī)械工程學(xué)報,2009,45(7):146-151. ZHANG Guohui, GAO Liang, LI Peigen, et al. Improved Genetic Algorithm for the Flexible Job-shop Scheduling Problem[J]. Journal of Mechanical Engineering,2009,45(7):146-151.

[3] 金弟,劉杰,楊博,等.局部搜索與遺傳算法結(jié)合的大規(guī)模復(fù)雜網(wǎng)絡(luò)社區(qū)探測[J].自動化學(xué)報,2011,37(7):874-882. JIN Di, LIU Jie, YANG Bo, et al. Genetic Algorithm with Local Search for Community Detection in Large-scale Complex Networks[J]. Acta Automatica Sinica,2011,37(7):874-882.

[4] Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning[M]. MA: Addison-Wesley,1989:80-86.

[5] 郭彤城,慕春棣.并行遺傳算法的新進(jìn)展[J].系統(tǒng)工程理論與實踐,2002(2):16-21. GUO Tongcheng, MU Chundi. The Parallel Drifts of Genetic Algorithms[J]. System Engineering Theory and Practice,2002(2):16-21.

[6] Lienig J. A Parallel Genetic Algorithm for Performance-driven VLSI Routing[J]. IEEE Trans on EC,1997,1(1):29-39.

[7] 岳嵚,馮珊.粗粒度并行遺傳算法的計算性能分析[J].武漢理工大學(xué)學(xué)報,2008,30(7):108-110. YUE Qin, FENG Shan. Performance Analysis of the Coarse-grained Parallel Genetic Algorithms[J]. Journal of WuHan University of Technology,2008,30(7):108-110.

[8] 胡玉蘭,潘福成,梁英,等.基于種群規(guī)?？勺兊拇至６炔⑿羞z傳算法[J].小型微型計算機(jī)系統(tǒng),2003,24(3):535-536. HU Yulan, PAN Fucheng, LIANG Ying, et al. Parallel Genetic Alogrithm Based on Population Size Mutable Coarse-grained[J]. Journal of Chinese Mini-Micro Computer Systems,2003,24(3):535-536.

[9] 龔雪晶,慈林林,姚康澤,等.顧及負(fù)載平衡的并行多種群自適應(yīng)遺傳算法[J].系統(tǒng)仿真學(xué)報,2009,21(17):5396-5398. GONG Xuejing, CI Linlin, YAO Kangze, et al. Parallel Multi-population Adaptive Genetic Algorithm by Considering Work Load Balance[J]. Journal of System Simulation,2009,21(17):5396-5398.

[10] 嚴(yán)曉明.粗粒度并行遺傳算法遷移算子的一種改進(jìn)[J].福建師范大學(xué)學(xué)報(自然科學(xué)版),2013,29(1):43-47. YAN Xiaoming. An Improved Migrate Operator of Coarse-Grained Parallel Genetic Algorithm[J]. Journal of Fujian Normal University(Natural Science Edition),2013,29(1):43-47.

[11] 陳國良.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社,1996:202-214. CHEN Guoliang. Genetic algorithm and its application[M]. Beijing: Posts and Telecom Press,1996:202-214.

[12] Rudolph G. Convergence Analysis of Canonical GA[J]. IEEE Trans on Neural Networks,1994,5(1):96-101.

[13] Holland J H. Adoption in Natural and Artificial Systems[M]. Massachusetts Institute of Technology Press,1975:126-137.

[14] 劉守生,于盛林,丁勇,等.基于均勻分割的多種群并行遺傳算法[J].數(shù)據(jù)采集與處理,2003,18(2):143-145. LIU Shousheng, YU Shenglin, DING Yong, et al. Multipopulation Parallel Genetic Algorithm Based on Even Partition[J]. Journal of Data Acquisition and Processing,2003,18(2):143-145.

[15] Reeves C R. Using genetic algorithms with small populations[C]//Proceedings of the 5th international conference on genetic algorithms, San Francisco: Morgan Kaufmann Publishers,1993:92-97.

A Parallel Genetic Algorithm Based on Solution Space Division

FENG Yong GUO Jun XU Hongyan FU Xiaoying

(School of Information, Liaoning University, Shenyang 110036)

Genetic algorithm is a kind of the optimization method which is commonly used in NP problem for approximate optimal solution, and it has been widely used in national defense, scientific research, economic management, engineering construction, and other important fields. But some problems often appear during its solving process, such as premature convergence to local optimal solution and the high computational complexity. To solve these problems, first of all, this paper proposes a parallel processing mechanism based on the solution space division which implement parallel processing to solve the optimization problem by dividing the problem solution space. Then the mechanism is introduced into the genetic algorithm, and this paper proposes a parallel genetic algorithm based on the solution space division. Finally, the experimental comparison indicate that the proposed algorithm in parallel processing has a good linear speedup, at the same time overcoming the premature convergence to local optimal solution is better than the standard genetic algorithm and coarse-grained parallel genetic algorithm.

solution space division, parallelization, genetic algorithm, linear speedup, optimization

2016年8月12日,

2016年9月25日

遼寧省本科教學(xué)改革項目(編號:201607);遼寧省自然科學(xué)基金項目(編號:2013020031);遼寧省檔案科技項目(編號:L-2016-R-7)資助。

馮勇,男,博士,教授,研究方向:數(shù)據(jù)挖掘和個性化推薦。郭軍,男,碩士研究生,研究方向:數(shù)據(jù)挖掘和個性化推薦。徐紅艷,女,碩士,副教授,研究方向:數(shù)據(jù)庫技術(shù)、deep web。付瀟瑩,女,研究方向:數(shù)據(jù)挖掘和個性化推薦。

TP183

10.3969/j.issn.1672-9722.2017.02.007