融合經驗共享Q 學習的粒子群優化算法

羅逸軒，劉建華+，胡任遠，張冬陽，卜冠南

1.福建工程學院 計算機科學與數學學院，福州 350118

2.福建省大數據挖掘與應用技術重點實驗室，福州 350118

粒子群優化算法（particle swarm optimization，PSO）是Kennedy 等受鳥群覓食行為的啟發，提出的一種群體優化算法。自粒子群算法提出以來，因其易于實現和計算效率高等特點，在實際問題中得到廣泛應用。但其也存在易陷入局部極小點，搜索精度不足等問題。針對這些問題，國內外學者提出參數調整、拓撲選擇和與其他算法相結合等不同的改進方法。例如，文獻[3-4]提出了自適應參數調整的粒子群算法，文獻[5-6]通過改進拓撲結構來優化粒子群算法，文獻[7-9]提出將其他優化算法（策略）與粒子群算法相結合，文獻[10-11]將多種改進方法同時優化粒子群算法，以上改進均提升了粒子群算法的精度與性能。

近年來，隨著強化學習發展，使用Q 學習解決粒子群算法的相關問題也逐漸受到國內外學者們的重視。Q 學習作為一種無模型的強化學習方法，具有無需環境模型的優點。因此，Q 學習與粒子群算法的結合可以應用于多種不同類型的目標函數并提升算法性能。文獻[12]通過粒子群算法與強化學習相結合的方法，在噪聲函數問題上取得了良好的效果。文獻[13]提出了一種基于強化學習的模因粒子群優化算法，使用Q 學習幫助算法選擇局部搜索策略，以提升算法的局部搜索能力。文獻[14]提出了一種Q 學習的量子粒子群優化算法，將Q 學習方法用于算法的量子參數控制。文獻[15]利用Q 學習的“經驗”機制，定義了最佳個體的選擇根據其累積績效而不依靠每次評估中的瞬間績效。文獻[16]根據粒子群處在不同拓撲結構時搜索方式的不同，提出將Q 學習控制粒子群的拓撲結構，通過實時選擇最佳的拓撲結構以提升種群的多樣性。文獻[17]提出一種基于Q 學習的自適應在線參數控制的粒子群算法，粒子群算法的參數決定著粒子的搜索行為，通過將粒子的參數選擇作為粒子的動作，依靠Q 學習實時控制粒子參數，以此提升算法性能。

目前，將Q 學習運用到粒子群算法時，其狀態、動作和獎勵等參數的定義都具有主觀性，若定義參數不當，不僅會使粒子缺乏靈活性，并且使Q 表無法收斂并無法有效指導粒子進行動作。在大部分結合的算法當中，僅單一地使用Q 學習來幫助粒子群算法的粒子選擇動作，使得粒子過于依賴Q 學習，導致算法多樣性與學習能力不足。如何將Q 學習與粒子群算法更好地結合，并且定義好參數組合，目前的文獻沒有進一步討論。針對存在的問題，本文對Q 學習與粒子群結合算法的狀態、動作和獎勵函數進行研究與實驗分析討論，選出最優的定義參數組合，并提出了一種粒子之間經驗共享的策略，形成一種融合經驗共享Q 學習的粒子群優化算法（Q-learning PSO with experience sharing，QLPSOES）。對粒子均賦予一個Q 表，通過一種經驗共享策略，在保持粒子自身的搜索機制之外，將粒子之間的Q 表進行了交互學習。不僅能加快Q 表的收斂，更快地學習到最優策略，也增強了粒子之間的學習能力，有利于算法在全局搜索與局部搜索當中的平衡，提升了種群的多樣性與粒子群算法的性能。

1 相關知識介紹

1.1 粒子群算法

粒子群算法是一種群體智能算法。在粒子群中，個體（粒子）通過搜索多維問題解空間，在每一輪迭代過程中評價自身的位置信息（適應度值）。在整個粒子群搜索過程中，粒子共享它們“最優”位置信息，并且受到自身先前最優解的影響來調整它們自己的速度和位置。假設在維搜索空間中，粒子的速度和位置更新公式如式（1）和式（2）所示。

1.2 Q 學習方法

Q 學習方法（Q-learning）是由Watkins 等人提出的一種無模型的強化學習方法，其主要思想是通過智能體與環境的不斷交互，并累計最大回報以得到最優的策略。Q 學習主要組成如圖1 所示。Q 學習擁有一個可以指導智能體選擇具有最大Q 值即最優動作的Q 表，其更新公式為：

圖1 Q 學習主要組成Fig.1 Composition of Q-learning

式中，s、s與a、a分別是第代與+1 代時的狀態與動作；和分別是學習率和折扣系數，并且都在[0,1]內。(s,a)是智能體在狀態s下執行動作a所獲得的即時獎勵，(s,a)是智能體在狀態s采取動作a的期望Q 值。

1.3 QLSOPSO 算法原理

QLSOPSO（Q-learning-based single-objective particle swarm optimization）算法是一種基于Q 學習的粒子群優化算法。如圖2 所示，將粒子群算法的粒子群當作Q 學習中的智能體，通過一系列的定義，能夠使Q 學習對粒子群進行自適應的參數控制，以提升粒子群算法的性能。

圖2 QL 與PSO 算法的關系Fig.2 Correspondence between QL and PSO

該算法設計了一個三維Q 表，如圖3 所示，它由粒子的狀態平面與動作列組成。粒子的狀態平面包括決策空間狀態與目標空間狀態，動作列設置不同動作參數用于控制粒子的探索與開發。其中，粒子的位置與全局最佳位置之間歐幾里德距離（與搜索空間的大小相比）作為決策空間的狀態，如圖4 所示，可以將其分為四種狀態：{最近，更近，更遠，最遠}。粒子與全局最佳適應度值和全局最差適應度值之差的相對性能作為目標空間的狀態，如圖5 所示，可以將其四等分為{適應度值大，適應度較大，適應度較小，適應度值小}。

圖3 三維Q 表Fig.3 3-D Q table

圖4 決策空間狀態Fig.4 Decision space state

圖5 目標空間狀態Fig.5 Objective space state

該算法通過自適應的參數控制，一定程度上提升了算法的性能，但其存在粒子的動作參數選擇不合理與Q 表收斂速度較快等問題，其定義見第2 章。

2 融合經驗共享Q 學習的粒子群算法

在QLSOPSO 算法中，粒子的動作參數存在著主觀性選擇問題，其會導致算法的收斂性能不佳；并且所有粒子僅共享一個Q 表，使得Q 表收斂過快。針對其存在的問題，本文首先確定合適的粒子動作定義，提出將每個粒子均賦予一個Q 表，作為粒子“經驗”，并設計一種經驗共享的策略，即一種Q 表的交互方式，使粒子之間的信息有更多的交流。粒子的動作定義有助于粒子做出最優的行為；單個粒子的Q 表有利于粒子的局部搜索；經驗共享策略增強了粒子的全局搜索能力，以改進算法的搜索性能。

2.1 粒子的動作定義

在圖3 的Q 表中，粒子動作是控制粒子在不同狀態下選擇最合適的搜索行為。因此，動作的定義至關重要，主要由三個參數影響，分別為、和。為慣性權重，和為加速度系數，這三個參數會影響粒子的搜索行為，以決定粒子的探索與開發。決定粒子對當前速度繼承性，越大，全局搜索能力越強，越小，局部搜索能力越強。同樣地，設置較大的，有助于增強全局搜索，而較大的，會促使粒子收斂。

因此本文算法中設置三種動作行為，使其符合粒子的搜索行為，將粒子的動作分為三類：{全局探索（），綜合搜索（），局部開發（）}。每一種動作會對應著不同的動作參數。通過對動作的不同選擇，得到粒子群算法的不同參數，實現對粒子的搜索控制，從而改變粒子的飛行行為。設置方法如表1 所示，而參數的具體設置值在第3章的實驗分析中得出。

表1 動作Table 1 Action

2.2 單個粒子的Q 表

三維Q 表由狀態平面與動作組成，如圖3 所示，其狀態平面由決策空間狀態和目標空間狀態組成。如圖4，決策狀態空間由粒子之間的相對距離衡量，反映了粒子的收斂狀態。如圖5，目標狀態空間由粒子適應度值衡量，直接反映了粒子的性能。如表1 所示，動作決定了粒子的算法參數組合。綜上所述，Q表的狀態平面能夠直觀反映粒子所處的空間環境狀態，而通過獎勵函數更新后的Q 表，可以幫助粒子根據其狀態來決定粒子的參數，因此Q 表對粒子的行為有著至關重要的影響。

本文提出將單個粒子賦予一個獨立的三維Q 表，如圖6 所示。若粒子群僅更新一個Q 表，Q 表的更新會受到每一個粒子的影響，使得Q 表的更新不穩定和收斂速度過快，且不能反映每一個粒子的之前的狀態。單個粒子的Q 表設計，使得每一個粒子均成為“智能體”對環境進行探索。在算法前期通過粒子探索并存儲單獨的“經驗”，而在算法后期再利用Q 表，能對搜索環境得到一個良好的反饋，從而更加準確幫助粒子確定合適的參數，調節種群的全局與局部搜索能力。

圖6 每個粒子均賦予Q 表Fig.6 Q table of each particle

2.3 粒子之間的經驗共享策略

粒子群算法通過改進粒子之間交互方式能夠提升算法的性能，因此，本文設計一種學習經驗共享策略，使得粒子之間具有更強的交互性。由于粒子均擁有一個Q 表，在迭代的過程中，可以將每個粒子的“行為經驗”存儲，而將當前最優位置粒子的Q 表作為“最優Q 表”。在粒子更新Q 表時，將作為“學習”對象，通過最優Q 表的“經驗”更新粒子本身的Q 表，以達到經驗共享。其步驟示意圖如圖7 所示。

圖7 經驗共享策略Fig.7 Experience sharing strategy

通過共享策略，粒子之間的交流通信更像人類社會中人與人之間的相互學習、并向更優秀的人學習的學習方式。通過Q 表的交互，有利于Q 表的收斂。同時粒子保留自身的經驗并能學習最優解粒子的策略，提升了種群的局部搜索能力與收斂于最優解的可能性。

2.4 QLPSOES 算法框架

算法具體偽代碼如下：

輸入：種群、最大迭代次數。

輸出：最后一代全局最優解的適應度值。

算法的框圖如圖8 所示。

圖8 QLPSOES 算法框架Fig.8 Framework of QLPSOES

2.5 時間復雜度分析

由QLPSOES 算法流程可知，其主要包括如下部分：（1）初始化，時間復雜度為(×)；（2）決定粒子的狀態、動作與參數的時間復雜度均為(_×)；（3）粒子進行速度與位置的更新，時間復雜度為(_××)；（4）計算粒子適應度值，更新個體最優及全局最優的時間復雜度為(_××) ；（5）更新Q 表的時間復雜度為(_×)；（6）判斷迭代是否停止的時間復雜度為(1)。因此，算法的時間復雜度為(_××)，與標準粒子群算法的時間復雜度保持相同。

3 QLPSOES 參數實驗分析

在Q 學習與粒子群算法結合時，Q 學習的狀態、動作和獎勵函數等要素的確定對算法有著顯著的影響。因此，粒子的狀態、動作參數該如何設定，使其更加符合粒子的“行為”；獎勵函數該如何設置，使其更加符合算法的收斂方式等。但是，目前文獻對這些要素的設置帶有主觀性選擇與盲目優化等問題，沒有對該問題進行實驗分析。本章通過實驗方法，分析QLPSOES 中三種定義對算法的影響，并采用正交設計法對三個定義進行方案選擇。通過CEC2013測試函數評判不同參數的好壞，以確定最優的參數組合。

3.1 實驗設計方法

本文采用CEC2013 測試集中的28 個基準函數進行實驗分析，28 個函數具體信息如表2 所示。其中1～5 為單峰函數，6～20 為多峰函數，21～28 為復雜函數，不同類型的函數有助于更全面更廣泛地測試算法性能。在每一個維度的搜索范圍均為[-100,100]。其中，種群規模設置為30，維度設置為10維，最大迭代次數設置為50 000，每種算法測試函數運行次數設置為30 次。

表2 CEC2013 測試函數Table 2 CEC2013 benchmark functions

3.2 實驗中三個定義的備選方案

根據上文中的定義，粒子與在不同的相對距離時，決策狀態能夠幫助粒子選擇最優動作。例如，在算法運行后期，若粒子與相距過遠，決策狀態就能使粒子選擇收斂的動作參數。本小節分析實驗確定了三種決策空間狀態，分別命名為決策空間狀態Ⅰ、決策空間狀態Ⅱ、決策空間狀態Ⅲ，其詳細劃分如表3 所示。表示粒子與全局最佳位置之間的歐幾里德距離，Δ表示決策空間的范圍，是指決策空間的上限和下限之差。

表3 決策空間狀態參數設置Table 3 Setting of decision space state parameters

在粒子群算法當中，參數的設定對于算法性能有著較大的影響。許多學者對其的設定進行了研究與分析，例如，文獻[3]推薦為固定的參數值，文獻[23]提出慣性權重隨迭代次數線性減少的策略，文獻[24]提出線性遞減、線性遞增的策略。以上參數方案都提高了算法的性能。但在QLPSOES 算法中，動作是離散的，粒子的參數變化需以離散的形式表示，因此無法直接與連續的參數變化對應，需要選擇合適的動作參數組合使得粒子做出的動作更好地符合實際的需求，以達到探索和開發的目的。本小節實驗中設置了三種動作參數組合，詳細的動作參數組合設置如表4 所示。

表4 動作參數設置Table 4 Setting of action parameters

在強化學習當中，獎勵函數起到引導智能體學習方向的作用，若缺乏獎勵信息會導致智能體學習進度緩慢甚至無法學習到最優策略。同樣，粒子群算法與強化學習結合過程中，獎勵函數的設定也十分重要。例如，文獻[13，16]都提出不同的設定方法。本小節實驗設置了三種獎勵函數，詳細的獎勵函數設置如表5 所示。其中，代表適應度，代表位置多樣性函數，為迭代次數，代表動作行為。

表5 獎勵函數Table 5 Reward functions

3.3 參數設置實驗分析

正交實驗設計是針對多因素多水平問題的設計方法，其借助于一種規格化的正交表來用部分實驗代替全面實驗。正交實驗設計具有實驗次數少、分析方法簡單等優點，能夠通過代表性的少數實驗找出最佳的參數組合。一個三因素三水平的實驗，若采用完全實驗方案，則共需要3=27 次的組合實驗。而利用正交表，只需做9 次實驗就能夠反映實際情況，充分提高了實驗的效率。正交實驗方法作為一種高效處理多因素優化問題的科學計算方法，已經廣泛應用于工業生產及科學研究。

本小節采用正交實驗方法，具體步驟如下：

確定影響因素與因素水平。根據上文分析，主要影響算法性能的因素分別為粒子的決策空間狀態、動作參數和獎勵函數。將這三個參數設定為正交設計實驗的三個因素，并分別對應因素1、因素2 和因素3，每一個因素有三個水平。其QLPSOES參數因素水平如表6 所示。

表6 參數因素水平表Table 6 Factors and levels of parameters

設計正交實驗表。SPSS（statistical product and service solutions）是一款用于數據管理和數據分析的軟件，因此本文運用SPSS23.0 進行正交實驗表的設計與分析。

制定實驗方案并實驗。根據SPSS 設計的正交表，本文制定九種實驗方案且不考慮各因素間的交互作用。按照表6 中不同參數組合的實驗方案進行實驗，運行環境參數設置同3.1 節的情況，評價指標為CEC2013 中28 個測試函數Friedman 檢驗的rank 得分。實驗結果如表7 所示。

表7 正交方案與實驗結果Table 7 Orthogonal experiment and results

實驗結果分析。本文將通過極差分析法和方差分析法對實驗結果進行分析。極差分析法可以直觀形象地分析主次因素和最優組合等，方差分析法能更精細地分析各因素對結果的影響程度。

首先，利用極差分析法對實驗結果進行分析，根據極差值可以確定因素的主次地位。極差分析結果如表8 所示，其中值代表極差值，值反映因素對結果的影響程度，值越大代表影響程度越大。從表8 可以看出，因素1 的值為0.573 3，因素2 的值為4.480 0，因素3 的值為0.883 3。因此動作參數對算法影響較大。三個因素對結果影響程度從大到小依次是動作參數、獎勵函數和決策狀態空間。rank 的評價指標是平均值誤差，因此rank 值越小代表參數組合的性能越優。并通過極差分析法的指標，得出了初步最優組合為。

表8 極差分析表Table 8 Range analysis

同時，也采用方差方法分析實驗結果，方差分析結果如表9 所示。表9 代表的是主體間效應的檢驗，其中值反映因素對結果的影響程度，值越大，因素對結果的影響程度越大；.是因素的顯著性水平，顯著性水平越小，代表其因素對結果的影響程度越大。根據表9 數據，QLPSOES 算法的參數影響排名從大到小為動作參數、獎勵函數和決策狀態空間。方差分析與極差分析得出的排名一致。動作參數的.小于0.05，代表動作參數會對算法性能產生顯著性影響。通過上述實驗結果可得，最優組合為，最終參數組合如表10 所示。

表9 主體間效應的檢驗（因變量：rank）Table 9 Test of intersubjective effect(rank)

表10 QLPSOES 參數組合Table 10 Parameters of QLPSOES

4 QLPSOES 算法的實驗與比較

第3 章通過實驗分析選取最優參數組之后，為了分析比較本文算法的有效性和適用性，本章選取CEC2013 中的28 個標準測試函數進行比較實驗，將本文算法與其他Q 學習結合的粒子群算法（QLPSO-1D、QLPSO-2D、QLSOPSO）、HPSO（hybrid PSO with topological time-varying and search disturbance）和HCPSO（particle swarm optimization based on hierarchical autonomous learning）進行對比實驗。這些算法的參數均采用其原始論文中的參數設置，實驗的參數設置如表11 所示。

表11 實驗的參數設置Table 11 Parameter setting for experiment

4.1 算法的精確性分析

表12 展示了6 種算法在28 個測試函數中的平均適應度值，表13 展示了各算法通過Friedman 檢驗對比的排名。從表12 可以看出，QLPSOES 算法在函數8、11、14、16、18、21、22、25、28 共9 個函數中獲得最優的平均適應度值。結合表13 各算法的秩均值，QLPSOES 以2.55 的平均排名獲得了最佳的綜合性能。

表12 函數測試實驗結果Table 12 Experimental results of function test

表13 算法的弗里德曼檢測與時間復雜度比較Table 13 Friedman test and time complexity comparison of algorithms

在多 峰函數中，QLPSOES 算法在8、11、14、16、18 中獲得最佳適應度值，同時，QLPSOES 算法在多峰函數的rank 排名第二，證明其在多峰函數中有著較好的優化效果。而在單峰函數中，QLPSOES并沒有獲得最優的適應度值，并從Friedman 檢驗可以看出，QLPSOES 的排名為第二，說明QLPSOES 算法在單峰函數中收斂情況一般。

針對復雜函數，QLPSOES 算法在8 個復雜函數中取得4 個最佳適應度值，且在函數23、24 中的收斂性能與最優算法差距較小，有著較好的收斂能力。結合Friedman 檢驗可以看出，QLPSOES 算法處理復雜函數的問題的排名明顯優于其他對比算法，獲得了最佳的綜合表現，證明了該算法處理復雜函數的優越性。表13 同時給出各算法的時間復雜度，QLPSOES 算法在與標準粒子群算法持平的復雜度中取得較好的效果。

4.2 收斂性分析

圖9 是各個算法在部分測試函數中的收斂情況，各在3 種類型的測試函數中選取兩個函數，以表現算法在不同函數模型下的收斂情況。

從圖9（a）和圖9（b）可以看出，QLPSOES 算法在2、4 即單峰函數中與其他算法的收斂速度與收斂精度相當。從圖9（d）和圖9（e）看出，算法在18、23 上都只需較少的迭代次數就能找到全局最優解，有著較快的收斂速度。從圖9（c）和圖9（f）看出，算法不僅前期收斂曲線下降速度快，且在后期也具備一定的尋優能力，且其精度更高。綜合看來，QLPSOES 算法在多峰與復雜函數中較其他算法具有更優的收斂性能。

圖9 六個測試函數的收斂曲線Fig.9 Convergence curves of six test functions

4.3 策略的有效性分析

本文提出將每個粒子均構建Q 表，并通過Q 表進行經驗共享。為了進一步驗證策略的有效性，本文對QLPSOES 算法及其兩種變體QLPSO-A 和QLPSO-B進行比較，算法的具體設置如表14 所示。

表14 對比算法的策略設置Table 14 Strategy setting of algorithms

為了更加直觀地反映策略對算法的影響，以25為例，對三種算法進行比較。圖10 是三個算法的種群動作數量變化圖，其通過種群中的動作數量分布反映整個種群的搜索狀態。圖10（b）所示的QLPSOB 算法中，粒子僅更新一張Q 表，Q 表會快速收斂，使得種群在一定的迭代次數中，做出長時間相同的“動作”；前期幾乎只做出探索的動作，而后期只做收斂的動作，導致前期收斂能力與后期的探索能力不足，容易陷入局部最優解。圖10（a）所示的QLPSO-A 算法，相比僅更新一張Q 表，單個粒子的Q 表前期不易收斂，粒子的更新不依賴于Q 表，其會以原先的更新公式更新速度與位置，使其種群中的動作類型豐富，證明了單個Q 表的設計能夠提升粒子的探索與勘探能力。但在Q 表收斂以后，也存在相同的種群缺乏動作類型的問題。

從圖10（c）可以看出，加上經驗共享策略后種群的動作數量變化更為平滑，提升了粒子動態參數選擇的準確性。通過粒子的參數自適應變化，做全局搜索的粒子總體呈現隨迭代次數減少，做局部搜索的粒子隨迭代次數增加，符合前期探索、后期收斂的策略。種群在保證收斂的同時，保留部分粒子探索，有效地平衡了粒子全局搜索與局部搜索能力。

圖10 種群動作數量Fig.10 Number of population actions

種群多樣性不足是粒子群算法易陷入局部最優點的主要原因。為了體現種群位置多樣性的變化情況，以23 和25 為例，將QLPSOES 與其變體和PSO 進行位置多樣性對比。圖11 給出了4 種算法的位置多樣性的變化曲線。

圖11 位置多樣性Fig.11 Position variety

從圖11 可以看出，PSO 算法的多樣性相比其他算法，在迭代初期就已呈現聚集狀態。QLPSO-B 的種群多樣性的初始范圍相對較大，但收斂速度仍較快，不利于全局搜索。相比QLPSO-B，QLPSO-A 與QLPSOES 算法前期多樣性的范圍不大，但其變化較為穩定，粒子分布均勻，保持較強的探索能力。說明了單個Q 表的策略有利于保持算法的全局搜索能力。但在迭代后期，QLPSO-A 最終的收斂時間較長，不利于算法的局部搜索。QLPSOES 算法加上了經驗共享策略，在中后期加速了粒子的收斂，提升算法中后期種群局部搜索的效果。

綜上所述，在迭代前期，單個Q 表的策略有助于粒子的探索，粒子通過自身運動并累積“經驗”，使得全局搜索能力較強，保持種群多樣性；在迭代后期，累積經驗后的Q 表通過經驗共享策略，幫助粒子依據Q 表狀態選擇最佳參數，提升了局部搜索能力，提高了收斂精度。QLPSOES 能夠在復雜函數取得較好的優化效果的原因在于兩種策略的共同作用，其有利于平衡種群的全局探索和局部探索能力，種群在收斂的同時保持探索，避免了算法陷入局部最優。

5 結束語

本文針對傳統粒子群算法易陷入局部與多樣性不足等問題，提出了一種基于Q 學習且具有經驗共享策略粒子群優化算法。首先利用Q 學習方法，通過每一個粒子賦予的Q 表幫助粒子進行參數選擇，提高了種群多樣性與全局搜索能力。其次，引入學習經驗共享策略，通過強化學習中的“經驗”機制，增強了粒子之間的學習能力，提升了種群的局部搜索能力。通過正交實驗方法，確定了Q 學習方法運用到粒子群算法當中的主觀性參數問題，提升了算法的性能。在CEC2013 測試函數中，與其他多種變體粒子群算法進行比較，驗證了算法的有效性。在未來的工作中，將研究如何將強化學習與其他的進化算法相結合，進一步地提升算法性能。