融合經(jīng)驗(yàn)共享Q 學(xué)習(xí)的粒子群優(yōu)化算法

羅逸軒，劉建華+，胡任遠(yuǎn)，張冬陽，卜冠南

1.福建工程學(xué)院 計(jì)算機(jī)科學(xué)與數(shù)學(xué)學(xué)院，福州 350118

2.福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，福州 350118

粒子群優(yōu)化算法（particle swarm optimization，PSO）是Kennedy 等受鳥群覓食行為的啟發(fā)，提出的一種群體優(yōu)化算法。自粒子群算法提出以來，因其易于實(shí)現(xiàn)和計(jì)算效率高等特點(diǎn)，在實(shí)際問題中得到廣泛應(yīng)用。但其也存在易陷入局部極小點(diǎn)，搜索精度不足等問題。針對這些問題，國內(nèi)外學(xué)者提出參數(shù)調(diào)整、拓?fù)溥x擇和與其他算法相結(jié)合等不同的改進(jìn)方法。例如，文獻(xiàn)[3-4]提出了自適應(yīng)參數(shù)調(diào)整的粒子群算法，文獻(xiàn)[5-6]通過改進(jìn)拓?fù)浣Y(jié)構(gòu)來優(yōu)化粒子群算法，文獻(xiàn)[7-9]提出將其他優(yōu)化算法（策略）與粒子群算法相結(jié)合，文獻(xiàn)[10-11]將多種改進(jìn)方法同時(shí)優(yōu)化粒子群算法，以上改進(jìn)均提升了粒子群算法的精度與性能。

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

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

1 相關(guān)知識介紹

1.1 粒子群算法

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

1.2 Q 學(xué)習(xí)方法

Q 學(xué)習(xí)方法（Q-learning）是由Watkins 等人提出的一種無模型的強(qiáng)化學(xué)習(xí)方法，其主要思想是通過智能體與環(huán)境的不斷交互，并累計(jì)最大回報(bào)以得到最優(yōu)的策略。Q 學(xué)習(xí)主要組成如圖1 所示。Q 學(xué)習(xí)擁有一個(gè)可以指導(dǎo)智能體選擇具有最大Q 值即最優(yōu)動(dòng)作的Q 表，其更新公式為：

圖1 Q 學(xué)習(xí)主要組成Fig.1 Composition of Q-learning

式中，s、s與a、a分別是第代與+1 代時(shí)的狀態(tài)與動(dòng)作；和分別是學(xué)習(xí)率和折扣系數(shù)，并且都在[0,1]內(nèi)。(s,a)是智能體在狀態(tài)s下執(zhí)行動(dòng)作a所獲得的即時(shí)獎(jiǎng)勵(lì)，(s,a)是智能體在狀態(tài)s采取動(dòng)作a的期望Q 值。

1.3 QLSOPSO 算法原理

QLSOPSO（Q-learning-based single-objective particle swarm optimization）算法是一種基于Q 學(xué)習(xí)的粒子群優(yōu)化算法。如圖2 所示，將粒子群算法的粒子群當(dāng)作Q 學(xué)習(xí)中的智能體，通過一系列的定義，能夠使Q 學(xué)習(xí)對粒子群進(jìn)行自適應(yīng)的參數(shù)控制，以提升粒子群算法的性能。

圖2 QL 與PSO 算法的關(guān)系Fig.2 Correspondence between QL and PSO

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

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

圖4 決策空間狀態(tài)Fig.4 Decision space state

圖5 目標(biāo)空間狀態(tài)Fig.5 Objective space state

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

2 融合經(jīng)驗(yàn)共享Q 學(xué)習(xí)的粒子群算法

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

2.1 粒子的動(dòng)作定義

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

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

表1 動(dòng)作Table 1 Action

2.2 單個(gè)粒子的Q 表

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

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

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

2.3 粒子之間的經(jīng)驗(yàn)共享策略

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

圖7 經(jīng)驗(yàn)共享策略Fig.7 Experience sharing strategy

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

2.4 QLPSOES 算法框架

算法具體偽代碼如下：

輸入：種群、最大迭代次數(shù)。

輸出：最后一代全局最優(yōu)解的適應(yīng)度值。

算法的框圖如圖8 所示。

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

2.5 時(shí)間復(fù)雜度分析

由QLPSOES 算法流程可知，其主要包括如下部分：（1）初始化，時(shí)間復(fù)雜度為(×)；（2）決定粒子的狀態(tài)、動(dòng)作與參數(shù)的時(shí)間復(fù)雜度均為(_×)；（3）粒子進(jìn)行速度與位置的更新，時(shí)間復(fù)雜度為(_××)；（4）計(jì)算粒子適應(yīng)度值，更新個(gè)體最優(yōu)及全局最優(yōu)的時(shí)間復(fù)雜度為(_××) ；（5）更新Q 表的時(shí)間復(fù)雜度為(_×)；（6）判斷迭代是否停止的時(shí)間復(fù)雜度為(1)。因此，算法的時(shí)間復(fù)雜度為(_××)，與標(biāo)準(zhǔn)粒子群算法的時(shí)間復(fù)雜度保持相同。

3 QLPSOES 參數(shù)實(shí)驗(yàn)分析

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

3.1 實(shí)驗(yàn)設(shè)計(jì)方法

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

表2 CEC2013 測試函數(shù)Table 2 CEC2013 benchmark functions

3.2 實(shí)驗(yàn)中三個(gè)定義的備選方案

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

表3 決策空間狀態(tài)參數(shù)設(shè)置Table 3 Setting of decision space state parameters

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

表4 動(dòng)作參數(shù)設(shè)置Table 4 Setting of action parameters

在強(qiáng)化學(xué)習(xí)當(dāng)中，獎(jiǎng)勵(lì)函數(shù)起到引導(dǎo)智能體學(xué)習(xí)方向的作用，若缺乏獎(jiǎng)勵(lì)信息會導(dǎo)致智能體學(xué)習(xí)進(jìn)度緩慢甚至無法學(xué)習(xí)到最優(yōu)策略。同樣，粒子群算法與強(qiáng)化學(xué)習(xí)結(jié)合過程中，獎(jiǎng)勵(lì)函數(shù)的設(shè)定也十分重要。例如，文獻(xiàn)[13，16]都提出不同的設(shè)定方法。本小節(jié)實(shí)驗(yàn)設(shè)置了三種獎(jiǎng)勵(lì)函數(shù)，詳細(xì)的獎(jiǎng)勵(lì)函數(shù)設(shè)置如表5 所示。其中，代表適應(yīng)度，代表位置多樣性函數(shù)，為迭代次數(shù)，代表動(dòng)作行為。

表5 獎(jiǎng)勵(lì)函數(shù)Table 5 Reward functions

3.3 參數(shù)設(shè)置實(shí)驗(yàn)分析

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

本小節(jié)采用正交實(shí)驗(yàn)方法，具體步驟如下：

確定影響因素與因素水平。根據(jù)上文分析，主要影響算法性能的因素分別為粒子的決策空間狀態(tài)、動(dòng)作參數(shù)和獎(jiǎng)勵(lì)函數(shù)。將這三個(gè)參數(shù)設(shè)定為正交設(shè)計(jì)實(shí)驗(yàn)的三個(gè)因素，并分別對應(yīng)因素1、因素2 和因素3，每一個(gè)因素有三個(gè)水平。其QLPSOES參數(shù)因素水平如表6 所示。

表6 參數(shù)因素水平表Table 6 Factors and levels of parameters

設(shè)計(jì)正交實(shí)驗(yàn)表。SPSS（statistical product and service solutions）是一款用于數(shù)據(jù)管理和數(shù)據(jù)分析的軟件，因此本文運(yùn)用SPSS23.0 進(jìn)行正交實(shí)驗(yàn)表的設(shè)計(jì)與分析。

制定實(shí)驗(yàn)方案并實(shí)驗(yàn)。根據(jù)SPSS 設(shè)計(jì)的正交表，本文制定九種實(shí)驗(yàn)方案且不考慮各因素間的交互作用。按照表6 中不同參數(shù)組合的實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn)，運(yùn)行環(huán)境參數(shù)設(shè)置同3.1 節(jié)的情況，評價(jià)指標(biāo)為CEC2013 中28 個(gè)測試函數(shù)Friedman 檢驗(yàn)的rank 得分。實(shí)驗(yàn)結(jié)果如表7 所示。

表7 正交方案與實(shí)驗(yàn)結(jié)果Table 7 Orthogonal experiment and results

實(shí)驗(yàn)結(jié)果分析。本文將通過極差分析法和方差分析法對實(shí)驗(yàn)結(jié)果進(jìn)行分析。極差分析法可以直觀形象地分析主次因素和最優(yōu)組合等，方差分析法能更精細(xì)地分析各因素對結(jié)果的影響程度。

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

表8 極差分析表Table 8 Range analysis

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

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

表10 QLPSOES 參數(shù)組合Table 10 Parameters of QLPSOES

4 QLPSOES 算法的實(shí)驗(yàn)與比較

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

表11 實(shí)驗(yàn)的參數(shù)設(shè)置Table 11 Parameter setting for experiment

4.1 算法的精確性分析

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

表12 函數(shù)測試實(shí)驗(yàn)結(jié)果Table 12 Experimental results of function test

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

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

針對復(fù)雜函數(shù)，QLPSOES 算法在8 個(gè)復(fù)雜函數(shù)中取得4 個(gè)最佳適應(yīng)度值，且在函數(shù)23、24 中的收斂性能與最優(yōu)算法差距較小，有著較好的收斂能力。結(jié)合Friedman 檢驗(yàn)可以看出，QLPSOES 算法處理復(fù)雜函數(shù)的問題的排名明顯優(yōu)于其他對比算法，獲得了最佳的綜合表現(xiàn)，證明了該算法處理復(fù)雜函數(shù)的優(yōu)越性。表13 同時(shí)給出各算法的時(shí)間復(fù)雜度，QLPSOES 算法在與標(biāo)準(zhǔn)粒子群算法持平的復(fù)雜度中取得較好的效果。

4.2 收斂性分析

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

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

圖9 六個(gè)測試函數(shù)的收斂曲線Fig.9 Convergence curves of six test functions

4.3 策略的有效性分析

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

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

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

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

圖10 種群動(dòng)作數(shù)量Fig.10 Number of population actions

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

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

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

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

5 結(jié)束語

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