一種求解NP-難問題的并行協同大規模差分進化算法

張 峰

安徽交通職業技術學院航海系,合肥,230051

1 引言

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

隨著NP-難問題規模的增大，數據維度的劇增，使得待優化問題的維度越來越高，優化算法的搜索空間呈指數式增長，大大降低了傳統優化算法的搜索效率[2]。另外，數據量的激增使得待優化問題的復雜度越來越大，大大增加了優化算法的執行時間，雖然可以通過計算機窮舉算法來解決這種問題，然而當問題的規模逐漸擴大時，這些算法也逐漸失效，因為這些實際問題本身就是一種NP-難問題，當問題規模變大時，計算機窮舉算法很難在人們可接受的時間范圍內給出一個可靠或者理想解。

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

2 相關研究綜述

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

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

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

3 求解NP-難問題的差分進化與大規模優化算法

3.1 差分進化算法

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

3.2 大規模優化算法

3.2.1 整體式進化算法

傳統進化算法在求解高維優化問題時失效的原因是難以在探索能力和開發能力中尋求一個好的平衡點。一個進化算法的多樣性往往取決于所使用的學習策略或者更新策略。因此，為了更好地求解高維度優化問題，提出了許多新的學習機制或者更新策略。

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

3.2.2 協同進化算法

協同進化算法是由Potter教授在1997年提出[14]，基于分治算法，將大規模問題通過維度分解的方法分為許多維度小的小規模問題，再對每個小問題使用傳統進化算法單獨進化，進化完成后，將各個子問題優化得到的最優解結合起來，即得到原問題。

3.2.3 維度分組策略

目前的維度分組算法主要分為兩大類：動態分組和固定分組。動態分組是一個動態過程，最基礎而且最簡單的動態分組算法就是隨機分組。固定組數的隨機分組雖然組數是固定的，但每個組的組成成分卻是不固定的。固定組數的隨機分組最大的缺點是需要提前設置好分組數[15,16]。

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

4 基于維度分組的并行協同大規模差分進化算法

為了提高并行進化算法的運行效率，本文依托新提出的維度分組策略提出了基于維度分組的并行進化算法——并行協同進化算法。不同于傳統的協同進化算法順序優化子問題，在該算法中，每個維度分組視為獨立子問題，而后算法同時優化每個子問題。

4.1 算法的基本設計

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

圖1 基于維度分組的并行協同進化算法框架

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

在并行算法中，主要的時間耗費應該集中于子問題的不斷優化，所以好的并行算法應該盡量減少通信時間的開銷。因此采用改進的差分分組算法可以大大減少通信開銷，提高了并行算法的執行效率。

4.2 并行差分進化算法的實現

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

算法:并行差分進化算法

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

1:將0號進程設為主進程，其余(n-1)個進程設為從進程，負責優化每個分組；

2:每個從進程負責優化的分組個數L=m/n;

3:If(m%n≠ 0)

4:前m%n個從進程負責的分組數為L=L+1；

5:End If;

6:主進程初始化gbest;

7:每個從進程初始化自己的種群;

8:iter= 0;

9While(outer_iter

10:主進程廣播gbest到每個子進程；

11:Fori= 1:n

12：Forj= 1:L

13：While(inner_iter

14:第i個子進程優化所負責的第j個分組；

15：inner_iter++;

16:End While

17:End For

18:第i個子進程發送優化好的所負責的所有分組的gbest；

19:End For

20:主進程接收每個子進程發送的gbest，并拼接為新的new_gbest

21:If(f(new_gbest)

22:gbest=new_gbest;

23:End If;

24:outer_iter++;

25:End While;

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

本文提出的算法需要的通信時間較少。這是因為在早期的并行算法中，主進程必須將一個或者多個個體信息傳遞給子進程，而后子進程負責計算適應值。而本文中的并行算法中，主進程只需要將gbest傳遞給各個子進程，同時每個子進程只需傳遞各自優化得到的gbest的部分給主進程，因此本文提出的并行算法所需要的通信量大大減少。

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

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

4.3 實驗結果

4.3.1 實驗環境設計

本研究首先實現了基于改進同進化算法應用在當今比較流行而且被人們廣泛使用的大規模優化基準函數庫——CEC’2010基準函數庫。該函數庫包含20個1 000維的大規模優化問題。這20個函數的主要特點如表1所示。

表1 20個CEC’2010函數的主要特性

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

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

4.3.2 結果分析

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

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

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

比如在F1,F6,F7,F13,F18,F20等函數上，DECC-DG-Parallel-4表現最好，但是隨著核數的增加，DECC-DG-Parallel表現越來越差，當核數增加到64時，DECC-DG-Parallel表現最差。這是因為核數的增加，使得每個子進程負責的分組數減少，從而使得子進程內部的同步通信減少，也就意味著并行間的異步通信程度變大。過度的異步通信，使得算法的收斂速度變慢，從而使得算法的性能下降。

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

具體來說，在不同核數下的DECC-DG-Parallel都明顯優于DECC-DG-Single，特別在F1,F3,F5,F6,F8-F11,F14等函數上，DECC-DG-Parallel大大優于DECC-DG-Single，而且在F1上，DECC-DG-Parallel-4 和DECC-DG-Parallel-8都能夠優化到函數的最優值——0。這也就意味著并行協同進化算法的異步通信策略大大優于串行協同進化算法的同步通信策略。這是因為同步通信策略往往太貪心，容易使得算法陷入局部最優。

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

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

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

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

圖2 DECC-DG的串行實現(DECC-DG-Single)和并行實現(DECC-DG-Parallel)之間的對比結果

以上通過實驗驗證了并行協同進化算法在解的質量方面大大優于串行協同進化算法。為進一步體現并行協同進化算法的優勢，本文將從算法運行時間方面來驗證并行協同進化算法的優勢。對于并行算法，研究者們往往關心并行算法相對于串行算法的加速比，其定義如下：

(1)

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

從該圖可知：當函數的分組數大于最大核數(64)時，比如F1-F3,F9-F12，隨著核數的增加，并行算法的加速比也在增加，而且這種增加接近線性。雖然核數是呈指數增加，但是并行算法的加速比往往不會呈指數增加，而是呈接近線性增加，這是因為并行算法中的各個子進程需要通信，需要消耗一定時間，另外，主進程在收集子進程發送的信息時需要一定的等待時間。

圖3 不同核數對并行協同進化算法加速比的影響

對于F8,F14-F17，當核數超過32時，加速比不再增加，這是因為這些函數的最大組數都少于32，當核數超過32時，只有等于組數個數的進程在工作，而其他進程則處于空閑狀態。因此，此時并行算法的時間不會再有縮短，從而導致并行算法的加速比保持不變。對于F19，發現在該函數上并行算法的加速比呈下降趨勢，但是這種下降不是很多，只是降低了少許。這是因為F19只有一個分組，當創建大量進程時，實際上只有兩個進程在工作——一個主進程，一個子進程。

5 結 論

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

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