針對混合變量優化問題的協同進化蟻群優化算法

韋銘燕，陳 彧，張 亮

（武漢理工大學理學院，武漢 430070）

（*通信作者電子郵箱chymath@gmail.com）

0 引言

科學研究和工程計算中的許多問題都可以建模為具有連續和離散決策變量的混合變量優化問題（Mixed-Variable Optimization Problem，MVOP）［1-4］。利用隨機啟發式算法（Random Heuristics Algorithm，RHA）求解MVOP，可以克服傳統數學優化問題難以定位到全局最優解的不足，但如何實現混合變量搜索空間中的高效協同搜索，設計出能夠快速收斂到MVOP 的全局最優解的混合變量啟發式算法（Mixed-Variable Random Heuristics Algorithm，MVRHA），已成為RHA研究的一個具有挑戰性的課題。

根據離散變量的可能取值是否具有大小（或先后）順序，可以將離散變量分為序數變量和分類變量。由于序數變量的取值具有大小（或先后）順序，可以根據序數變量取值的大小（或先后順序）將其映射到連續實數搜索空間，利用實數空間的搜索策略得到實數值并將其轉化為對應的序數變量值［5］。為了降低連續變量和離散變量之間的轉化所產生的額外計算代價，Chen 等［6］設計了一種模仿連續差分進化（Differential Evolution，DE）算法搜索策略的離散編碼DE 算法，并借鑒粒子群優化（Particle Swarm Optimization，PSO）的社會學習機制提高其對離散變量空間的搜索效率；Chen 等［7］提出了基于集合的PSO 算法，在離散解空間模仿PSO 在連續搜索空間中的動力學行為來提高算法在離散變量空間的搜索效率。對于取值集合沒有大小（或先后）順序的分類變量，Liao 等［8］則通過檔案庫構建面向分類變量的信息素模型，并采用蟻群優化（Ant Colony Optimization，ACO）策略來實現分類變量空間的有效搜索；Lin 等［9］設計了基于集合的DE 算法來模仿連續DE算法的搜索機制，從而實現在離散解空間的高效搜索。

為了實現對混合變量決策空間的高效協同搜索，Li 等［10］分別設計了針對連續變量和離散變量的變異策略；Liao 等［8］利用離散ACO 和連續ACO 來生成離散變量和連續變量子種群，并提出了相應的自適應參數設置方案［11］；Lin 等［9］分別采用基于集合的DE策略和連續DE策略來生成處理離散變量和連續變量；Wang等［12］分別構建了針對離散變量和連續變量空間的柱狀圖概率模型，設計了求解報童問題的混合變量模型的分布估計算法（Estimation of Dsitribution Algorithm，EDA）。這些研究工作在連續和離散變量子空間采用了同一類個體生成策略來實現子空間的協同搜索，試圖在離散和連續變量空間中采用具有類似動力學特性的搜索機制來提高MVRH 算法的求解效率。

然而，離散變量的不連續跳躍取值可能產生具有強支配性的局部吸引域，即使采用同一類個體生成策略來得到連續和離散變量，也可能在連續和離散空間中產生完全迥異的搜索進程從而導致算法收斂到局部最優解。特別地，當離散變量為取值無序的分類變量時，模擬連續搜索策略的離散個體生成機制無法對離散取值空間的適應值分布進行有效的學習，更加難以實現對全局最優解的準確定位。為了解決無序性分類變量空間給定位全局最優解所造成的難題，本文采用協同進化（Coevolution）策略［13］來定位混合變量全局最優解，提出了求解MVOP 的協同進化蟻群優化算法（Coevolutionary Ant Colony Optimization Algorithm for MVOP，CACOAMV）。通過檔案庫來學習分類變量空間的適應值分布，CACOAMV利用離散變量的蟻群搜索策略來生成分類變量子向量；同時，利用連續蟻群搜索策略生成連續解向量，實現連續解空間的高效率局部開發；通過協作解（Cooperator）來對連續子向量和分類子向量進行評價，并基于評價結果對連續和分類種群進行更新，CACOAMV能夠學習到分類變量的跳躍取值目標函數的適應值地形產生的支配性的影響，從而通過在混合變量空間的協同進化來收斂到MVOP的全局最優解。

1 求解MVOP的協同進化蟻群優化算法

考慮具有混合決策變量的最小化問題：

其中：X=(XR，XO，XC)由連續變量子向量XR=[x1，x2，…，xr]、序數變量子向量XO=[xr+1，xr+2，…，xr+o]以及分類變量子向量XC=[xr+o+1，xr+o+2，…，xr+o+c]構成，r、o、c分別是連續、序數和分類變量子向量的維數。連續變量xi的取值區間為（i=1，2，…，r），序數變量xj和分類變量xk的取值集合分別記為Oj（j=r+1，r+2，…，r+o）和Ck（k=r+o+1，r+o+2，…，r+o+c）。由于序數變量的取值可以按數的大小（或先后）排序，可以模仿連續優化搜索策略進行可行解空間的高效搜索［6-8］；然而分類變量的取值卻沒有明確的大小（或先后）順序，更難確定全局最優的分類變量取值的吸引區域。因此，本文重點研究連續變量和分類變量共存的MVOP。

1.1 CACOAMV的算法框架

在MVOP（1）中，連續變量與離散變量具有性質迥異的可行區域，目標函數f(X)與兩類變量也具有完全不同的相關關系，需要設計面向不同變量類型的空間搜索策略；同時，由于連續和離散變量空間的迭代搜索過程具有不同的動力學特性，分別采用面向連續變量和離散變量的個體生成策略來生成MVRSH 的連續變量子種群和離散變量子種群，并利用協同進化機制來實現兩個子種群的合作協同搜索。

合作協同進化算法（Cooperative Co-Evolutionary Algorithm，CCEA）通過學習決策變量的相關關系來對決策變量進行分組，將復雜優化問題分解成若干個子問題，每個子問題都由一個單獨的子種群來進行可行域搜索；各個子種群在迭代過程中通過協作解相互作用來實現子種群之間的協同進化，從而實現在MVOP 的混合變量可行域的全局搜索［13］。CCEA 的求解性能與其待優化問題中決策變量的相關關系的學習效率及問題的分解策略緊密相關，對決策變量相關關系的學習和子問題的分解策略是CCEA 設計的一個關鍵問題。然而，由于MVOP 中連續變量和分類變量具有顯著的不同數學特性，可以分別將連續變量和分類變量分為一組，構建連續變量子種群PR和分類變量子種群PC來對連續變量子空間和分類變量子空間進行協同搜索，得到如下所示的CACOAMV。

算法1 CACOAMV。

輸入 決策變量的個數n，連續決策變量個數r，分類決策變量個數c，檔案庫規模NA，蟻群大小M，最大迭代次數MaxIt；

輸出 最優協作解B，最優解的目標函數值f*。

1.2 解檔案庫的構建和更新

為了使蟻群優化搜索過程具有較好的全局開發能力，需要構建反映全局適應值地形的檔案庫和信息素模型。為此，混合變量的蟻群優化（Mixed-Variable Ant Colony Optimization，ACOMV）［8］構建了面 向MVOP 可行解的解檔案庫（Solution Archive，SA），并由此來構建蟻群搜索的信息素模型。然而，構建面向MVOP的混合變量解向量檔案庫忽略了連續變量子空間和離散變量子空間的不同屬性，不能準確反映和滿足兩個子空間的不同適應值分布對檔案庫中解分布的需求。因此，ACOMV所構建的信息素模型無法對離散和連續子空間的適應值地形進行準確刻畫。

因此，CACOAMV分別對分類變量和連續變量構建解檔案庫。記檔案庫規模為NA，SA 將r維連續變量（或c維分類變量）子向量和對應的適應值存儲在解檔案庫AR（或AC）中。在算法迭代初始，AR（或AC）由NA個隨機生成的連續（或分類）變量子向量初始化，然后根據評價結果（評價策略見1.3.3 節）從優到劣對其進行排序。在迭代過程中，對生成的M個連續（或分類）解向量進行評價，將所有的NA+M個連續（或分類）解向量按適應值從優到劣進行排序，并將最好的NA個保留下來作為新的檔案庫AR（或AC）。

1.3 解的構造及評價策略

1.3.1 連續變量的解向量構造

根據檔案庫AR中個體的評價結果來構建信息素模型，采用高斯函數來對解的影響力進行量化［8］：

其中rank(j)是解Sj在檔案庫AR中的排名。解檔案庫中的最佳解將獲得最大的影響力，而其他解的影響力則隨著其排名呈指數下降。為了讓算法能夠適應不同優化問題中不同適應值地形對算法性能的影響，式（2）中引入了參數q來調節檔案庫中隨著排名降低的解的影響力的衰減速度。

根據式（2）中所得到的影響力指標ωj，CACOAMV應用ACOR［14］中的連續變量生成策略，以概率pconj=從檔案庫AR中選擇一個連續子向量XR(j)=(x1(j)，x2(j)，…，xr(j))來構造新的連續解向量TXR(j)=(tx1(j)，tx2(j)，…，txr(j))。對任意的1 ≤i≤r，txi(j)服從均值為xi(j)、標準差為σji的正態分布，其中，標準差σji由解檔案庫中所有解的第i個連續變量取值和參數ξ共同決定：

其中：參數ξ的值越大，則變異的標準差越大，在連續子空間的收斂速度越慢。

1.3.2 分類變量的解向量構造

設分類變量xj具有tj個可能的取值ν1，ν2，…，，則分類變量解生成策略以概率將值νk分配給xj，其中，概率分布由沉積在變量xj的取值νk上的信息素τj，k所確定：

信息素的揮發和沉積策略為：

其中信息素揮發率為ρ，在分類變量xj的值νk上的信息素沉積量［15］為：

其中me為精英螞蟻數量的正整數。與MAX-MIN 螞蟻系統［16］類似，CACOAMV對信息素的累積量的上下限進行了限制。信息素累積量的上、下限分別為：

當分類變量種群PC停滯代數超過設定值limit時，CACOAMV采用如下平滑機制調整沉積在變量xj的取值νk上信息素：

其中0 ＜θ＜1。式（9）對信息素的分布進行了重置，縮小了算法后期當前種群最優解中的信息素量與其他較差解的信息素量之間的差值，使得螞蟻有可能選擇非當前最優解，從而重新賦予了算法較強的全局探索能力。本文θ取值為0.5。

1.3.3 解的評價策略

根據協同進化算法的個體生成評價策略，CACOAMV分別生成連續變量子向量XR和分類變量子向量XC，并分別結合B=(BR，BC)的分類變量子向量BC和連續變量子向量BR來進行評價，即

1.4 重啟機制

為了進一步提高CACOAMV的全局收斂能力，當算法所搜索到的最優解的連續停滯代數大于設定值StagIt時，則會觸發重啟機制。重啟機制被觸發后，將連續和分類變量子種群隨機初始化，并保留所搜索到的最佳連續和分類變量子向量。對重啟后子種群PR和PC中的個體的評價采用如圖1 所示的“最佳+隨機合作者”評價策略。

圖1 “最佳+隨機”合作者策略Fig.1 “Best+random cooperators”strategy

在圖1（a）所示的最佳合作者策略中，將子種群P1的個體Xi與子種群P2中的最佳個體Ybest構成一個完整解TX；在圖1（b）的隨機合作者策略中，另一個完整解TY由P1的個體Xi與P2中隨機選擇的個體Yrnd結合而得到；利用目標函數對TX和TY進行評價，將較好的目標函數值作為P1的個體Xi的適應值，即：

2 仿真實驗與結果分析

為了測試CACOAMV的性能，本文采用了由CEC’05 連續基準測試問題［17］生成的人造混合變量基準測試問題進行數值實驗。首先，確定n維混合變量測試函數中的連續變量和分類變量的維數r和c（r+c=n）；然后，將CEC’05 連續基準測試問題的前r維連續變量保持不變，后c維連續變量通過如下方法轉化為分類變量并確定其取值集合：在后c維連續變量的取值區間使用等距網格生成tj個數據點，再將其進行隨機排列得到分類變量Cj的取值集合Tj={θj，1，θj，2…，θj，tj}，j=r+1，r+2，…，n。本文令測試問題的決策變量個數n為偶數，r=c=n/2，分類變量取值集合的大小為tj=100，j=r+1，r+2，…，n，生成的基準測試問題如下：

其中

式（12）～（17）分別代表6 個人造混合變量基準測試函數；式（18）表示經過旋轉和移位后的混合變量，其中M為旋轉矩陣，s*為問題的全局最優解；式（19）表示未經過旋轉和移位處理的混合變量；式（20）表示連續變量的取值范圍；式（21）表示分類變量的取值范圍；式（22）表示n維決策變量由r維連續變量和c維分類變量組成。

2.1 CACOAMV的參數分析

為了能得到合適的參數設置，使得CACOAMV達到最佳的收斂性能，以10維的單峰函數f1和多峰函數f2作為測試問題，分析CACOAMV的分類變量解生成策略中的參數ρ和b對算法收斂性能的影響，FEs為算法運行過程中的目標函數評價次數。考慮到算法中的重啟策略會對全局探索及局部開發能力產生影響，本節中的參數分析中關閉了CACOAMV中的重啟機制。

函數f1具有橢球形的等值面，求解f1的高效算法需要具有能夠適應不同位置的不同適應值地形的自適應局部開發能力。從圖2 中的收斂曲線可以發現，CACOAMV的收斂進程在y=1(lgy=0)附近會出現停滯，而參數ρ和b的值越大，停滯階段的持續時間越長。由此可見，在（局部）最優解的吸引區域，CACOAMV的開發能力隨著ρ和b的值的增大而增大。

圖2 CACOAMV求解f1的收斂曲線Fig.2 Convergence curves of CACOAMV on solving f1

從圖3中的收斂曲線對比分析中可以發現，對于多峰問題f2，在經歷了初期的快速收斂過程以后，由于分類變量子種群多樣性的降低，離散子種群的收斂幾乎停滯，而對連續變量子空間的局部開發使得其收斂曲線具有一個長期的緩慢收斂過程。雖然ρ的不同取值需要不同的b的取值相配合來獲得相對較好的收斂效果，但從最終收斂結果來看，當ρ=0.15時，算法的收斂精度最好。這是因為當ρ較小，信息素的揮發速度較慢，信息素值的上限更大，從而使得蟻群具有更好的全局開發能力，無論是對于測試問題f1還是f2都可以得到更加好的全局探索能力，從而提高了CACOAMV在離散子空間的全局探索能力。

圖3 CACOAMV求解f2的收斂曲線Fig.3 Convergence curves of CACOAMV on solving f2

2.2 在目標函數值空間的收斂結果比較

通過參數實驗分析可以看到，較小的參數ρ和b的取值可以在獲得較好的全局探索能力的同時得到較強的局部開發能力。考慮到CACOAMV可以通過重啟機制來提高算法的全局收斂性能，本文中ρ和b都取得了較小的值，如表1所示。對于基準測試函數f1～f6，將 CACOAMV與 ACOMV［8］和L-SHADEACO［15］獨立運行50 次，每次運行記錄1.0E+06 次個體評價以后種群中的最佳目標函數值。若所得到的近似最優解的誤差小于1.00E -10，則認為算法已經收斂到了精確的全局最優解，即近似誤差為0。

表1 算法參數設置Tab.1 Algorithm parameter setting

首先，將三種算法對6 維和10 維測試問題的求解結果進行比較，結果見表2。結果表明，對于單峰的測試函數f1、f5以及在全局最優解附近具有平坦山谷的f4，CACOAMV的尋優成功率均達到了100%，表明CACOAMV在（局部或全局）最優解的吸引區域內能快速收斂到（局部或全局）最優解，具有較好的局部開發能力；對于多模態測試問題f2、f3、f6，CACOAMV的求解性能與ACOMV相比有顯著提升，且其收斂結果也優于LSHADEACO，表明基于協同進化的迭代機制也提高了算法對混合變量可行域的全局探索和局部開發能力。

表2 對6維和10維測試問題f1～f6的實驗結果比較Tab.2 Experimental results of solving 6-and 10-dimensional f1～f6 problems

通過橫向比較可以看到，當測試問題的維數從6 維增加到10 維時，ACOMV和L-SHADEACO的收斂性能發生了較大的退化；相對而言，CACOAMV的收斂結果只發生了輕微的退化現象，對于大多數統計數據均優于其他兩個算法的對應指標。

為了進一步比較算法性能隨著維數的退化速度，將CACOAMV和L-SHADEACO在14 和18 維的測試問題上的優化結果進行比較，所得結果的平均值和標準差如表3所示。

表3 L-SHADEACO和CACOAMV對14、18維測試問題f1～f6的優化結果比較Tab.3 Performance comparison of L-SHADEACO and CACOAMV for solving 14-and 18-dimensional f1～f6 problems

表3 結果表明，CACOAMV在對于單峰和多峰問題的求解性能總體上均優于L-SHADEACO，CACOAMV中所采用的協同進化機制使其具有更好的全局探索和局部開發能力，降低了算法的收斂性能隨著所求解優化問題的維數增加的退化速度。

2.3 在決策變量空間的收斂結果比較

由于不同的測試問題的目標函數值具有迥異的適應值地形，對最優目標函數值的近似誤差不能準確反映其在決策空間中對全局最優解的近似程度，因此，本文將CACOAMV與GA、ACO-DE、GA-DE、ACOMV［8］和DEMV［9］進行了比較。其中，ACO-DE 和GA-DE 采用ACO 和GA 來生成分類變量解，并用經典的DE 算法來生成連續變量子向量。根據CEC’05 的基準測試集［17］中的5個單峰函數和8個多峰函數生成了13個10維的混合變量測試問題（記為F1～F6，F8～F14），測試CACOAMV在決策空間中的收斂性能。

為了得到公平的比較結果，本文對測試函數采用了與文獻［9］相同的設置：每個測試問題中具有5 個連續變量和5 個分類變量，分類變量的取值集合包含100 個均勻分布的離散取值。以50 000次個體評價后所得到的最佳近似結果在決策空間中與全局最優解的距離作為評價指標，經過100 次獨立運行后的平均距離和平均排名如表4 所示。數值實驗結果表明，從決策空間中對全局最優解的近似程度來看，CACOAMV的近似性能整體上來看優于其他五種算法，表明基于協同進化框架下的混合變量優化方法能夠更好地實現混合變量決策空間的協同搜索，大大提高隨機啟發式算法對MVOP 的優化性能。

表4 決策變量空間中的近似性能比較Tab.4 Comparison of approximation performances in decision variable space

3 結語

針對MVOP 中連續變量子空間和離散變量子空間的合作搜索難題，本文提出了一種基于協同進化框架的混合變量蟻群優化算法CACOAMV。通過構建連續搜索空間和離散搜索空間的信息素模型，CACOAMV分別生成連續和離散解向量并通過協同進化機制來實現連續、分類變量解向量的評價和混合決策變量空間的合作協同搜索。通過與信息素平滑機制和重啟機制相結合，CACOAMV具有更強的局部開發能力和全局探索能力，其在混合變量解空間的搜索能力由空間維數的上升所導致的性能退化更加緩慢。由此可見，基于協同進化的隨機啟發式搜索是一種求解MVOP 的有效搜索機制，有望在復雜的高維MVOP中取得令人滿意的優化性能。