演化信息協助的動態協同隨機漂移粒子群優化算法

趙 吉，程 成

（1.無錫環境科學與工程研究中心，江蘇無錫 214153；2.江南大學物聯網工程學院，江蘇無錫 214122；3.中國船舶科學研究中心，江蘇無錫 214082）

（?通信作者電子郵箱queenji97@hotmail.com）

0 引言

隨著科學技術的發展，許多現實世界中的優化問題變得越來越復雜，迫切需要更好、更有效的優化算法。粒子群優化（Particle Swarm Optimization，PSO）算法［1］自1995 年首次提出以來，學者們對提高其性能進行了許多嘗試［2］。然而，就PSO本身而言，它并不是一種全局優化算法［3］。為此，Sun 等［4］根據外部電場中金屬導體的自由電子模型［5］提出了一種新的隨機漂移粒子群優化（Random Drift PSO，RDPSO）算法，并且能更加高效地估計復雜生化動力系統的參數。RDPSO 能保持群體的多樣性，利用平均位置的等待機制提高粒子的全局搜索能力，比PSO 和遺傳算法（Genetic Algorithm，GA）具有更好的性能［6］。RDPSO 算法也可以用作數據挖掘中的優化問題的通用工具，例如聚類、分類、回歸等，其廣泛存在于現實世界的優化問題［7-8］中。

與其他進化算法一樣，RDPSO 算法也面臨著早熟收斂和陷入局部最優的問題，導致性能損失和次優解。非重復訪問策略與智能進化算法相結合［9-14］，通過使用二維空間分割樹避免估計候選解被重復訪問，引導算法搜索方向趨于有希望的搜索區域，從而提升搜索能力以提高算法的性能。文獻［14］提出了基于搜索歷史信息的非重復訪問量子行為粒子群優化（Non-revisited Quantum-behaved PSO，NrQPSO）算法，利用搜索歷史記錄訪問過的解位置，有效提高算法性能。但是其變異方式采用了簡單的單粒子隨機翻轉變異，沒有充分利用群體中粒子間的信息傳遞。同時NrQPSO 需要設置參數閾值e，該值是個經驗值，對解的影響很大，需要多次調試才能達到最優值，因此算法性能對該值的依賴度較大，不具備普遍性。為了進一步提高RDPSO 算法在復雜優化問題中的性能，提高粒子的多樣性，本文提出演化信息協助的動態協同隨機漂移粒子群優化（Cooperative RDPSO，CRDPSO）算法，粒子動態地進行協同合作，通過演化過程中的信息協助同時記錄訪問過的解位置和適應度值，避免算法重復訪問，增強自適應變異從而顯著提高收斂精度和速度。

1 隨機漂移粒子群優化算法

給定一個最小優化問題：

其中F(X)是一個在連續可行空間S 中的適應度函數（或目標函數）。假設在具有m個粒子的群優化算法中，每個個體都被視為D 維空間中的無體積粒子，第k 代第i 個粒子的位置向量和速度向量分別表示為：以及粒子的個體最優位置（personal best，pbest）（給出最佳目標函數值或適應值的位置）。群體有一個稱為全局最佳（global best，gbest）位置的向量它定義為種群中所有粒子中最佳粒子的位置。根據式（1）分別按式（2）和式（3）計算：

軌跡分析［15］表明，假設每個粒子都收斂到其局部吸引子，粒子群優化算法的收斂性是可以實現的。在PSO 算法中，粒子向個體最優位置的方向運動類似于外部電場中金屬導體內電子的漂移運動。然而，根據自由電子模型［5］，除了電場引起的定向運動外，電子還處于隨機性的熱運動中。電子運動的總體效應是電子傾向最小勢能的位置。因此，如果把電子的位置作為問題的候選解，勢能函數作為問題的目標函數，電子的運動顯然與求最小解的過程非常相似。受此啟發，假設PSO 中的粒子像是在外部電場中金屬導體內移動的電子，粒子的運動是熱運動和指向粒子個體最優值方向運動的疊加。因此，粒子的速度可以表示為：其 中分別表示熱運動和定向運動的速度。基于這樣的假設，文獻［4］提出了下列RDPSO粒子更新方程：

2 演化信息協助的CRDPSO算法

2.1 動態協同機制

對于高維問題，包含隨機算法（如隨機漂移粒子群算法和遺傳算法等）在內的搜索算法都存在尺度規模的“維數災難”問題。協同機制的重要性在于，它能使粒子群中粒子“好”的維度信息得以保留，并能防止丟棄潛在的有用信息。粒子的每個維度通過執行協同操作，可以分別評估每個維度的優劣，并保存最有用的信息加速收斂。協同進化機制可以提高算法在高維問題中的性能［17-18］。在進化的每次迭代中，每個粒子都會動態地連續更新一個上下文粒子向量，以便在協同合作過程的每個連續階段獲得新的信息。為了減少每個維度替換的適應度函數計算量，通過選擇最優粒子向量并與其他粒子協作。改進的動態協同進化方式，進一步提高動態協作性能。在進化過程中，每個粒子xi通過進化公式產生5個進化的粒子｛xi_1，xi_2，…，xi_5｝。因此，連同xi共得到6個個體，根據式（1）分別計算其適應度值，在6 個個體中選擇最佳個體xi_b；然后將xi_b指定為粒子xi的當前較優局部上下文粒子向量，隨后將xi_b與其余5 個個體進行協同進化。對于xi_b向量的每個維度，分別用其他5 個個體的對應維度替換，并測試替換維度是否提高了適應度值。如果是，則采用替換值，并使用結果向量替換上下文粒子向量。重復此過程，直到所有5 個測量向量的所有維度都得到評估，并選擇最佳排列以形成新一代的粒子。動態協同進化機制的過程算法描述如下。

步驟1 對于當前粒子xi根據RDPSO 進化式（4）、（5）、（8）進化產生5個子代粒子｛xi_1，xi_2，…，xi_5｝。

步驟2 從｛xi，xi_1，xi_2，…，xi_5｝中選取最優的粒子作為動態協作的上下文粒子向量xi_b。

步驟3 對于剩下的5個粒子，分別對每個粒子的每一個維度用xi_b的相應維度替換，同時根據式（1）計算適應度值，如果替換后的粒子適應度值優于F（xi_b）則保留相應維度，否則保留原有維度值。

步驟4 直到所有剩余5 個粒子都和上下文粒子向量比較完，保留具有最優適應度值的粒子作為本次粒子進化的子代粒子。

步驟5 返回步驟1 直到粒子群所有粒子都進行了動態協同進化后產生新的子代粒子群。

2.2 基于演化信息的自適應變異

CRDPSO 使用二維空間分割（Binary Space Partitioning，BSP）樹作為演化歷史信息的存儲方式，其記錄了每個粒子的位置和適應度值｛［xi，F（xi）］｝，根據｛xi｝的分布將整個搜索空間S 進行劃分。最初，CRDPSO 中的BSP 樹T 僅包含根節點。樹的每個節點記錄了RDPSO 先前訪問的不同解xi。同時，它還記錄了搜索空間的子區域Si。節點使用歐幾里得度量來對搜索空間進行二維分割。兩個子節點a 和b 子節點沿著第k維將父節點的子區域線性分割為兩個重疊的子區域，k的選取滿足a 和b 在k 維上的距離最大，即arg max|a(k) -b(k)|。假設｛x1，x2，x3，x4，x5｝是二維搜索空間內的估計解，它們在二維平面空間的分布如圖1（b）所示。記錄估計解的BSP樹結構如圖1（a）所示，BSP 樹根據估計解將二維搜索空間劃分為多個小區域，如圖1（b）的虛線區域所示，每個區域對應于現有的解。每個樹節點包含其關聯解的各種搜索演化信息（包括搜索空間中的解位置、適應度值等）及其在搜索空間分配的子區域。以這種方式，RDPSO 生成的每個歷史解被記錄在樹的節點中，并且BSP樹用作查詢xi子區域的有效數據結構［11］。

圖1 BSP樹結構實例Fig.1 Example of BSP tree structure

因為BSP 樹同時記錄了所有解的適應度值F（xi），該記錄可以看作適應度值F（x）的近似值如果解xk的子區域是Sk，一個候選解x 在子區域Sk內，那么解x 的適應度值可以近似為xk的適應度值，即通過標準樹節點插入操作來實現，其近似誤差隨著BSP 樹中一個一個記錄的解數量增加而單調減小。本文采用的基于梯度下降式的變異方式是一種自適應的、無參數和引導的變異操作。其基于整個搜索歷史自適應地調整變異步長，其搜索方向由近似適應度值控制，而不是像單粒子隨機翻轉突變那樣隨機。假設X 和Y 分別是節點x和y的子區域，如果X?Y，則Y 是X 的鄰居。與X 相關的Y 的鄰居數量為節點x 和y 的深度差。因此，首先找到子區域X 的最優值，即節點x 的適應度值是其子區域鄰居中最佳值，那么其所在子區域可以看作是其鄰居子區域的最優子區域。引導自適應變異被定義為指向其最近的最優子區域方向，其變異方向就是向著離近似適應值F?(x)局部增長最大的方向移動。設置一個變異方向變量W作為指向x 的最近歷史最優y 的方向，即W=y -x。近似適應度值被看作一個階躍函數，因此其最優值的形式是一個D 維子區域而不是一個點。因為BSP樹記錄適應度值的拓撲結構代表了子區域之間的鄰接關系，因此找到離x 最近的最優值相當于在中尋找x的最近最優子區域。為了平衡梯度下降方向分配的搜索效果，引入區間（0，1）內的隨機值作為變異步長α。因此x變異公式為：

如果x 就是局部最優，即x=y，那么將從x 的子區域中隨機選擇一個突變體xm。圖2 顯示了自適應變異的示例，搜索空間S 和個體序列（即BSP 樹）空間分割和圖1 一樣。假設x是要變異的個體，相應的變異從搜索x 子區域開始，在實際編程中是從根節點開始。假設搜索終止于節點x5，S2是x的子區域，然后計算S2到所有最優子區域的距離，其最近的最優子區域是S5。因此，x 的變異范圍是位于x 和x5之間直線上的一個點。變異操作步驟如下：

步驟1 搜索待變異粒子x的子區域s ?S。

步驟2 找到子區域s的最近最優子區域。

步驟3 y是子區域s中的估計解。

步驟4 如果x=y，x 在子區域內進行隨機變異，xm=Random（s）；否則xm=(1-α)x+αy（變異步長在自適應調整范圍內隨機分配，α=Random(0，1)。

圖2 自適應變異（x和x5之間的直線是x變異的可能范圍）Fig.2 Adaptive mutation（straight line between x and x5 is the range of possible mutation range of x）

2.3 演化信息協助的動態協同隨機漂移粒子群優化算法

本文提出的CRDPSO 可以看作是RDPSO 算法模塊和自適應變異模塊的結合體，其中算法模塊包含了動態協同進化的隨機漂移粒子群優化算法，而自適應模塊則是由歷史信息記錄和隨機梯度下降式自變異操作組成，如圖3 所示。對于一個D 維搜索空間S?RD，算法中的單個粒子x 是一個1×D 的實值向量，即x ∈RD。算法通過4 個主要步驟來搜索最優值，即種群初始化、搜索、變異和進化，其重點是通過演化歷史信息，動態協同進化的自適應變異來增強種群多樣性。CRDPSO 從初始化粒子群P=｛xi｝開始，同時BSP 樹初始化為只包含根節點的樹T，記錄每個粒子的位置和適應度值。之后，粒子群經過自適應變異操作產生粒子群。隨后根據動態協同機制，選擇最好的置換粒子形成子代粒子群。產生新的粒子群子代后需要重新計算粒子的適應度值并連同位置一起插入樹T中，重復算法直到迭代次數超過預定值為止。

圖3 顯示了CPDRSO 算法的流程，數字表示CPDRSO 迭代中的步驟順序。

圖3 CRDPSO算法流程Fig.3 Flowchart of CRDPSO algorithm

3 測試及結果

3.1 測試函數

本文采用一組標準測試函數包括多峰或單峰基準函數F=｛f1（x），f2（x），…，f10（x）｝［19-20］來測試所提出的算法并驗證其性能，表1中顯示了10個測試函數，所有的仿真研究都是在Matlab中進行的。

表1 測試函數Tab.1 Test functions

3.2 算法設置

除了RDPSO 和CRDPSO 算法，差分進化算法（Differential Evolution，DE）［21］、協方差矩陣適應進化策略算法（Covariance Matrix Adaptation Evolutionary Strategy，CMA-ES）［22］、非重復訪問遺傳算法（Continuous Non-revisiting Genetic Algorithm，cNrGA）［11］和三種版本的QPSO，即CCQPSO（Cooperative Quantum-behaved PSO）［18］、CLQPSO（Comprehensive Learning Quantum-behaved PSO）［23］和NrQPSO［14］也通過測試函數進行性能比較。在實驗中，CRDPSO 和RDPSO 的參數設置與文獻［4］中推薦的參數相同。對于CLQPSO，β 從1 線性下降到0.5，其他因子設置同文獻［23］；NrQPSO設置同文獻［14］。對于cNrGA，交叉速率是均勻交叉，設置為rx=0.5。對于所有比較的算法，群體大小設置為100，最大迭代次數設置為2 000。所有測試函數的維數設置為D=30。每種算法在實驗中獨立運行30 次，測試結果取值為30 次獨立實驗獲得最優解的最好，最差和平均值以及標準偏差。

3.3 結果分析

對于所有測試函數，表2 中列出了每種算法30 次獨立運行2 000 次迭代的統計值，其中“Best”“Worst”和“Ave.”，分別代表30 次獨立運行中獲得的最優解的最好值、最差值以及最優解的平均值，“Std.”代表獲得的最優解平均值的標準偏差。黑體字的值意味著對應算法對于特定測試函數是測試算法中最優的。從表2 可以清楚地看到，對于所有測試函數，本文提出的CRDPSO 算法性能都優于其他七種算法。雖然RDPSO和CCQPSO在f1、f2和f6上均表現了出色的性能，但CRDPSO算法在所有其他測試函數上均勝過它們。除f9以外，CRDPSO算法的標準偏差對于幾乎所有測試函數都是最優的。這表明CRDPSO 對于絕大多數測試函數都能獲得最優解，具有最好的算法穩定性。此外，詳細的仿真結果（“Best”“Worst”“Ave.”和“Std.”）表明，CRDPSO 的性能表現在十種測試情況下均排名第一。因此表2中列出的仿真結果表明，CRDPSO的整體性能優于其他比較的算法。通過使用演化信息機制，CRDPSO 可以確保搜索過程中的非重復訪問以及快速收斂到局部最優。同時，它利用自適應突變來指導粒子搜索更好的鄰域，進一步提高局部搜索能力，使得CRDPSO 算法可以獲得最好的平均最優值，并且也是最穩定的。

不同算法的收斂曲線如圖4所示。

圖4 不同算法的收斂曲線Fig.4 Convergence curves of different algorithms

表2 結果表明，對于f1、f2和f6，RDPSO、CRDPSO 和CCQPSO 算法最終都達到了最優值。然而，從圖4（a）、（b）、（f）的收斂曲線可以看出，CRDPSO 的收斂速度遠優于其他兩種算法，在不到200 次的搜索迭代中，它就已經能收斂到全局最優值。對于f3～f5和f7～f10，CRDPSO 的收斂速度和收斂精度也遠遠超過其他七種算法，在很短的迭代次數內就找到了每個測試函數的全局最優值。CRDPSO 算法能夠更快地搜索到最優值是因為粒子一旦利用整個演化歷史信息找到自己最近的最優鄰域子區域，就可以進行自適應變異；同時，利用動態協同機制保持最優信息，使算法能夠快速收斂到全局最優值。在圖4中，對于f1～f5和f8，CRDPSO已經達到Matlab能夠識別的0，并且0 的對數比例是負無窮大，因此適應度值不能再在圖中顯示。這很好地說明，對于這些測試函數，CRDPSO 獲得的目標函數值的仿真結果無限接近理論值，即0。對于圖4（g）中的f7，即使CRDPSO 算法已經趨于收斂，但在后期（即1 500次迭代后）還能夠進一步找到一個新的更好的解，這說明CRDPSO 算法在搜索過程的最后階段仍然具有更好的搜索能力，并且有很大的機會逃離局部最優解而得到更好的解。綜上所述，CRDPSO 算法與其他算法相比，具有最佳的收斂性能和優化精度。

為了確定除精度和收斂性外，CRDPSO 算法與其他七種算法之間的性能是否存在顯著差異，表3 列出了不同算法之間的顯著性水平為0.05的Wilcoxon秩和檢驗結果。從表3中可以看出，對于f1、f2和f6，CRDPSO，RDPSO 和CCQPSO 沒有顯著差異。然而，對于絕大多數測試函數，CRDPSO 算法可以得到h=1，這表明與其他算法相比，CRDPSO 的優化性能有了顯著提高。結果表明，無論是在單峰函數還是多峰函數中，CRDPSO 算法的最優性能都明顯較高，收斂更快、最優值精度更高。

表2 測試函數仿真結果Tab.2 Simulation results of test functions

進化算法運行時間主要耗費在生成解和適應度函數計算。不同算法采用不同的策略生成可能解，CRSPSO 的群體多樣性保持比較好，因此目標函數收斂較快，主要運算時間在于訪問BSP 樹（即搜索和插入節點）和動態協作的適應度計算。對比cNrGA 和NrQPSO，由于CRDPSO 還需要進行額外的動態協同計算，因此花費的時間也會相應增加，但是CRDPSO獲得的解精度比cNrGA 和NrQPSO 有大幅提高。CRDPSO 和CCQPSO算法都具備協同操作。CRDPSO每次迭代時，每個粒子都需要和動態上下文粒子向量進行對比獲取更好的適應度值從而增加了計算開銷。CRDPSO 又利用了搜索歷史信息，因此比CCQPSO 提高了整體收斂速度并進一步提高了準確度。總體而言，CRDPSO 算法增加時間和空間成本提升精確度和收斂度性能，這也充分符合了沒有免費午餐的理論。對于實際問題如表面配準、加熱優化設計和能源管理、通風和空調系統等，適應度函數評價需要比解生成耗費更多的時間。根據目前電腦硬件的發展，對于這類實際應用問題，CRDPSO所需要的額外時間開銷和建立BSP樹所需要的容量對于提高算法性能都是可以接受的，其綜合性能是可以適應的。

表3 Wilcoxon秩和檢驗結果Tab.3 Wilcoxon rank sum test results

4 結語

在RDPSO 算法中，早熟收斂和粒子多樣性是急需解決的兩個問題。為此，本文提出了演化信息協助的動態協同RDPSO 算法（CRDPSO），將動態協作機制與標準RDPSO 算法相結合。群體粒子之間的動態協作機制采用動態上下文粒子信息可以更好地利用任何新的信息，增強了群體的搜索能力，有助于防止算法的早熟收斂。該算法通過搜索歷史信息方案，利用二維空間分割（BSP）樹結構來存儲估計解的位置和適應度值。受益于空間劃分方案，使用的記錄樹結構獲得一種用于改進CRDPSO 中突變策略的快速適應度函數，由此產生無參數的自適應變異，從而提高了粒子的變異能力。與其他比較流行的搜索隨機算法相比，對于10 個標準測試函數上的實驗結果表明，該算法具有最好的全局尋優能力，并且收斂速度和精度都有所提高，證明了CRDPSO 的有效性和高效率。改進后的算法在理論上可以證明其優越性，但在實際問題中還需要進一步驗證。因此，將CRDPSO 算法應用于實際工程問題成為未來的研究重點。下一步研究工作是驗證CRDPSO算法在電力經濟調度、數據分析和生物路徑參數識別等工程應用中的性能。同時，為了進一步充分利用和挖掘有效歷史信息，歷史演化信息在粒子群搜索中的信息動態可視化也是今后的一個研究內容。