《中國人工智能學會通訊》——8.30 并行與分布式進化分布方式

目前的并行與分布式進化分布方式主要有種群式分布和次元分塊式分布兩種。

種群式分布

種群式分布是目前并行與分布式算法主要采用的分布方式[41-44,50-52,74-79] 。該分布方式将進化算法的種群分為若幹個小種群（甚至将單獨個體視為一個小種群）；而後根據并行與分布式進化算法選用的分布式模型，将每個小種群配置設定給一個節點。每個節點負責更新所配置設定的種群，并與相關節點通信，交換資訊。

在種群式分布方式中，每個個體是完整的，即包含所有次元的資訊。每個節點在優化過程中，搜尋的仍然是優化問題的整個解空間。因而，面對高次元優化問題，該分布方式面臨着以下挑戰。

（1） 收斂速度過慢。随着優化問題次元的增長，問題的解空間往往呈指數式增長。由于每個節點的搜尋空間仍然是優化問題的整個解空間，是以，并行與分布式進化算法即使采用每個節點維護一個種群的政策，也面臨着收斂速度過慢的問題。

（2）容易陷入局部最優。随着次元的增加，優化問題解空間中的局部最優值的個數往往也呈指數式增加。由于每個節點的搜尋空間不變，仍為整個解空間，是以每個節點陷入局部最優的機率相同，當大部分甚至全部節點陷入局部最優時，就很容易導緻并行與分布式進化算法陷入局部最優。

次元分塊式分布方式

為了突破種群式分布方式的局限性，研究者們最近提出了次元分塊式分布方式。該方式主 要 利 用 了 協 同 進 化 算 法（CC，CooperativeCoevolution）的思想[80] 。協同進化算法是一種分治算法，它将一個高次元的問題降解為多個低次元子問題，而後每個子問題視為獨立問題單獨優化，其主要架構如圖 5 所示。從圖中可以看出，CC 算法主要由次元分組和協同進化兩部分組成。

CC 算法假設每個子問題互相獨立，是以這些子問題便可以獨立優化，分别獲得對應子空間的最優解；而後将各個子空間的最優解拼湊在一起，便可以得到優化問題完整的全局最優解。顯然地，對于 CC 算法而言，算法的核心在于如何将高次元優化問題降解為獨立不相關的子問題。理想情況下，一個好的降解算法應該将相關變量放在相同組，将不相關變量放在不同組，而後每組變量視為一個獨立子問題。為此，在串行 CC 算法研究中，學者們提出了許多降解算法（DecompositionAlgorithms）。目前的降解算法大緻分為動态降解算法[81-87]和固定降解算法[88-90] 兩類。

• 動态降解算法将變量之間的相關性視為動态屬性，在進化過程中動态執行，是以每次算法分組得到的結果可能不同。最簡單的動态分組算法是文獻 [82] 提出的随機分組算法。該算法在每次疊代優化前随機地将優化問題的次元分解為大小相同的若幹組。為了提高将兩個相關變量放入同一組的機率，文獻 [83-84] 提出了動态調節分組個數的随機分組算法。進一步地，為了更好地劃分分組，文獻[85-86,91]在每次進化前根據曆史進化資訊對次元進行分組。

• 固定降解算法将變量之間的相關性視為靜态屬性，其一般先于協同進化操作執行，一旦分組确定之後，在整個協同進化過程中，分組資訊将保持不變。目前，最典型的固定分組算法是文獻 [88] 提 出 的 差 分 分 組 算 法（DG，DifferentialGrouping）。該算法通過兩兩變量之間的偏差分資訊來檢測變量的相關性。一旦變量的相關性确定之後，分組算法便根據相關性資訊将變量分為不同的組，而後在協同進化過程中變量分組保持不變。DG隻能檢測變量間的直接相關性，而無法檢測變量間接相關性。為克服該缺點，文獻 [89-90] 擴充了 DG算 法， 分 别 提 出 了 XDG（Extended DifferentialGrouping） 和 GDG（Global DifferentialGrouping）算法，能夠同時檢測變量之間的直接相關性和間接相關性。

至于 CC 算法的第二個操作——協同進化，每個子問題被視為獨立問題單獨優化。具體地，針對每個子問題，進化算法維持一個種群優化該子問題。然而由于評估個體時，需要所有次元的資訊，是以在優化過程中子問題與子問題之間需要交換資訊，評估種群适應值，進而篩選個體。在目前的串行 CC 算法中，每個子問題優化過程中，除該子問題對應的次元外，其他次元的值都固定為全局最優解對應的次元值。

基于以上資訊，可以看出，基于動态分組的CC 算法不适合用于并行與分布式進化算法，這是因為分組資訊在進化過程中動态變化，因而導緻并行模型的節點之間需要互相交換種群資訊，以此才能根據上一代種群資訊生成下一代個體。這種通信勢必導緻并行模型的通信量和通信時間大大增加，不利于并行與分布式進化算法的性能提升。是以，基于次元分塊式的并行分布式進化算法主要采用固定分組算法。

結合島嶼式分布式模型，文獻 [42,92] 提出了并行與分布式協同進化算法。該算法将每個變量單獨成組，視為獨立子問題，而後島嶼式模型中的每個節點負責一個子問題的優化。每個節點優化過程中，将其他節點所對應的次元資訊固定；所有節點進化完成後，每個節點将優化得到的最優解發送給其他節點。

綜上所述，可以看出次元分塊式分布式方式具有以下三個特點。

（1）擴充性強。該分布方式通過對次元分塊，将高維優化問題降解為低維優化問題。是以，理論上該分布方式可以處理任意次元的優化問題。

（2）收斂速度快。該分布方式将優化問題分解為低維優化問題；相應地，優化問題的解空間也被劃分為多個低維的子空間。是以，在優化每個子問題時，每個節點所負責優化的種群都能快速地收斂到所對應子空間的最優解。

（3）對分組算法的依賴性強。由于每個子問題獨立優化，分組算法的好壞直接影響着協同進化算法的性能。是以，該分布方式下的并行與分布式進化算法對分組算法有着比較強的依賴性。