基于維度缺失檢測與恢復的協同進化算法

陳 昊, 陳 園, 黎 明, 李軍華, 張聰炫

(1.南昌航空大學信息工程學院,江西南昌 330063;2.南昌航空大學無損檢測技術教育部重點實驗室,江西南昌 330063)

1 引 言

在實際的工程應用中,高維、超高維優化問題普遍存在,決策變量超過100 維的此類問題被稱為大規模優化問題[1].例如資源調度,交通網絡規劃等約束弧路徑問題通常具有上千維的決策變量[2];生物計算中飽和系統優化問題的維數約為2N(N+1),分量數N=50 時,問題規模為5 100 維.

大規模全局優化(LSGO)問題可以被定義為

其中X ?Rn為n維的決策空間;n≥100;x=(x1,x2,...,xn)∈Rn為決策變量;f:Rn →R表示n元函數.LSGO 問題中不同決策變量之間通常存在復雜的耦合關系,屬于不可分問題(non-separable problems)[2],如何處理該類復雜大規模優化問題是當前進化計算研究領域的研究熱點.目前,解決LSGO 問題的算法主要分為兩大類,非分解算法和協同進化算法,前者未對高維決策變量分解,通過改進算法中進化算子以提高算法的性能,后者通過分解LSGO 問題,并對分解后的低維子問題分別進行優化.

非分解算法[3]通過在進化過程中針對收斂速度慢,變異策略失效,初始化種群差等問題進行一系列改進的方法,以顯著增強其在探索期間處理LSGO 問題的能力.Tizhoosh 等[4]提出一種基于反方向學習的算法OBL, 主要思想是對一個可行解, 同時計算并評估其反向解, 從中選擇較優的解作為下一代個體, 反向解是指基于搜索空間中心對稱的可行解,可以加快收斂速度.Chu 等[5]發現在高維空間內,易出現“種群退化”現象,因此提出維度缺失的概念,發現未被樣本群體覆蓋維度,并在這些維度兩側生成新的個體代替種群最差個體達到維度恢復效果.Cheng 等[6]提出一種競爭學習的PSO 算法,隨機從當前種群中抽取兩個個體比較適應度值,失敗者向勝利者學習,勝利者并不學習直接進入下一次循環.Mahdavi 等[7]發現中心點附近的點接近未知解的概率要高于其它點,并提出基于中心的正態分布采樣,中央黃金區域和混合隨機中心正態分布采樣等有效初始化方法.

協同進化算法[8]通過設計不同的分解策略將LSGO 問題分解成多個低維子問題,對子問題分別進行優化,進而通過合并獲得問題的完整解.Potter 等[9]最早提出靜態分組,將n維問題分為n個子問題,或將n維問題分為2 個子問題.但是,靜態分組不能達到分組的目的,Yang 等[10]提出一種隨機動態分組,將n維問題隨機分為m個s維的子問題,這種設計可以增加相互關聯變量分在一起的概率.在此基礎上,Yao 等[11]提出將s設計為一個集合,若當前的s導致進化停滯,則在集合中重新隨機選擇一個s值.由于隨機動態分組依舊不能完全區分決策變量,若能通過在優化過程之前或期間獲得問題的特征經驗來了解識別變量間的相關性,根據相關性對問題分組可以增加分組的正確性.Omidvar 等[12]提出差分分組的分組方法,對所有的決策變量兩兩進行相關性計算,根據獲得的相關性進行分組.Mohammad 等[13]發現大規模優化問題的維度間具有不平衡性,認為平均計算資源不合理,提出一種基于變量效應的多層優化框架算法MOFBVE,根據靈敏度分析獲得每個維度對輸出的影響,并根據獲得的影響對維數進行聚類,計算每類的貢獻,優先優化貢獻大的類,能夠合理利用有限資源.

由于進化算法在解決LSGO 問題時易出現“維度缺失、種群退化”現象,降低算法的搜索能力.維度缺失檢測與恢復策略可以增加種群多樣性,能夠有效跳出“種群退化”現象.本文針對LSGO 問題維度缺失檢測與恢復復雜度高,耗時長等問題,利用協同進化算法框架,選擇差分分組方式,將高維問題分解成多個低維子問題,以達到降低復雜度的效果;對所有子問題進行維度缺失檢測,選擇一定數量個體對所有缺失維度進行維度恢復,并替換種群中適應度較差個體.

2 維度缺失

種群退化現象的發生是由于當前種群中個體在絕大多數維度上出現趨同甚至重疊,導致種群多樣性降低,因此稱這種現象為維度缺失.如何有效檢測缺失維度是解決種群退化現象的關鍵所在,主成分分析[14]也稱主分量分析,旨在利用降維的思想,把多指標轉化為少數幾個綜合指標,其中每個主成分都能夠反映原始變量的大部分信息,且所含信息互不重復[5].對于維數為n,個體數為p的種群C,R為種群標準化后的協方差矩陣,特征分解R得到特征值λ和特征向量V,若存在λ小于設定閾值ε,則該特征值對應的種群特征向量方向上存在缺失信息,稱為維度缺失現象.令C= [cij]n×p, 對C標準化得到C′如C′= [], 其中和vi是C中第i行元素的均值和方差,標準化可減少實際問題中不同參數單位差異影響.

特征向量對應特征值是該特征向量方向上的方差,每個特征向量的期望方差是總方差的1/n.因此,如果一個特征向量的方差小于預期方差的10%,將其視為一個缺失維度.

特征值的大小代表了矩陣正交化之后所對應特征向量對于整個矩陣的貢獻程度,因此特征值越大,對應的特征向量包含的信息量越大.相反,當特征值λi小于閾值ε,則特征值λi對應的特征向量Vi視為缺失維度.圖1(a)是二維維度缺失圖,v1和v2為特征向量.可以發現圖中5 個個體在v1方向上呈線性,所以v1對應的特征值大于v2對應的特征值,當v2對應特征值小于設定閾值,視v2為缺失維度.

圖1 維度缺失檢測與恢復Fig.1 Dimensional missing detection and recovery

維度缺失檢測是基于主成分分析方法的原理, 對于一個n維問題, 當投影到k個主成分時復雜度為O(kn2),以二分組為例,子問題復雜度為O(kn2/4),對于整個問題,復雜度為O(kn2/2).所以當結合分組策略后,組內規模會更小,則維度缺失檢測的復雜度更低.

3 基于維度缺失檢測與恢復的協同進化算法

由于LSGO 問題有上千維決策變量, 進行維度缺失檢測復雜度高, 利用分解策略分解高維問題;對分解后的子問題進行維度缺失檢測;針對缺失維度,選取種群中較差的q%個體,對所有缺失維度同時進行恢復,選擇優異的個體進入下一代.圖2 是基于分組的維度缺失檢測與恢復示意圖,圖中第一列是LSGO 問題的所有維數,其中每一個小矩形代表一個維度,有相同灰度的矩形表示具有相關性;第二列是分組后的所有子問題,每個子問題由具有相關性的維度組成;第三列是對所有子問題進行維度缺失檢測;第四列表示進行維度恢復操作后的維度缺失情況,其中無色矩形表示缺失維度.

圖2 基于分組的維度缺失檢測與恢復示意圖Fig.2 Schematic diagram of group-based dimension missing detection and recovery

3.1 分解策略

協同進化算法的關鍵是分解策略,已有分解策略主要分為靜態分組,隨機分組,動態分組.

靜態分組是最早的分解策略,不考慮維數間相關性,直接將n維決策變量硬性分為組內規模為1 的n組子問題或組內規模為n/2 的2 組子問題n →1(n)或n →n/2(2).

考慮到變量間相關性,提出隨機分組[12],將n維決策變量隨機分為組內規模為s的m組子問題,意味著每個變量都有相同的機會被分配到任何子問題中,n=ms.

動態分組是通過在優化過程之前或期間獲得問題的特征經驗來了解識別變量間的相關性,并根據變量間相關性進行分組.以差分分組為例,從第一個變量開始,分別檢測其它變量與第一個變量之間的交互關系,如果不可分(即具有交互關系),從所有決策變量中將其排除,放到一個子成分中,重復這個過程,直到所有與第一變量交互的變量都被檢測出來,形成第一個子成分.對于不可分問題,?a,b1=b2,δ ∈R,δ= 0,若滿足ε=σ/ni,則xp與xq之間有相關性,為不可分變量,即

其中Δδ,xpf(x)=f(...,xp+δ,...)?f(...,xp,...)是f關于xp間隔δ的前向差分.從靜態分組,隨機分組到動態分組,分組正確性逐漸提升.

3.2 基于分組的維度缺失檢測

基于分組的維度缺失檢測旨在降低LSGO 問題維度缺失檢測復雜度.對于LSGO 問題,決策變量維數常達1 000 維以上,因此,將高維決策變量分解,對低維子問題進行維度缺失檢測則不存在復雜度高問題.此處先標準化子種群并計算協方差矩陣,并對協方差矩陣特征分解,計算其特征值與特征向量,當特征值小于閾值ε時,該特征值對應的維度缺失,閾值為

其中ni為第i個子問題維數,σ為比例系數,σ=0.01.

基于分組的維度缺失檢測的算法步驟如下:

步驟1根據子種群生成矩陣C.

步驟2對矩陣C標準化,得到矩陣p.

步驟3計算p的協方差矩陣R.

步驟4對進行特征分解的特征值λ和特征向量V.

步驟5將特征值降序排列,特征向量也作相應排序.

步驟6將小于閾值的特征值對應的特征向量視為缺失維度.

3.3 維度恢復

檢測出缺失維度后,用所有特征向量建立新坐標系,計算種群在新坐標系上的坐標表示,在新坐標系對種群所有缺失維度進行恢復.如圖1(b)所示,以v1和v2為新坐標方向建立坐標系,選擇部分個體在缺失維度v2上進行恢復,具體步驟如下:

步驟1對任意子問題,以特征向量為坐標向量建立坐標系空間V ni.

步驟2將子種群在基坐標空間坐標轉換為V ni的坐標,如

其中t為子種群在V ni中的坐標,p為子種群在基坐標空間中的坐標,C為過渡矩陣(基變換矩陣).

步驟3選擇t中q%較差個體在缺失維度同時進行恢復得到t′,對第j個體第k維度恢復,即

其中ajk為N(2,1)隨機數,r為子種群最大半徑.

步驟4對恢復后的t′轉換為基坐標空間中坐標p′,p′ ←t′C.

步驟5從p和p′中選擇優異個體進入下一代.

維度恢復的算法步驟如下:

步驟1根據子種群適應度的大小,對子種群作降序排列.

步驟2以特征向量為新的基,建立一個新的坐標系.

步驟3將種群中的個體轉換到新的坐標系.

步驟4選擇適應度較差的部分個體在缺失維度上進行擴展恢復.

步驟5將恢復后的個體轉換到原來的空間.以任意子種群中符合條件的第j個體pj為例,pj在基坐標空間中坐標為(xj1,xj2,...,xjni).根據式(2)轉換為V ni中坐標,即tj= (vj1,vj2,...,vjni),對個體在缺失維度同時進行擴展后坐標為t′j=(vj1,vj2,...,vjk±ajkr,...,vjni ±ajnir).

根據式(3)將恢復后的種群坐標轉換回基坐標空間坐標,即p′j=(xj1,xj2,...,xjni).

3.4 基于維度缺失檢測與恢復的協同進化算法

在對子問題分別進行維度缺失檢測并進行維度恢復后,結合協同進化算法框架,進一步優化種群,提出一種基于維度缺失檢測與恢復的協同進化算法(co-evolutionary algorithm based on dimension monitoring and recovery,CCDMR).全局維度恢復的協同進化算法步驟如下:

步驟1初始化種群和所有參數.

步驟2任選一種分組策略,對問題維數進行分組.

步驟3當算法連續2 代進行停滯,對所有子種群進行維度缺失檢測.

步驟4對所有子種群進行維度恢復.

步驟5對所有恢復維度的子種群進行恢復.

步驟6若沒有達到終止條件,返回步驟3.

4 實驗與分析

為了分析CCDMR 算法的性能, 在本文中, 分別對算法的有效性、多樣性、參數選擇有效性以及收斂精度進行實驗比較與分析.實驗中僅限于CEC2013 LSGO[16]基準函數(f411)等8 個不完全可分函數進行實驗,未包含完全可分函數(f13),重疊函數(f1214)和完全不可分函數(f15).對所有實驗,設置自變量維數n= 1 000, 種群規模為100, 進行全局維度恢復的個體數量q為50, 最大迭代次數為500.在DECC-G和CCDMR-G 中設定分組規模s=50,每個測試函數獨立運行30 次,記錄結果的平均值和標準差.

4.1 有效性分析

CCDMR 算法有效性分析選擇以靜態分組, 隨機動態分組和動態學習分組等三種分組方式為代表的CCGA,DECC-G 和DECC-DG[15]算法進行實驗.比較算法在加入維度缺失檢測與恢復算子前后的結果,算法優化函數均選擇差分進化算法,實驗結果見表1,兩兩比較將較好值用粗體顯示.

表1 CCDMR 結合三種不同分組方式與CCGA,DECC-G 和DECC-DG 優化結果Table 1 CCDMR combines three different grouping methods with CCGA,DECC-G and DECC-DG optimization results

從表1 的求解結果均值看,與CCGA 算法相比,基于靜態分組的CCDMR 在8 個測試函數上均優于CCGA;與DECC-G 算法相比,CCDMR-G 在6 個測試函數(f5,f6,f7,f9,f10,f11)上優于DECC-G,2 個測試函數(f4,f8)上差于DECC-G;與DECC-DG算法相比,CCDMR-DG 在7 個測試函數(f4,f5,f6,f7,f9,f10,f11)上優于DECC-DG,1 個測試函數(f5)上差于DECC-DG.這說明CCDMR 算法在求解LSGO 問題的數據結果要整體優于CCGA,DECC-G 和DECC-DG.

比較CCDMR,CCDMR-G 和CCDMR-DG 三種算法的數據可以發現,CCDMR 在選定的8 個測試函數上結果普遍表現最差,而CCDMR-DG 在大部分測試函數中結果要優于CCDMR-G,僅在測試函數f6和f7上略差于CCDMR-G.表明在解決LSGO 問題時,靜態分組的分組準確性最差,動態學習分組的分組準確性最好,隨機動態分組的分組準確性介于兩者之間.

圖3 是各算法在8 個測試函數上運行30 次結果平均值的收斂曲線圖,橫軸為進化代數,縱軸為函數值.

圖3 CCDMR,CCGA,CCDMR-G,DECC-G,CCDMR-DG 和DECC-DG 算法在CEC2013 中f4 ～f11 收斂曲線對比Fig.3 Comparison of convergence curves of f4 ～f11 in CEC2013 by CCDMR,CCGA,CCDMR-G,DECC-G,CCDMR-DG and DECC-DG algorithms

續圖3Fig.3 Continues

從圖3(a),圖3(b),圖3(c),圖3(d),圖3(f),圖3(g),圖3(h)可以看出在f4,f5,f6,f7,f9,f10,f11等7 個測試函數中,均是本文提出的CCDMR 結合不同分組方法的CCDMR-DG 和CCDMR-G 結果最優,CCGA 結果最差.8 個測試函數的求解結果說明CCDMR 優于未加入維度缺失檢測與恢復算子的算法.由于選擇分組方法不同,CCDMR 的優化結果也不同,從圖中可以看出,CCDMR-DG 優于CCDMR-G 和CCDMR,所以動態學習分組要優于隨機動態分組和靜態分組.從8 幅圖整體情況來看,收斂曲線依然支持以上數據分析結果.

圖4 是各算法在8 個測試函數上運行30 次結果的Box Plot 圖,橫軸為對比算法,縱軸為函數值.

圖4 CCDMR,CCGA,CCDMR-G,DECC-G,CCDMR-DG,DECC-DG 算法在CEC2013 中f4 ～f11 box plot 圖Fig.4 Box plot of f4 ～f11 in CEC2013 by CCDMR,CCGA,CCDMR-G,DECC-G,CCDMR-DG and DECC-DG algorithms

續圖4Fig.4 Continues

從圖4(a),圖4(b),圖4(e),圖4(f),圖4(h)中可以看出在f4,f5,f8,f9,f11函數中,CCDMR-DG 不僅收斂性最好,并且最穩定;對于圖4(c),圖4(d)中f6,f7函數結果,CCDMR-G 的收斂性最好,DECC-DG 最穩定;對于圖4(g)中f10函數結果,CCDMR-DG 的收斂性最好,DECC-DG 最穩定.整體來看,維度缺失檢測算子和維度恢復算子在各分組情況下對算法收斂性都有提升,不過對于不同測試函數,效果也不一樣.

4.2 多樣性分析

CCDMR 算法在保證收斂的前提下,可以保持種群多樣性,比較維度缺失檢測與恢復前后種群多樣性.此處用種群熵表征種群多樣性,分別計算各算法在所選測試函數全局維度恢復前后種群熵的相對偏差,選擇不同分組方式,分別為不分組,靜態分組,隨機分組和差分分組,對應種群熵的相對偏差如表2 所示.

表2 CCDMR 結合四種不同分組方式種群熵的相對偏差Table 2 CCDMR combines the relative deviation of population entropy in four different grouping methods

從表2 的數據可以發現,全局維度恢復方法結合不同分組方式在所有選取測試函數上種群熵均有所增大,說明種群多樣性得以維持.其中f5,f9函數在CCDMR 結合四種不同分組方式上種群熵的相對偏差較大,f6,f10函數在CCDMR 結合四種不同分組方式上種群熵的相對偏差不明顯,因為f5,f9函數的基函數是單峰函數,而f6,f10函數的基函數是多峰函數,有大量局部最優值.

圖5 是CCDMR 在f5和f11函數全局恢復前后種群熵變化曲線,橫軸為進化過程中出現的停滯次數,縱軸為種群熵值.

圖5 f5,f11 全局維度恢復前后種群熵對比曲線圖Fig.5 f5,f11 global dimension before and after population entropy comparison curve

從圖5(a)中可以看出f5函數恢復后的種群熵明顯大于恢復前的種群熵,且恢復前的種群熵曲線較為平滑,而恢復后的種群熵曲線出現上下波動.這是由于算法在迭代過程中,個體向最優值靠近,種群熵減小,導致種群多樣性減小,而全局恢復可以增大種群熵,從而達到維持種群多樣性的效果.從圖5(b)中也可以看出種群多樣性得以維持.

4.3 比例系數對算法影響分析

比例系數σ大小決定維度缺失被檢測的程度,決定需要被恢復的維度,對算法收斂速度有較大影響.σ越大,缺失維度門檻會對應提高,則有較少維度被視為缺失維度,反之,較多維度被視為缺失維度.對此,分別對σ=0.005,σ=0.05,σ=0.1 和σ=0.01 進行實驗分析,結果對比如表3 所示

表3 比例系數對比結果Table 3 Scale factor comparison results

根據表3 的結果顯示,當σ= 0.01 時,在所選擇的8 個測試函數上均獲得最優結果.則當σ= 0.01 時,維度缺失檢測與恢復效果較好,可以跳出進化停滯概率,提高算法收斂精度與收斂速度.

4.4 CCDMR與MOFBVE,CBCC3,CC-CNS對比

結合目前研究情況,選擇在CEC2013 測試函數上進行評估的已有算法MOFBVE,CBCC3 和CC-CNS與之進行比較.比較結果如表4 所示,其中CCDMR 算法的優化函數選擇自適應的基于鄰域搜索的差分進化算法(SaNSDE),分組方式選擇差分分組.

表4 為本文方法數據與文獻[7,13,17]中的數據對比.

表4 CCDMR 與MOFBVE,CBCC3 和CC-CNS 結果比較Table 4 Comparison of CCDMR with MOFBVE,CBCC3 and CC-CNS results

從表4 中可以看到,本文方法在4 個測試函數(f5,f7,f9,f11)上優于另外三個算法;CC-CNS 在2 個測試函數(f6,f10)上優于另外三個算法;CCBC3 在2 個測試函數(f4,f8)上優于另外三個算法.在所選測試函數中,本文方法在一半測試函數上優于其它算法,收斂精度高于其它算法.

5 結束語

為了解決LSGO 問題中維度缺失、進化停滯問題, 對進化停滯種群進行維度缺失檢測與恢復.由于優化問題搜索空間隨著維數增加成指數倍增長, 將維度缺失檢測與恢復結合協同進化算法框架, 提出一種CCDMR 算法.根據理論分析及仿真結果可知: 1)CCDMR 算法結合協同進化算法框架,可以降低維度缺失檢測與全局維度恢復的復雜度,加快收斂速度;2)CCDMR 算法能夠避免種群陷入局部最優,維持種群多樣性,提高了算法的收斂精度.

本文提出的基于維度缺失檢測與恢復的協同進化算法選用了已有的三種分組策略,這三種分組策略尚不能夠準確地將高維問題進行分組,需研究出更加準確的分組策略,這也是本文后續的研究內容.