基于反向?qū)W習(xí)的微種群教與學(xué)優(yōu)化算法及其應(yīng)用

范勤勤，柳締西子，王筱薇，韓 新，王維莉

(1.上海海事大學(xué) 物流研究中心，上海 201306；2.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200237；3.同濟(jì)大學(xué) 上海防災(zāi)救災(zāi)研究所，上海 200092)

0 引言

教與學(xué)優(yōu)化算法(teaching-learning-based optimization，TLBO)是Rao等[1-2]于2011年提出的一種新的智能優(yōu)化算法，它主要模擬老師的“教”過程和學(xué)生的“學(xué)”過程。由于教與學(xué)算法具有參數(shù)少、算法易于實(shí)現(xiàn)、尋優(yōu)性能好等優(yōu)點(diǎn)，受到學(xué)者的關(guān)注和研究[3]。目前，教與學(xué)優(yōu)化算法已被成功地應(yīng)用于多個領(lǐng)域。

一般來說，小的種群規(guī)模(微種群)會加速優(yōu)化算法收斂，但會使其全局探索能力下降[4]，即易陷入局部最優(yōu)。因此，為提高微種群優(yōu)化算法的全局探索能力，眾多學(xué)者對其進(jìn)行研究。例如，Ren等[5]提出一種小種群的差分進(jìn)化算法(differential evolution using smaller population,DESP)。在該算法中，變異策略使用額外的擾動來提高其全局搜索能力，并使用一種自適應(yīng)調(diào)整策略來控制擾動的強(qiáng)度。Brown等[6]提出一種微種群的JADE(adaptive differential evolution with optional external archive)算法。該算法在Rcr-JADE算法[7]的基礎(chǔ)上進(jìn)行改進(jìn)，并加入了新的差分變異策略來提高算法的全局搜索能力。Marquez-Grajales等[8]提出了μJADEε算法。該算法將ε約束方法用于μJADE算法，以此來提高μJADE算法求解約束優(yōu)化問題的能力。Salehinejad等[9]提出一種向量化隨機(jī)變異因子的微種群差分進(jìn)化算法(micro-differential evolution with vectorized random mutation factor，MDEVM)。在該算法中，每個個體均有各自的差分變異因子F，以此來提高種群多樣性。上述研究表明，提高微種群啟發(fā)式算法的全局搜索能力是避免算法“早熟收斂”的有效方式之一。

博弈論又稱對策論，是研究具有沖突和對抗性質(zhì)現(xiàn)象的數(shù)學(xué)理論和方法，在很多科學(xué)領(lǐng)域中得到了廣泛的應(yīng)用。在博弈問題中，非合作博弈納什均衡是其最核心的研究內(nèi)容。1951年，Nash[10]在提出的“納什定理”中揭示并證明了博弈納什均衡解的存在，但是Nash并沒有給出求解納什均衡的一般性方法。傳統(tǒng)方法在求解納什均衡問題時均存在一定的局限性，特別是對于高維的博弈模型(如3維及以上的矩陣策略)，傳統(tǒng)算法計算復(fù)雜且求解成本較高。最近幾十年來，隨著元啟發(fā)式算法的迅速發(fā)展，諸多學(xué)者開始使用遺傳算法[11]、免疫算法[12]、粒子群算法[13]、蟻群算法[14]等來求解博弈納什均衡問題，并取得較好結(jié)果，這為求解非合作博弈問題提供了一種新的有效途徑和方法。

為進(jìn)一步提高微種群TLBO算法的全局搜索能力并有效地求解非合作博弈問題，筆者提出一種OBL-μTLBO算法。在該算法中，微種群有利于加快TLBO算法的收斂速度，而反向?qū)W習(xí)有助于提高TLBO算法的全局探索能力。實(shí)驗結(jié)果表明，OBL-μTLBO 算法的整體性能明顯優(yōu)于其他所比較微種群和非微種群算法。最后，將改進(jìn)的算法應(yīng)用于非合作博弈問題的求解，所得結(jié)果明顯好于其他比較算法。

1 反向?qū)W習(xí)

反向?qū)W習(xí)(opposition-based learning,OBL)是Tizhoosh[15]于2005年提出的一種應(yīng)用于計算智能領(lǐng)域的機(jī)器學(xué)習(xí)方法。因為反向?qū)W習(xí)策略具有較強(qiáng)的探索能力[16]，所以被廣泛地用于提高元啟發(fā)式算法的搜索性能。一些術(shù)語介紹如下。

反向數(shù)(opposite number)：設(shè)存在實(shí)數(shù)x∈[a，b]，則與其對應(yīng)的反向數(shù)xo被定義為：

xo=a+b-x,x∈[a,b]。

(1)

反向點(diǎn)(opposite point)：對于D維的搜索空間，設(shè)Xi=(xi,1,xi,2,…,xi,D)為其解向量空間內(nèi)的一個點(diǎn)，且xij∈ [aj，bj](j=1,2,…,D)，則與其對應(yīng)的反向點(diǎn)表示為：

(2)

另外，Wang等[17]于2011年提出一種廣義的反向?qū)W習(xí)策略(generalized opposition-based learning,GOBL)，其反向個體生成如下：

(3)

式中：r是被用來控制反向解的搜索范圍。研究表明，GOBL策略可以有效地使算法跳出局部最優(yōu)[18]。

2 基于反向?qū)W習(xí)的微種群教與學(xué)優(yōu)化算法

2.1 基于反向?qū)W習(xí)的“教”階段

對于微種群而言，由于種群規(guī)模較小，因此種群多樣性更容易迅速丟失。故筆者將結(jié)合GOBL策略，在教學(xué)階段使用反向?qū)W習(xí)個體XGO來指導(dǎo)種群進(jìn)化，從而提高微種群教與學(xué)優(yōu)化算法的探索能力。其反向個體更新方式如下：

(4)

Xi,new=Xi,old+N(0.5,0.2)·(XT-TF·XM)+

N(0.5,0.2)·(XGO-Xi,old)，

(5)

式中：N表示正態(tài)分布函數(shù)。若Xi,new的適應(yīng)度值優(yōu)于Xi,old，則更新個體；否則，不更新。

2.2 OBL-μTLBO算法的實(shí)現(xiàn)步驟

Step1初始化。設(shè)定微種群規(guī)模NP，最大評價次數(shù)FES；初始化種群。

Step2教學(xué)階段。根據(jù)式(5)對個體進(jìn)行更新，并對個體進(jìn)行選擇。

Step3學(xué)習(xí)階段。根據(jù)文獻(xiàn)[19]利用正態(tài)分布隨機(jī)數(shù)代替式(2)的均勻隨機(jī)數(shù)，其更新公式如下：

(6)

Step4判定算法是否達(dá)到最大適應(yīng)度評價次數(shù)，若沒有達(dá)到，則跳轉(zhuǎn)至Step 2繼續(xù)執(zhí)行；如達(dá)到，則執(zhí)行Step 5。

Step5輸出結(jié)果。

3 仿真測試

為驗證OBL-μTLBO算法的有效性，筆者選取文獻(xiàn)[6]中13個30維的測試函數(shù)。其中f1～f7為單峰函數(shù)，f8～f13為多峰函數(shù)。OBL-μTLBO算法性能分別與TLBO[1-2]、DESP[5]、μJADE[6]、Rcr-JADE-s4[7]、MDEVM[9]、TLBO-CSWL[19]、FSADE[20]、ODE[21]以及MDEVM-Fajfar[22]等微種群或非微種群算法進(jìn)行對比。對于每個測試函數(shù)，所有比較算法均獨(dú)立運(yùn)行50次。同時，為保證所得結(jié)論的可靠性，仿真結(jié)果采用Friedman[23]、Bonferroni-Dunn[24]、Iman-Davenport[25]、Holm和 Hochberg[25]檢驗進(jìn)行統(tǒng)計分析。顯著性水平設(shè)定為5%。此外，所得最好結(jié)果在表中用黑體表示。

3.1 與微種群算法的比較

在該實(shí)驗中，本文算法OBL-μTLBO與其他5種微種群算法進(jìn)行比較，并通過設(shè)定的求解精度來比較哪種算法所使用的適應(yīng)度函數(shù)評價次數(shù)最小。對于所有比較算法，實(shí)驗參數(shù)設(shè)置均與文獻(xiàn)[19]一致。即種群規(guī)模設(shè)定為8，對于f7，函數(shù)的結(jié)果精度設(shè)定為1.0E-02，其余測試函數(shù)的尋優(yōu)精度設(shè)定為1.0E-08,最大適應(yīng)度函數(shù)評價次數(shù)為3 000 000。若算法在達(dá)到終止條件時仍然沒有求解到設(shè)定的求解精度，則認(rèn)為算法在該函數(shù)上尋優(yōu)失敗，用“—”表示。仿真結(jié)果如表1所示。由表1可知,OBL-μTLBO算法在計算f1、f2、f3、f4、f5、f6、f7、f8、f9、f10、f11、f12上使用的函數(shù)評價次數(shù)最少，尋優(yōu)效率明顯優(yōu)于其他所比較算法。這說明OBL-μTLBO算法不僅可以加速收斂，還可以提高尋優(yōu)性能。對于函數(shù)f8和f13，μJADE算法的仿真結(jié)果略優(yōu)于OBL-μTLBO算法。其主要原因可能是：雖然反向?qū)W習(xí)能夠有效地幫助TLBO提高全局搜索能力，但是差分進(jìn)化算法的全局搜索能力要好于TLBO算法。除以上比較外，還使用非參數(shù)的統(tǒng)計分析方法來對實(shí)驗結(jié)果進(jìn)行進(jìn)一步分析，所得統(tǒng)計分析結(jié)果見表2和表3。從表2中可知，OBL-μTLBO算法在所有算法中的尋優(yōu)效率是最高的。從表3可以看出，OBL-μTLBO算法的尋優(yōu)效率要顯著優(yōu)于DESP、MDEVM、MDEVM-Fajfar算法，OBL-μTLBO算法的整體性能要比μJADE好。綜上所得，OBL-μTLBO算法的收斂速度在所有比較算法中是最快的，且可得到高質(zhì)量的解。

表1 微種群算法的實(shí)驗結(jié)果Table 1 Experimental results of micro-population algorithms

表2 Friedman測試在微種群算法上所得排序結(jié)果Table 2 Ranking obtained by Friedman′s test for micro-population algorithms

表3 Bonferroni-Dunn、Holm和Hochberg在OBL-μTLBO和微種群算法上所得p值Table 3 p-values obtained by Bonferroni-Dunn′s,Holm′s,and Hochberg′s procedures for OBL-μTLBO and micro-population algorithms

3.2 與非微種群算法的比較

在本實(shí)驗中，OBL-μTLBO算法與4種非微種群算法的性能進(jìn)行比較。期望求解精度同3.1節(jié)。標(biāo)準(zhǔn)TLBO算法的種群規(guī)模設(shè)定為30；TLBO-CSWL算法的種群規(guī)模設(shè)定為40；FSADE算法和Rcr-JADE-s4的種群規(guī)模分別設(shè)定為50和100，算法參數(shù)設(shè)置均與文獻(xiàn)[6]一致，結(jié)果見表4。從表4可以看出，OBL-μTLBO算法在f1、f2、f3、f4、f6、f7、f9、f10、f11上的平均評價次數(shù)均明顯少于所有比較算法，這說明所提方法具有較快的收斂速度。而在函數(shù)f5、f8、f13上，Rcr-JADE-s4算法的實(shí)驗結(jié)果要優(yōu)于本文的OBL-μTLBO算法。這說明Rcr-JADE-s4算法在這3個函數(shù)上具有較快的收斂速度。統(tǒng)計分析結(jié)果見表5和表6。由表5可知，筆者所提算法與非微種群算法相比，OBL-μTLBO同樣具有較高的搜索效率。從表6可以看出，OBL-μTLBO算法的搜索效率要明顯優(yōu)于其他所有比較的非微種群算法。

表4 OBL-μTLBO算法與非微種群算法的結(jié)果Table 4 Experimental results of the OBL-μTLBO algorithm and non-micro-population algorithms

表5 Friedman測試在OBL-μTLBO和非微種群算法上所得排序結(jié)果Table 5 Ranking obtained by Friedman′s test for OBL-μTLBO and non-micro-population algorithms

表6 Bonferroni-Dunn、Holm和Hochberg在OBL-μTLBO和非微種群算法上所得p值Table 6 p-values obtained by Bonferroni-Dunn′s,Holm′s,and Hochberg′s procedures for OBL-μTLBOand non-micro-population algorithms

3.3 OBL-μTLBO與μJADE、TLBO-CSWL、ODE的比較

為進(jìn)一步驗證OBL-μTLBO算法的尋優(yōu)性能，本部分將對OBL-μTLBO算法與表現(xiàn)較好的微種群算法μJADE和非微種群算法TLBO-CSWL、ODE進(jìn)行性能比較。與3.1和3.2節(jié)不同，在本實(shí)驗中，所有算法終止條件設(shè)定為最大的適應(yīng)度函數(shù)評價次數(shù)，即30 000。同時，μJADE、ODE、TLBO-CSWL的種群規(guī)模分別設(shè)定為8、100、40。所得結(jié)果見表7。從表7可以看出,OBL-μTLBO 算法在f1、f2、f3、f4、f5、f6、f7、f9、f10、f11、f12上得到的平均結(jié)果明顯優(yōu)于μJADE算法。而μJADE只在f8和f13這兩個函數(shù)上要比所提算法表現(xiàn)得好。這足以說明OBL-μTLBO算法的尋優(yōu)效率要好于μJADE算法。相比于TLBO-CSWL，除測試函數(shù)f7、f8、f12外，OBL-μTLBO算法在所有函數(shù)上都要比它表現(xiàn)得好。此外，OBL-μTLBO算法在所有測試函數(shù)上的優(yōu)化結(jié)果都要好于ODE。綜上，OBL-μTLBO算法不僅具有較快的收斂速度和能夠降低計算內(nèi)存的要求，而且還有較強(qiáng)的全局搜索能力。

表7 所有比較算法30維仿真測試結(jié)果Table 7 Experimental results on all Comparison algorithms with 30 D

為得到可靠結(jié)論，3種非參數(shù)統(tǒng)計分析方法被用來對所有比較算法的平均值進(jìn)行統(tǒng)計分析，其結(jié)果見表8。由表8可知，OBL-μTLBO算法的性能要明顯優(yōu)于μJADE和ODE。另外，雖然OBL-μTLBO算法和TLBO-CSWL算法的性能在統(tǒng)計學(xué)意義上不存在顯著性的差異，但是從表7中的結(jié)果可知，OBL-μTLBO算法的整體性能要優(yōu)于TLBO-CSWL算法。

表8 Bonferroni-Dunn、Holm在OBL-μTLBO和其他3種算法上所得p值Table 8 p-values obtained by Bonferroni-Dunn′s,Holm′s,and Hochberg′s procedures for OBL-μTLBO and three algorithms

3.4 種群規(guī)模的敏感性分析

本部分對OBL-μTLBO算法的種群規(guī)模進(jìn)行敏感性分析。其種群規(guī)模分別設(shè)定為5、8、10、15、20、30、40、50、100。對于每個測試函數(shù)，算法終止條件設(shè)定為最大適應(yīng)度函數(shù)評價次數(shù)30 000,并使用13個30維的測試函數(shù)來對不同的種群規(guī)模進(jìn)行分析。同時,Friedman統(tǒng)計方法用來對實(shí)驗結(jié)果進(jìn)行統(tǒng)計分析，結(jié)果見表9。從表9可知，種群規(guī)模對OBL-μTLBO算法的性能沒有顯著影響。因此，算法使用者可以對OBL-μTLBO算法的種群規(guī)模進(jìn)行方便設(shè)置。此外，從Friedman的排序結(jié)果(見圖1)來看，在有限的計算資源且要保證算法良好尋優(yōu)能力的情況下，較小的種群規(guī)模更有利于OBL-μTLBO算法的搜索。

表9 OBL-μTLBO算法的種群規(guī)模敏感性分析Table 9 Sensitivity analysis to population size of OBL-μTLBO

圖1 Friedman 測試排序結(jié)果Figure 1 Ranking obtained by Friedman′s test

4 OBL-μTLBO算法在非合作博弈問題中的應(yīng)用

4.1 博弈問題描述

假設(shè)有n個局中人參與博弈，所有局中人策略構(gòu)成一個策略組合(strategy profile)，如果某情況下無一參與者可以獨(dú)自行動而增加收益(即為了自身利益的最大化，沒有任何單獨(dú)的一方愿意改變其策略)，此時博弈模型處于穩(wěn)定的狀態(tài)，此策略組合被稱為納什均衡。參考文獻(xiàn)[13]中的問題描述，對于兩人有限非合作博弈問題：設(shè)局中人1的混合策略x=(x1,x2,…,xm)，局中人2的混合策略y=(y1,y2,…,yn)。Am×n、Bm×n分別為局中人1和局中人2的支付矩陣，則局中人1和局中人2的期望支付分別為xAyT和xByT。其中，(x*,y*)為雙矩陣博弈問題的一個納什均衡解的充分必要條件為：

(7)

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

(8)

式中：Ai表示Am×n的第i行；Bj表示Bm×n的第j列。

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

4.2 案例研究

選取兩個雙矩陣博弈問題[26-27]。

例1：博弈模型1,Γ1≡(x1,y1;A1,B1)，支付矩陣如下：

該問題的唯一納什均衡解為(1/3,1/3,1/3;1/3,1/3,1/3)。

例2：博弈模型2,Γ2≡(x2,y2;A2,B2)，支付矩陣如下：

該問題的唯一納什均衡解為(0,0,1;0,0,1)。

為了驗證微種群算法OBL-μTLBO求解非合作博弈納什均衡問題的有效性，將OBL-μTLBO算法和測試中性能較好的TLBO-CSWL[19]算法應(yīng)用于求解以上兩個3維雙矩陣博弈問題，并與其他幾種知名算法jDE[28]、SaDE[29]、CLPSO[30]進(jìn)行性能比較。其中OBL-μTLBO 的種群規(guī)模設(shè)定為8，而其余所有對比算法的參數(shù)設(shè)定均與對比文獻(xiàn)[6]一致。求解結(jié)果使用Wilcoxon秩和檢驗[31]

所有算法的求解結(jié)果(平均值和標(biāo)準(zhǔn)方差，括號內(nèi)是標(biāo)準(zhǔn)方差)以及統(tǒng)計分析結(jié)果見表10。從表10中可以看出，OBL-μTLBO 算法在兩個博弈實(shí)例上所得平均值均要好于所比較算法。表11和表12為所有算法在算例1和算例2上得到的最好結(jié)果。從表11和12可以看出，OBL-μTLBO算法在兩個算法上均可以取得最優(yōu)的納什均衡解，且求解的適應(yīng)度函數(shù)精度明顯優(yōu)于jDE、SaDE、CLPSO以及TLBO-CSWL算法。

表10 所有算法在博弈問題上得到的實(shí)驗結(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

以上分析結(jié)果表明，所提出的OBL-μTLBO算法能夠有效地求解非合作博弈納什均衡問題。

5 結(jié)論

為平衡微種群教與學(xué)優(yōu)化算法的全局和局部搜索能力，筆者提出了OBL-μTLBO算法。在該算法中，利用微種群來提高教與學(xué)優(yōu)化算法的收斂速率，且在教學(xué)階段加入了反向?qū)W習(xí)來指導(dǎo)種群進(jìn)化，使算法具備反向?qū)W習(xí)的能力，提高了算法的全局探索能力。OBL-μTLBO算法跟μJADE、DESP、MDEVM、MDEVM-Fajfar等微種群算法和FSADE、Rcr-JADE-s4、TLBO、TLBO-CSWL、ODE等非微種群算法進(jìn)行性能比較，結(jié)果表明，OBL-μTLBO算法的整體性能在所有比較算法中是最好的。因此，反向?qū)W習(xí)策略對于提升微種群算法的優(yōu)化性能是有效的。另外，對OBL-μTLBO算法的種群規(guī)模進(jìn)行敏感性分析。統(tǒng)計分析結(jié)果表明，OBL-μTLBO算法的性能不受種群大小影響,但在有限計算資源下，小的種群規(guī)模更有利于其搜索。最后，將OBL-μTLBO算法應(yīng)用到非合作博弈問題，仿真結(jié)果表明，所提OBL-μTLBO算法能夠取得較好的優(yōu)化結(jié)果。