演化信息協(xié)助的動(dòng)態(tài)協(xié)同隨機(jī)漂移粒子群優(yōu)化算法

趙 吉，程 成

（1.無(wú)錫環(huán)境科學(xué)與工程研究中心，江蘇無(wú)錫 214153；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫 214122；3.中國(guó)船舶科學(xué)研究中心，江蘇無(wú)錫 214082）

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

0 引言

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

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

1 隨機(jī)漂移粒子群優(yōu)化算法

給定一個(gè)最小優(yōu)化問(wèn)題：

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

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

2 演化信息協(xié)助的CRDPSO算法

2.1 動(dòng)態(tài)協(xié)同機(jī)制

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

步驟1 對(duì)于當(dāng)前粒子xi根據(jù)RDPSO 進(jìn)化式（4）、（5）、（8）進(jìn)化產(chǎn)生5個(gè)子代粒子｛xi_1，xi_2，…，xi_5｝。

步驟2 從｛xi，xi_1，xi_2，…，xi_5｝中選取最優(yōu)的粒子作為動(dòng)態(tài)協(xié)作的上下文粒子向量xi_b。

步驟3 對(duì)于剩下的5個(gè)粒子，分別對(duì)每個(gè)粒子的每一個(gè)維度用xi_b的相應(yīng)維度替換，同時(shí)根據(jù)式（1）計(jì)算適應(yīng)度值，如果替換后的粒子適應(yīng)度值優(yōu)于F（xi_b）則保留相應(yīng)維度，否則保留原有維度值。

步驟4 直到所有剩余5 個(gè)粒子都和上下文粒子向量比較完，保留具有最優(yōu)適應(yīng)度值的粒子作為本次粒子進(jìn)化的子代粒子。

步驟5 返回步驟1 直到粒子群所有粒子都進(jìn)行了動(dòng)態(tài)協(xié)同進(jìn)化后產(chǎn)生新的子代粒子群。

2.2 基于演化信息的自適應(yīng)變異

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

圖1 BSP樹(shù)結(jié)構(gòu)實(shí)例Fig.1 Example of BSP tree structure

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

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

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

步驟2 找到子區(qū)域s的最近最優(yōu)子區(qū)域。

步驟3 y是子區(qū)域s中的估計(jì)解。

步驟4 如果x=y，x 在子區(qū)域內(nèi)進(jìn)行隨機(jī)變異，xm=Random（s）；否則xm=(1-α)x+αy（變異步長(zhǎng)在自適應(yīng)調(diào)整范圍內(nèi)隨機(jī)分配，α=Random(0，1)。

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

2.3 演化信息協(xié)助的動(dòng)態(tài)協(xié)同隨機(jī)漂移粒子群優(yōu)化算法

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

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

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

3 測(cè)試及結(jié)果

3.1 測(cè)試函數(shù)

本文采用一組標(biāo)準(zhǔn)測(cè)試函數(shù)包括多峰或單峰基準(zhǔn)函數(shù)F=｛f1（x），f2（x），…，f10（x）｝［19-20］來(lái)測(cè)試所提出的算法并驗(yàn)證其性能，表1中顯示了10個(gè)測(cè)試函數(shù)，所有的仿真研究都是在Matlab中進(jìn)行的。

表1 測(cè)試函數(shù)Tab.1 Test functions

3.2 算法設(shè)置

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

3.3 結(jié)果分析

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

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

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

表2 結(jié)果表明，對(duì)于f1、f2和f6，RDPSO、CRDPSO 和CCQPSO 算法最終都達(dá)到了最優(yōu)值。然而，從圖4（a）、（b）、（f）的收斂曲線可以看出，CRDPSO 的收斂速度遠(yuǎn)優(yōu)于其他兩種算法，在不到200 次的搜索迭代中，它就已經(jīng)能收斂到全局最優(yōu)值。對(duì)于f3～f5和f7～f10，CRDPSO 的收斂速度和收斂精度也遠(yuǎn)遠(yuǎn)超過(guò)其他七種算法，在很短的迭代次數(shù)內(nèi)就找到了每個(gè)測(cè)試函數(shù)的全局最優(yōu)值。CRDPSO 算法能夠更快地搜索到最優(yōu)值是因?yàn)榱Ｗ右坏├谜麄€(gè)演化歷史信息找到自己最近的最優(yōu)鄰域子區(qū)域，就可以進(jìn)行自適應(yīng)變異；同時(shí)，利用動(dòng)態(tài)協(xié)同機(jī)制保持最優(yōu)信息，使算法能夠快速收斂到全局最優(yōu)值。在圖4中，對(duì)于f1～f5和f8，CRDPSO已經(jīng)達(dá)到Matlab能夠識(shí)別的0，并且0 的對(duì)數(shù)比例是負(fù)無(wú)窮大，因此適應(yīng)度值不能再在圖中顯示。這很好地說(shuō)明，對(duì)于這些測(cè)試函數(shù)，CRDPSO 獲得的目標(biāo)函數(shù)值的仿真結(jié)果無(wú)限接近理論值，即0。對(duì)于圖4（g）中的f7，即使CRDPSO 算法已經(jīng)趨于收斂，但在后期（即1 500次迭代后）還能夠進(jìn)一步找到一個(gè)新的更好的解，這說(shuō)明CRDPSO 算法在搜索過(guò)程的最后階段仍然具有更好的搜索能力，并且有很大的機(jī)會(huì)逃離局部最優(yōu)解而得到更好的解。綜上所述，CRDPSO 算法與其他算法相比，具有最佳的收斂性能和優(yōu)化精度。

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

表2 測(cè)試函數(shù)仿真結(jié)果Tab.2 Simulation results of test functions

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

表3 Wilcoxon秩和檢驗(yàn)結(jié)果Tab.3 Wilcoxon rank sum test results

4 結(jié)語(yǔ)

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