并行計(jì)算在元啟發(fā)式算法的應(yīng)用

朱淑娟，孫 穎，胡 沛，2，司明超，潘正祥

(1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266590；2.南陽理工學(xué)院 計(jì)算機(jī)與軟件學(xué)院，河南 南陽 473004)

近年來，隨著科學(xué)研究的不斷深入，面臨問題的復(fù)雜性也在不斷增加。尋優(yōu)問題在其中出現(xiàn)的比重也不斷提高。面對這種挑戰(zhàn)，人們采用各種各樣的優(yōu)化方法：機(jī)器學(xué)習(xí)方法，元啟發(fā)式算法，數(shù)據(jù)挖掘方法等。其中，元啟發(fā)式算法逐漸成為人們關(guān)注的焦點(diǎn)，它受到仿生學(xué)的啟發(fā)，從自然界中獲取靈感，跳出局部最優(yōu)，從而找到全局最優(yōu)解。而且，元啟發(fā)式算法被用于解決生活中各種各樣的優(yōu)化問題，并取得了不錯(cuò)的效果。常見的元啟發(fā)式算法有：遺傳算法(GA)[1]模擬達(dá)爾文的進(jìn)化理論和適者生存的遺傳機(jī)制；粒子群優(yōu)化算法(PSO)[2]通過粒子模擬鳥群覓食行為，更新粒子的速度和位置，從而找到全局最優(yōu)值。蟻群優(yōu)化算法(ACO)[3]的靈感來源于螞蟻在尋找食物的過程中，根據(jù)釋放信息素的多少而發(fā)現(xiàn)路徑的行為。貓群優(yōu)化算法(CSO)[4]是通過觀察貓的兩種行為產(chǎn)生的，一種是貓的跟蹤模式，另一種是貓的尋找模式。魚類洄游優(yōu)化算法(FMO)[5]將魚類遷徙的行為和運(yùn)動的模型集成到優(yōu)化過程中，并利用魚類生物學(xué)中游動的運(yùn)動方程尋找最優(yōu)值。擬仿射變換進(jìn)化算法(QUATRE)[6]是一種基于群體的優(yōu)化算法，該算法將仿射變換作為一種進(jìn)化方法，利用粒子間的協(xié)同合作進(jìn)行優(yōu)化。竹節(jié)蟲種群進(jìn)化算法(PPE)[7]靈感來源于自然界，模擬竹節(jié)蟲的4種生長方式并將其分為4個(gè)進(jìn)化階段：趨同進(jìn)化、路徑依賴、種群增長、種群競爭。把有利的基因遺傳給下一代，使其更好的生存。鯨魚優(yōu)化算法(WOA)[8]模擬座頭鯨捕獵的行為，將鯨魚吐泡泡的行為看作開發(fā)階段，將其尋找獵物的行為看作探索階段，使該算法相比其它傳統(tǒng)算法更具有競爭力?；诮虒W(xué)的優(yōu)化方法(TLBO)[9]，根據(jù)教學(xué)的過程將算法分為兩個(gè)階段：第1個(gè)階段是學(xué)生向老師學(xué)習(xí)成為“教師階段”；第2個(gè)階段是學(xué)習(xí)者相互交流稱為“學(xué)習(xí)者階段”。

元啟發(fā)式算法在展現(xiàn)出較好性能的同時(shí)，也存在一些局限性——不能很好地平衡探索和開發(fā)的關(guān)系，容易陷入局部最優(yōu)。為了克服這個(gè)缺點(diǎn)，各種元啟發(fā)式算法的改進(jìn)版本被提出。改進(jìn)的主要策略有：并行、二進(jìn)制、自適應(yīng)、緊湊、混沌、多目標(biāo)、混合算法、離散、反向?qū)W習(xí)。

并行策略是元啟發(fā)式算法常見的改進(jìn)方式。與操作系統(tǒng)層面并行(硬件上的并行[10-11])不同的是優(yōu)化算法的并行屬于分群[12]：將一個(gè)大種群分為多個(gè)小種群，每隔一定的迭代次數(shù)，種群間進(jìn)行信息交流。目前，已有許多研究者使用并行策略對元啟發(fā)式算法進(jìn)行改進(jìn)[13-14]，并將改進(jìn)后的元啟發(fā)式算法應(yīng)用于各個(gè)領(lǐng)域。例如，具有3種通信策略的并行粒子群優(yōu)化算法(PPSO)[12]，并行遺傳算法在噪聲信道中的應(yīng)用(PGA)[15]，求解多目標(biāo)優(yōu)化問題的并行多群粒子群優(yōu)化策略(MOPSO)[16]。

目前工作是將互聯(lián)網(wǎng)中收集的各種并行元啟發(fā)算法資料進(jìn)行整理。首先介紹一些常見的元啟發(fā)式算法，以及變體。第2部分結(jié)合具體的文獻(xiàn)介紹了兩類并行策略。首先是分組的元啟發(fā)式算法，具體展示了分組的策略和代表性論文。然后對并行元啟發(fā)式算法的文獻(xiàn)按照算法分類進(jìn)行了總結(jié)。最后敘述了真實(shí)的并行元啟發(fā)式算法的分類、交流策略以及相關(guān)論文的綜述。第3部分介紹了并行策略在元啟發(fā)式算法的應(yīng)用。第4部分描述了本文的工作和未來的建議。

1 并行計(jì)算和元啟發(fā)式算法的結(jié)合

由于各類優(yōu)化問題的不斷復(fù)雜化，研究者們越來越關(guān)注并行的元啟發(fā)式算法。并行策略分為兩種：一種是真實(shí)的并行(操作系統(tǒng)層面)，使用多處理器實(shí)現(xiàn)，可以解決高計(jì)算成本的優(yōu)化問題，提高執(zhí)行效率。另一種是虛擬并行，將種群分解為多個(gè)子種群，各子種群進(jìn)行種間交流，產(chǎn)生更好的解。

1.1 分組策略

1.1.1 并行的粒子群算法

原始的PSO算法[2]由KENNEDY 和 EBERHART在1995年提出，它是一個(gè)基于種群的優(yōu)化算法。模仿鳥類的捕食行為，將每只鳥賦予位置和速度兩個(gè)屬性。其中vi=[v1，v2，…，vd]，d表示維度，vi代表第i個(gè)粒子的速度。xi=[x1，x2，…，xd]，xi代表第i個(gè)粒子的位置。并且將每次迭代的個(gè)體最優(yōu)值(pbest)和全局(gbest)最優(yōu)值保存下來，用于引導(dǎo)個(gè)體朝著最優(yōu)值的方向前進(jìn)。在PSO中，粒子被隨機(jī)初始化，更新公式如下：

(1)

(2)

PSO算法的步驟如下：

Step1：初始化N個(gè)粒子，并為每個(gè)粒子隨機(jī)初始化一定范圍內(nèi)的位置和速度；

Step2：評估每個(gè)粒子的適應(yīng)度值；

Step4：使用式(1)～(2)更新粒子的速度和位置；

Step5：重復(fù)步驟(2)～(4)，直到結(jié)束。

并行的粒子群算法(PPSO)[12]將原始PSO算法的種群分為多個(gè)子種群，每個(gè)子種群使用的更新方式與原始PSO算法一樣。在進(jìn)行一定的迭代次數(shù)之后，進(jìn)行種間交流，文獻(xiàn)[12]提出了3種信息交流策略。第1種策略是每隔r1代，對粒子進(jìn)行變異和更新。首先，計(jì)算迭代次數(shù)為t時(shí)的全局最優(yōu)值Gt，將其變異；然后，替代每個(gè)組中最差的粒子。第2種策略是每隔r2代，將每個(gè)組中最好的粒子Gt移到相鄰的組中，替換掉相鄰組中一些較差的粒子。第3種策略是前兩種策略的結(jié)合，每隔r1代使用第1種策略，每隔r2代使用第2種策略。

PPSO算法的步驟如下：

Step1：初始化，將N個(gè)粒子分為g個(gè)組，每個(gè)組的個(gè)數(shù)為ng；

Step2：評估，對每個(gè)組中的粒子進(jìn)行評估，計(jì)算其適應(yīng)度值；

Step3：更新，計(jì)算每個(gè)組中的全局最優(yōu)值得到所有粒子的全局最優(yōu)值，并且計(jì)算每個(gè)粒子的個(gè)體最優(yōu)值；利用式(1)～(2)進(jìn)行更新粒子的速度和位置；

Step4：交流，選擇交流策略的一種進(jìn)行信息交換；

Step5：終止，重復(fù)步驟(2)～(4)，直到結(jié)束。

1.1.2 并行的差分進(jìn)化算法

原始的DE算法[17]由STORN和PRICE在1997年提出，DE算法使用較少的參數(shù)，達(dá)到的效果最優(yōu)，非常適合并行計(jì)算。DE算法有以下幾個(gè)主要的過程：變異、交叉和選擇。

變異：從所有個(gè)體中隨機(jī)選擇3個(gè)個(gè)體p1、p2、p3，并利用式(3)對當(dāng)前個(gè)體vi進(jìn)行更新：

vi=p1+F×(p2-p3)，

(3)

其中F是[0，2]之間的常數(shù)，p1、p2、p3屬于{1，2，…，N}，N是種群中個(gè)體的數(shù)量。

交叉：對當(dāng)前的2個(gè)個(gè)體vi和xi的某些維度進(jìn)行交叉，得到新的個(gè)體ui更新公式如下：

(4)

其中CR代表交叉概率，它是[0，1]之間的隨機(jī)數(shù)；jrand是[1，D]之間的隨機(jī)數(shù)，其中D是維度。

選擇：選擇一個(gè)實(shí)驗(yàn)個(gè)體ti，如果f(ti)小于或者等于f(vi)則將ti個(gè)體代替當(dāng)前個(gè)體vi。

(5)

DE算法的步驟如下：

step1：初始化種群的數(shù)量N；

step2：根據(jù)更新公式(3)和(4)，對個(gè)體執(zhí)行變異和交叉操作；

step3：使用式(5)執(zhí)行貪婪選擇過程；

step4：重復(fù)步驟(2)～(3)，直到結(jié)束。

文獻(xiàn)[18]提出了改進(jìn)的差分進(jìn)化算法(PaDE)，該算法對原始DE算法進(jìn)行了3個(gè)方面的改進(jìn)：(1)采用分組策略，并對每個(gè)組的參數(shù)使用自適應(yīng)策略，例如每個(gè)個(gè)體的控制參數(shù)F服從柯西分布，交叉概率CR服從正態(tài)分布，選擇概率P(j)=1/j。(2)提出了拋物線種群方案，每個(gè)組中的種群數(shù)量動態(tài)減少，詳細(xì)的縮減公式如下：

(6)

式中psmin代表種群規(guī)模的最小值；psini代表種群規(guī)模的初始值；nfe代表當(dāng)前個(gè)體的適應(yīng)度值，nfemax代表函數(shù)的最大值，對最終的結(jié)果進(jìn)行四舍五入(round)得到第t+1代的個(gè)體數(shù)量pst+1。(3)在DE算法的3個(gè)主要過程中，變異是關(guān)鍵性的步驟，本篇論文提出了基于時(shí)間戳的變異方案。

PaDE算法的步驟如下：

Step1：初始化種群的大小和所有個(gè)體的位置；

Step2：計(jì)算每個(gè)個(gè)體的適應(yīng)度大小，并記錄全局最優(yōu)個(gè)體的位置和適應(yīng)度值；

Step3：將所有個(gè)體隨機(jī)分為k個(gè)子種群，并根據(jù)控制參數(shù)F自動生成每個(gè)個(gè)體的F值；

Step4：為每個(gè)子種群生成交叉概率Cr；

Step5：使用策略3進(jìn)行選擇操作；

Step6：使用策略1對參數(shù)進(jìn)行更新，并記錄全局最優(yōu)個(gè)體；

Step7：使用策略2調(diào)整每個(gè)子種群的大小；

Step8：重復(fù)執(zhí)行步驟(3)～(7)，直到終止。

1.1.3 并行的貓群優(yōu)化算法

原始的CSO算法是由CHU等人在2006年提出的[4]，其靈感來源于貓的行為。CSO將貓?jiān)谛菹r(shí)的狀態(tài)看作算法的搜尋模式，一旦貓發(fā)現(xiàn)目標(biāo)算法就會進(jìn)入另一個(gè)階段即跟蹤模式。同時(shí)，通過一定的概率控制兩種模式的執(zhí)行比例。值得注意的是：在搜尋模式中，利用一定概率從記憶池中選擇位置進(jìn)行移動。概率公式如下：

(7)

其中，記憶池中有j只貓，Pi代表選中當(dāng)前解的概率，F(xiàn)i代表貓的適應(yīng)度值，F(xiàn)max和Fmin.代表適應(yīng)度值的最大和最小。Fb由目標(biāo)函數(shù)確定，如果是最大化問題Fb=Fmin，相反則Fb=Fmax。在跟蹤模式中，使用式(3)～(4)更新貓的速度和位置。

vi=vi+r1×c1×(xbest-xi)，

(8)

xi=vi+xi，

(9)

式中vi和xi代表第i只貓的速度和位置；xbest代表適應(yīng)度值最好的貓的位置，c1為常數(shù)，r1是[0，1]之間的隨機(jī)數(shù)。

CSO算法的步驟如下：

Step1：創(chuàng)建N只貓，隨機(jī)初始化每只貓的位置、速度和標(biāo)志；

Step2：評估每只貓的適應(yīng)度值并記錄全局最優(yōu)個(gè)體；

Step3：根據(jù)標(biāo)志判斷執(zhí)行跟蹤過程或者搜尋過程；

Step4：根據(jù)一定的比例重新選取一定的個(gè)體執(zhí)行搜尋模式，剩余的執(zhí)行跟蹤模式；

Step5：重復(fù)步驟(2)～(3)，直到結(jié)束。

文獻(xiàn)[19]提出了CSO的并行化，稱為并行的貓群優(yōu)化算法(PCSO)。PCSO在跟蹤過程中執(zhí)行并行策略，滿足交流條件時(shí)，對分組的個(gè)體執(zhí)行組間交流。本文中具體的并行策略如下：

首先，隨機(jī)選擇一組個(gè)體，并對該組個(gè)體按照適應(yīng)度值大小進(jìn)行排序，適應(yīng)度值最小的為個(gè)體L；

其次，在剩余組中隨機(jī)選擇一組個(gè)體，并記錄局部最優(yōu)解P；

最后，使用局部最優(yōu)解P替換適應(yīng)度值最差的個(gè)體L。

PCSO算法的步驟如下：

Step1：創(chuàng)建N只貓，同時(shí)將其分為g組，隨機(jī)初始化每只貓的位置、速度和標(biāo)志；

Step2：評估每只貓的適應(yīng)度值并記錄全局最優(yōu)個(gè)體；

Step3：根據(jù)標(biāo)志判斷執(zhí)行跟蹤過程或者搜尋過程，如果是跟蹤模式，則并行執(zhí)行；

Step4：根據(jù)一定的比例選取一定的個(gè)體執(zhí)行搜尋模式，剩余的執(zhí)行跟蹤模式；

Step5：判斷是否滿足信息交換的迭代次數(shù)，如果滿足，則執(zhí)行并行策略；

Step6：重復(fù)步驟(2)～(5)，直到結(jié)束。

1.1.4 其它并行的元啟發(fā)式優(yōu)化算法

表1整理了常見的并行元啟發(fā)式算法。下面將按照算法進(jìn)行分類，詳細(xì)介紹這些常見算法的分組策略。

并行的共生生物搜索算法(SOS)：在文獻(xiàn)[20]中，考慮到共生生物搜索算法的局限性，提出了多組思想和基于量子行為的組間交流策略(MQSOS)。對每個(gè)組中最好的5個(gè)個(gè)體根據(jù)式(10)更新，同時(shí)對每個(gè)組中較差的5個(gè)個(gè)體根據(jù)式(11)更新：

(10)

(11)

式中xnew為更新后的個(gè)體向量；xi為當(dāng)前個(gè)體的位置；avei代表第i個(gè)個(gè)體歷史最優(yōu)位置的平均值；Pi是量子力學(xué)中的吸引點(diǎn)，個(gè)體在運(yùn)動過程中，向Pi靠近；α和u分別為收斂系數(shù)和隨機(jī)變量。

并行的狼群優(yōu)化算法(GWO)：文獻(xiàn)[21]提出了具有交流策略的分組的狼群優(yōu)化算法(PGWO)。經(jīng)過一定的迭代次數(shù)，將第i個(gè)組的m個(gè)最佳個(gè)體，替換第i+1組中較差的m個(gè)個(gè)體。文獻(xiàn)[22]提出了多組GWO算法，將狼群按照適應(yīng)度值分為多組，適應(yīng)度值由大到小，最優(yōu)的第1只狼分到第1組，第2只狼分到第2組，依次類推，循環(huán)分組。每隔一定的迭代次數(shù)，重新分組。

并行的差分進(jìn)化算法(DE)：文獻(xiàn)[23]動態(tài)地將種群分為3組，每個(gè)組中的個(gè)體按照由適應(yīng)度值大小進(jìn)行排序。然后將每個(gè)組中的前3個(gè)個(gè)體，隨機(jī)替換其他組中后3個(gè)解。在下一次迭代的時(shí)候，再重新合并為一個(gè)大的群體，然后分為3個(gè)子種群。文獻(xiàn)[24]提出了具有兩種交流策略的并行緊湊差分進(jìn)化算法(pcDE)。第1種是精英策略，該策略將所有組中的最優(yōu)解替換為全局最優(yōu)解。第2種是均值精英策略，對所有組中的最優(yōu)解求平均值替換全局最優(yōu)解。

并行的貓群優(yōu)化算法(CSO)：文獻(xiàn)[25]對PCSO算法進(jìn)行的改進(jìn)版本，提出了改進(jìn)的并行貓群優(yōu)化算法(EPCSO)。組間交流策略與PCSO中的交流策略一樣，但是，使用了田口正交方法對PSCO進(jìn)行改進(jìn)。文獻(xiàn)[26]對改進(jìn)的PCSO進(jìn)行了研究。與之前一樣的是都在跟蹤模式采用了并行策略，并進(jìn)行信息交換。這篇論文主要對應(yīng)用方面做出了突出的貢獻(xiàn)。文獻(xiàn)[27]將具有3種策略的PCSO算法與緊湊方案結(jié)合，應(yīng)用到無線傳感器網(wǎng)絡(luò)定位問題上。策略1：平均替換，將每個(gè)組的局部最優(yōu)解取平均代替每個(gè)組中最差的解。策略2：最佳替換，隨機(jī)選擇一組的最優(yōu)值代替每個(gè)組的最差解。策略3：權(quán)重替換，將每個(gè)組的最優(yōu)值，用不同的權(quán)重對應(yīng)相乘之和代替每個(gè)組的隨機(jī)解。

并行的蝙蝠算法(BA)：文獻(xiàn)[28]提出了PBA算法并將其應(yīng)用于車間調(diào)度問題。采用的交流策略是將第i組中k個(gè)最佳個(gè)體替換第i+1組較差的個(gè)體，第i+1組替換第i+2組，依次循環(huán)。文獻(xiàn)[29]將并行與壓縮策略結(jié)合，提出了一種改進(jìn)的BA算法(pcBA)。該算法使用3種策略：所有組中最優(yōu)值替換每個(gè)組中最差的；一個(gè)組中最優(yōu)個(gè)體移動到相鄰組中替換較差的個(gè)體；隨機(jī)選擇兩個(gè)組進(jìn)行交換。通過動態(tài)參數(shù)控制3種策略的執(zhí)行。文獻(xiàn)[30]提出了混合的并行蝙蝠算法(HPBA)，將變異操作嵌入到PBA中，克服了原始算法的不足。

并行的擬仿射變換進(jìn)化算法(QUATRE)：文獻(xiàn)[31]將并行策略引入到原始的QUATRE算法中，使用的策略是將每個(gè)組中最優(yōu)的個(gè)體移動到相鄰組中，替換相鄰組較差的粒子。文獻(xiàn)[32]將自適應(yīng)、分組和QUATRE算法結(jié)合，使用3個(gè)組，每個(gè)組采用不同的策略更新迭代。文獻(xiàn)[33]采用3種交流策略，每次隨機(jī)選擇一種對每個(gè)組中最差的個(gè)體進(jìn)行更新。策略1：使用隨機(jī)一組的最優(yōu)個(gè)體與當(dāng)前最差的粒子作差，再加上最差個(gè)體的位置偏移量，來替換最差的粒子。策略2：使用隨機(jī)兩組的最優(yōu)個(gè)體平均值與當(dāng)前最差的粒子作差，再加上最差個(gè)體的位置偏移量，替換最差的粒子。策略3，與之前的流程一樣，不同的是選用3個(gè)組的最優(yōu)個(gè)體平均值作差。

當(dāng)然，還有一些其它的并行元啟發(fā)式算法(見表1)。例如，多分組蜂群算法(MCBA)[34]，多組螢火蟲算法(IMGFA)[35]，基于DE和花授粉算法(FPA)的并行優(yōu)化算法(FDA)[36]，分布式并行螢火蟲算法(DPFA)[37]，一個(gè)新的異構(gòu)元啟發(fā)式算法(PGWO)[38]，改進(jìn)的花授粉算法(pcFPA)[39]，多分組花朵授粉算法(MFPA)[40]，并行多宇宙優(yōu)化算法(PMVO)[41]，并行鯨魚優(yōu)化算法(PWOA)[42]，并行自適應(yīng)布谷鳥搜索算法(pcCS)[43]，并行緊湊差分進(jìn)化算法(pcDE)[24]，多組正余弦算法(MMSCA)[44]，并行正余弦算法(PSCA)[45]，自適應(yīng)并行阿基米德優(yōu)化算法(APAOA)[46]，多組協(xié)同進(jìn)化的多目標(biāo)蚱蜢優(yōu)化算法(MOGOW)[47]，多組蜻蜓算法(MDA)[48]，自適應(yīng)分組樽海鞘群算法(AMSSA)[49]等。

表1 多分組的并行元啟發(fā)式算法總結(jié)

續(xù)表1

1.2 真實(shí)的并行

在本節(jié)中，對表2整理的文獻(xiàn)進(jìn)行分類，并簡要的概述。并行元啟發(fā)式算法的效率比較突出，有效的降低了運(yùn)算成本，提高了運(yùn)算時(shí)間，在復(fù)雜的全局優(yōu)化問題上有突出效果。表2中，整理了真實(shí)的并行文章。

表2 真實(shí)的并行元啟發(fā)式算法總結(jié)

1.2.1 并行化模型

并行化模型主要分為以下4種：主從模型、島嶼模型(粗粒度)、細(xì)胞元模型(細(xì)粒度)和混合模型[65，66，70，72，73，79]。

(1)主從模型：主從模式有一個(gè)主處理器，多個(gè)從處理器，所有的操作并行的在從處理器工作，并由主處理器控制。如圖1所示，主從模式結(jié)構(gòu)類似于星型。

(2)粗粒度模型：粗粒度模型也稱島嶼模型，將一個(gè)種群分為多個(gè)子種群，每個(gè)子種群代表一個(gè)處理器單元。如圖2所示，每個(gè)子種群之間通過交流策略進(jìn)行溝通，從而交換部分個(gè)體。

(3)細(xì)粒度模型：細(xì)粒度模型也稱細(xì)胞元模型，將一個(gè)種群劃分為多個(gè)小的子種群，并將子種群映射到二維網(wǎng)格中。通常，每個(gè)子種群包含4個(gè)領(lǐng)域個(gè)體。然而，當(dāng)與領(lǐng)域個(gè)體交換信息時(shí)，速度較快，與其他個(gè)體溝通時(shí)會出現(xiàn)延遲。如圖3所示。

(4)混合模型：由上面兩個(gè)或兩個(gè)以上模型組合的并行化模型稱為混合模型。如圖4所示。

圖1 主從模式 圖2 粗粒度模式

圖3 細(xì)粒度模式 圖4 混合模式

1.2.2 并行元啟發(fā)式算法的研究

ASADZADEH使用3種模型實(shí)現(xiàn)了并行ABC算法(pABC)[74]：主從模型，細(xì)粒度模型和粗粒度模型。在粗粒度模型中，pABC在每個(gè)處理器上設(shè)置了一個(gè)殖民地，共有n個(gè)，每個(gè)殖民地使用的領(lǐng)域拓?fù)浣Y(jié)構(gòu)是立方體，并且每兩個(gè)殖民地之間動態(tài)地進(jìn)行信息溝通。

在文獻(xiàn)[64]使用主從模式對原始GA進(jìn)行改進(jìn)，共享多處理器，并將其應(yīng)用于學(xué)校時(shí)間表問題。文獻(xiàn)[67]分析了同步和并行式GA的響應(yīng)力，還涉及了島嶼模型和細(xì)胞元模型。文獻(xiàn)[68]中提出了并行GA，并將其應(yīng)用于帶時(shí)間窗的車輛路徑規(guī)劃。該算法將種群分為兩個(gè)組(G1和G2)，每個(gè)組負(fù)責(zé)一個(gè)目標(biāo)：G1負(fù)責(zé)最小化移動距離，G2負(fù)責(zé)最小化約束沖突，并且兩個(gè)種群協(xié)同進(jìn)化。

文獻(xiàn)[16]使用了廣播的交流策略，研究了同步和異步的并行多分組PSO算法，并將其用于解決多目標(biāo)問題。文獻(xiàn)[71]中，使用3種模型實(shí)現(xiàn)PPSO算法：島嶼模型、細(xì)胞元模型和領(lǐng)域島嶼模型。島嶼-PPSO使用環(huán)形結(jié)構(gòu)實(shí)現(xiàn)每個(gè)子種群的演化，在進(jìn)化過程中，通過遷移實(shí)現(xiàn)信息交流。遷移策略是將每個(gè)島的最佳粒子替換相鄰島中隨機(jī)選擇的粒子。細(xì)胞-PPSO將粒子分布到處理單元中，全局最優(yōu)解不可見，故交流策略使用局部粒子中最佳的粒子更新。領(lǐng)域島嶼-PPSO與島嶼-PPSO不同，將遷移的概念取消，使用環(huán)形拓?fù)浣Y(jié)構(gòu)和二維網(wǎng)絡(luò)拓?fù)浣Y(jié)合。

文獻(xiàn)[14]提出了并行蟻群算法(PACS)，該算法使用3種通信方式，有效的解決了旅行商問題。文獻(xiàn)[69]提出了并行蟻群優(yōu)化算法(PACS)，采用7種交流策略。策略1，將最優(yōu)個(gè)體分為一組，將剩余的個(gè)體隨機(jī)分為多組，每隔一定的迭代次數(shù)，用最好的組去優(yōu)化其他組的個(gè)體。策略2，每隔一定的迭代次數(shù)，隨機(jī)找一對組進(jìn)行交流。策略3，組與組構(gòu)成環(huán)結(jié)構(gòu)進(jìn)行信息素的更新。策略4，向相鄰組更新信息素。策略5、策略6和策略7是策略1分別和策略2、策略3、策略4的組合。

2 基于并行優(yōu)化算法的應(yīng)用

近年來，越來越多的論文使用并行元啟發(fā)式算法解決各樣格式的復(fù)雜問題，主要包括以下幾個(gè)方面：無線傳感器網(wǎng)(WSN)、旅行商問題(TSP)、圖像分割、調(diào)度問題、路徑規(guī)劃等問題。在本節(jié)中，主要回顧并行元啟發(fā)式算法的應(yīng)用問題。同時(shí)，在表1和表2中列舉了相關(guān)文章的應(yīng)用。

(1)無線傳感器網(wǎng)絡(luò)是一種很有前途的新興技術(shù)，它由傳感器節(jié)點(diǎn)組成，節(jié)點(diǎn)用于獲取周圍的信息。例如，文獻(xiàn)[26]使用EPCSO對無線傳感器節(jié)點(diǎn)的部署進(jìn)行了優(yōu)化，延長了無線傳感器網(wǎng)絡(luò)的使用壽命，同時(shí)降低了傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的損耗。文獻(xiàn)[32]將改進(jìn)的擬仿射變換算法(AMG-QUATRE)應(yīng)用于WSN的定位，實(shí)驗(yàn)結(jié)果表明，AMG-QUATRE與其他算法相比，定位更準(zhǔn)確。文獻(xiàn)[29]使用pcBA對WSN的能量平衡問題進(jìn)行優(yōu)化。文獻(xiàn)[42]使用PWOA算法準(zhǔn)確預(yù)測WSN節(jié)點(diǎn)的位置，提前預(yù)防各種災(zāi)害的發(fā)生。

(2)旅行商問題是組合優(yōu)化中常見的問題，目標(biāo)是如何找到最短的路徑。例如，文獻(xiàn)[30]將并行的蝙蝠算法對TSP進(jìn)行建模，有效地解決了旅行商問題。由于原始的蟻群算法求解TSP時(shí)，會出現(xiàn)陷入局部最優(yōu)的現(xiàn)象。所以文獻(xiàn)[63]對原始的算法進(jìn)行改進(jìn)，使用獎(jiǎng)勵(lì)機(jī)制，使得更快更準(zhǔn)的找到了各個(gè)城市之間的最短路徑。文獻(xiàn)[69]使用3種交流策略，將PACO算法應(yīng)用于TSP，并使用了大量的數(shù)據(jù)進(jìn)行檢驗(yàn)?？傮w而言，所提出的算法可以獲得很好的性能。

(3)調(diào)度問題被廣泛應(yīng)用于工業(yè)、交通和醫(yī)療保健等各個(gè)領(lǐng)域。例如，文獻(xiàn)[55]解決了經(jīng)濟(jì)負(fù)荷調(diào)度問題；文獻(xiàn)[56]解決了云計(jì)算調(diào)度問題；文獻(xiàn)[28，74]有效解決了車間調(diào)度問題；文獻(xiàn)[77]解決了經(jīng)濟(jì)排放負(fù)荷調(diào)度問題。

3 結(jié)論

近年來，關(guān)于元啟發(fā)式算法的研究越來越多。本文對并行元啟發(fā)式算法進(jìn)行了總結(jié)，將并行策略分為兩大類：第1類是虛擬的并行，也稱分群。詳細(xì)介紹了分群的概念，然后根據(jù)所調(diào)查的文獻(xiàn)對并行元啟發(fā)式算法進(jìn)行展開；第2類是真實(shí)的并行，將種群分為多組，每個(gè)組在不同的處理器上面執(zhí)行。本文首先詳細(xì)介紹了4種常見的并行化模型(主從模式、粗粒度模型、細(xì)粒度模型和混合模型)和一些代表性的研究成果。由于并行元啟發(fā)式算法廣泛應(yīng)用于各個(gè)領(lǐng)域，論文中最后對所調(diào)查文獻(xiàn)中的應(yīng)用進(jìn)行了整理，主要介紹了3類常見的應(yīng)用問題。在未來，可以采用各種并行化模型與元啟發(fā)式發(fā)進(jìn)行結(jié)合，應(yīng)用于多目標(biāo)問題上，有效的提高效率和性能。