基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法

1、第卷第期吉林大學(xué)學(xué)報(bào)（理學(xué)版）年月（） 基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法劉華鎣，王靜，許少華，孫毅（東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江大慶；吉林大學(xué)數(shù)學(xué)學(xué)院，長春）摘要：提出一種基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法，該算法采用網(wǎng)格擁擠距離與網(wǎng)格密度相結(jié)合的策略選取全局極值，能加速算法收斂，保持種群多樣性，在提高全局極值選取準(zhǔn)確度的同時(shí)使最終解保持了較好的分布性關(guān)鍵詞：多目標(biāo)優(yōu)化；粒子群算法；維空間劃分；空間劃分樹中圖分類號：文獻(xiàn)標(biāo)志碼：文章編號：（），（，；，）：，：；收稿日期：作者簡介：劉華鎣（），女，漢族，碩士，教授，從事群體智能優(yōu)化算法的研究，：基金項(xiàng)目：國家自然科學(xué)基金（批準(zhǔn)

2、號：）、中國石油科技創(chuàng)新基金（批準(zhǔn)號：）、黑龍江省自然科學(xué)基金（批準(zhǔn)號：）和黑龍江省科技攻關(guān)項(xiàng)目（批準(zhǔn)號：）粒子群優(yōu)化算法（）以其易于實(shí)現(xiàn)、參數(shù)設(shè)置較少等優(yōu)點(diǎn)，廣泛應(yīng)用于多目標(biāo)優(yōu)化和其他優(yōu)化問題中多目標(biāo)粒子群優(yōu)化算法（）主要分為聚集函數(shù)法、基于目標(biāo)函數(shù)排序法、子群法、基于支配法等，目前研究者主要集中于基于支配的多目標(biāo)粒子群優(yōu)化算法自從等首次提出用一個(gè)外部集保存每次迭代得到的非支配解后，大多數(shù)多目標(biāo)粒子群優(yōu)化算法都采用了外部存檔策略張利彪等的算法采用新的全局極值和個(gè)體極值選取方式，提高了算法的有效性；孫小強(qiáng)等采用聚類算法裁剪非支配解，提高了解的分布性但這些算法在收斂性和分布性方面，特別是解決高維

3、多目標(biāo)問題上仍需做進(jìn)一步改進(jìn)在多目標(biāo)條件下，可能存在很多彼此不受支配的全局最優(yōu)解，個(gè)體的密度信息是選取全局最優(yōu)解的主要因素之一典型的基于密度方法有非劣分層遺傳算法（）和近鄰密度估值法（），這兩種方法能對個(gè)體密度進(jìn)行準(zhǔn)確地估計(jì)，但其計(jì)算復(fù)雜度偏高算法和自適應(yīng)網(wǎng)格的多目標(biāo)粒子群算法（）使用存檔進(jìn)化策略（）中自適應(yīng)網(wǎng)格法維護(hù)外部集（，簡稱），用網(wǎng)格中的粒子數(shù)作為網(wǎng)格密度定義網(wǎng)格適應(yīng)度值，其網(wǎng)格密度計(jì)算性能較好，但其估值還存在一定誤差本文提出一種基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法（），用網(wǎng)格把目標(biāo)空間劃分為多個(gè)體積相等的單元格，用空間劃分樹建立非空單元格的索引，采用擁擠距離和網(wǎng)格密度相結(jié)合的策略選取

4、全局極值，進(jìn)一步提高了解集的分布性多目標(biāo)優(yōu)化問題及粒子群優(yōu)化算法多目標(biāo)優(yōu)化問題可以表示如下：（）（），（），（），（）（，），其中：決策向量；目標(biāo)向量；（）（，）是目標(biāo)函數(shù)；（）（，）是約束條件大多數(shù)情況下各目標(biāo)函數(shù)之間是相互沖突的，某目標(biāo)的改善可能引起其他目標(biāo)性能的降低，同時(shí)使多個(gè)目標(biāo)均達(dá)到最優(yōu)很難實(shí)現(xiàn)，只能在各目標(biāo)之間進(jìn)行協(xié)調(diào)權(quán)衡和折中處理，使所有目標(biāo)函數(shù)盡可能達(dá)到最優(yōu)不同于單目標(biāo)優(yōu)化，多目標(biāo)優(yōu)化中使用支配評價(jià)最優(yōu)解，相關(guān)概念如下：定義若（ ）（）（，），且 ，使得（）（），則稱解 支配，記作 定義若 ： ，則稱解 是最優(yōu)解或非支配解定義所有最優(yōu)解的集合 稱為最優(yōu)解集或非支配解集定義所有最

5、優(yōu)解對應(yīng)的目標(biāo)函數(shù)值所形成的區(qū)域（）（），（），（）稱為最優(yōu)前端標(biāo)準(zhǔn)粒子群優(yōu)化算法使用一群粒子表示特定問題的潛在解給定一個(gè)維搜索空間，第個(gè)粒子在時(shí)刻的位置為（），速度為（），它經(jīng)歷過的最好位置記為，整個(gè)粒子群經(jīng)歷過的最好位置記為算法通過不斷更新粒子速度與位置使粒子向最優(yōu)解飛行第個(gè)粒子的速度與位置更新公式如下：（）（）（）（），（）（）（）（），（）其中：為慣性權(quán)重；和為常數(shù)，稱為學(xué)習(xí)因子；和是，上的隨機(jī)數(shù)式（）中的（）為認(rèn)知部分，（）為社會部分，認(rèn)知部分和粒子的個(gè)體經(jīng)驗(yàn)相關(guān)，社會部分則表示粒子間的交互基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法外部集維護(hù)和全局最優(yōu)位置的選取是多目標(biāo)粒子群優(yōu)化算法的兩個(gè)

6、重要步驟維護(hù)外部集的主要目的是為群體的演化提供多樣化的全局最優(yōu)位置，而為每個(gè)粒子選擇適當(dāng)?shù)娜肿顑?yōu)位置能保持或進(jìn)一步增加外部集中解的多樣性，兩者相互配合，使算法獲得更多均勻分布在目標(biāo)空間上的非支配解，逼近最優(yōu)前端本文使用空間劃分樹對目標(biāo)空間進(jìn)行劃分外部集的空間劃分樹索引給定維目標(biāo)空間×××，其中為中第維的數(shù)據(jù)域定義將外部集所對應(yīng)的維目標(biāo)空間的每一維平均分為個(gè)相等的間隔段，則被劃分為個(gè)互不相交的超矩形單元，它們覆蓋整個(gè)維目標(biāo)空間每個(gè)單元的空間位置表示為（，），其中，對應(yīng)于第維的第個(gè)左閉右開的間隔段這個(gè)單元在劃分目標(biāo)空間的同時(shí)也劃分了外部集，稱為外部集的維空間劃分圖為

7、一個(gè)外部集對應(yīng)的維空間劃分結(jié)果每維劃分為個(gè)間隔段，編號為，外部集空間被劃分為個(gè)子空間其中（，），（，），（，），（，），（，），（，），（，）為非空單元第期劉華鎣，等：基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法在對外部集進(jìn)行劃分后，需要為其建立高效索引，以便對其進(jìn)行有效管理本文采用空間劃分樹索引外部集的維空間劃分由于維空間劃分的規(guī)模與為指數(shù)增長關(guān)系，為了以最小的代價(jià)存儲有效信息，空間劃分樹僅索引非空單元定義外部集在維空間劃分下的空間劃分樹（，簡稱）結(jié)構(gòu)定義如下：）它有一個(gè)根節(jié)點(diǎn)，共有層；）的第層對應(yīng)外部集的第維（，），第層存儲所有非空單元中的粒子數(shù)；）除了第層，第層（非葉節(jié)點(diǎn)層）包含形如（，）的節(jié)點(diǎn)

8、，其中表示該單元在第維上的間隔號，為指向下一層節(jié)點(diǎn)的指針，所指向節(jié)點(diǎn)包含與本單元對應(yīng)的下一維的所有相異非空單元；）第層節(jié)點(diǎn)指向葉節(jié)點(diǎn)：葉節(jié)點(diǎn)形如（，），其中為葉節(jié)點(diǎn)中包含的非支配解個(gè)數(shù)，為葉節(jié)點(diǎn)中保存的非支配解集；）從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑對應(yīng)一個(gè)非空單元圖為對圖中外部集的維空間劃分結(jié)果進(jìn)行索引建立的，該共層，第層有個(gè)節(jié)點(diǎn)，分別表示非空單元在維的間隔號例如根節(jié)點(diǎn)中的節(jié)點(diǎn)指向第層節(jié)點(diǎn)和節(jié)點(diǎn)，說明與維第個(gè)間隔號對應(yīng)的非空單元在維的間隔段編號分別為和葉節(jié)點(diǎn)存儲從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)經(jīng)過的路徑所對應(yīng)非空單元中的非支配解數(shù)目及非支配解如圖中第層最后一個(gè)節(jié)點(diǎn)表示非空單元（，）中有個(gè)非支配解和 圖外部集對應(yīng)的

9、維空間劃分示意圖 圖空間劃分樹非支配解的存儲非支配解的存儲過程即建立的過程，也即把非支配解插入的過程例如，把維目標(biāo)空間每維劃分為個(gè)相等的間隔段，非支配解 的插入過程即依次由 所在網(wǎng)格各維間隔段號（，）查找其存儲網(wǎng)格的過程其中（ ）（）×）（） （，），（）和（）分別為目標(biāo)函數(shù)的最大值和最小值全局極值的選取直接采用中方法計(jì)算擁擠距離的計(jì)算代價(jià)太高采用基于自適應(yīng)網(wǎng)格的方法直接根據(jù)網(wǎng)格密度決定全局極值的選取，可降低計(jì)算代價(jià)，但該方法未考慮相鄰網(wǎng)格對網(wǎng)格密度的影響如圖所示，若只考慮單個(gè)網(wǎng)格密度會得出（，）（，）的結(jié)論，但由于與（，）相鄰的（，）的網(wǎng)格密度較高，所以事實(shí)上的密度高于的密度，即可

10、直觀得出（，）（，）的結(jié)論考慮到相鄰網(wǎng)格對網(wǎng)格密度的影響，本文采用網(wǎng)格擁擠距離與網(wǎng)格密度相結(jié)合的策略選擇全局極值本文計(jì)算網(wǎng)格擁擠距離與中方法不同之處在于網(wǎng)格擁擠距離的計(jì)算基于進(jìn)行，由于從根節(jié)點(diǎn)到網(wǎng)格節(jié)點(diǎn)之間各層節(jié)點(diǎn)本身包含了計(jì)算擁擠距離所需信息，因此在上計(jì)算所有網(wǎng)格的擁擠距離只需遍歷一次，其計(jì)算復(fù)雜度比 降低了一個(gè)量級定義網(wǎng)格單元對應(yīng)的第維擁擠距離為（），其中吉林大學(xué)學(xué)報(bào)（理學(xué)版）第卷為網(wǎng)格在第維上與其最近鄰的距離，最多可能有個(gè)，也可能有個(gè)（處在該維邊界上）或個(gè)（只有一個(gè)網(wǎng)格）（）計(jì)算在第維上與所有的平均距離定義網(wǎng)格的擁擠距離為（）（）網(wǎng)格擁擠距離的計(jì)算從根節(jié)點(diǎn)開始在每層非葉節(jié)點(diǎn)上進(jìn)行計(jì)算所有

11、網(wǎng)格的擁擠距離只需從根節(jié)點(diǎn)開始遍歷一次不同網(wǎng)格如果有公共祖先，則它們在公共祖先對應(yīng)各維的擁擠距離相同，如圖中的網(wǎng)格（，）和（，），它們的公共祖先是第層間隔段號為的節(jié)點(diǎn)，故有（，）（，）為了避免公共部分擁擠距離的重復(fù)計(jì)算，使用棧保存計(jì)算各維擁擠距離的中間結(jié)果，當(dāng)算法遍歷到一個(gè)葉節(jié)點(diǎn)時(shí)，中依次保存了該葉節(jié)點(diǎn)對應(yīng)各維的擁擠距離，求和即可得到其擁擠距離當(dāng)計(jì)算相鄰節(jié)點(diǎn)時(shí)，只需執(zhí)行（）操作，然后把相鄰節(jié)點(diǎn)在該維的擁擠距離入棧（）網(wǎng)格的擁擠距離越大，其中的非支配解作為進(jìn)行搜索的潛力越大為了維持解集分布的均勻性，規(guī)定每個(gè)網(wǎng)格中保存非支配解的最大個(gè)數(shù)為定義網(wǎng)格密度（）（）越小，其中非支配解的局部搜索能力越強(qiáng)定義

12、擁擠距離密度比（）（）優(yōu)先從最大的網(wǎng)格中選取外部集的更新設(shè) 為的規(guī)模如果非支配解 插入網(wǎng)格時(shí)其中非支配解數(shù)目已達(dá)到，則從中隨機(jī)刪除一個(gè)粒子，然后把 插入若 插入外部集時(shí)，外部集中非支配解數(shù)目已經(jīng)達(dá)到 ，則優(yōu)先從值最小的網(wǎng)格中隨機(jī)刪除一個(gè)非支配解若網(wǎng)格中非支配解已被全部刪除，則從中刪除對該網(wǎng)格的索引算法下面給出基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法設(shè)為粒子群的規(guī)模，為第次迭代后得到的非支配解集，為中非支配解個(gè)數(shù)為最大迭代次數(shù)，函數(shù)，從集合，中隨機(jī)選擇一個(gè)粒子搜索時(shí)有速度限制，當(dāng)粒子飛出搜索空間時(shí)，令粒子的位置在邊界上，其速度算法描述如下：（）；初始化粒子群（）；劃分目標(biāo)空間網(wǎng)格，建立執(zhí)行（， ）把

13、非支配解 加入并對其建立索引； ！（ ），；通過（）計(jì)算索引的每個(gè)網(wǎng)格的（）與（）；從值最大的網(wǎng)格中隨機(jī)選擇一個(gè)粒子作為；用式（），（）更新中所有粒子的速度和位置；執(zhí)行（， ）； 使用索引劃分后的目標(biāo)空間網(wǎng)格不僅能有效保存數(shù)據(jù)的空間位置信息，而且能保存單元的相對空間位置信息計(jì)算任意網(wǎng)格密度（）即為查找網(wǎng)格的過程，最差情況下中有個(gè)非葉節(jié)點(diǎn)，共層，查找網(wǎng)格在某層的間隔段號需要進(jìn)行次比較，查找一個(gè)網(wǎng)格共需次比較從根節(jié)點(diǎn)到網(wǎng)格節(jié)點(diǎn)之間各層節(jié)點(diǎn)本身包含了計(jì)算擁擠距離所需信息，在上計(jì)算所有網(wǎng)格的擁擠距離只需遍歷一次，最差情況下索引 個(gè)非空網(wǎng)格（此時(shí)每個(gè)非空網(wǎng)格中只落入一個(gè)非支配解），遍歷需要 次比較對于不

14、同問題，規(guī)模為常數(shù)，因此算法確定的時(shí)間復(fù)雜度為（ ）由于規(guī)模 的設(shè)置采用與相同的方法，即與種群規(guī)模呈線性關(guān)系，于是確定的時(shí)間復(fù)雜度為（），而為（）僅索引非空網(wǎng)格，一般情況下非空網(wǎng)格數(shù)量遠(yuǎn)小于空網(wǎng)格數(shù)量，因此實(shí)際計(jì)算量要小得多實(shí)驗(yàn)結(jié)果與分析多目標(biāo)優(yōu)化算法的性能評價(jià)指標(biāo)很多，主要分為三類：收斂性能、分布性能（多樣性能）和綜合性能本文選用其中兩個(gè)指標(biāo)評價(jià)算法的性能定義算法所獲得的解與最優(yōu)前端的趨近程度（）定義為其中：表示算法最終獲得的解個(gè)數(shù)；為第個(gè)解到最優(yōu)前端的最短距離值越小，表明算法所獲得的解越趨近最優(yōu)前端定義（）用于描述算法獲得的解在目標(biāo)空間上的分布是否均勻，定義為（ ），其中：， ；表示算法最

15、終獲得的解個(gè)數(shù)； 是的平均值值越小，表明該算法獲得的解分布越均勻本文使用，和四個(gè)測試函數(shù)驗(yàn)證算法這些測試函數(shù)的最優(yōu)前端有凸的、非凸的和不連續(xù)的對這些具有不同形狀最優(yōu)前端的函數(shù)進(jìn)行測試，并把實(shí)驗(yàn)結(jié)果與和的結(jié)果進(jìn)行對比算法參數(shù)設(shè)置如下：粒子群初始規(guī)模為；最大迭代次數(shù)為；學(xué)習(xí)因子；從隨迭代線性變化到；和的參數(shù)設(shè)置如下：種群大小，外部集合大小為，交叉概率為，二元錦標(biāo)賽選擇和二進(jìn)制編碼，變異概率為染色體長度的倒數(shù)的每維目標(biāo)被劃分的數(shù)量為種算法分別對每個(gè)函數(shù)獨(dú)立運(yùn)行次圖圖為本文算法所得的近似最優(yōu)前端表列出了種算法的計(jì)算結(jié)果由表可見，算法具有較好的收斂性能，在個(gè)測試函數(shù)上都優(yōu)于，在，和三個(gè)函數(shù)上優(yōu)于這是由于

16、算法的全局極值選取策略更合理，而且基于空間劃分樹的全局極值選擇算法具有更高的計(jì)算效率表的計(jì)算結(jié)果也驗(yàn)證了在空間劃分樹上使用擁擠距離和網(wǎng)格密度相結(jié)合策略維護(hù)外部種群的有效性由于考慮了相鄰網(wǎng)格對網(wǎng)格密度的影響，所以算法對個(gè)測試函數(shù)產(chǎn)生的非支配解在最優(yōu)前端的分布都比更廣、更均勻，在和上分布性能略差于，而在和上比具有更好的分布性第 期 劉華鎣， 等： 基于空間劃分樹的多目標(biāo)粒子群優(yōu)化算法 圖 的近似 最優(yōu)前端 圖 的近似 最優(yōu)前端 圖 的近似 最優(yōu)前端 圖 的近似 最優(yōu)前端 表 種算法的計(jì)算結(jié)果對比 函數(shù) 參數(shù) 平均值 中間值 標(biāo)準(zhǔn)差 平均值 中間值 標(biāo)準(zhǔn)差 平均值 中間值 標(biāo)準(zhǔn)差 平均值 中間值 標(biāo)

17、準(zhǔn)差 由于 算法中全局極值的選取不僅考慮了個(gè)體網(wǎng)格的密度信息， 而且綜合了個(gè)體網(wǎng)格與 相鄰網(wǎng)格間的擁擠距離信息， 使得選取全局極值時(shí)的估值更準(zhǔn)確、 分布更均勻， 能夠較好地逼近 最優(yōu)前端所以， 與其他兩種算法相比， 算法具有一定的優(yōu)勢 綜上可見， 算法使用網(wǎng)格對多維目標(biāo)空間進(jìn)行劃分， 網(wǎng)格保存數(shù)據(jù)空間位置信息， 空 間劃分樹在索引存儲非支配解的非空網(wǎng)格的同時(shí)記錄非空網(wǎng)格的相對空間位置信息， 為外部集維護(hù)提 供了高效的數(shù)據(jù)結(jié)構(gòu)支持， 能有效提高 的計(jì)算性能； 算法用 中擁擠距離的概 念重新定義網(wǎng)格擁擠距離并結(jié)合網(wǎng)格密度選取全局極值， 使算法能較好地逼近 最優(yōu)前端， 并且 可使 最優(yōu)解分布較均勻

18、吉 林 大 學(xué) 學(xué) 報(bào) （ 理 學(xué) 版） 第 卷 參 考 文 獻(xiàn) ， ， ， ， ： ， ： ： ， ， （）： （ 張利彪， 周春光， 劉小華， 等粒子群算法在求解優(yōu)化問題中的應(yīng)用 吉林大學(xué)學(xué)報(bào)： 信息科學(xué)版， ， （）： ） ， ， 分配方法 東北師大學(xué)報(bào)： 自然科學(xué)版， ， （）： ） 基于支持向量機(jī)和粒子群算法的結(jié)構(gòu)損傷識別 吉林大學(xué)學(xué)報(bào)： 工學(xué)版， ， （）： ） ： ， ， （）： （ 于繁華， 劉寒冰 ： ， ， （）： （ 劉淑華， 張?；诹Ｗ尤合伻核惴ǖ亩鄼C(jī)器人任務(wù) ， ， （）： （ 李秀英， 韓志剛基于粒子群 算法優(yōu)化的 型模糊神經(jīng)網(wǎng)絡(luò)控制器 黑龍江大學(xué)自然科學(xué)學(xué)報(bào)， ， （）： ） ， ， 系統(tǒng)學(xué)報(bào)， ， （）： ） ， ， （）： （ 王艷， 曾建潮 多目標(biāo)微粒群優(yōu)化算法綜述 智能 ， ， （）： ， ， ， ， ， ， ， （）： （ 張利彪， 周春光，