柳締西子，范勤勤,2，胡志華

近幾十年來，博弈論得到了許多研究人員的關(guān)注，逐漸成為了經(jīng)濟(jì)學(xué)中的標(biāo)準(zhǔn)分析工具之一，并且在經(jīng)濟(jì)學(xué)、軍事科學(xué)和其他社會科學(xué)中得到了廣泛的應(yīng)用。在博弈問題中，非合作博弈納什均衡是其最核心的研究內(nèi)容。1951年，Nash[1]在提出的“納什定理”中揭示并證明了納什均衡解的存在，但是Nash并沒有給出求解納什均衡的一般性方法。傳統(tǒng)的求解方法如Lemke-Howson算法[2]、牛頓算法[3]、同倫算法[4]等均存在一定的局限性；特別是對于高維的博弈模型(如3維及以上的矩陣策略)，傳統(tǒng)算法的計(jì)算復(fù)雜求解成本較高。除了傳統(tǒng)的優(yōu)化方法，許多學(xué)者還利用遺傳算法[5]、免疫算法[6]、粒子群算法[7]、蟻群算法[8]等啟發(fā)式算法來求解博弈納什均衡問題，這為求解非合作博弈問題提供了一種新的有效途徑和方法。

教與學(xué)優(yōu)化算法(teaching-learning-based optimization，TLBO)是 Rao 等[9-10]于 2011 年提出，它是一種模擬教師教學(xué)與學(xué)生學(xué)習(xí)的群體智能優(yōu)化算法。由于該算法參數(shù)設(shè)置少、操作簡便、尋優(yōu)性能好，引起了國內(nèi)外學(xué)者的重視。目前它已被成功應(yīng)用于各個領(lǐng)域，如LQR控制器優(yōu)化設(shè)計(jì)[11]、熱交換器優(yōu)化設(shè)計(jì)[12]、人工神經(jīng)網(wǎng)絡(luò)優(yōu)化[13]等。

一般來說，原始的TLBO算法容易出現(xiàn)“早熟收斂”的現(xiàn)象，從而易于陷入局部最優(yōu)。為了提高TLBO算法的尋優(yōu)性能，很多學(xué)者提出了改進(jìn)算法。比如，Rao等[14]提出了ETLBO算法，該算法將精英策略引入TLBO算法中，保留每代中的最優(yōu)解，并隨機(jī)對精英個體進(jìn)行變異操作，其主要目的是提高算法的收斂速度和尋優(yōu)精度；Yu等[15]提出了ITLBO算法，該算法在TLBO算法中引入教學(xué)反饋階段和差分算法中的交叉變異策略，并在算法后期加入混沌擾動機(jī)制；Zou等[16]提出了DGSTLBO算法，該算法在教學(xué)階段引入動態(tài)分組教學(xué)策略，在學(xué)習(xí)階段加入量子行為策略，以增加種群的多樣性和避免算法早熟收斂；Chen等[17]提出了VTTLBO算法，該算法將種群的數(shù)量以先增后減的方式來進(jìn)行動態(tài)調(diào)整。在種群數(shù)量增加階段利用高斯分布生成個體，并在減少階段進(jìn)行相同個體的去重操作，其主要目的是減少計(jì)算成本以及增強(qiáng)算法的收斂精度和速度。Wu等[18]提出了NIWTLBO算法，在該算法中，利用非線性慣性權(quán)重因子來控制個體的學(xué)習(xí)速率，同時(shí)使用動態(tài)慣性權(quán)重因子代替原有隨機(jī)數(shù)，仿真結(jié)果表明此改進(jìn)策略提高了算法的收斂速率和尋優(yōu)性能。Shahbeig等[19]提出了TLBO-PSO算法，該算法將改進(jìn)的變異模糊自適應(yīng)的PSO算法與TLBO算法進(jìn)行結(jié)合，目的在于提高算法的尋優(yōu)精度從而解決多目標(biāo)優(yōu)化問題。上述研究結(jié)果均表明，將改進(jìn)策略引入TLBO算法中可以提高算法的尋優(yōu)性能。

為了能更進(jìn)一步提高TLBO的搜索性能，本文提出一種基于混沌搜索和權(quán)重學(xué)習(xí)的教與學(xué)優(yōu)化(TLBO-CSWL)算法。仿真結(jié)果表明，所提算法的整體優(yōu)化性能明顯優(yōu)于其他所比較的算法。最后，將改進(jìn)的算法應(yīng)用于非合作博弈納什均衡問題的求解。

1 預(yù)備知識

1.1 標(biāo)準(zhǔn)的教與學(xué)優(yōu)化算法

標(biāo)準(zhǔn)TLBO算法[9-10]主要包括兩個階段，教學(xué)階段與學(xué)習(xí)階段。

1.1.1 教學(xué)階段

式中：Xi,old表示第i個個體學(xué)習(xí)之前的個體；為[0, 1]之間的均勻隨機(jī)數(shù)，表示學(xué)習(xí)步長；TF=round[1+rand(0, 1)]，取值1或2，表示教學(xué)因子。若Xi,new的適應(yīng)度值優(yōu)于Xi,old，則更新個體；否則，不更新。

1.1.2 學(xué)習(xí)階段

在TLBO算法的學(xué)習(xí)階段中，個體的更新公式為

1.2 混沌映射

混沌是指確定性動力學(xué)系統(tǒng)產(chǎn)生的一種不可預(yù)測的、類似隨機(jī)性的運(yùn)動，最顯著的特點(diǎn)是初值敏感性。混沌模型不僅具有隨機(jī)性、初值敏感性，同時(shí)還有一個很重要的性質(zhì)是遍歷性。由于混沌序列是遍歷的，它已被越來越多地應(yīng)用到智能優(yōu)化算法中。其主要被用來初始化種群[20]，以及能夠?qū)€體進(jìn)行隨機(jī)次數(shù)的擾動使其跳出局部最優(yōu)[21]，從而在個體周圍進(jìn)行遍歷搜索。借鑒文獻(xiàn)[21]中的混沌擾動策略，所提算法利用Logistics搜索策略來對個體進(jìn)行更新，公式為

式中：xold和xnew分別表示混沌映射之前和混沌映射之后的變量，x∈[0, 1];∈[0, 4]為控制參數(shù)，當(dāng)=4時(shí)，Logistics映射將處于完全混沌狀態(tài)。

2 基于混沌搜索和權(quán)重學(xué)習(xí)的教與學(xué)優(yōu)化算法

2.1 權(quán)重學(xué)習(xí)

在原始的TLBO算法中，教學(xué)階段主要是使用當(dāng)前最佳個體來指導(dǎo)種群進(jìn)化，這將會造成算法陷入局部最優(yōu)。因此，本文提出一種權(quán)重學(xué)習(xí)的策略，基于個體適應(yīng)度值產(chǎn)生一個可以代表種群適應(yīng)度水平的綜合個體Xweight，并且引導(dǎo)其他個體向其學(xué)習(xí)。這可以緩解算法“早熟”現(xiàn)象的發(fā)生。

1) 計(jì)算種群的最大適應(yīng)度值及每個個體的權(quán)重

2) 計(jì)算加權(quán)平均個體

3) 改進(jìn)后的教學(xué)階段更新公式為

式中r =N(0.5, 0.2)。若Xi,new的適應(yīng)度值優(yōu)于Xi,old,則更新個體；否則，不更新。

2.2 混沌搜索

為了提高TLBO算法的全局搜索能力，將混沌搜索策略加入到該算法中?；煦缢阉鞯膱?zhí)行步驟如下：

1) 對種群中的所有個體進(jìn)行適應(yīng)度值降序排列(最小化問題)；

2) 隨機(jī)取出一個排名前10的個體；

3) 利用式(3)對選擇的個體進(jìn)行混沌擾動，產(chǎn)生混沌個體Xchaos；

4)若Xchaos的適應(yīng)度值優(yōu)于Xi，則更新個體；否則，不更新。

2.3 TLBO-CSWL算法的實(shí)現(xiàn)步驟

1) 初始化：設(shè)定種群大小NP，維數(shù)D，最大評價(jià)次數(shù)，初始化種群。

2) 教學(xué)階段：根據(jù)式(7)對個體進(jìn)行更新。

3) 學(xué)習(xí)階段：利用正態(tài)分布隨機(jī)數(shù)代替式(2)的均勻隨機(jī)數(shù)，然后根據(jù)式(2)對個體進(jìn)行更新。

4) 混沌搜索：利用2.2部分隨機(jī)對個體進(jìn)行混沌擾動操作，并更新個體。

5) 判定程序是否達(dá)到最大評價(jià)次數(shù)，若沒有達(dá)到，則轉(zhuǎn)至2)；如達(dá)到，則執(zhí)行6)。

6) 輸出最優(yōu)解。

3 仿真測試

為驗(yàn)證TLBO-CSWL算法的有效性，本文選取了文獻(xiàn)[17]中的18個測試函數(shù)，其中f1～f5為單峰函數(shù)，f6～f10為多峰函數(shù)，f11～f18為旋轉(zhuǎn)函數(shù)。改進(jìn)算法分別與 jDE[22]、SaDE[23]、PSOwFIPS[24]、CLPSO[25]、TLBO[9-10]、ETLBO[14]、VTTLBO[17]等算法進(jìn)行對比。根據(jù)文獻(xiàn)[17]的設(shè)定, 最大的函數(shù)評價(jià)次數(shù)均為50 000。對于每個測試函數(shù)，所有算法均獨(dú)立運(yùn)行30次。為了保證結(jié)論的可靠性，采用 Friedman[26]、Dunn[27]、Holm 和 Hochberg[28]檢驗(yàn)來對結(jié)果進(jìn)行統(tǒng)計(jì)分析，其中，顯著水平設(shè)定為5%。

3.1 TLBO-CSWL算法與其他算法的比較

3.1.1 與其他算法在10維測試上的比較

在該實(shí)驗(yàn)中，所有算法的種群規(guī)模設(shè)定為30，仿真結(jié)果如表1所示。由表1可知，TLBOCSWL 在函數(shù) f1、f2、f3、f4、f6、f11、f12、f14、f15、f17上均有很好的尋優(yōu)效果，性能明顯優(yōu)于其他所比較算法。但在函數(shù) f5、f10、f13、f18上，所有其他算法的尋優(yōu)性能都略優(yōu)于TLBO-CSWL算法，其主要原因有兩個方面：1)雖然所提算法使用正態(tài)分布和權(quán)重學(xué)習(xí)來提高原始TLBO的搜索效率，但在某種程度上卻降低了算法的全局搜索能力；2)每種算法都有自身的尋優(yōu)特性，到目前為止，沒有一種算法能夠在所有的測試函數(shù)上都能表現(xiàn)得最好，因此，所提算法在某些測試函數(shù)上表現(xiàn)的差，也符合沒有免費(fèi)午餐定理[29]。而對于其余測試函數(shù)，TLBO-CSWL所獲得的結(jié)果與所比較算法中獲得的最好結(jié)果相同。同時(shí)，利用非參數(shù)的統(tǒng)計(jì)方法來對實(shí)驗(yàn)結(jié)果進(jìn)行分析，所得結(jié)果見表2、3所示。從表2可知，TLBO-CSWL算法的整體性能是最好的。從表3可以看出，所提算法的整體性能要顯著好于PSOwFIPS算法和CLPSO算法。另外，雖然TLBO-CSWL的整體性能在統(tǒng)計(jì)意義上沒有顯著好于SaDE、ETLBO、TLBO、jDE、VTTLBO，但是從結(jié)果來看，所提算法的整體性能優(yōu)于其他算法。

表1 10維仿真測試結(jié)果Table 1 Experimental results on 10D

表2 Friedman測試在10維函數(shù)上得到的排序Table 2 Ranking obtained by Friedman’s test on 10D

3.1.2 與其他算法在30維測試上的比較

在該實(shí)驗(yàn)中，所有算法的種群規(guī)模設(shè)定為40。仿真結(jié)果見表4，從表4可以看出本文算法獲得的平均結(jié)果在 f1、f2、f3、f4、f6、f7、f11、f12、f14、f15上均明顯優(yōu)于其他所比較算法。對于函數(shù)f5，除了CLPSO外，其他比較算法的整體性能都要好于TLBO-CSWL。對于函數(shù)f10，從結(jié)果來看，TLBO及其改進(jìn)算法的性能比改進(jìn)的差分進(jìn)化算法差，這主要是由算法的本身搜索特性所決定的。對于函數(shù)f13，雖然TLBO-CSWL的性能比jDE、SaDE和PSOwFIPS差，但比CLPSO和TLBO及其改進(jìn)算法要好。對于函數(shù)f18，TLBOCSWL的性能表現(xiàn)要比其他所比較算法差，其主要原因可能是所提方法雖然可以加快TLBO的收斂速度，但也損失了算法一部分全局搜索的能力。在其余測試函數(shù)中，TLBO-CSWL的尋優(yōu)結(jié)果與所比較算法中獲得的最好的結(jié)果相同。統(tǒng)計(jì)分析結(jié)果見表5和表6。由表5可知，本文所提出的TLBO-CSWL算法與其他算法相比具有優(yōu)越的整體性能。由表6可知，TLBO-CSWL算法的性能要顯著性優(yōu)于PSOwFIPS算法和CLPSO算法。此外，雖然TLBO-CSWL的尋優(yōu)性能在統(tǒng)計(jì)學(xué)意義上沒有顯著性地優(yōu)于其他比較算法，但是結(jié)合以上分析可知，TLBO-CSWL算法在解決18個測試函數(shù)問題上整體表現(xiàn)得最好。

表3 10維測試結(jié)果Bonferroni-Dunn、Holm以及Hochberg檢驗(yàn)的p-ValuesTable 3 p-Values obtained by Bonferroni-Dunn’s, Holm’s, and Hochberg’s procedures on experimental results with 10D

表4 30維仿真測試結(jié)果Table 4 Experimental results on 30D

續(xù)表 4

表5 Friedman測試在30維函數(shù)上得到的排序Table 5 Ranking obtained by Friedman’s test on 30D

3.2 TLBO-CSWL算法分析

為了驗(yàn)證所提算法的有效性，利用18個30維測試函數(shù)來對TLBO-CSWL和它的變種算法TLBO-CSWL-1(使用均勻隨機(jī)數(shù))、TLBO-CSWL-2(沒有混沌搜索)進(jìn)行測試。其中，種群規(guī)模設(shè)定為40，最大評價(jià)次數(shù)50 000。針對每個測試函數(shù)，每個算法均獨(dú)立運(yùn)行30次。同時(shí)，利用Friedman、Bonfeeroni-Dunn、Holm 以及 Hochberg檢驗(yàn)等非參數(shù)的統(tǒng)計(jì)方法對結(jié)果進(jìn)行統(tǒng)計(jì)分析，其中顯著性水平設(shè)定為5%。

3.2.1 與變種算法TLBO-CSWL-1的比較

為了驗(yàn)證策略正態(tài)隨機(jī)數(shù)的有效性，將對TLBO-CSWL-1與TLBO-CSWL進(jìn)行仿真測試。結(jié)果見表7。由表7可知，TLBO-CSWL算法所得到的平均結(jié)果在 f2、f6、f10、f14和 f18上要比 TLBOCSWL-1好，而對于其余的測試函數(shù)，兩者結(jié)果相同；這說明TLBO-CSWL算法具有更好的尋優(yōu)性能。統(tǒng)計(jì)分析結(jié)果見表8，由表8可知TLBOCSWL和TLBO-CSWL-1在統(tǒng)計(jì)學(xué)意義上雖然不存在顯著性差異，但是從Friedman測試所得到的排序結(jié)果來看(見圖1)，TLBO-CSWL的整體性能要好于TLBO-CSWL-1。以上統(tǒng)計(jì)分析結(jié)果表明，利用正態(tài)分布產(chǎn)生隨機(jī)數(shù)替代原有均勻隨機(jī)數(shù)的策略對于提升TLBO算法的性能是有效的。

表6 30維測試結(jié)果Bonferroni-Dunn、Holm以及Hochberg檢驗(yàn)的p-ValuesTable 6 p-Values obtained by Bonferroni-Dunn’s, Holm’s, and Hochberg’s procedures on experimental results with 30D

表7 TLBO-CSWL-1、TLBO-CSWL-2與TLBO-CSWL算法的30維仿真測試結(jié)果Table 7 Comparison of TLBO-CSWL-1, TLBO-CSWL-2, and TLBO-CSWL with experimental results on 30D

表8 Bonferroni-Dunn、Holm以及Hochberg檢驗(yàn)的p-Values (TLBO-CSWL-1)Table 8 p-Values obtained by Bonferroni-Dunn’s, Holm’s, and Hochberg’s procedures (TLBO-CSWL-1)

圖1 Friedman測試排序結(jié)果(TLBO-CSWL-1)Fig. 1 Ranking obtained by Friedman’s test(TLBOCSWL-1)

3.2.2 與變種算法TLBO-CSWL-2的比較

本文對不加混沌搜索的TLBO-CSWL-2和TLBO-CSWL在同樣的18個測試函數(shù)上進(jìn)行仿真測試。結(jié)果如表7所示。從表7可以看出所提出的 TLBO-CSWL 算法在 f2、f5、f6、f7、f10、f13、f14和f18上的尋優(yōu)結(jié)果要比TLBO-CSWL-2好，而在其余測試函數(shù)上，兩者的尋優(yōu)結(jié)果相同；以上表明TLBO-CSWL算法的性能要好于TLBO-CSWL-2算法。統(tǒng)計(jì)分析結(jié)果見表9，由表9可知TLBOCSWL和TLBO-CSWL-2在統(tǒng)計(jì)學(xué)意義上不存在顯著性差異。但是，從圖2的Friedman測試所得到的排序結(jié)果來看，與TLBO-CSWL-2相比，TLBO-CSWL具有更好的整體性能。以上統(tǒng)計(jì)分析表明，混沌搜索策略對于提升TLBO算法的性能是有效的。

表9 Bonferroni-Dunn、Holm以及Hochberg檢驗(yàn)的p-Values (TLBO-CSWL-2)Table 9 p-Values obtained by Bonferroni-Dunn’s, Holm’s, and Hochberg’s procedures (TLBO-CSWL-2)

圖2 Friedman測試排序結(jié)果(TLBO-CSWL-2)Fig. 2 Ranking obtained by Friedman’s test(TLBOCSWL-2)

4 在非合作博弈問題中的應(yīng)用

在本實(shí)驗(yàn)中，將所提算法應(yīng)用于非合作博弈納什均衡問題的求解。

4.1 博弈問題的描述

N人有限非合作博弈納什均衡問題，主要是求解一種混合策略使得博弈雙方均基于一定的概率來選擇自己的每一個純策略，使得博弈雙方的利益均最大化，此時(shí)博弈模型處于穩(wěn)定的狀態(tài)。參考文獻(xiàn)[7]中的問題描述，對于2人有限非合作博弈問題：設(shè)局中人1的混合策略為，局中人2的混合策略為。Am×n,Bm×n分別為局中人1和局中人2的支付矩陣，則局中人1和局中人2的期望支付分別為和。(,)為雙矩陣博弈問題的一個納什均衡解的充分必要條件，即

算法中的每一個個體的取值表示所有局中人的混合策略，則雙矩陣博弈問題z=(x, y)的適應(yīng)度函數(shù)可以表示為

式 (9)中，Ai表示 Am×n的第 i行，Bj表示Bm×n的第 j列。

根據(jù)納什均衡的定義和性質(zhì)[1]可知，混合局勢=(，)為雙矩陣博弈問題的一個納什均衡解的充分必要條件為：存在=(，)，使得f()=0；且對于任意的≠，都有 f ()＞0。

4.2 案例研究

本文選取2個雙矩陣博弈問題[30-31]。

為了求解以上兩個問題，選取jDE、SaDE、CLPSO、TLBO、TLBO-CSWL來對其進(jìn)行求解。對于所有的算法，種群大小均設(shè)定為40，最大的評價(jià)次數(shù)為2 000，每個問題均獨(dú)立運(yùn)行30次。并使用Wilcoxon秩和檢驗(yàn)方法[32]來對實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)分析。

實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)分析結(jié)果見表10，其中，“+”表示所提算法優(yōu)于其比較算法；“–”表示所提算法差于其比較算法 ；“≈”表示TLBO-CSWL算法與其他算法性能相似。從表10的統(tǒng)計(jì)結(jié)果可知，TLBO-CSWL算法在2個博弈問題上的求解結(jié)果均優(yōu)于 jDE、SaDE、CLPSO、TLBO 算法，說明TLBO-CSWL算法在解決非合作博弈問題上表現(xiàn)得最好。另外，對于博弈問題1和2，所有算法的最好結(jié)果見表11和表12。從表11可以看出，相對于其他算法，TLBO-CSWL算法能夠得到更好的納什均衡解。同時(shí)對于博弈模型1，本文算法求解的適應(yīng)度函數(shù)精度明顯優(yōu)于其他算法。另外，從表12可以看出，TLBO-CSWL比其他算法能找到更好的納什均衡解，適應(yīng)度函數(shù)的精度顯著好于其他所有算法，這說明TLBO-CSWL算法在計(jì)算結(jié)果的精度比其他算法有了較大的改進(jìn)。

上述分析表明，將本文提出的TLBO-CSWL算法應(yīng)用到非合作博弈問題，取得了較滿意的結(jié)果。

表10 所有算法在博弈問題上得到的結(jié)果Table 10 Experimental results of all algorithms on game problems

表11 所有算法在博弈模型1上得到的最好結(jié)果Table 11 The best experimental results of all algorithms on game problem 1

表12 所有算法在博弈模型2上得到的最好結(jié)果Table 12 The best experimental results of all algorithms on game problem 2

5 結(jié)束語

本文針對教與學(xué)優(yōu)化算法容易早熟收斂的問題，提出了一種基于混沌搜索和權(quán)重學(xué)習(xí)的教與學(xué)優(yōu)化(TLBO-CSWL)算法。在該算法中，利用當(dāng)前種群的加權(quán)平均值來指導(dǎo)種群的進(jìn)化，并且使用正態(tài)分布隨機(jī)數(shù)替代均勻隨機(jī)數(shù)來提高原始TLBO算法的尋優(yōu)性能；另外，將混沌搜索策略加到所提算法中，以此來提高算法的全局搜索能力。實(shí)驗(yàn)仿真結(jié)果表明，所提算法的整體性能在所有比較算法中是最好的。同時(shí)，采用TLBOCSWL算法與其變種算法TLBO-CSWL-1、TLBOCSWL-2進(jìn)行比較分析，仿真結(jié)果顯示本文所提出的改進(jìn)策略對于提升TLBO算法的性能是有效的。最后，將TLBO-CSWL算法應(yīng)用于求解非合作博弈納什均衡問題，其結(jié)果表明所提算法得到的結(jié)果要好于其他算法。