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

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

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

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

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

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

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

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

1.1 分組策略

1.1.1 并行的粒子群算法

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

(1)

(2)

PSO算法的步驟如下：

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

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

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

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

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

PPSO算法的步驟如下：

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

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

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

Step4：交流，選擇交流策略的一種進行信息交換；

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

1.1.2 并行的差分進化算法

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

變異：從所有個體中隨機選擇3個個體p1、p2、p3，并利用式(3)對當前個體vi進行更新：

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

(3)

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

交叉：對當前的2個個體vi和xi的某些維度進行交叉，得到新的個體ui更新公式如下：

(4)

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

選擇：選擇一個實驗個體ti，如果f(ti)小于或者等于f(vi)則將ti個體代替當前個體vi。

(5)

DE算法的步驟如下：

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

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

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

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

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

(6)

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

PaDE算法的步驟如下：

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

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

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

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

Step5：使用策略3進行選擇操作；

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

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

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

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

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

(7)

其中，記憶池中有j只貓，Pi代表選中當前解的概率，F(xiàn)i代表貓的適應(yīng)度值，F(xiàn)max和Fmin.代表適應(yīng)度值的最大和最小。Fb由目標函數(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]之間的隨機數(shù)。

CSO算法的步驟如下：

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

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

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

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

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

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

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

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

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

PCSO算法的步驟如下：

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

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

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

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

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

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

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

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

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

(10)

(11)

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

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

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

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

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

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

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

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

續(xù)表1

1.2 真實的并行

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

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

1.2.1 并行化模型

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

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

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

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

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

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

圖3 細粒度模式 圖4 混合模式

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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