融合Tent混沌和維度學習的陰陽對算法

李大海，劉慶騰，王振東

(江西理工大學 信息工程學院，江西 贛州 341000)

0 引 言

目前，越來越多的非線性、高維度的工業類優化問題已難以使用傳統優化方法進行求解。隨機搜索算法因為其易于實現，并且具有的靈活性、以及高效性，正被越來越廣泛的應用于此類優化問題。

陰陽對算法(Yin Yang pair optimization，YYPO)是Punnathanam等[1]受中國古代陰陽平衡思想啟發提出的一種輕量級單目標隨機搜索算法，其基于陽點(P1)和陰點(P2)的兩點的交換實現搜索。YYPO算法的優點是設置參數較少，時間復雜度相對較低，缺點是在求解復雜困難的優化問題時，易早熟收斂。

目前已有諸多YYPO的改進算法被提出。Punnathanam和Debasis等[3]提出的改進陰陽對優化算法一定程度上提高了算法的收斂性能，但同樣存在對于優化復雜問題時易早熟收斂的缺陷。Song等[4]提出了一種改進陰陽對算法3D-YYPO(3 dimensional Yin Yang pair optimization)提高了算法的收斂速度。李大海等[5]提出的改進陰陽對算法YYPO-SA(Yin Yang pair optimization with simulated annealing)，實驗結果表明YYPO-SA在統計學意義上擁有更穩定求解的能力以及更高的計算精度，并且YYPO-SA1比YYPO-SA2具有輕微的性能優勢。

本文提出了一種基于YYPO-SA1的改進陰陽對算法YYPO-TP。YYPO-TP采用了以下的2個改進措施：

(1)引入Tent混沌機制優化P1和P2兩點的初始位置的分布。其目的是使生成的P1和P2兩點初始分布更加均勻，以增強算法的全局搜索能力，從而提高算法的性能。

(2)引入關于P1和P2兩點的基于維度學習策略的新分割方式。新分割方式舍棄了原YYPO算法中使用的單向分割與D向分割方式，引入類似于PSO算法中的全局最佳粒子和局部最佳粒子，并使用維度學習策略以等概率進行正向搜索和反向搜索進行P1和P2兩點的分割更新。

為測試YYPO-TP的性能，本文選用了16個CEC2013的測試函數作為性能基準函數，并將YYPO-TP和7個經典的對比算法進行性能測試和比較。并將算法應用在風力發電機的工程優化上也取得了較優效果。

1 YYPO

陰陽對優化算法將所有的決策變量都歸一化處理(介于0到1之間)。若設f(x)，x=(x1，…，xn)∈Rn是待尋優的函數。當YYPO完成歸一化處理后，x應滿足條件：0≤xi≤1，1≤i≤n。

如前文所述，YYPO的核心思想是基于P1和P2兩點的交換機制進行問題最優解的搜索，其中點P1專注于局部搜索，而點P2側重于全局搜索。在基本YYPO中，P1和P2是以參數δ1和δ2為半徑的解搜索空間中的超球體的球心。在搜索時，新的附加點始終產生在兩個超球體的內部，并且周期性的減小δ1和增大δ2。YYPO存在3個用戶自定義的參數 (Imin，Imax，α)， 其中Imin和Imax分別為存檔次數I的最大值和最小值，α是固定的縮放因子。YYPO在搜索時通過縮放因子α按以下的式(1)來控制搜索半徑的縮放

{δ1=δ1-(δ1/α)

δ2=δ2+(δ2/α)

(1)

YYPO同時通過采用等概率的進行單向分割與D向分割在P1和P2為球心的超球體內部產生2D個新的附加點。其中單向分割的更新式(2)如下所示

{NPjk=Pj+r*δ，k=1，2，…D

NPjk=Pj-r*δ，k=D+1，D+2…2D

(2)

D向分割的更新式(3)如下所示

{NPjk=Pj+r*δ/2，Bjk=1NPjk=Pj-r*δ/2，Bjk=0

k=1，2，3，…2D，j=1，2，3…D

(3)

式中：下標表示點數(或行)，上標表示決策變量數(或列)，r是介于0到1之間的隨機數。由于在NP中每個點的每個變量生成一個新的隨機數r，所以需要2D*D個隨機數。B是一個長度為D的二維隨機二進制字符串矩陣。

2 改進陰陽對算法YYPO-TP

2.1 Tent混沌映射

YYPO是根據優化問題的維度D使用簡單的偽隨機數序列初始化P1和P2兩點的位置。文獻[6]表明搜索點的初始位置的分布對于搜索算法的性能有較大的影響。Mirjalili等[7]也在文獻中指出增強初始化尋優點的遍歷性，可以改善其分布均勻性，進而增強算法的全局搜索能力。

混沌是非線性確定系統中由于內在隨機性而產生的一種復雜的動力學行為，具有隨機性規律性和遍歷性等特點[8]。例如，Shao等[6]提出一種用混沌映射改進種群初始點分布的PSO算法，實驗結果表明采用混沌映射改進粒子的初始分布能夠獲取較大的性能改善。Dai等[9]提出一種自適應混沌模擬退火算法，其使用Tent混沌映射改進了初始分布，也提高了算法的優化性能。目前常用的混沌序列是Logistic映射和Tent映射。岳龍飛等[10]發現Tent混沌映射在遍歷性，均勻性和迭代速度方面比logistic混沌映射具有更大優勢。

本文選用Tent映射改進YYPO算法的P1和P2兩點的初始分布。Tent映射公式如式(4)所示

Pia={2Pia-1，0≤Pia-1≤0.5

2(1-Pia-1)，0.5

i=1，2，…D

(4)

其中，初始點P的下標a表示混沌迭代次數，上標i表示初始點P所在的維度，D為初始點的維度，最大迭代次數設為500。Li等[11]發現，當Pia的值為0，0.25，0.5和0.75時，Tent混沌映射會陷入小周期循環，所以當Pia的值為0，0.25，0.5，0.75時，本文采用的方法是重新給Pia賦一個介于0至1的隨機值。

本文使用Tent混沌映射初始化P1和P2兩點的初始位置的具體步驟如下所示：

(1)隨機生成一個維度為D，并且各維的取值都介于0至1之間的初始點P。

(2)將P點每一維度的值Pia根據式(4)進行Tent混沌映射。生成一個新的D維的混沌點，為了避免小周期循環，當新的混沌點Pia值為0，0.25，0.5，0.75時，重新賦一個介于0至1的隨機值。

(3)計算新產生的混沌點的適應度值，繼續進行Tent混沌產生下一個混沌點。

(4)達到最大混沌迭代次數時終止，輸出適應度值最優和次優的兩點，并分別設為P1和P2的初始位置。

2.2 正反向搜索和維度學習策略

由式(2)和式(3)可知，YYPO使用的單向分割和D向分割本質上都不具備方向性并且YYPO的兩點交換策略也只選擇每次分割后得到的最優的兩個點分別作為P1和P2，其沒有充分利用在各維度上已經探索到的有效信息。本文提出了一種新的分割方式，受PSO全局最優點gbest和局部最優點pbest領導粒子群的尋優模式的啟發，新分割方式也引入了全局最優點gbest和局部最優點pbest并以等概率進行正向或反向搜索，同時也引入了Xu等[12]提出的維度學習策略。在新分割方式中，全局最佳點gbest是在當前迭代中適應度最佳的點，初始的局部最優點pbest設為P1和P2兩點位置的維度平均值，后續的pbest則在迭代中通過維度學習策略進行調整。

維度學習策略利用已知的多維信息算法性能，能夠讓算法獲得更多有效的信息增強算法的性能[13]。例如，Xu等[12]提出了一種維度學習策略改進的PSO算法，將種群分為兩個子種群并使用不同的維度學習策略讓個體最佳粒子向全局最優粒子學習。Liu等[13]提出一種維度均值策略改進的PSO算法，利用粒子在多維度空間探索到的有效信息改進算法的個體最佳粒子點，平衡了算法的全局開發和局部探索。

新分割方式采用維度學習的基本思想是讓個體適應度最佳點pbest向全局適應度最佳的點gbest學習。因為在多維度問題中可能不是gbest點的所有維度的值都值得學習，所以應挑選gbest點的某些維度的值進行學習。本文采用的維度學習的偽代碼如下：

輸入：pbest點和gbest點(假設是求優化函數f最小值)

輸出：維度學習策略優化后的pbest點

(1)計算初始pbest點的適應度值f(pbest)。

(2)for i = 1 toD(其中D為優化問題的維度)：

(5)end for循環

(6)輸出經維度學習后的pbest。

圖1 維度學習過程

新分割方式使用正向搜索是為了增加搜索的方向性，因為全局適應度值最佳的粒子gbest和經過維度學習策略的粒子pbest給出了潛在的最優解所在的方向，新分割方式加入反向搜索[14]的策略是讓算法在當前解的反方向進行搜索以進一步提高算法跳出局部最優的能力，因為Rahnamayan等[15]證明當前解存在50%的概率比其反向解更遠離最優解。這種正反向搜索的思想也和陰陽對算法中基本的陰陽轉換的思想相契合。YYPO-TP的分割方式仍保留了YYPO分割方式中將P1和P2復制2D份存儲在NP中的操作，NP可視為一個2D*D維度的矩陣。其具體的分割公式如下

{NPjk=Pj+(c1*r1*(pbestj-Pj)+

c2*r2*(gbestj-Pj))*δ，r<0.5

NPjk=Pj-(c1*r1*(pbestj-Pj)+

c2*r2*(gbestj-Pj))*δ，r≥0.5

k=1，2，3，…2D，j=1，2，3…D

(5)

其中，gbest是全局適應度值最佳點，pbest是經過維度學習策略后的點，δ是搜索半徑，NPjk是指復制的2D個點中的第k個點的第j維，Pj是進行分割操作點的第j維，c1和c2是權重系數并都設為2，r，r1，r2是介于0至1之間均勻分布的隨機數。當隨機數r<0.5時，算法專注于側重性更好的正向搜索，當隨機數r≥0.5時算法在當前解的反方向進行探索更新。等概率的進行正向反向兩種探索方式也象征著陰陽平衡。

YYPO-TP算法的偽代碼如下：

輸入：待尋優函數法f(本文求優化函數的最小值)，用戶自定義參數 (Imin，Imax，α)。

輸出：全局最優點gbest的適應度值f(gbest)和位置

(1)初始化隨機生成一個維數為D，取值范圍在[0，1]之間的點P，將點P進行Tent混沌迭代200次，計算經過混沌后的所有點的適應度值。適應度最優的點設為P1，適應度次優的點設置為P2。

(3)當不滿足迭代終止條件時對P1和P2兩點分別按式(5)進行分割各生成2D個點。對于點的每一維都生成一個隨機數r，若r<0.5，進行正向搜索分割更新，若r≥0.5，則進行反向搜索分割更新。

(5)將更新后兩點存儲在檔案中，分割次數i=i+1，判斷i是否等于存檔數I，達到則選出存檔中最優的兩個點分別賦值給P1和P2。按照維度學習策略更新pbest。

(6)按照式(1)進行搜索半徑更新，清空存檔數據生成新的存檔數。直到迭代終止。

2.3 時間復雜度分析

和原YYPO算法相同，YYPO-TP算法迭代的時間復雜度也與求解問題的維度D直接相關。在YYPO-TP初始化階段，其對P1和P2兩點進行賦值時間復雜度為O(2D)。初始化后，進行混沌遍歷的時間復雜度為O(D2)，算法進入第一次存檔后便進行分割階段，分割階段分割方式雖然改變，但依舊是復制了2D份副本進行更新，時間復雜度為O(D2)。適應度評估階段對所有的點進行縮放，所以時間復雜度為O(2D*D)=O(D2)。 如果到達存檔數I，則存檔階段時間復雜度為O(I)，存檔階段內的維度學習策略的時間復雜度是O(D2)。

3 實驗結果與分析

3.1 實驗設計

為了驗證YYPO-TP算法的有效性，本文從于2013年IEEE進化計算大會中舉行的單目標實參算法競賽所使用的28個測試函數中選擇了16個代表性的測試函數(其中4個單峰函數f1-f4，7個多峰函數f5-f11，5個復合函數f12-f16)作為實驗的性能基準函數。各測試函數的參數取值范圍統一設置為[-100，100]。各測試函數名稱以及全局最優點見表1。

表1 測試函數

本文實驗選取了YYPO-SA1、YYPO以及其它5個具有代表性的高性能單目標算法：烏鴉搜索算法(crow search algorithm，CSA)、粒子群優化算法(particle swarm optimization，PSO)、鯨魚算法(whale optimization algorithm，WOA)、花授粉算法(flower pollination algorithm，FPA)、麻雀算法(sparrow search algorithm，SSA)與YYPO-TP進行性能比較。為了減少參數不同引起的差異，YYPO-TP和YYPO-SA1的3個用戶自定義參數 (Imin，Imax，α) 的設置都參考原YYPO算法中的設置。PSO、CSA、WOA、SSA、FPA都是按照原文獻中使用的參數進行設置，并且種群數目統一設置為30。

在實驗中，將YYPO-TP、YYPO-SA1以及上述的6個算法分別在維度為10維、30維、50維的測試函數f1-f16獨立運行50次，每一次算法的迭代次數2500次，考慮文章篇幅，僅列出算法在50維下的測試結果。取每50次運行后，各算法獲得的測試函數的最優解的均值(Mean)和方差(Std)兩項指標來評估各個算法的優化性能和穩定性。同時本文采用了排名(Rank)方法。排名的標準是首先比較各個算法的均值，均值越小，算法名次越好。若均值相等，再比較各自的方差，方差越小，則算法名次越好。

3.2 實驗結果分析

表2給出了各參與測試的算法對于16個測試函數在50維的測試的結果。各表中的最后3行中的Count表示排名為第一的總次數，Ave Rank表示平均排名情況，Total Rank表示基于Ave Rank排序的總排名情況，最優者用加粗表示。YYPO-TP在16個測試函數上取得10次最優，7個多峰函數6次排名第一，5個組合函數4次排名第一。其表明，隨著測試函數維數的提升，YYPO-TP在多維函數上的性能上依舊優秀。同時，YYPO-TP的Ave rank值為1.69，仍排名第一。這表明YYPO-TP在高維的測試函數上能保持較為穩定的優化性能。

表2 維度為50時算法的比對結果

3.3 Friedman檢驗

為了驗證新算法YYPO-TP的改進是否有效，文本基于上述的實驗數據，應用Friedman檢驗從統計學角度檢驗YYPO-TP算法優勢的顯著性。

Friedman檢驗的統計值Ff計算公式如式(6)所示

Ff=12nk(k+1)[∑jR2j-k(k-1)2/4]

(6)

Rj=(1/n)∑ni-1rji， 是所有問題中求出每個算法的平均排名，Ff的值越小，各算法之間的差異的顯著性水平越高。

依據實驗數據，對YYPO-TP和參與實驗的其它算法分別進行Friedman檢驗。檢驗結果見表3，其中表中的P-value值即是式(6)的計算結果Ff， 表中其它的值是各算法的平均排名秩Rj。 從表3里面可以看出YYPO-TP在維度10維、30維、50維的16個測試函數上，通過Friedman檢驗獲得的漸進顯著性P-value值均遠遠小于0.01，并且維度越高差異性越大。這主要是由于對比算法隨著維度的提升而精度下降。這個事實表明本文提出的算法YYPO-TP的尋優性能相比于參與評測的其它算法在統計學意義下有顯著的優勢。

表3 Friedman檢驗結果

3.4 收斂情況分析

為了驗證YYPO-TP的收斂性能，圖2分別給出了YYPO-TP、YYPO與YYPO-SA1、WOA、PSO、CSA、SSA、FPA在50維的8個測試函數上的算法隨迭代次數收斂曲線。圖中的橫坐標表示迭代次數，縱坐標表示算法在當前迭代次數中找到的被測函數的收斂精度。

圖2 收斂曲線

從單峰函數的收斂圖2(a)、圖2(b)中，可以看出YYPO-TP，YYPO和YYPO-SA1的收斂精度要高于其它比對算法雖然在單峰測試函數上，YYPO-TP的收斂精度不如YYPO-SA1，但二者的收斂速度都明顯快于對比算法。

圖2(c)、圖2(d)、圖2(e)、圖2(f)顯示的是各參評算法在4個50維的多峰測試函數上伴隨迭代次數的收斂圖。相比于單峰函數，多峰函數都具有較多的局部最優點。可以觀察到，在多峰測試函數上，YYPO-TP在圖2(c)、圖2(d)、圖2(e)、圖2(f)這4個函數上達到最高的收斂精度且其達到最佳收斂精度明顯優于YYPO-SA1和YYPO和其它4個對比算法。

圖2(h)、圖2(g)顯示的是復合測試函數上伴隨迭代次數的收斂圖。復合函數存在較多的局部最優點。在50維的測試函數上，YYPO-TP無論是收斂速度和還是收斂精度都與YYPO非常接近，并且在組合函數圖2(h)、圖2(g)上，兩者的表現都明顯強于其它的對比算法。這表明YYPO-TP可以對復雜目標函數進行有效快速搜索的單目標優化算法。

根據以上分析，YYPO-TP是一種高效的單目標優化算法，并且YYPO-TP對于YYPO的改進措施是有效的。

4 高海拔風力發電機

能源需求的快速增長導致世界能源發展逐漸轉向可再生能源。在各種可再生能源中，風能正迅速發展。據統計，至2018年，全球的風電總裝機容量已達591 GW[16]。與傳統能源技術相比，風能具有較高的發電成本。因此，有必要進一步降低風能的成本，使其更具競爭力。風力發電機的設計目標是通過優化風力發電機組參數來優化風力發電機的性能，并降低生產成本。隨著海拔的升高，空氣密度和氣壓發生變化，其對風力發電機成本和生產率的影響不容忽視。具體表現為成本增加，生產率降低，導致能源成本增加[4]。為了使經濟效益最大化，可以選擇不同的技術經濟模型來分析風電場的投資和建設可行性。其中，COE(cost of energy)是最常用的評價指標。COE是指每生產1 KWh電能的成本，包括年能源生產成本和年能源產量。目前，風力發電機組優化設計中廣泛使用的COE模型主要來自“國家可再生能源實驗室風力發電機組設計成本和比例模型”的研究成果[17]。

該模型由兩部分組成：年生產成本(annual production cost，APC)和年發電量(annual energy production，AEP)。COE的獲得表達式可由年生產成本與年發電量的比值得到，如式(7)所示

COE=APCAEP

(7)

本文使用參考文獻[4]中關于高海拔風力發電機的設計參數優化模型進行實驗，該模型具體的表達式如式(8)所示

COE=0.00622R3.5+0.07756R3+0.0612R2.946+0.009426R2.887+0.3508R2.6578+1.3377R2.531744.992ρπR2(∫VrVcf(v)dv+∫VfVrV3rf(v)dv)+

0.5297R2.5025-0.00701R2.5+0.06901πR2H+5.343R1.953+23.9347R+55.7435H0.4037R0.80741744.992ρπR2(∫VrVcf(v)dv+∫VfVrV3rf(v)dv)+4.041×10-7P3r-0.002445P2r+2.096P1.249r+15.0656Pr+6.8004Pr+0.00108AEP(1-halt/15000)1744.992ρπR2(∫VrVcf(v)dv+∫VfVrV3rf(v)dv)+

8265.6416+(0.2082P3r-0.006P2r+49.4518Pr+0.5133H1.1736R1.1736)(1+hait/15000)1744.992ρπR2(∫VrVcf(v)dv+∫VfVrV3rf(v)dv)+0.007(1+halt/15000)

(8)

其中，R是風力發電機輪廓轉子的半徑，ρ是空氣密度，H是風力發電機輪廓的高度，Vc是讓風力發電機工作的最小風速，Vr是風力發電機達到額定功率發電的額定風速，Vf是風力發電機工作的最大風速，超過最大風速發電機會停止發電，Pr是風力發電機的額定功率，halt是發電機所在的海拔高度。

因為制作工藝對于輪廓轉子半徑R和輪廓轉子高度H和額定功率Pr有著一定的約束關系，所以為了滿足結構約束，輪轂高度設定為轉子半徑的1.5～3倍，額定功率設定為轉子半徑的20～40倍。為了公式化這個優化問題，適應度函數和結構約束如式(9)所示

{COEmin(R，H，Pr)=min(COE(R，H，Pr))

1.5R

Rmin≤R≤Rmax，Hmin≤H≤Hmax，Pminr≤Pr≤Pmaxr

(9)

本文實驗的參數設置半徑R的范圍為20 m～50 m，高度H的范圍為10 m～150 m，功率Pr范圍為100 kw～3000 kw，工作最小風速Vc和最大風速Vf分別為3 m/s和25 m/s。使用風機優化的原文獻[4]中提出的3D-YYPO算法與YYPO-TP算法分別對于海拔高度為2000 m、3000 m、4000 m的3種情況來優化的風機的3個參數：輪廓轉子的半徑R、輪廓轉子高度H、額定功率Pr以及COE。3D-YYPO的參數參考文獻進行設置。YYPO-TP的參數與前述實驗使用的設置相同。

不同海拔高度下兩種優化算法得到的風機最優參數見表4。YYPO-TP獲得的最小COE值和相應的參數要優于3D-YYPO。當高度從2000 m 增加到4000 m 時，轉子半徑R有著些許的減少，輪轂高度從59.1275 m變化到59.0243 m，額定功率從0.5172兆瓦變化到0.5149兆瓦，COE從0.016 723千瓦小時增加到0.020 441千瓦小時。即隨著海拔高度的升高平均每千瓦時發電量的成本在增加，原因主要是海拔升高空氣密度變小，以及維護的成本增加。從表4中的COE值來看，YYPO-TP要明顯優于3D-YYPO。

表4 不同海拔高度下算法優化得到的最優結果

5 結束語

本文提出的YYPO-TP算法是在YYPO算法基礎上運用Tent混沌策略增強算法P1和P2點初始位置分布的均勻性，引入基于全局和局部最優點導向的正向和反向分割機制并利用了維度學習策略，以更好利用已知探索到的有效信息增強算法的搜索能力?；?6個測試函數上的測試結果，應用Friedman檢驗，YYPO-TP在統計學意義上優于YYPO和YYPO-SA1，并顯著優于其它參與評測的5個算法。在高海拔風力發電機的設計參數優問題上，YYPO-TP也能獲得優于3D-YYPO的優化性能。

YYPO-TP算法在單峰函數上效果不理想，這可能與算法設計的分割模式有關，過強的隨機性可能讓算法在只有一個全局最優點的單峰測試函數無法快速獲得最優解。這也是今后值得改進的一個方向。