一種新穎的混沌動(dòng)態(tài)團(tuán)隊(duì)博弈算法

胡紅萍，鄒娜娜，馬利兵，史 娜

(中北大學(xué) 理學(xué)院，山西 太原 030051)

0 引 言

現(xiàn)實(shí)世界的很多領(lǐng)域存在很多優(yōu)化問(wèn)題, 例如統(tǒng)計(jì)物理學(xué)[1]、 計(jì)算機(jī)科學(xué)[2]、 人工智能[3]、 模式識(shí)別[4]等. 對(duì)于優(yōu)化問(wèn)題，傳統(tǒng)的優(yōu)化技術(shù)難以找到全局最優(yōu)解，例如爬山(Hill-Climbing)、 隨機(jī)搜索(Random Search)和模擬退火(Simulated Annealing,SA)[5]等. 元啟發(fā)算法的提出給優(yōu)化問(wèn)題提供了解決問(wèn)題的一種思路. 遺傳算法(GA)[6-7]是1992年由Holland提出的利用染色體和基因?qū)ふ胰肿顑?yōu)解的第一個(gè)進(jìn)化算法. 粒子群優(yōu)化算法(PSO)[8-12]是1995年由Kennedy等人提出的模擬鳥(niǎo)類覓食的社會(huì)行為用以找到全局最優(yōu)解的優(yōu)化算法. 正余弦算法(SCA)[13-14]是2016年由Seyedali Mirjalili提出的一種新的基于群體的優(yōu)化算法，用于解決優(yōu)化問(wèn)題，初始化種群，并使用基于正弦和余弦函數(shù)的數(shù)學(xué)模型向外或向最佳解波動(dòng). 人工樹(shù)算法(AT)[15-16]是2017年由Li等人提出的模擬樹(shù)的生長(zhǎng)規(guī)律提出的一種基于種群的算法. 這些啟發(fā)式算法還有例如人工魚(yú)群算法[17]、 果蠅優(yōu)化算法[18-19]、 飛蛾撲火優(yōu)化算法[19]和鯨優(yōu)化算法[20-21], 但這些算法不能解決所有的優(yōu)化問(wèn)題.

學(xué)者們對(duì)這些元啟發(fā)算法不斷改進(jìn)，通過(guò)優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的參數(shù)構(gòu)建多種模型來(lái)解決各種實(shí)際問(wèn)題，例如：改進(jìn)的指數(shù)遞減慣性權(quán)重的PSO優(yōu)化徑向基神經(jīng)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)空氣指數(shù)的預(yù)測(cè)[9], 基于改進(jìn)的動(dòng)態(tài)PSO和AdaBoost算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)上證指數(shù)的預(yù)測(cè)[10]，混沌的動(dòng)態(tài)加權(quán)PSO[12]用于函數(shù)優(yōu)化，且克服了早熟收斂和易陷入局部最優(yōu)解的缺點(diǎn)，在鯨優(yōu)化算法中引入了混沌理論，提高了全局收斂的速度，獲得了更好的性能[22].

2018年提出的團(tuán)隊(duì)博弈算法(Team Game Algorithm,TGA)[23]是一種基于競(jìng)賽策略的元啟發(fā)優(yōu)化算法，這些競(jìng)賽策略包括足球、 排球、 籃球、 水球等. 本文在TGA中引入了混沌參數(shù)以強(qiáng)化TGA的性能，這樣就得到了混沌的動(dòng)態(tài)TGA，記為CDTGA. 通過(guò)10個(gè)基準(zhǔn)函數(shù)驗(yàn)證CDTGA的性能，并將CDTGA與BP神經(jīng)網(wǎng)絡(luò)(BPNN)相結(jié)合建立預(yù)測(cè)美國(guó)流感樣疾病(Influence-Like Illness, ILI)的預(yù)測(cè)模型CDTGA-BPNN，并將CDTGA與PSO, SCA, AT和TGA進(jìn)行了比較，且將CDTGA-BPNN與BPNN, PSO-BPNN, SCA-BPNN, AT-BPNN和TGA-BPNN進(jìn)行了比較.

1 團(tuán)隊(duì)博弈算法

團(tuán)隊(duì)博弈算法(Team Game Algorithm, TGA)[23]是2018年由M.J. Mahmoodabadi等人提出的一種基于競(jìng)賽策略的元啟發(fā)優(yōu)化算法. 在TGA中，球員是個(gè)體的角色，他們的表現(xiàn)將通過(guò)耐力來(lái)衡量，耐力用優(yōu)化方法中的適應(yīng)度來(lái)表示. 個(gè)體包括兩隊(duì)的球員，并相互聯(lián)系. 隊(duì)友之間的合作是為了爭(zhēng)取進(jìn)球. 耐力越強(qiáng)的球員在球場(chǎng)上呆的時(shí)間越長(zhǎng)，也越有可能一直呆到比賽結(jié)束.

在TGA中，每個(gè)個(gè)體包括三類算子：傳球、 犯規(guī)和替補(bǔ)，其中傳球是一種邏輯算子，犯規(guī)是一種隨機(jī)算子，替補(bǔ)是在疲憊的隊(duì)中所采用的算子. 一個(gè)隊(duì)只有通過(guò)傳球才有希望贏得比賽，比賽中的最優(yōu)球員也有可能在輸了的隊(duì)中.

在搜索空間中，任意給出n個(gè)球員為

式中：xi是第i個(gè)球員；D是xi的維數(shù).

A={x1A,x2A,…,xnA},

(1)

B={x1B,x2B,…,xnB}.

(2)

顯然，A∪B=X. 替補(bǔ)隊(duì)員的個(gè)數(shù)是任意的，他們坐在替補(bǔ)座位等待教練的命令進(jìn)行替補(bǔ).

球任意給了一個(gè)隊(duì)，在比賽中執(zhí)行三種算子：傳球、 犯規(guī)和替補(bǔ).

1) 傳球算子

傳球算子定義為

xi(t+1)=xi(t)+γCi(t+1),

(3)

Ci(t+1)=2xcap(t)-Ci(t)-xrand(t),

(4)

式中：xi(t)為東道主隊(duì)中的第i個(gè)球員的位置；C為拿球的球員、 任意球員xrand(t)和隊(duì)長(zhǎng)xcap(t)之間的交流方式；γ是分量在 [0,1]內(nèi)的任意數(shù)的向量.

2) 犯規(guī)算子

犯規(guī)算子是球員的錯(cuò)誤，只有當(dāng)概率條件滿足時(shí)才執(zhí)行. 在這個(gè)算子中，拿球的球員與對(duì)方球隊(duì)的球員相互接觸. 這種接觸的結(jié)果是改變拿球球員的分量，公式為

(5)

3) 替補(bǔ)算子. 在迭代過(guò)程中通過(guò)檢查球員的適應(yīng)度引進(jìn)替補(bǔ)算子. 如果在一定的迭代次數(shù)內(nèi)球員的適應(yīng)度沒(méi)有得到改進(jìn)，該球員被新的替補(bǔ)球員替換，替補(bǔ)球員參加比賽.

另外，檢查拿球的球員的位置. 一旦他離開(kāi)了比賽場(chǎng)地，該位置將被重置為任意向量.

在TGA的結(jié)構(gòu)中，球員觀察彼此的性能，從他們犯規(guī)算子中進(jìn)行學(xué)習(xí)以改進(jìn)其適應(yīng)度； 替補(bǔ)算子的作用是阻止算法陷入局部最優(yōu)值.

2 混沌動(dòng)態(tài)TGA

將動(dòng)態(tài)參數(shù)引入到TGA中，得到動(dòng)態(tài)的TGA，記為DTGA.

(6)

(7)

(8)

(9)

式中：s是第s次迭代；Maxgen是最大迭代次數(shù). 因?yàn)閯?dòng)態(tài)參數(shù)是在混沌理論的基礎(chǔ)上選擇的，因此，將DTGA稱為混沌的動(dòng)態(tài)TGA, 記為CDTGA.

3 實(shí) 驗(yàn)

3.1 函數(shù)優(yōu)化

本節(jié)所選用的10個(gè)基準(zhǔn)函數(shù)見(jiàn)表1.

表1 10個(gè)基準(zhǔn)函數(shù)

表1 中列出了7個(gè)單峰函數(shù)f1,f2,f3,f4,f5,f6,f7和3個(gè)多峰函數(shù)f8,f9,f10的名稱、 數(shù)學(xué)表達(dá)式、 變量的范圍和最小值.

為了驗(yàn)證CDTGA的有效性，選取PSO,AT,TGA作為比較算法. 這四種算法中，最大迭代次數(shù)為4 000或10 000，種群大小為50，每個(gè)函數(shù)的變量的個(gè)數(shù)n=30. PSO 的慣性權(quán)重選取CDTGA的動(dòng)態(tài)參數(shù)ωs.

在TGA和CDTGA中，執(zhí)行替補(bǔ)算子滿足的條件是迭代2 000次適應(yīng)度沒(méi)有變換. 分別獨(dú)立運(yùn)行PSO,AT,TGA和CDTGA各30次，得到的數(shù)值結(jié)果如表2 和表3 所示.

表2 10個(gè)基準(zhǔn)函數(shù)在最大迭代次數(shù)為4 000時(shí)的數(shù)值結(jié)果

表3 10個(gè)基準(zhǔn)函數(shù)在最大迭代次數(shù)為10 000時(shí)的數(shù)值結(jié)果

表2 和表3 列出了30次運(yùn)行結(jié)果的最小值、 最大值、 平均值和標(biāo)準(zhǔn)差. 由表2 和表3 可以看到，CDTGA得到的f1,f3,f4,f7,f8,f9和f10的最小值、 最大值、 平均值和標(biāo)準(zhǔn)差均不超過(guò)PSO,SCA,AT和TGA得到的最小值、 最大值、 平均值和標(biāo)準(zhǔn)差. 兩個(gè)表的比較結(jié)果表明，本文所提出的CDTGA優(yōu)于PSO,SCA,AT和TGA，且改進(jìn)了TGA，是一種較好的算法.

3.2 基于CDTGA優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)的流感樣疾病預(yù)測(cè)

3.2.1 預(yù)測(cè)模型

在網(wǎng)絡(luò)訓(xùn)練過(guò)程中將預(yù)測(cè)值與實(shí)際值之間的均方根誤差(Mean Square Error, MSE)作為CDTGA-BPNN的適應(yīng)度函數(shù)，定義為

(10)

3.2.2 數(shù)據(jù)

本文所采用的美國(guó)CDC流感樣疾病的數(shù)據(jù)是從網(wǎng)站https://gis.cdc.gov/grasp/fluview/fluportaldashboard.html下載的，這些數(shù)據(jù)包括由健康與公共事業(yè)(Health and Human Services,HHS)定義的10個(gè)區(qū)從2002年第40周到2017年第36周的780周的數(shù)據(jù).

在利用CDTGA-BPNN預(yù)測(cè)CDC的流感樣疾病之前，需要將這些流感樣疾病預(yù)處理為區(qū)間[-1,1]中的值，處理方式為

(11)

式中：x為預(yù)處理之前的原始數(shù)據(jù)；xmin和xmax分別為預(yù)處理之前原始數(shù)據(jù)的最小值和最大值；y為預(yù)處理后的數(shù)據(jù)；ymin和ymax分別為預(yù)處理之后原始數(shù)據(jù)的最小值和最大值.本文中，ymin=-1,ymax=1.

本文考慮了美國(guó)CDC定義的10個(gè)區(qū)的未加權(quán)的%ILI，選取前5周未加權(quán)的%ILI預(yù)測(cè)第6周的未加權(quán)的%ILI，預(yù)測(cè)模型的評(píng)價(jià)標(biāo)準(zhǔn)為均方誤差(Mean Squared Error, MSE)[8], 相對(duì)均方誤差(Relative Mean Squared Error,RMSE)[8]，平均絕對(duì)百分比誤差(Mean Absolute Percentage Error, MAPE)[8].

(12)

(13)

(14)

3.2.3 模型

本節(jié)選取從2002年第40周到2017年第36周的780周的未加權(quán)的%ILI 數(shù)據(jù)，利用前5周的未加權(quán)的%ILI預(yù)測(cè)第6周的未加權(quán)的 %ILI. 這樣就獲得了779個(gè)5維向量. 將這779個(gè)向量最初90%的向量作為訓(xùn)練樣本，剩余的向量作為測(cè)試樣本.

所建立的BPNN的結(jié)構(gòu)為p-m-r，其中p是輸入向量的維數(shù)，m是隱含層神經(jīng)元的節(jié)點(diǎn)個(gè)數(shù)，r是輸出層神經(jīng)元的個(gè)數(shù).本文中p=5,r=1.經(jīng)過(guò)大量的實(shí)驗(yàn)，選取m=10，最大迭代次數(shù)為5 000，動(dòng)量因子為0.95, 學(xué)習(xí)率為0.002. 為了與CDTGA-BPNN作比較，本文分別選取PSO，SCA，AT和TGA優(yōu)化BPNN 的參數(shù)，得到模型: PSO-BPNN, SCA-BPNN, AT-BPNN和TGA-BPNN. 將這5種模型獨(dú)立運(yùn)行10次. 模型PSO-BPNN, SCA-BPNN, AT-BPNN, TGA-BPNN和CDTGA-BPNN的BPNN部分的參數(shù)設(shè)置與BPNN的參數(shù)設(shè)置相同. PSO, SCA, AT, TGA和CDTGA的種群大小為50，最大迭代次數(shù)為500. 模型PSO-BPNN中，慣性權(quán)重選取如式(8)所示.

3.2.4 預(yù)測(cè)結(jié)果

首先利用式(11)將原始數(shù)據(jù)處理成標(biāo)準(zhǔn)數(shù)據(jù). 對(duì)于上述選擇的參數(shù)，利用訓(xùn)練樣本訓(xùn)練BPNN, PSO-BPNN, SCA-BPNN, AT-BPNN, TGA-BPNN和CDTGA-BPNN，得到測(cè)試樣本的輸出，通過(guò)反歸一化得到測(cè)試樣本的預(yù)測(cè)值，并得到每個(gè)模型的評(píng)價(jià)指標(biāo)MSE,RMSE和MAPE. 每種模型獨(dú)立運(yùn)行10次，得到測(cè)試樣本的平均MSE, RMSE和MAPE，如表4 所示.

表4 列出了10個(gè)區(qū)的預(yù)測(cè)值與實(shí)際值之間的平均MSE,RMSE和MAPE. 通過(guò)比較可以發(fā)現(xiàn)，本文所提出的模型CDTGA-BPNN優(yōu)于模型BPNN,PSO-BPNN,SCA-BPNN,AT-BPNN和TGA-BPNN. 從表4 可以看到, CDTGA-BPNN 在區(qū)1～區(qū)6和區(qū)8具有最小的平均MSE,RMSE和MAPE，區(qū)1～區(qū)6和區(qū)8具有最小的MSE，分別為0.039 2, 0.129 6, 0.128 8, 0.163 5, 0.068 6, 0.108 6, 0.041 5； 區(qū)1～區(qū)6和區(qū)8具有最小的RMSE，分別為0.031 1, 0.013 8, 0.014 9, 0.019 8, 0.015 6, 0.016 0, 0.034 8； 區(qū)1～區(qū)6和區(qū)8具有最小的MAPE，分別為13.899 8%, 9.298 2%, 9.879 8%, 11.692 9%, 10.298 4%, 9.336 8%, 13.327 8%，說(shuō)明模型CDTGA-BPNN適合這7個(gè)區(qū)的未加權(quán)的%ILI預(yù)測(cè). 但PSO-BPNN適合區(qū)9 的未加權(quán)的%ILI預(yù)測(cè)，具有最小的平均MSE=0.039 2,MSE=0.011 5，MAPE=8.550 5%. 對(duì)于區(qū)7, PSO-BPNN是具有最小平均RMSE的模型, AT-BPNN是具有最小MSE的模型，TGA-BPNN是具有最小MAPE的模型. 對(duì)于區(qū)10, PSO-BPNN是具有最小平均MSE的模型, TGA-BPNN是具有最小RMSE和MAPE的模型.

表4 10個(gè)區(qū)測(cè)試樣本的平均MSE，RMSE和MAP

為了綜合考慮所提出模型的性能，我們將這10個(gè)區(qū)的MSE，RMSE和MAPE取平均作為整個(gè)美國(guó)未加權(quán)的%ILI的MSE，RMSE和MAPE，如表5 所示. 從表5 可見(jiàn)，CDTGA-BPNN的MSE=0.100 5,RMSE=0.070 7和MAPE=15.190 4%，低于其它比較的模型BPNN, PSO-BPNN, SCA-BPNN, AT-BPNN和TGA-BPNN的MSE，RMSE和MAPE, 表明CDTGA-BPNN優(yōu)于BPNN, PSO-BPNN, SCA-BPNN, AT-BPNN和GTA-BPNN.

表5 整個(gè)美國(guó)測(cè)試樣本的平均MSE,RMSE和MAPE

4 結(jié) 論

本文在團(tuán)隊(duì)博弈算法的基礎(chǔ)上提出了混沌的動(dòng)態(tài)團(tuán)隊(duì)博弈算法CDTGA，通過(guò)10個(gè)基準(zhǔn)函數(shù)驗(yàn)證了CDTGA的有效性. 為了克服BPNN初始權(quán)值的任意性，將CDTGA與BPNN相結(jié)合建立了預(yù)測(cè)模型CDTGA-BPNN來(lái)預(yù)測(cè)美國(guó)CDC未加權(quán)的%ILI. 比較結(jié)果表明，模型CDTGA-BPNN優(yōu)于模型BPNN, PSO-BPNN, SCA-BPNN, AT-BPNN和TGA-BPNN，CDTGA適合找到函數(shù)的全局最優(yōu)解且適于與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合預(yù)測(cè)流感樣疾病，由此可得到一些啟示：群智能算法能夠求解優(yōu)化問(wèn)題，并可與不同的神經(jīng)網(wǎng)絡(luò)相結(jié)合實(shí)現(xiàn)預(yù)測(cè)和分類. 另外，可以提出更多新的或改進(jìn)的算法，并與人工神經(jīng)網(wǎng)絡(luò)相結(jié)合以應(yīng)用于更多領(lǐng)域.