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

馮 勇 郭 軍 徐紅艷 付瀟瑩

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

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

馮 勇 郭 軍 徐紅艷 付瀟瑩

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

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

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

Class Number TP183

1 引言

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

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

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

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

1) 分割階段。對(duì)解空間進(jìn)行劃分,設(shè)待優(yōu)化的問(wèn)題共有m個(gè)自變量,即X1,X2,…,Xm,整體解空間S為m個(gè)自變量構(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ù)為最小的計(jì)算單元,各子任務(wù){(diào)K1,K2,…,Kn}分別在其所在的解空間{S1,S2,…,Sn}中對(duì)目標(biāo)函數(shù)F(X1,X2,…,Xm)進(jìn)行尋優(yōu)運(yùn)算,得出各子任務(wù){(diào)K1,K2,…,Kn}的最優(yōu)解,對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值為{A1,A2,…,An}。各子任務(wù)的尋優(yōu)過(guò)程是完全獨(dú)立的,子任務(wù)在各自的解空間中對(duì)優(yōu)化問(wèn)題求解。

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所對(duì)應(yīng)的解(x1,x2,…,xm)為整體解空間中的最優(yōu)解。

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

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

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

3.1 算法理論分析

根據(jù)文獻(xiàn)[11～12]可知選擇算子采用精英選擇法,即每一代選擇的時(shí)候最優(yōu)個(gè)體淘汰掉最差個(gè)體的遺傳算法收斂到全局最優(yōu)點(diǎn)。優(yōu)化問(wèn)題中函數(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)解。對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行性能分析可知在固定迭代次數(shù)下其運(yùn)算的時(shí)間復(fù)雜度為關(guān)于個(gè)體數(shù)N的O(N)。對(duì)解空間進(jìn)行K等分分割,若每個(gè)子空間的個(gè)體數(shù)為N/K,可知各子群的運(yùn)算時(shí)間均為原運(yùn)算時(shí)間的1/K,從而達(dá)到線(xiàn)性加速。

3.2 算法思想

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

3.3 算法描述

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

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

Step2 分割階段,將整體解空間S等分為n份,子種群個(gè)體數(shù)為整體個(gè)體數(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)值,其對(duì)應(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 算法示例

為更好地說(shuō)明算法的運(yùn)行,這里給出具體示例。如果一個(gè)遺傳算法的目標(biāo)函數(shù)的搜索域是在二維空間中,即目標(biāo)函數(shù)的自變量為X、Y,目標(biāo)函數(shù)F(X,Y)=X2+Y2為關(guān)于X、Y的復(fù)雜函數(shù)。本例設(shè)種群個(gè)體數(shù)M為200、進(jìn)化代數(shù)T為300、交叉概率Pc為0.6、變異概率Pm為0.01。對(duì)整體解空間即X、Y的范圍進(jìn)行4等份分割,每個(gè)子空間中的個(gè)體數(shù)為50。假設(shè)解空間為0≤X≤10,0≤Y≤10,將X、Y的范圍空間進(jìn)行4等份分割后,即分割后的4個(gè)子任務(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)行搜索,每個(gè)子群采用基本遺傳算法獨(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ù)值,其所對(duì)應(yīng)的解X4=10、Y4=10作為全局最優(yōu)解。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

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

-5≤x1,x2≤5

max(F)=1

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 結(jié)果分析

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

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

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

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

5 結(jié)語(yǔ)

為提升并行遺傳算法的性能及克服過(guò)早收斂問(wèn)題,本文提出了一種基于解空間分割的并行處理機(jī)制,并在此基礎(chǔ)上給出了一種基于解空間分割的并行遺傳算法,改進(jìn)算法對(duì)問(wèn)題解空間進(jìn)行分割,使分割后的子任務(wù)在其解空間內(nèi)進(jìn)行最優(yōu)化求解,將各子任務(wù)得出的解匯總,從中選出全局最優(yōu)解。最后,經(jīng)實(shí)驗(yàn)分析表明本文所提算法設(shè)計(jì)簡(jiǎn)單、便于實(shí)現(xiàn)、沒(méi)有過(guò)多的參數(shù)設(shè)定,在并行化處理方面具有良好的線(xiàn)性加速比,同時(shí)在克服過(guò)早收斂于局部最優(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] 張國(guó)輝,高亮,李培根,等.改進(jìn)遺傳算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].機(jī)械工程學(xué)報(bào),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ū)探測(cè)[J].自動(dòng)化學(xué)報(bào),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)工程理論與實(shí)踐,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ì)算性能分析[J].武漢理工大學(xué)學(xué)報(bào),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ì)算機(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é)報(bào),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é)報(bào)(自然科學(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] 陳國(guó)良.遺傳算法及其應(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é)改革項(xiàng)目(編號(hào):201607);遼寧省自然科學(xué)基金項(xiàng)目(編號(hào):2013020031);遼寧省檔案科技項(xiàng)目(編號(hào):L-2016-R-7)資助。

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

TP183

10.3969/j.issn.1672-9722.2017.02.007