基于Q學習的代理模型輔助優(yōu)化算法

一、前言

進化算法常被用于解決各種優(yōu)化問題。然而，傳統(tǒng)的進化算法需要大量的目標函數(shù)評價才能獲得一個可接受的解。在實際應(yīng)用中，一次目標函數(shù)評價可能耗時數(shù)分鐘至數(shù)小時（如仿真模擬、物理實驗），這類問題被稱為計算昂貴優(yōu)化問題[。為了解決這個問題，研究人員在優(yōu)化算法中使用代理模型來替代目標函數(shù)，稱為代理模型輔助的優(yōu)化算法。在代理模型輔助的優(yōu)化算法中，需要選擇樣本點使用目標函數(shù)進行評價，并對代理模型進行更新。選擇樣本點的策略已經(jīng)成為一個重要的研究問題。面對日漸復雜的應(yīng)用問題，單一的模型和優(yōu)化方法已經(jīng)不能滿足需求，需要根據(jù)算法的搜索情況動態(tài)切換代理模型和算法，當前多模型協(xié)同方法在模型切換策略方面依賴人工經(jīng)驗，缺乏自適應(yīng)性。

盡管代理模型輔助優(yōu)化已取得一定進展，但其性能仍受限于固定的模型一優(yōu)化器組合框架。因此，如何實現(xiàn)動態(tài)策略選擇成為亟待解決的關(guān)鍵問題。Q學習技術(shù)可以通過Q表評估模型一優(yōu)化器組合的收益，使算法在不同問題下自適應(yīng)地選擇適合的策略。

二、相關(guān)理論

（一）Kriging模型

Kriging模型[2是一種非參數(shù)型模型，常用于地理科學、優(yōu)化設(shè)計等領(lǐng)域，其功能函數(shù) 的數(shù)學表達式為：

其中， 為基函數(shù)，多為常數(shù)、一次回歸多項式、二次回歸多項式， β 是相應(yīng)的回歸系數(shù)， 是均值為0、方差為 的隨機過程。

（二）徑向基函數(shù)網(wǎng)絡(luò)（RBF）

徑向基函數(shù)網(wǎng)絡(luò)[3是一種基于前向傳播結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)模型，公式如下：

其中， 是訓練集的數(shù)量， 代表第i個訓練樣本， 代表第i個訓練樣本的權(quán)重， 是核函數(shù)。在本文中，

使用“cubic”核函數(shù)。

（三）粒子群優(yōu)化算法（PSO）

粒子群優(yōu)化算法是一種被廣泛使用的群體優(yōu)化算法。為了找到優(yōu)化問題的全局最優(yōu)解，粒子從個體最優(yōu)和全局最優(yōu)位置學習。具體而言，粒子的學習機制概括如下：

其中t是迭代次數(shù)， 和 是第i個粒子的位置和速度， ω 是慣性權(quán)重， 是自學習因子， 是群體學習因子， 是[0，1]\"范圍內(nèi)的隨機向量，n是決策空間的維度，pbesti是個體歷史最優(yōu)位置，gbest是種群歷史最優(yōu)位置。

（四）社會學習粒子群優(yōu)化算法（SL-PSO）

社會學習粒子群優(yōu)化算法[是粒子群優(yōu)化算法的一種變體，它引入了一種新的學習機制。在SL-PSO中，粒子的更新不僅依賴于它們自己的經(jīng)驗（即它們找到的最佳位置），還依賴于整個群體的經(jīng)驗。排名靠前后的粒子會學習排名靠前的粒子的行為，以提高自己的性能。當前最優(yōu)粒子的位置信息會被其他所有粒子所學習。算法中粒子的更新公式如下：

其中 （t）表示粒子i在第t代的飛行速度， （t）表示粒子i在第t代的位置。 是種群在第t代的平均位置，反映了整個群體的中心趨勢。 是社會影響因子。 和 用于在速度和位置更新中引入隨機性，范圍是[0，1]。 （t）是隨機數(shù)，用于在粒子更新過程中引入隨機性。 代表在種群中降序排列在第i位的粒子的學習概率。m代表種群大小，n代表決策空間維度， 、M是一個定值。

總的來說，SL-PSO算法通過引入社會學習機制，允許粒子根據(jù)它們在種群中的相對位置和整個種群的中心趨勢來調(diào)整自己的速度和位置。這種機制有助于粒子探索解空間，并最終找到問題的最優(yōu)解或近似最優(yōu)解。

（五）Q學習（Q-learning）

Q學習[是一種無模型的強化學習算法。它根據(jù)當前狀態(tài)下執(zhí)行動作將會獲得的獎勵來決定執(zhí)行哪個動作。Q學習方法原理簡單，適應(yīng)動態(tài)環(huán)境，可收斂到最佳策略。Q表的更新公式為：

其中， ）代表在當前狀態(tài)和動作下的Q值。 和 分別是學習率和折扣因子，范圍均為[0，1]。r代表在當前狀態(tài) 下執(zhí)行動作 后會獲得的獎勵。max Q（ ，A）代表在下一狀態(tài) 可獲得的最大獎勵。A

三、基于Q學習的代理模型輔助優(yōu)化算法（QL-SAEA）

（一）算法詳細介紹

算法1給出了基于Q學習的代理模型輔助優(yōu)化算法的偽代碼。算法結(jié)合了Q學習框架和代理模型輔助的進化算法，設(shè)計了4種不同的采樣策略。首先，初始化Q表，每種采樣策略對應(yīng)一個動作action，每個動作執(zhí)行后是否更新最優(yōu)解各對應(yīng)一個狀態(tài)state，因此Q表設(shè)置為8行4列，所有Q值初始化為0.25，隨機選擇一個狀態(tài)作為當前狀態(tài)state。使用拉丁超立方體（LHS）生成NP個初始樣本，使用目標函數(shù)進行評價，存入數(shù)據(jù)庫DB中，從DB中找到當前最優(yōu)樣本 ，更新目標函數(shù)評價次數(shù)NFE。然后根據(jù)式子（4）和（5）選擇動作action，其 s）代表當前狀態(tài)s下第i個動作 被選中的概率， 代表當前狀態(tài)s下第i個動作 的Q值，rand表示一個[0，1]范圍內(nèi)的隨機數(shù)，A為被選中概率不小于rand值中最接近rand的動作。接下來執(zhí)行所選動作代表的策略，獲得候選解x并使用目標函數(shù)評價，將 存入DB中，更新NFE。當候選解 的目標函數(shù)值f 小于f（ ）時，將 賦值給 模型更新標志 success置為1，否則將success置為 隨后按照式子（3）更新當前狀態(tài)和動作對應(yīng)的Q值，按照式子（6）更新狀態(tài)值state，第一個動作的成功與失敗分別對應(yīng)第1、2行，第二個動作的成功與失敗分別對應(yīng)第3、4行，以此類推。此后返回式子（3）繼續(xù)執(zhí)行，直到算法結(jié)束，輸出最優(yōu)解 及其目標函數(shù)值f（

算法1：QL-SAEA的框架。

輸入：問題維度Dim，最大目標函數(shù)評價次數(shù)MaxNFE。

輸出：最優(yōu)解xbest及其目標函數(shù)值。

1.初始化Q表及當前狀態(tài)state；

2.初始化DB，更新NFE、xbest；

3.while：NFE

4.選擇動作action；

5.執(zhí)行動作action，確定候選解x；

6.使用目標函數(shù)評價候選解 ，更新DB、xbest、NFE、success；

7.更新Q-table（state，action）對應(yīng)的Q值和當前狀態(tài) state；

8.endwhile。

（二）采樣策略

采樣策略用于尋找新的候選解更新 。為提高候選解搜索效率與算法穩(wěn)定性，本文采用Kriging與RBF雙代理模型協(xié)同策略。在建立Kriging模型時，為了防止模型過擬合，同時規(guī)避Kriging模型在訓練樣本數(shù)量大時計算量過大的問題，從DB中隨機選擇N個樣本作為訓練集，而不是選擇DB中的全部樣本。RBF模型使用DB全部樣本訓練，通過累積樣本密度引導搜索聚焦于最優(yōu)解 鄰域。本文使用了兩種優(yōu)化器：粒子群優(yōu)化算法[5（PSO）和社會學習粒子群優(yōu)化算法[（SL-PSO）。PSO算法全局搜索能力較強：粒子通過跟蹤個體最優(yōu)（pbest）和群體最優(yōu)（gbest）探索解空間，適合初期廣泛搜索。SL-PSO算法引入社會學習機制，對探索與開發(fā)的平衡較好。通過對PSO/SL-PSO優(yōu)化器與Kriging/RBF模型的交叉組合，形成4組策略組合：Kriging+PSO（策略1）、Kriging+SL-PSO（策略2）RBF+PSO（策略3）、RBF SL-PSO（策略4，通過不同模型與算法的優(yōu)勢互補增強算法魯棒性。

四、實驗及結(jié)果分析

（一）實驗設(shè)置

為了驗證本文所提出算法QL-SAEA的有效性，在CEC2005的5個基準測試函數(shù)上與CAL-SAPSO、

經(jīng)驗交流

LMSRBF、DYCORS、SSLPSO進行比較，每個測試函數(shù)的維度分別設(shè)置為10、20、30維。MaxNFE設(shè)置為 ，所有實驗獨立運行20次。NP設(shè)置為 。PSO和SL-PSO的最大迭代次數(shù)設(shè)置為 。在建立Kriging模型時，N為 PSO中慣性權(quán)重 ω 為0.8，自學習因子 為0.5，群體學習因子 為0.5。在Q-learning中，學習率 為0.1，折扣因子 為0.9，獎勵r為1。

（二）實驗結(jié)果和分析

表1給出了實驗的統(tǒng)計結(jié)果，為20次獨立運行結(jié)果的均值。對統(tǒng)計結(jié)果采用了顯著性水平為0.05的Wilcoxon秩和檢驗，所提出的算法的性能明顯優(yōu)于、無明顯差異或差于所比較的算法分別用 + ， ≈ 和-表示。可以看出，相比較其他4種算法，本文所提出的算法在6個問題上獲得了最好的結(jié)果。在30維的Ellipsoid問題上與取得最好結(jié)果的CAL-SAPSO無明顯差異，在20、30維的Rosenbrock問題上和30維的Griewank問題上僅差于CAL-SAPSO，說明本文提出的QL-SAEA在計算昂貴問題上是有效的。

五、結(jié)語

本文針對計算昂貴優(yōu)化問題，提出了一種基于Q學習的代理模型輔助優(yōu)化算法QL-SAEA。在QL-SAEA中使用了Q學習方法用于選擇不同的策略用于采樣，使用Kriging模型輔助搜索時，注重對全局的擬合能力，使用RBF模型輔助搜索時，注重對最優(yōu)區(qū)域的擬合能力。實驗結(jié)果表明，本文提出的QL-SAEA在15個測試問題上比其他算法更有效。

參考文獻

[1]ZhenH.，GongW.，WangL..EvolutionarySamplingAgent forExpensive Problems [J].IEEE Transactions on Evolutionary Computation，2023，3 （27）：716-727.

[2]張磊，胡震.基于克里金模型的潛水器耐壓艙結(jié)構(gòu)優(yōu)化[J].船舶力學，2020，24（01）：108-117.

[3]Diaz-Manriquez，Alan， ToscanoG，Coello Coello C.Comparison of metamodeling techniques in evolutionary algorithms [J].Soft Computing， 2017， 19 （21）：5647-5663.

[4]Watkins ChristopherJ.C.H.，Dayan Peter.Q-learning[J]. MachineLearning，1992，3（08）：279-292.

[5]KennedyJ.，EberhartR.Particleswarmoptimization[C]. Proceedings of ICNN'95-International Conference on Neural Networks，1995（04）：1942-1948.

[6]ChengRan，Jin Yaochu.A social learningparticle swarm optimizationalgorithm for scalableoptimization[J].Information Sciences，2015 （291）：43-60.

作者單位：山西電子科技學院

責任編輯：王穎振楊惠娟