基于深度確定性策略梯度的粒子群算法

魯華祥，尹世遠，龔國良*，劉 毅，陳 剛

(1. 中國科學院半導體研究所 北京 海淀區 100083；2. 中國科學院大學微電子學院 北京 海淀區 100089；3. 中國科學院腦科學與智能技術卓越創新中心 上海 松江區 200031；4. 半導體神經網絡智能感知與計算技術北京市重點實驗室 北京 海淀區 100083)

群智能優化算法屬于隨機優化算法的一種，包括經典粒子群算法(particle swarm optimization, PSO)[1]、鯨魚群算法(whale optimization algorithm, WOA)[2]、灰狼算法(gray wolf optimization algorithm, GWO)[3]、蝙蝠算法(BAT)[4]等，這些算法都是模擬大自然中某種生物的生活習性而創造的算法。

PSO[1]是一種群智能優化算法，其原理是模仿鳥群捕食和聚集的行為，并采用計算機模擬的方式創造一種隨機優化的算法。該算法自首次提出開始就受到廣泛關注，其優勢主要在于它簡單的基本原理、較少的參數和快速的收斂速度。該算法已經廣泛應用于工業生產[5]、礦山[6]、煤炭[7]、水電調度[8]等領域。

但PSO 算法也有一些不足。傳統PSO 算法可以很好地工作在低維問題上，但是在高維問題上經常表現很差。另外，PSO 算法在求解復雜問題時，經常會被困在局部最優點中，過早地收斂[9]。研究者對PSO 算法存在的問題進行了很多改進。文獻[10]首次提出了慣性權重，文獻[11]首次提出了收縮系數。這些方法都通過控制算法的一些運行參數較好地平衡了算法的探索能力和挖掘已有信息的能力。自組織層次化粒子群算法[12]通過采用一個隨時間變化的參數，提升了算法的收斂能力。文獻[13]提出了一種自適應粒子群優化算法，通過進化狀態估計將種群狀態劃分為探索、開發、收斂和跳出4 種狀態，然后根據這4 種狀態自適應地調整慣性權重和加速度系數。文獻[14]通過將粒子位置的各維度進行逐通道學習避免了PSO 算法在優化過程中經常出現震蕩的問題。文獻[15]提出了無速度約束多群粒子群優化，通過加入約束處理技術，在優化可行域之前將總體搜索引向搜索空間的可行區域，使得PSO 算法可以解決約束優化問題。文獻[16]提出了基于末端彈性機制和交叉轉向機制的粒子群算法，通過引入非線性慣性權重和彈性機制，更好地平衡了算法的利用與開發。文獻[17]提出了一種具有變異算子的粒子群優化算法，通過將種群分為不同的亞群，引入非均勻突變算子，增加高斯變異操作，提高了算法的探索能力。

這些改進方法具有一個共同的特點，即通過人工對算法的超參數進行設置，只有經過多次反復嘗試才能得到一個相對較優的參數組。近年來，隨著機器學習和強化學習的興起，神經網絡逐漸展現出強大的參數搜索能力。優化問題的目標是優化一個函數的值，而每步之間該值的差非常適合作為強化學習中的獎勵基準來使用。這使得在群智能算法領域應用強化學習成為可能。

但是，在傳統的連續控制領域，動作空間十分巨大并且動作值均為連續的實數值。這使得強化學習智能體直接從像素級別信息進行學習變得十分困難。近些年Google DeepMind 團隊提出了一種新型的深度強化學習算法：深度確定性策略梯度算法(deep deterministic policy gradient, DDPG)[18]，其在很多連續控制問題上表現突出，比如Atari 電子游戲[18-19]，但尚未有人將該算法與群體智能算法相結合來進行研究。

本文提出了一種基于深度確定性策略梯度的粒子群優化算法，在原有的粒子群算法中引入神經網絡來動態調節算法的收斂速度。通過提前訓練，獲得一個動作網絡，然后應用動作網絡求解優化問題。對改進的算法進行仿真驗證，在多種測試函數上與其他優化函數進行對比，得出DDPGPSO 有了更高的尋優速度和精度。

1 提出算法的基本原理

本文首先介紹基本的粒子群算法，然后介紹DDPG 的基本思想，最后介紹融合了DDPG 的粒子群優化算法DDPGPSO。

1.1 粒子群優化算法

粒子群優化算法是一種群體智能的算法。這種算法源于對鳥群捕食和聚集行為的研究，通過設計一種無質量的粒子來模擬鳥群中的鳥，粒子僅具有兩個屬性：速度和位置，速度代表移動的快慢，位置代表移動的方向。每個粒子在搜索空間中單獨的搜尋最優解，將其記為當前個體極值，并將個體極值與整個粒子群里的其他粒子共享，找到最優的個體極值作為整個粒子群的當前全局最優解，粒子群中的所有粒子根據自己找到的當前個體極值和整個粒子群共享的當前全局最優解來調整自己的速度和位置。其具體流程如下：

假設種群中含有m 個粒子，解空間的維度是n，每個粒子代表解空間中的一個點。粒子i 包含一個n 維的位置向量(x1,x2,···,xn)和速度向量(v1,v2,···,vn)。每個粒子通過學習它的最優歷史位置和全局最優位置來更新速度和位置，更新公式如下：

式中，i=1,2,···,m，j=1,2,···,n，m 和n 分別是種群數量和解空間的維度；vij和xij分別代表粒子i 的第j 維的速度和位置；xpbestij代表粒子i 的歷史最佳位置；xgbest代表種群內的歷史最佳位置；c1和c2是控制加速的參數；r1j和r2j是兩個均勻分布于[0,1]區間的隨機數。最大速度參數vmaxj被用來將每個粒子的速度控制到一個合適的區間中。如果|vij|＞vmaxj，則令vij=vijvmaxj/|vij|。為了平衡種群的探索和挖掘能力，文獻[9]提出了速度慣性權重來控制速度，式(1)被修改成：

式中， ω一般設置為從0.4～0.9 隨時間線性遞減。在搜索過程中，慣性參數 ω的這種變化確保算法在早期擁有強大的全局探索能力，在后期擁有強大的局部搜索能力。

1.2 深度確定性策略梯度原理

在標準的強化學習環境中，每一個智能體與環境進行交互，最終目標是最大化環境收益。這種互動過程被格式化地描述為馬爾科夫決策過程(MDP)，可以通過四元組(S, A, R, P)來描述這個過程。S 是狀態空間，A 是動作空間，R：S×A→R 是獎勵函數，P：S×A×S→[0,1]是轉移概率。在這個環境下，一個智能體會去學習一個策略π：S→A來最大化在環境中的收益：

式中，T 是交互結束時前進的步數；r(si,ai)是在環境si中執行ai所獲得的收益。通常情況下環境中的長期收益會通過參數γ來縮減：

一般用動作價值函數代表在s 環境中執行a 動作的長期收益：

通常使用貝爾曼方程來尋找這種最優的動作價值函數：

然而，這種方式只適合于那些動作和狀態空間都是離散情況的場合。為了應用強化學習到動作空間和狀態空間為連續情況的問題，DDPG 設計了兩個深度神經網絡，分別是動作價值網絡Q(st,at|θQ)和動作網絡μ(st|θμ)，其中 θQ和 θμ為網絡參數。動作網絡μ(st|θμ)就是一個對應狀態空間和動作空間的映射，可以直接根據狀態產生需要的動作。動作價值網絡Q(st,at|θQ)用于接近動作價值函數，并且可以為動作網絡的訓練提供梯度。

對這種動作價值網絡的訓練是要最小化損失函數：

式中， Q′是目標價值網絡，從 Q網絡同步權重。而動作網絡參數的更新需要策略梯度算法，其梯度更新方向為：

1.3 基于深度確定性策略梯度的粒子群優化算法原理

1.3.1 迭代參數改進原理

標準的粒子群優化算法在運行過程中，參數都是確定的，如式(3)所示。也有一些文獻采用提前設置參數變化形式的方式來自動修改參數[20]，但其實質仍是在開始運行時就已經確定，無法根據后續情況進行變化，不能達到最佳的算法效果。為了增加算法的自動調整能力，提高算法的尋優和收斂能力，本文引入了動態自適應參數調整算法，根據當前運行的情況來生成下次迭代所需的參數。改進后的速度更新公式為：

式中，t 為當前的迭代次數；G 為生成函數，本文使用神經網絡作為生成函數，這樣就可以在迭代過程中動態生成運行參數。

1.3.2 參數生成改進原理

隨著PSO 各種改進方式越來越復雜，越來越多的參數需要進行設定，但人工設定各種參數不僅麻煩，而且也不一定能獲得最佳性能。加入了參數生成函數后，所需調整的參數量更加巨大，迫切地需要一種自動化的方式來自動配置算法。但是，由于這種優化效果本質上也是一個優化的問題，是不可求導的，也沒有合適的損失函數可供使用，傳統的深度學習算法無法應用到這種優化問題之中。因此，本文利用DDPG 算法，創建一個智能體，通過跟算法的交互自動習得參數。

該算法所使用的狀態空間為六維，前5 個維度代表群智能過去的平均適應性函數的變化量，最后一個維度代表當前的迭代次數，其計算公式為：

式中，fitmeant代表粒子群在第t 輪循環時所有粒子解的平均值；Tmax代表迭代的最大次數；Sit表示第t 輪循環、第i 維的狀態向量。

算法的動作空間為三維，動作值介于-1～1 之間，通過線性變換將動作映射到合理的區間。三維動作分別對應式(3)中的 w，c1，c2，其中c1，c2變換到0.5～2.5 區間，w 變換到0.1～0.9 區間。線性變換公式為：

式中，a0，a1，a2分別為動作的3 個維度。算法的獎勵值設置如下：當PSO 在當前環境最佳值發生變化，則獎勵為1，否則獎勵為-1：

這樣設置是為了讓網絡尋找參數，使原有算法更快地對問題進行優化，提高算法的尋優速度。

1.4 算法步驟

1.4.1 訓練步驟

1)初始化訓練所需參數：訓練最大次數TrainMax，當前訓練次數episode =1；

2)隨機初始化動作網絡μ(s|θμ)和動作價值網絡Q(s,a|θQ)的參數 θQ和 θμ，具體結構如表1～表2所示；

3)初始化目標網絡 Q′和 μ′，其權重值從Q 和μ復制過來；

4)初始化回放緩存R；

5)初始化環境(粒子種群)Xi(i=1,2,···,Q)，計算每個個體Xi的適應度值F，得到初始最優位置X*，當前迭代次數t=0，最大迭代次數Tmax；

6) For episode=1, TrainMax do

7)初始化一個隨機過程來對動作進行探索；

8)接收環境的初始化觀測s1；

9) for t=1, Tmaxdo

10)根據當前的策略和探索噪聲選擇動作：

11)在環境中執行動作at并觀察獎勵回報rt和新的狀態st+1；

12)將(st, at, rt, st+1)保存到緩存R 中；

15)通過采樣的動作策略梯度來更新動作網絡：

16)更新目標網絡函數的權值：

17) end for

18) end for

19)保存訓練好的動作網絡權重，用于之后的優化問題。

表1 動作網絡結構

表2 動作價值網絡結構

1.4.2 優化步驟

1)初始化粒子種群xi(i=1,2,···,Q)，計算每個個體xi的適應度值，得到初始的全局最優位置x*，最優解F*，當前迭代次數t=0，最大迭代次數Tmax；

2) while t ＜ Tmax

3)計算當前狀態，更新全局最優值；

4)根據動作網絡μ(s|θμ)和當前狀態，獲取當前動作，由式(15)轉化為群探索參數；

5) for i = 1∶Q

6)應用式(3)更新Xi的速度vi；

7)應用式(2)更新Xi的位置xi；

8) end for

9) end while

2 實驗仿真測試

本文將DDPGPSO 算法同飛蛾撲火算法(moth flame optimization, MFO)、布谷鳥算法(CUCKOO)、蝙蝠算法(BAT)、烏賊算法(cuttlefish algorithm, CFA)、多元宇宙算法(multi verse optimizer, MVO)、鯨魚算法(WOA)、細菌覓食算法(bacterial foraging optimization, BFA)8 種常用的優化算法，以及一種粒子群算法的變種混沌粒子群算法(a chaotic pso algorithm based on sequential algorithm, CPSOS)[20]進行實驗對比，參數設置如表3 所示。由于本文主要驗證DDPGPSO 的參數生成能力，為了保持一致，CPSOS 的一些復雜操作不予考慮。選用了8 個常用的基準測試函數[21](F1～F8)如表4 所示，最優值均為0。對于所有的算法和測試函數，算法的參數設置如下：最大迭代次數設為100，種群數量設為40，重復計算10 次，采用平均值(mean)、標準差(std)和迭代中的最優值(best)來評價算法的性能，F1～F8 的迭代圖分別如圖1～圖8 所示。在這些測試中，所有的優化算法的初始值均隨機生成，在解空間中符合均勻分布。由于畫圖中采用對數坐標作為縱坐標，為了防止在算法搜索到最優值0 時產生無意義數據，所有繪圖的y 數據均增加了一個極小值。圖2 和圖4 中的DDPGPSO 由于已經搜索到最小值0，對數圖中會產生無窮小，因此刪去部分末尾數據。

表3 算法參數設置

表4 基準測試函數

圖1 F1 迭代圖

圖2 F2 迭代圖

圖3 F3 迭代圖

圖7 F7 迭代圖

圖4 F4 迭代圖

圖5 F5 迭代圖

圖6 F6 迭代圖

圖8 F8 迭代圖

表5 為8 種算法在8 個測試函數的實驗結果對比，可以看出，DDPGPSO 在F2、F4 函數上直接搜索到了最優值，而在其他函數上雖然沒有搜索到最優值，但是與其他算法相比，在尋優精度上也有很大提高，另外，在F5 和F8 中，雖然算法不是第一名，但是所搜索出的最優值與第一名相比較，差距也在10%以內，說明DDPGPSO 在各種情況下的性能都處于較好水平。另外可以看到，CPSOS在多種情況下也優于標準粒子群網絡，說明采用人工方式對參數進行一些設定也可以優化算法性能。而DDPGPSO 在大多數情況下優于CPSOS 也證明了機器學習在參數生成方面相較于人工方式的優勢。

從圖1～圖8 可以看出，DDPGPSO 算法相較其他算法在收斂速度上提升明顯，另外在多個測試函數中也取得了更好的測試結果。這種結果與強化學習中設定的更快收斂的獎勵是一致的。這說明通過強化學習對PSO 進行訓練可以顯著改善算法的各項性能，同時在多個函數測試項目上也取得了更好的收斂精度。

表6 為DDPGPSO 在不同迭代次數情況下的結果。可以看出，在迭代次數增加到500、1 000 后，DDPGPSO 仍是幾種對比算法中最有競爭力的算法，在平均排名和排名第一的百分比兩項參數上都有很大優勢，也說明了該算法的優越性和強化學習應用于群智能算法的潛力。

表5 實驗結果對比

綜上所述，基于深度確定性策略梯度算法的粒子群優化算法(DDPGPSO)相較于其他同類別算法具有更高的尋優精度，更快的收斂速度，能夠有效解決高維度的復雜數值優化問題。基于強化學習的群優化算法相較于手工設定參數的群優化算法擁有更好的尋優能力與探索能力。

3 結 束 語

粒子群優化算法是模擬鳥群和魚群的覓食和聚集行為而提出的一種群智能優化算法。本文提出了一種基于深度確定性策略梯度的粒子群算法(DDPGPSO)，利用強化學習的手段來自動控制參數的變化，提高了原有PSO 算法的收斂精度和收斂速度。通過測試算法在基準測試函數上的效果，驗證了該算法的有效性和可行性，為以后強化學習與群智能算法的結合提供了一種方案。結果表明，同其他 9 種優化算法相比，DDPGPSO 算法求解質量取得了很好的效果。今后的研究工作一方面會通過更多的實驗來驗證并改進算法的性能，另一方面將探索DDPG 與其他算法結合是否能產生更好的效果。