一種求解NP-難問題的并行協(xié)同大規(guī)模差分進(jìn)化算法

張 峰

安徽交通職業(yè)技術(shù)學(xué)院航海系,合肥,230051

1 引言

隨著科學(xué)技術(shù)的發(fā)展以及大數(shù)據(jù)時代的到來，優(yōu)化問題的規(guī)模日益增長，因而也給當(dāng)前主流的優(yōu)化算法帶來了嚴(yán)峻挑戰(zhàn)。NP-難問題在人們實(shí)際生活中隨處可見，比如，隨著中國城鎮(zhèn)化建設(shè)速度越來越快，大城市的交通流暢性問題越來越嚴(yán)重，如在大城市中合理布局公交站點(diǎn)問題。站點(diǎn)和路線的選擇都是從上千乃至上萬甚至上十萬的候選點(diǎn)以及候選路線中篩選的，因此這種站點(diǎn)優(yōu)化以及路線優(yōu)化問題均屬于一種大規(guī)模優(yōu)化問題[1]。

隨著NP-難問題規(guī)模的增大，數(shù)據(jù)維度的劇增，使得待優(yōu)化問題的維度越來越高，優(yōu)化算法的搜索空間呈指數(shù)式增長，大大降低了傳統(tǒng)優(yōu)化算法的搜索效率[2]。另外，數(shù)據(jù)量的激增使得待優(yōu)化問題的復(fù)雜度越來越大，大大增加了優(yōu)化算法的執(zhí)行時間，雖然可以通過計(jì)算機(jī)窮舉算法來解決這種問題，然而當(dāng)問題的規(guī)模逐漸擴(kuò)大時，這些算法也逐漸失效，因?yàn)檫@些實(shí)際問題本身就是一種NP-難問題，當(dāng)問題規(guī)模變大時，計(jì)算機(jī)窮舉算法很難在人們可接受的時間范圍內(nèi)給出一個可靠或者理想解。

進(jìn)化算法又稱為計(jì)算智能算法，為求解以上問題提供了有效解決途徑。但盡管傳統(tǒng)進(jìn)化算法已經(jīng)在低維空間中獲得良好的效果，然而，隨著問題維度的增加，傳統(tǒng)進(jìn)化算法的可行性及有效性遇到極大挑戰(zhàn)。因此，為了有效解決大規(guī)模優(yōu)化問題，新型大規(guī)模優(yōu)化算法亟須被提出。雖然目前已經(jīng)有很多協(xié)同進(jìn)化算法被提出，但是現(xiàn)有的協(xié)同進(jìn)化算法主要著眼于維度分組算法的研究，并且大都采用串行方式，執(zhí)行效率低是當(dāng)前協(xié)同進(jìn)化算法主要面臨的瓶頸[3]。因此，為了提高進(jìn)化算法的執(zhí)行效率，本文提出了一種求解NP-難問題的并行協(xié)同大規(guī)模差分進(jìn)化算法，基于現(xiàn)有的維度分組算法提出了一種改進(jìn)維度分組算法，從而將高維度優(yōu)化問題降解為多個低維度的子問題，從而能夠獲得更加準(zhǔn)確的分組；其次，針對獲得的維度分組，獨(dú)立優(yōu)化每個子問題，最后在CEC’2010數(shù)據(jù)集上進(jìn)行大量實(shí)驗(yàn)，驗(yàn)證本文提出的并行協(xié)同進(jìn)化算法對于求解NP-難問題的有效性。

2 相關(guān)研究綜述

為高效求解NP-難問題，美國的Holland教授借鑒生物界的進(jìn)化規(guī)律，基于達(dá)爾文的進(jìn)化理論提出了遺傳算法(Genetic Algorithm)來求解NP-難問題。因此，在短期內(nèi)大量的改進(jìn)版的遺傳算法被提出，而且被應(yīng)用于各個領(lǐng)域，比如電力系統(tǒng)調(diào)度、云計(jì)算、車輛調(diào)度、機(jī)器學(xué)習(xí)等[3，4]。隨著研究的深入，各種智能演化算法相繼出現(xiàn)，比如分布估計(jì)算法、人工蜂群算法、煙花算法等。這些算法隨后被用于求解各種優(yōu)化問題，比如多目標(biāo)優(yōu)化、多峰優(yōu)化和動態(tài)優(yōu)化等[5-7]。

目前，大規(guī)模優(yōu)化算法研究主要分為兩個大方向：其一，提出新的整體式進(jìn)化算法，包括基于反饋機(jī)制的PSO算法(FBE)、基于競爭機(jī)制的群體智能算法(CSO)等。其二，提出新的協(xié)同進(jìn)化算法。協(xié)同進(jìn)化算法是一種基于分治算法的智能進(jìn)化算法，其主要思想是將高維問題分解為多個低維問題，再將每個低維問題視為獨(dú)立的子問題。主要的分組算法有隨機(jī)分組(RG)、Delta分組(Delta-G)、多層隨機(jī)分組(MLCC)和差分進(jìn)化分組(DG)等[8-10]。

一方面，雖然現(xiàn)有的而且比較流行的整體式優(yōu)化算法已經(jīng)在高維度問題上獲得了比較好的優(yōu)化效果，但是這些算法在多峰問題上卻表現(xiàn)較差，主要是受到了大量的局部最優(yōu)解的影響。另一方面，目前的協(xié)同進(jìn)化算法都是串行實(shí)現(xiàn)，往往需要較長時間的運(yùn)行才能得到最終結(jié)果。因此，如何在廣袤的搜索空間中高效快速地尋找大規(guī)模優(yōu)化問題的最優(yōu)解仍然是比較棘手的問題。如何有效地平衡進(jìn)化算法的多樣性與收斂速度是求解大規(guī)模優(yōu)化問題的關(guān)鍵。

3 求解NP-難問題的差分進(jìn)化與大規(guī)模優(yōu)化算法

3.1 差分進(jìn)化算法

差分進(jìn)化算法(differential evolution， DE)是一種基于種群的進(jìn)化算法，自1997年被Storn和Price提出之后，越來越多的研究者們將注意力集中于DE的研究，并提出了多種DE的變種算法。DE算法大致包含四個組成成分：初始化、變異算子、交叉算子和選擇算子。交叉算子中的二項(xiàng)交叉因其簡單有效，參數(shù)容易設(shè)置等特點(diǎn)，已經(jīng)成為一種主流的交叉算子，并被廣泛應(yīng)用于DE的各種變種算法[11]。

3.2 大規(guī)模優(yōu)化算法

3.2.1 整體式進(jìn)化算法

傳統(tǒng)進(jìn)化算法在求解高維優(yōu)化問題時失效的原因是難以在探索能力和開發(fā)能力中尋求一個好的平衡點(diǎn)。一個進(jìn)化算法的多樣性往往取決于所使用的學(xué)習(xí)策略或者更新策略。因此，為了更好地求解高維度優(yōu)化問題，提出了許多新的學(xué)習(xí)機(jī)制或者更新策略。

Cheng等提出了一種競爭學(xué)習(xí)機(jī)制[12,13]，將該學(xué)習(xí)機(jī)制結(jié)合不同的雙親選擇機(jī)制，提出了不同的粒子群進(jìn)化算法。該算法中，各粒子都不向自己的歷史最優(yōu)解(pbest)以及種群的歷史最優(yōu)解(gbest)或者各自的最優(yōu)近鄰(lbest)學(xué)習(xí)，而是向當(dāng)前種群中較優(yōu)的粒子學(xué)習(xí)。在種群進(jìn)化過程中，特別是在進(jìn)化階段的后期，pbest，gbest，或者lbest可能在連續(xù)幾代中維持不變，因此，它們對維持種群的多樣性不利。

3.2.2 協(xié)同進(jìn)化算法

協(xié)同進(jìn)化算法是由Potter教授在1997年提出[14]，基于分治算法，將大規(guī)模問題通過維度分解的方法分為許多維度小的小規(guī)模問題，再對每個小問題使用傳統(tǒng)進(jìn)化算法單獨(dú)進(jìn)化，進(jìn)化完成后，將各個子問題優(yōu)化得到的最優(yōu)解結(jié)合起來，即得到原問題。

3.2.3 維度分組策略

目前的維度分組算法主要分為兩大類：動態(tài)分組和固定分組。動態(tài)分組是一個動態(tài)過程，最基礎(chǔ)而且最簡單的動態(tài)分組算法就是隨機(jī)分組。固定組數(shù)的隨機(jī)分組雖然組數(shù)是固定的，但每個組的組成成分卻是不固定的。固定組數(shù)的隨機(jī)分組最大的缺點(diǎn)是需要提前設(shè)置好分組數(shù)[15,16]。

動態(tài)組數(shù)的隨機(jī)分組的主要策略是事先定義一個組數(shù)的集合(假設(shè)r為集合S的大小，其中的每個元素都代表一個分組數(shù)目)，而后在每次隨機(jī)分組前，事先都從集合S中隨機(jī)選取一個元素作為分組的數(shù)目，而后再根據(jù)這個選擇的分組數(shù)對維度進(jìn)行隨機(jī)分組。起初從集合S中選擇組數(shù)的機(jī)制是隨機(jī)機(jī)制，明顯地，動態(tài)分組算法將變量之間的關(guān)聯(lián)信息當(dāng)作局部信息，因此維度的分組也在優(yōu)化過程中動態(tài)調(diào)整[17]。

4 基于維度分組的并行協(xié)同大規(guī)模差分進(jìn)化算法

為了提高并行進(jìn)化算法的運(yùn)行效率，本文依托新提出的維度分組策略提出了基于維度分組的并行進(jìn)化算法——并行協(xié)同進(jìn)化算法。不同于傳統(tǒng)的協(xié)同進(jìn)化算法順序優(yōu)化子問題，在該算法中，每個維度分組視為獨(dú)立子問題，而后算法同時優(yōu)化每個子問題。

4.1 算法的基本設(shè)計(jì)

在基于維度分組的并行協(xié)同大規(guī)模差分進(jìn)化算法中，每個進(jìn)程負(fù)責(zé)優(yōu)化一個或者多個維度分組(子問題)。該算法的主要框架如圖1所示。由圖1可知，本文提出的并行算法框架是一種主從式并行算法設(shè)計(jì)。

圖1 基于維度分組的并行協(xié)同進(jìn)化算法框架

根據(jù)圖1所示的協(xié)同進(jìn)化算法框架，在優(yōu)化每個子問題時，負(fù)責(zé)該子問題的子種群需要將種群其他分組維度設(shè)定為目前全局最優(yōu)解所對應(yīng)的值，因此，每個子進(jìn)程需要獲得全局最優(yōu)解信息。而主節(jié)點(diǎn)對應(yīng)的主進(jìn)程主要有兩個任務(wù)：搜集各個子問題所優(yōu)化得到的全局最優(yōu)解，然后拼湊在一起，得到整個問題的最優(yōu)解；將搜集得到的整個問題的最優(yōu)解廣播到每個子進(jìn)程，以便每個子進(jìn)程獲得最新的全局最優(yōu)信息。而每個子節(jié)點(diǎn)對應(yīng)的子進(jìn)程則只需要不斷進(jìn)化子種群，并定期將進(jìn)化得到的最新的最優(yōu)解傳遞給主進(jìn)程。

在并行算法中，主要的時間耗費(fèi)應(yīng)該集中于子問題的不斷優(yōu)化，所以好的并行算法應(yīng)該盡量減少通信時間的開銷。因此采用改進(jìn)的差分分組算法可以大大減少通信開銷，提高了并行算法的執(zhí)行效率。

4.2 并行差分進(jìn)化算法的實(shí)現(xiàn)

基于維度分組的并行協(xié)同大規(guī)模差分進(jìn)化算法的并行框架是一種異構(gòu)進(jìn)化策略。并行協(xié)同進(jìn)化算法則只有等到主進(jìn)程搜集到所有的子種群進(jìn)化得到的部分最優(yōu)解之后，將各部分拼湊起、廣播出去，子進(jìn)程才能利用到最新的全局最優(yōu)解信息，這是一種異步進(jìn)化策略。在后續(xù)實(shí)驗(yàn)中，分析和對比并行協(xié)同的異步進(jìn)化策略與順序協(xié)同的同步進(jìn)化策略，分析兩種進(jìn)化策略對協(xié)同進(jìn)化算法的影響。本文提出的并行協(xié)同進(jìn)化算法的偽代碼如算法所示。

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

輸入:維度分組G={G1,G2,…,Gm},分組個數(shù)m，計(jì)算機(jī)核數(shù)n；種群大小NP；最大迭代次數(shù)Max_Iter；

1:將0號進(jìn)程設(shè)為主進(jìn)程，其余(n-1)個進(jìn)程設(shè)為從進(jìn)程，負(fù)責(zé)優(yōu)化每個分組；

2:每個從進(jìn)程負(fù)責(zé)優(yōu)化的分組個數(shù)L=m/n;

3:If(m%n≠ 0)

4:前m%n個從進(jìn)程負(fù)責(zé)的分組數(shù)為L=L+1；

5:End If;

6:主進(jìn)程初始化gbest;

7:每個從進(jìn)程初始化自己的種群;

8:iter= 0;

9While(outer_iter

10:主進(jìn)程廣播gbest到每個子進(jìn)程；

11:Fori= 1:n

12：Forj= 1:L

13：While(inner_iter

14:第i個子進(jìn)程優(yōu)化所負(fù)責(zé)的第j個分組；

15：inner_iter++;

16:End While

17:End For

18:第i個子進(jìn)程發(fā)送優(yōu)化好的所負(fù)責(zé)的所有分組的gbest；

19:End For

20:主進(jìn)程接收每個子進(jìn)程發(fā)送的gbest，并拼接為新的new_gbest

21:If(f(new_gbest)

22:gbest=new_gbest;

23:End If;

24:outer_iter++;

25:End While;

輸出:gbest及其對應(yīng)的適應(yīng)值f(gbest);

本文提出的算法需要的通信時間較少。這是因?yàn)樵谠缙诘牟⑿兴惴ㄖ校鬟M(jìn)程必須將一個或者多個個體信息傳遞給子進(jìn)程，而后子進(jìn)程負(fù)責(zé)計(jì)算適應(yīng)值。而本文中的并行算法中，主進(jìn)程只需要將gbest傳遞給各個子進(jìn)程，同時每個子進(jìn)程只需傳遞各自優(yōu)化得到的gbest的部分給主進(jìn)程，因此本文提出的并行算法所需要的通信量大大減少。

另外，還可以看出，在早期的并行進(jìn)化算法中，子進(jìn)程只負(fù)責(zé)適應(yīng)值的計(jì)算，而主進(jìn)程負(fù)責(zé)個體的更新。然而在本文提出的并行進(jìn)化算法中，子進(jìn)程維護(hù)一個子種群，用來優(yōu)化一個或者多個子問題。而主進(jìn)程只負(fù)責(zé)收集各個子進(jìn)程的優(yōu)化得到的gbest信息。子進(jìn)程不僅僅負(fù)責(zé)適應(yīng)值的計(jì)算，而且負(fù)責(zé)子種群的更新；而主進(jìn)程只負(fù)責(zé)收集和廣播信息。因此，本文提出的并行算法并行度更高。

本研究用C++語言基于MPI并行環(huán)境實(shí)現(xiàn)本文提出的并行算法框架。主進(jìn)程的任務(wù)主要有兩個：(1)收集各個進(jìn)程發(fā)送過來的各自優(yōu)化得到的gbest分量，并將它們整合成為一個完整的gbest值，并更新當(dāng)前找到的歷史最優(yōu)解；(2)將更新過的gbest廣播給每個子進(jìn)程，進(jìn)入下一輪優(yōu)化。首先，子進(jìn)程接收主進(jìn)程廣播的歷史最優(yōu)解；而后利用SaNSDE算法進(jìn)行迭代優(yōu)化；最后在優(yōu)化一定代數(shù)后，將優(yōu)化得到的最優(yōu)解傳遞給主進(jìn)程。

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

4.3.1 實(shí)驗(yàn)環(huán)境設(shè)計(jì)

本研究首先實(shí)現(xiàn)了基于改進(jìn)同進(jìn)化算法應(yīng)用在當(dāng)今比較流行而且被人們廣泛使用的大規(guī)模優(yōu)化基準(zhǔn)函數(shù)庫——CEC’2010基準(zhǔn)函數(shù)庫。該函數(shù)庫包含20個1 000維的大規(guī)模優(yōu)化問題。這20個函數(shù)的主要特點(diǎn)如表1所示。

表1 20個CEC’2010函數(shù)的主要特性

本研究將種群大小NP設(shè)為50，每個子種群迭代次數(shù)設(shè)為40,即算法的內(nèi)層循環(huán)次數(shù)Inner_Max_Iter= 40；整個種群的迭代次數(shù)設(shè)為200，即外層循環(huán)次數(shù)Outer_Max_Iter=200。為了保證實(shí)驗(yàn)的公平性，每個算法都獨(dú)立運(yùn)行30次，實(shí)驗(yàn)結(jié)果取這30次獨(dú)立實(shí)驗(yàn)的平均值。為了后續(xù)描述，本文將順序協(xié)同進(jìn)化算法表示為“DECC-DG-Single”，而將并行協(xié)同進(jìn)化算法表示為“DECC-DG-Parallel”。

同時，為了研究分配的計(jì)算機(jī)核數(shù)對本文提出的并行協(xié)同算法的影響，在實(shí)驗(yàn)過程中，在不同的核數(shù)下運(yùn)行本文提出的并行協(xié)同進(jìn)化算法。不同核數(shù)下的并行進(jìn)化算法可以表示為“DECC-DG-Parallel-m”，其中m表示所分配的核數(shù)。比如基于4核的并行進(jìn)化算法可以表示為“DECC-DG-Parallel-4”。另外，順序和并行協(xié)同進(jìn)化算法都運(yùn)行在相同配置的機(jī)器上，每臺機(jī)器的配置為4 個Intel(R) Core(TM) i5-3470 3.20GHz CPU,4Gb 內(nèi)存和64位的Ubuntu 12.04 LTS操作系統(tǒng)。其中順序協(xié)同進(jìn)化算法獨(dú)立運(yùn)行在一臺機(jī)器上，并行算法最多運(yùn)行在16臺機(jī)器上，也就意味著本文中并行算法的最大核心數(shù)為64。

4.3.2 結(jié)果分析

為了探索不同核數(shù)對并行協(xié)同進(jìn)化算法的影響，本研究將實(shí)現(xiàn)的并行協(xié)同進(jìn)化算法分別分配4核、8核、16核、32核、48核以及64核進(jìn)行并行實(shí)驗(yàn)，圖2展示了串行協(xié)同進(jìn)化算法和并行協(xié)同進(jìn)化算法在進(jìn)化過程中獲得的函數(shù)值對比結(jié)果。

值得注意的是，圖2(a)中，基于4核和8核運(yùn)行的并行協(xié)同進(jìn)化算法(DECC-DG-Parallel-4和DECC-DG-Parallel-8)分別在50和100代后在圖中沒有了顯示結(jié)果，這是因?yàn)镈ECC-DG-Parallel-4和DECC-DG-Parallel-8分別在50和100代后得到了該函數(shù)的最優(yōu)值——0。從該圖可以得出以下結(jié)論：

(1)當(dāng)函數(shù)的分組數(shù)大于最大核數(shù)64時，隨著核數(shù)的增加，在大部分函數(shù)上，DECC-DG-Parallel的表現(xiàn)越來越差。

比如在F1,F6,F7,F13,F18,F20等函數(shù)上，DECC-DG-Parallel-4表現(xiàn)最好，但是隨著核數(shù)的增加，DECC-DG-Parallel表現(xiàn)越來越差，當(dāng)核數(shù)增加到64時，DECC-DG-Parallel表現(xiàn)最差。這是因?yàn)楹藬?shù)的增加，使得每個子進(jìn)程負(fù)責(zé)的分組數(shù)減少，從而使得子進(jìn)程內(nèi)部的同步通信減少，也就意味著并行間的異步通信程度變大。過度的異步通信，使得算法的收斂速度變慢，從而使得算法的性能下降。

(2)除了F2外，并行協(xié)同進(jìn)化算法幾乎在所有的函數(shù)上都明顯好于串行協(xié)同進(jìn)化算法。

具體來說，在不同核數(shù)下的DECC-DG-Parallel都明顯優(yōu)于DECC-DG-Single，特別在F1,F3,F5,F6,F8-F11,F14等函數(shù)上，DECC-DG-Parallel大大優(yōu)于DECC-DG-Single，而且在F1上，DECC-DG-Parallel-4 和DECC-DG-Parallel-8都能夠優(yōu)化到函數(shù)的最優(yōu)值——0。這也就意味著并行協(xié)同進(jìn)化算法的異步通信策略大大優(yōu)于串行協(xié)同進(jìn)化算法的同步通信策略。這是因?yàn)橥酵ㄐ挪呗酝澬?，容易使得算法陷入局部最?yōu)。

(3)DECC-DG-Parallel-4在大部分函數(shù)上表現(xiàn)最好。

具體說來，DECC-DG-Parallel-4在F1,F4,F7,F8,F12-F14,F16-F18,F20函數(shù)上表現(xiàn)得明顯比其他任何核數(shù)下的DECC-DG-Parallel和DECC-DG-Single都要好。從收斂速度方面來看，與DECC-DG-Single相比較，在不損失所得解的質(zhì)量甚至獲得更高質(zhì)量解的前提下，DECC-DG-Parallel幾乎在所有的函數(shù)上獲得更快的收斂速度。

(4)在F8,F14-F17上，DECC-DG-Parallel-32，DECC-DG-Parallel-48和DECC-DG-Parallel-64得到相同的效果。

在F19上幾乎所有核數(shù)下的DECC-DG-Parallel都獲得了相同的表現(xiàn)。這是因?yàn)樵贔8,F14-F17上，當(dāng)核數(shù)大于等于32時，此時的核數(shù)超過了函數(shù)的最大分組數(shù)，因此只有等于最大分組數(shù)的進(jìn)程才真正起進(jìn)化子種群，并且這些進(jìn)程都只優(yōu)化一個函數(shù)分組，而其他進(jìn)程則空閑。在F19上，由于只有一個分組，因此在該函數(shù)下只有兩個進(jìn)程起作用，一個是主進(jìn)程，一個是子進(jìn)程，并且該子進(jìn)程負(fù)責(zé)優(yōu)化整個函數(shù)(因?yàn)樵摵瘮?shù)只有一個分組)。因此，可以得出并行協(xié)同進(jìn)化算法大大優(yōu)于串行協(xié)同進(jìn)化算法，也證明了對于協(xié)同進(jìn)化算法，并行環(huán)境下的異步通信策略大大優(yōu)于串行環(huán)境下的同步通信策略。但是這種異步通信并不是異步程度越高越好。過度的異步通信使得算法收斂速度變慢，算法的性能下降。

圖2 DECC-DG的串行實(shí)現(xiàn)(DECC-DG-Single)和并行實(shí)現(xiàn)(DECC-DG-Parallel)之間的對比結(jié)果

以上通過實(shí)驗(yàn)驗(yàn)證了并行協(xié)同進(jìn)化算法在解的質(zhì)量方面大大優(yōu)于串行協(xié)同進(jìn)化算法。為進(jìn)一步體現(xiàn)并行協(xié)同進(jìn)化算法的優(yōu)勢，本文將從算法運(yùn)行時間方面來驗(yàn)證并行協(xié)同進(jìn)化算法的優(yōu)勢。對于并行算法，研究者們往往關(guān)心并行算法相對于串行算法的加速比，其定義如下：

(1)

其中，TSingle是串行算法的運(yùn)行時間，TParallel是并行算法的運(yùn)行時間。圖3展示了DECC-DG-Parallel相對于DECC-DG-Single的加速比隨著核數(shù)增加的變化情況。

從該圖可知：當(dāng)函數(shù)的分組數(shù)大于最大核數(shù)(64)時，比如F1-F3,F9-F12，隨著核數(shù)的增加，并行算法的加速比也在增加，而且這種增加接近線性。雖然核數(shù)是呈指數(shù)增加，但是并行算法的加速比往往不會呈指數(shù)增加，而是呈接近線性增加，這是因?yàn)椴⑿兴惴ㄖ械母鱾€子進(jìn)程需要通信，需要消耗一定時間，另外，主進(jìn)程在收集子進(jìn)程發(fā)送的信息時需要一定的等待時間。

圖3 不同核數(shù)對并行協(xié)同進(jìn)化算法加速比的影響

對于F8,F14-F17，當(dāng)核數(shù)超過32時，加速比不再增加，這是因?yàn)檫@些函數(shù)的最大組數(shù)都少于32，當(dāng)核數(shù)超過32時，只有等于組數(shù)個數(shù)的進(jìn)程在工作，而其他進(jìn)程則處于空閑狀態(tài)。因此，此時并行算法的時間不會再有縮短，從而導(dǎo)致并行算法的加速比保持不變。對于F19，發(fā)現(xiàn)在該函數(shù)上并行算法的加速比呈下降趨勢，但是這種下降不是很多，只是降低了少許。這是因?yàn)镕19只有一個分組，當(dāng)創(chuàng)建大量進(jìn)程時，實(shí)際上只有兩個進(jìn)程在工作——一個主進(jìn)程，一個子進(jìn)程。

5 結(jié) 論

本文提出了一種求解NP-難問題的并行協(xié)同大規(guī)模差分進(jìn)化算法，從而將高維度優(yōu)化問題降解為多個低維度的子問題，進(jìn)而能夠獲得更加準(zhǔn)確的分組；其次，針對獲得的維度分組，獨(dú)立優(yōu)化每個子問題。求解NP-難問題的并行協(xié)同大規(guī)模差分進(jìn)化算法有以下優(yōu)點(diǎn)：(1)通信量小。種群式并行方式需要傳遞一個或者多個個體給節(jié)點(diǎn)，而維度分塊式并行只需要傳遞維度分塊信息給每個節(jié)點(diǎn)，因此通信信息遠(yuǎn)遠(yuǎn)小于種群式并行；(2)并行粒度大，可擴(kuò)展性強(qiáng)。維度分塊式并行方式取決于維度，與優(yōu)化問題直接相關(guān)，隨著維度的增加，維度分塊越多，并行粒度也就相對較大；而種群式并行方式跟種群相關(guān)，該方式下的并行粒度最多與種群大小相同。

最后，通過大量實(shí)驗(yàn)論證了并行協(xié)同進(jìn)化算法大優(yōu)于串行協(xié)同進(jìn)化算法。結(jié)果表明，隨著核數(shù)的增加，并行協(xié)同進(jìn)化算法的加速呈近線性增加，而其獲得的解的質(zhì)量卻在下降。說明加速比的提高與解的質(zhì)量提高存在著沖突。因此，為了使并行協(xié)同進(jìn)化算法的性能最大化，應(yīng)該在加速比和解的質(zhì)量之間尋求一個最佳平衡。