1 算法介紹

1.1 蟻群算法

?1 蟻群算法(ant colony algorithm,ACA)起源和發(fā)展歷程
Marco Dorigo等人在研究新型算法的過程中，發(fā)現(xiàn)蟻群在尋找食物時(shí)，通過分泌一種稱為信息素的生物激素交流覓食信息從而能快速的找到目標(biāo)，于是在1991年在其博士論文中首次系統(tǒng)地提出一種基于螞蟻種群的新型智能優(yōu)化算法“螞蟻系統(tǒng)（Ant system,簡(jiǎn)稱AS）”，后來，提出者及許多研究者對(duì)該算法作了各種改進(jìn)，將其應(yīng)用于更為廣泛的領(lǐng)域，如圖著色問題、二次分配問題、工件排序問題、車輛路徑問題、車間作業(yè)調(diào)度問題、網(wǎng)絡(luò)路由問題、大規(guī)模集成電路設(shè)計(jì)等。近些年來，M.Dorigo等人把螞蟻算法進(jìn)一步發(fā)展成一種通用的優(yōu)化技術(shù)“蟻群優(yōu)化（Ant Colony Optimization,簡(jiǎn)稱ACO）”，并將所有符合ACO框架的算法稱為“蟻群優(yōu)化算法（ACO algorithm）”。

具體來說，各個(gè)螞蟻在沒有事先告知食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物以后，它會(huì)向環(huán)境釋放一種揮發(fā)性分泌物pheromone (稱為信息素,該物質(zhì)隨著時(shí)間的推移會(huì)逐漸揮發(fā)消失，信息素濃度的大小表征路徑的遠(yuǎn)近)信息素能夠讓其他螞蟻感知從而起到一個(gè)引導(dǎo)的作用。通常多個(gè)路徑上均有信息素時(shí)，螞蟻會(huì)優(yōu)先選擇信息素濃度高的路徑，從而使?jié)舛雀叩穆窂叫畔⑺貪舛雀?，形成一個(gè)正反饋。有些螞蟻并沒有像其它螞蟻一樣總重復(fù)同樣的路，他們會(huì)另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那么，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時(shí)間運(yùn)行，可能會(huì)出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。最終，信息素濃度最高的路徑即是最終被螞蟻選中的最優(yōu)路徑。
與其他算法相比，蟻群算法是一種比較年輕的算法，具有分布式計(jì)算、無中心控制、個(gè)體之間異步間接通信等特點(diǎn)，并且易于與其他優(yōu)化算法相結(jié)合，經(jīng)過不少仁人志士的不斷探索，到今天已經(jīng)發(fā)展出了各式各樣的改進(jìn)蟻群算法，不過蟻群算法的原理仍是主干。

2 蟻群算法的求解原理
基于上述對(duì)蟻群覓食行為的描述，該算法主要對(duì)覓食行為進(jìn)行以下幾個(gè)方面模擬：
（1）模擬的圖場(chǎng)景中包含了兩種信息素，一種表示家，一種表示食物的地點(diǎn)，并且這兩種信息素都在以一定的速率進(jìn)行揮發(fā)。
（2）每個(gè)螞蟻只能感知它周圍的小部分地方的信息。螞蟻在尋找食物的時(shí)候，如果在感知范圍內(nèi)，就可以直接過去，如果不在感知范圍內(nèi)，就要朝著信息素多的地方走，螞蟻可以有一個(gè)小概率不往信息素多的地方走，而另辟蹊徑，這個(gè)小概率事件很重要，代表了一種找路的創(chuàng)新，對(duì)于找到更優(yōu)的解很重要。
（3）螞蟻回窩的規(guī)則與找食物的規(guī)則相同。
（4）螞蟻在移動(dòng)時(shí)候首先會(huì)根據(jù)信息素的指引，如果沒有信息素的指引，會(huì)按照自己的移動(dòng)方向慣性走下去，但也有一定的機(jī)率改變方向，螞蟻還可以記住已經(jīng)走過的路，避免重復(fù)走一個(gè)地方。
（5）螞蟻在找到食物時(shí)留下的信息素最多，然后距離食物越遠(yuǎn)的地方留下的信息素越少。找到窩的信息素留下的量的規(guī)則跟食物相同。蟻群算法有以下幾個(gè)特點(diǎn):正反饋算法、并發(fā)性算法、較強(qiáng)的魯棒性、概率型全局搜索、不依賴嚴(yán)格的數(shù)學(xué)性質(zhì)、搜索時(shí)間長，易出現(xiàn)停止現(xiàn)象。
螞蟻轉(zhuǎn)移概率公式：

公式中：是螞蟻k從城市i轉(zhuǎn)移到j(luò)的概率；α，β分別為信息素和啟發(fā)式因子的相對(duì)重要程度；為邊（i，j）上的信息素量；為啟發(fā)式因子；為螞蟻k下步允許選擇的城市。上述公式即為螞蟻系統(tǒng)中的信息素更新公式，是邊（i,j)上的信息素量；ρ是信息素蒸發(fā)系數(shù)，0<ρ<1;為第k只螞蟻在本次迭代中留在邊（i,j）上的信息素量；Q為一正常系數(shù)；為第k只螞蟻在本次周游中的路徑長度。
在螞蟻系統(tǒng)中，信息素更新公式為：

3 蟻群算法的求解步驟：
（1）初始化參數(shù)在計(jì)算之初，需要對(duì)相關(guān)參數(shù)進(jìn)行初始化，如蟻群規(guī)模（螞蟻數(shù)量）m、信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素會(huì)發(fā)銀子ρ、信息素釋放總量Q、最大迭代次數(shù)iter_max、迭代次數(shù)初值iter=1。
（2）構(gòu)建解空間將各個(gè)螞蟻隨機(jī)地置于不同的出發(fā)點(diǎn)，對(duì)每個(gè)螞蟻k（k=1,2,3…m），按照（2-1）計(jì)算其下一個(gè)待訪問城市，直到所有螞蟻訪問完所有城市。
（3）更新信息蘇計(jì)算每個(gè)螞蟻經(jīng)過路徑長度Lk(k=1,2,…，m），記錄當(dāng)前迭代次數(shù)中的最優(yōu)解（最短路徑）。同時(shí)，根據(jù)式（2-2）和（2-3）對(duì)各個(gè)城市連接路徑上信息素濃度進(jìn)行更新。
（4） 判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經(jīng)過路徑的記錄表，并返回步驟2；否則，終止計(jì)算，輸出最優(yōu)解。
（5）判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經(jīng)過路徑的記錄表，并返回步驟2；否則，終止計(jì)算，輸出最優(yōu)解。3. 判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經(jīng)過路徑的記錄表，并返回步驟2；否則，終止計(jì)算，輸出最優(yōu)解。

1.2 bp神經(jīng)網(wǎng)絡(luò)

說明：1.1節(jié)主要是概括和幫助理解考慮影響因素的BP神經(jīng)網(wǎng)絡(luò)算法原理，即常規(guī)的BP模型訓(xùn)練原理講解（可根據(jù)自身掌握的知識(shí)是否跳過）。1.2節(jié)開始講基于歷史值影響的BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型。

使用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)時(shí)，從考慮的輸入指標(biāo)角度，主要有兩類模型：

1.2.1?受相關(guān)指標(biāo)影響的BP神經(jīng)網(wǎng)絡(luò)算法原理

如圖一所示，使用MATLAB的newff函數(shù)訓(xùn)練BP時(shí)，可以看到大部分情況是三層的神經(jīng)網(wǎng)絡(luò)（即輸入層，隱含層，輸出層）。這里幫助理解下神經(jīng)網(wǎng)絡(luò)原理：
1）輸入層：相當(dāng)于人的五官，五官獲取外部信息，對(duì)應(yīng)神經(jīng)網(wǎng)絡(luò)模型input端口接收輸入數(shù)據(jù)的過程。
2）隱含層：對(duì)應(yīng)人的大腦，大腦對(duì)五官傳遞來的數(shù)據(jù)進(jìn)行分析和思考，神經(jīng)網(wǎng)絡(luò)的隱含層hidden Layer對(duì)輸入層傳來的數(shù)據(jù)x進(jìn)行映射，簡(jiǎn)單理解為一個(gè)公式hiddenLayer_output=F(w*x+b)。其中，w、b叫做權(quán)重、閾值參數(shù)，F(xiàn)()為映射規(guī)則，也叫激活函數(shù)，hiddenLayer_output是隱含層對(duì)于傳來的數(shù)據(jù)映射的輸出值。換句話說，隱含層對(duì)于輸入的影響因素?cái)?shù)據(jù)x進(jìn)行了映射，產(chǎn)生了映射值。
3）輸出層：可以對(duì)應(yīng)為人的四肢，大腦對(duì)五官傳來的信息經(jīng)過思考（隱含層映射）之后，再控制四肢執(zhí)行動(dòng)作（向外部作出響應(yīng)）。類似地，BP神經(jīng)網(wǎng)絡(luò)的輸出層對(duì)hiddenLayer_output再次進(jìn)行映射，outputLayer_output=w *hiddenLayer_output+b。其中，w、b為權(quán)重、閾值參數(shù)，outputLayer_output是神經(jīng)網(wǎng)絡(luò)輸出層的輸出值（也叫仿真值、預(yù)測(cè)值）（理解為，人腦對(duì)外的執(zhí)行動(dòng)作，比如嬰兒拍打桌子）。
4）梯度下降算法：通過計(jì)算outputLayer_output和神經(jīng)網(wǎng)絡(luò)模型傳入的y值之間的偏差，使用算法來相應(yīng)調(diào)整權(quán)重和閾值等參數(shù)。這個(gè)過程，可以理解為嬰兒拍打桌子，打偏了，根據(jù)偏離的距離遠(yuǎn)近，來調(diào)整身體使得再次揮動(dòng)的胳膊不斷靠近桌子，最終打中。

再舉個(gè)例子來加深理解：

圖一所示BP神經(jīng)網(wǎng)絡(luò)，具備輸入層、隱含層和輸出層。BP是如何通過這三層結(jié)構(gòu)來實(shí)現(xiàn)輸出層的輸出值outputLayer_output，不斷逼近給定的y值，從而訓(xùn)練得到一個(gè)精準(zhǔn)的模型的呢？

從圖中串起來的端口，可以想到一個(gè)過程：坐地鐵，將圖一想象為一條地鐵線路。王某某坐地鐵回家的一天：在input起點(diǎn)站上車，中途經(jīng)過了很多站（hiddenLayer），然后發(fā)現(xiàn)坐過頭了（outputLayer對(duì)應(yīng)現(xiàn)在的位置），那么王某某將會(huì)根據(jù)現(xiàn)在的位置離家（目標(biāo)Target）的距離（誤差Error），返回到中途的地鐵站（hiddenLayer）重新坐地鐵（誤差反向傳遞，使用梯度下降算法更新w和b），如果王某某又一次發(fā)生失誤，那么將再次進(jìn)行這個(gè)調(diào)整的過程。

從在嬰兒拍打桌子和王某某坐地鐵的例子中，思考問題：BP的完整訓(xùn)練，需要先傳入數(shù)據(jù)給input，再經(jīng)過隱含層的映射，輸出層得到BP仿真值，根據(jù)仿真值與目標(biāo)值的誤差，來調(diào)整參數(shù)，使得仿真值不斷逼近目標(biāo)值。比如（1）嬰兒受到了外界的干擾因素（x），從而作出反應(yīng)拍桌（predict），大腦不斷的調(diào)整胳膊位置，控制四肢拍準(zhǔn)（y、Target）。（2）王某某上車點(diǎn)（x），過站點(diǎn)（predict），不斷返回中途站來調(diào)整位置，到家（y、Target）。

在這些環(huán)節(jié)中，涉及了影響因素?cái)?shù)據(jù)x，目標(biāo)值數(shù)據(jù)y（Target）。根據(jù)x，y，使用BP算法來尋求x與y之間存在的規(guī)律，實(shí)現(xiàn)由x來映射逼近y，這就是BP神經(jīng)網(wǎng)絡(luò)算法的作用。再多說一句，上述講的過程，都是BP模型訓(xùn)練，那么最終得到的模型雖然訓(xùn)練準(zhǔn)確，但是找到的規(guī)律（bp network）是否準(zhǔn)確與可靠呢。于是，我們?cè)俳ox1到訓(xùn)練好的bp network中，得到相應(yīng)的BP輸出值（預(yù)測(cè)值）predict1，通過作圖，計(jì)算Mse，Mape，R方等指標(biāo)，來對(duì)比predict1和y1的接近程度，就可以知道模型是否預(yù)測(cè)準(zhǔn)確。這是BP模型的測(cè)試過程，即實(shí)現(xiàn)對(duì)數(shù)據(jù)的預(yù)測(cè)，并且對(duì)比實(shí)際值檢驗(yàn)預(yù)測(cè)是否準(zhǔn)確。

圖一 3層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

1.2.2?基于歷史值影響的BP神經(jīng)網(wǎng)絡(luò)

以電力負(fù)荷預(yù)測(cè)問題為例，進(jìn)行兩種模型的區(qū)分。在預(yù)測(cè)某個(gè)時(shí)間段內(nèi)的電力負(fù)荷時(shí)：

一種做法，是考慮?t?時(shí)刻的氣候因素指標(biāo)，比如該時(shí)刻的空氣濕度x1，溫度x2，以及節(jié)假日x3等的影響，對(duì)?t?時(shí)刻的負(fù)荷值進(jìn)行預(yù)測(cè)。這是前面1.1所說的模型。

另一種做法，是認(rèn)為電力負(fù)荷值的變化，與時(shí)間相關(guān)，比如認(rèn)為t-1，t-2，t-3時(shí)刻的電力負(fù)荷值與t時(shí)刻的負(fù)荷值有關(guān)系，即滿足公式y(tǒng)(t)=F(y(t-1),y(t-2),y(t-3))。采用BP神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練模型時(shí)，則輸入到神經(jīng)網(wǎng)絡(luò)的影響因素值為歷史負(fù)荷值y(t-1),y(t-2),y(t-3)，特別地，3叫做自回歸階數(shù)或者延遲。給到神經(jīng)網(wǎng)絡(luò)中的目標(biāo)輸出值為y(t)。

?

2 部分代碼

clc clear close all data=xlsread('data1.xls'); data(:,[7,9,20])=[]; [r c]=size(data); k=rand(1,r); [m,n]=sort(k); kkk=round(r*0.7); % b=ismissing(data); % sum(b) input=data(:,1:end-1); output=data(:,end); %% 訓(xùn)練數(shù)據(jù) P_train=input(n(1:kkk),:)';% 輸入3-12列 T_train=output(n(1:kkk),:)';% 輸出13列 %% 測(cè)試樣本 P_test=input(n(kkk+1:end),:)';% 輸入3-12列 T_test=output(n(kkk+1:end),:)';% 輸出13列 %% 數(shù)據(jù)歸一化 % 訓(xùn)練樣本 [Pn_train,inputps] = mapminmax(P_train,-1,1); Pn_test = mapminmax('apply',P_test,inputps); % 測(cè)試樣本 [Tn_train,outputps] = mapminmax(T_train,-1,1); Tn_test = mapminmax('apply',T_test,outputps); [inputnum,N]=size(Pn_train);%輸入節(jié)點(diǎn)數(shù)量 outputnum=size(Tn_train,1);%輸出節(jié)點(diǎn)數(shù)量 hiddennum=8; %構(gòu)建網(wǎng)絡(luò) net=newff(Pn_train,Tn_train,hiddennum); %% HS算法參數(shù)初始化 nVar=inputnum*hiddennum+hiddennum+hiddennum*outputnum+outputnum; %% 蟻群算法ACO參數(shù)初始化 Ant = 20; ? ?% 螞蟻數(shù)量 Times =10; % 螞蟻移動(dòng)次數(shù) Rou = 0.82; ? % 信息素?fù)]發(fā)系數(shù) P0 = 0.21; ? ?% 轉(zhuǎn)移概率常數(shù) %% 取值范圍 popmax = 8; ? ? ? ? ? ? ? ? % 待尋優(yōu)閾值最大取值初始化 popmin =-8; ? ? ? ? ? ? ? ?% 待尋優(yōu)閾值最小取值初始化 %% BP網(wǎng)絡(luò)訓(xùn)練 %網(wǎng)絡(luò)進(jìn)化參數(shù) net.trainParam.epochs=1e5; net.trainParam.lr=0.1; net.trainParam.goal=0.001; %網(wǎng)絡(luò)訓(xùn)練 net=train(net,Pn_train,Tn_train); %% 訓(xùn)練集 T_sim=sim(net,Pn_train); T_simu=mapminmax('reverse',T_sim,outputps); T_simu figure plot(1:length(T_simu),T_simu,'r-o','linewidth',1) hold on plot(1:length(T_train),T_train,'b-.','linewidth',1) xlabel('訓(xùn)練樣本') ylabel('污垢') % title('蟻群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)（ACO-BP）') legend('預(yù)測(cè)值','實(shí)際值') %% BP網(wǎng)絡(luò)預(yù)測(cè) % %數(shù)據(jù)歸一化 % Pn_test=mapminmax('apply',P_test,inputps); an=sim(net,Pn_test); test_simu=mapminmax('reverse',an,outputps); %error=test_simu-output_test; figure plot(1:length(test_simu(1:100)),test_simu(1:100),'r-o','linewidth',1) hold on plot(1:length(test_simu(1:100)),T_test(1:100),'b-.','linewidth',1) ylabel('污垢') % title('蟻群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)（ACO-BP）') legend('預(yù)測(cè)值','實(shí)際值') kk=test_simu-T_test % % 自程序objfun_BP % function error = objfun_BP(x,inputnum,hiddennum,outputnum,net,inputn,outputn) % %該函數(shù)用來計(jì)算適應(yīng)度值 % %x ? ? ? ? ?input ? ? 個(gè)體 % %inputnum ? input ? ? 輸入層節(jié)點(diǎn)數(shù) % %outputnum ?input ? ? 隱含層節(jié)點(diǎn)數(shù) % %net ? ? ? ?input ? ? 網(wǎng)絡(luò) % %inputn ? ? input ? ? 訓(xùn)練輸入數(shù)據(jù) % %outputn ? ?input ? ? 訓(xùn)練輸出數(shù)據(jù) % % %error ? ? ?output ? ?個(gè)體適應(yīng)度值 % % %提取 % w1=x(1:inputnum*hiddennum) % B1=x(inputnum*hiddennum+1:inputnum*hiddennum+hiddennum); % w2=x(inputnum*hiddennum+hiddennum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum); % B2=x(inputnum*hiddennum+hiddennum+hiddennum*outputnum+1:inputnum*hiddennum+hiddennum+hiddennum*outputnum+outputnum); % % % %網(wǎng)絡(luò)權(quán)值賦值 % net.iw{1,1}=reshape(w1,hiddennum,inputnum); % net.lw{2,1}=reshape(w2,outputnum,hiddennum); % net.b{1}=reshape(B1,hiddennum,1); % net.b{2}=reshape(B2,outputnum,1); % % % %網(wǎng)絡(luò)進(jìn)化參數(shù) % net.trainParam.epochs=1e5; % net.trainParam.lr=0.1; % net.trainParam.goal=0.00001; % net.trainParam.show=100; % net.trainParam.showWindow=0; % % % %網(wǎng)絡(luò)訓(xùn)練 % net=train(net,inputn,outputn); % % an=sim(net,inputn); % % error=sum(abs(an-outputn)); % end

3 仿真結(jié)果

?

4 參考文獻(xiàn)

[1]劉瑞晨. 基于蟻群算法與BP神經(jīng)網(wǎng)絡(luò)的橋式起重機(jī)驅(qū)動(dòng)優(yōu)化研究[D].太原科技大學(xué),2020.

?