基于自適應精英蟻群算法的GM(1,1)預測模型

李 眩,吳曉兵,童百利

(銅陵職業技術學院 經貿系，安徽 銅陵 244061)

20世紀80年代，鄧聚龍教授創立了研究“少數據，貧信息的不確定問題”的灰色系統理論，其中灰色GM(1,1)預測模型被廣泛應用于工業、農業、經濟等領域，是應用非常廣泛的一種預測模型.但對于非準光滑數據序列、非平穩的高增長數據序列(發展系數|-a|大于0.5)，模型的預測精度不理想.研究學者迫切尋找能提升GM(1,1)模型預測精度的有效方法，他們從GM(1,1)模型的初始值[1]、背景值構造[2]、殘差修正[3]、灰導數[4]等多方面進行改進，取得了不少成果.但在模型參數辨識上，傳統數學方法始終是存在缺陷，得到的參數并非最優參數，尤其是在預測非平穩數據序列時，傳統數學方法求解的參數模型會產生較大誤差[5].模型參數直接影響著模型的預測精度，實質上求解GM模型最優參數來提升精度問題是一個優化問題，近年來人類通過模仿生物體進化機制發展起來的人工智能算法完美解決了一些高度復雜的優化問題，為該問題的解決提供了新的思路.考慮到蟻群算法像其他智能算法一樣容易陷入局部最優的缺點，本文提出一種信息素濃度自適應調整的精英蟻群算法(ACO算法)來求解GM模型的發展系數和灰色作用量，期望為提升灰色預測模型精度提供一種新的有效方法，并通過實例分析證明該方法的有效性和科學性.

1 灰色GM(1,1)預測模型

GM(1,1)模型是灰色系統理論中最基礎的預測模型，在預測形式上屬于單數列預測模型，只用到系統行為序列，而無外作用序列，是應用最廣泛的灰色系統預測模型.GM(1,1)模型的預測原理是：對某一數據序列用累加的方式生成一組趨勢明顯的新數據序列，按照新數據序列的增長趨勢建立模型進行預測，然后再用累減的方法進行逆向還原，恢復出原始數據序列的預測值.

假設原始數據數列x(0)存在n個觀測值，即x(0)={x(0)(1),x(0)(2)…x(0)(n)}，將原始數據序列x(0)通過累加生成新數列x(1)，以此弱化數據序列的無規律性和隨機性以及隨機擾動對數據帶來的影響.通過累加生成可看出灰量累積過程的發展態勢，使雜亂原始數據中蘊含的規律體現出來.

得到新數列X(1)(n)={X(1)(1),X(1)(2)…X(1)(n)}，

由X(1)計算其緊鄰均值等權新數列Z(1)={Z(1)(2),Z(1)(3)…Z(1)(n)},

其中，Z(1)(k)=0.5x(1)(k)+0.5x(1)(k-1).

(1)

對數列X(1)，Z(1)建立白化微分方程構建GM(1,1)模型：

(2)

其白化方程為：x(0)(k)+a*Z(1)(k)=b.

(3)

a和b都是模型的待定參數，傳統GM模型都是根據數據采用最小二乘法求解參數.

由此可以求出兩個方程參數.方程(2)的解如式(4)所示：

(4)

GM(1,1)模型的時間響應序列為：

將上述結果累減還原，即可得到預測值：

(5)

GM模型的預測精度與模型參數(-a系統發展系數、b驅動項系數)有很大關系，所求參數解是否最優，直接影響到模型的預測精度.有理論分析和實踐表明,傳統的最小二乘法求解GM模型參數在數據“異常”時會失真較大[6].數據序列變化平穩(發展系數的絕對值<0.5)時，GM(1,1)模型的誤差很小，預測效果十分理想；但對于高增長數據序列(發展系數的絕對值>0.5)時，誤差很大，做預測都應十分謹慎.

灰色GM模型參數辨識的傳統數學求解方法是根據實際值與理論值的誤差平方和為目標函數，以其取值最小為目標計算偏導來求解.這樣建立的GM模型存在病態性和比較差的魯棒性，尤其當原始數據序列受到隨機擾動影響變化非平穩時，預測值會有較大誤差[7].人類通過模仿生物體進化機制使看起來高度復雜的優化問題得以完美解決，為傳統優化技術難以解決的優化問題提供了切實可行的解決方案，因此人們轉而采取仿生智能優化算法求解模型的最優參數，以此來降低求解參數誤差對模型精度的影響，大大促進了灰色理論與信息技術的融合，豐富了灰色系統理論的內涵.因此，本文對蟻群算法進行改進，提出了基于信息素濃度自適應調整的精英蟻群算法，在不改變GM(1,1)模型表示方式的前提下運用其求解GM模型最優參數來提高模型的預測精度.動態自適應精英蟻群算法求解模型參數的基本思想是通過螞蟻個體在解空間獨立搜索，通過信息共享找出群體當前最優解，蟻群在當前最優解的信息素引導下不斷迭代進化直至算法收斂尋得最終的全局最優解，其尋找參數最優解的科學性、合理性遠勝于傳統的數學方法.在此，并通過實際應用結果證明運用動態自適應精英蟻群算法提高GM模型預測精度的合理性和科學性.

2 信息素濃度自適應調整的蟻群算法求解GM模型參數

2.1 蟻群算法(ACO算法)簡介

蟻群算法是受自然界蟻群集體覓食行為的啟發而誕生的仿生智能算法.螞蟻個體行為很簡單，但由個體組成的蟻群卻能完成遠超個體能力的復雜任務，他們個體之間通過信息素來相互通訊和進行信息的傳遞，共同協作完成復雜任務.蟻群有能力在沒有任何先行提示情況下找到巢穴到食物的最短路徑，并能跟隨環境變化搜索新的路徑，其中體現了一種信息的正反饋現象：某一路徑上走過的螞蟻越多，該路徑上螞蟻留下的信息素就多，對后來螞蟻的吸引力就越大，使他們選擇信息素強度高的方向移動，螞蟻個體之間正是通過這種信息的交流而達到搜索食物的目的[8].螞蟻具有的智能行為得益于其簡單行為規則，該規則讓其具有多樣性和正反饋，在覓食時，多樣性使螞蟻不會走進死胡同而無限循環，是一種創新能力；正反饋使優良信息保存下來，是一種學習強化能力.兩者的巧妙結合使智能行為涌現，如果多樣性過剩，系統過于活躍，會導致過多的隨機運動，陷入混沌狀態；如果多樣性不夠，正反饋過強，會導致僵化，當環境變化時蟻群不能相應調整[9].受蟻群覓食尋找最短路徑行為的啟發，意大利學者Dorigo等人提出了模仿蟻群覓食行為的蟻群算法，其應用從最初的TSP問題擴展到了網絡路由、車輛調度、路線航跡規劃及集成電路布線設計等領域，蟻群算法的出現為解決復雜困難的系統優化問題提供了新的求解算法.

人工蟻群算法的螞蟻個體被表征為優化問題的一個潛在可行解，在眾多潛在可行解構成的解空間中根據適應度不斷進化迭代，直至算法收斂得到最終的全局最優解.算法體現了螞蟻覓食行為中的自催化機制，當一個問題的較優解附近聚集的螞蟻較多，其留下的信息素也就多，根據螞蟻傾向于選擇信息素強度大地方的特點，后來螞蟻移向該解區域的概率也就越大，反過來又增強了該區域的信息素強度，這種自催化機制利用信息作為反饋，通過對系統演化過程中較優解或較優方案的自增強，使得問題的解向著全局最優的方向不斷進化[10].蟻群算法中信息素和真實蟻群一樣存在著揮發，使得螞蟻逐漸淡忘過去，不受歷史經驗的過分約束，同時基于概率的前進決策策略使其趨向較優區域移動，從而逐步找到問題的最優解或最優方案[11].蟻群算法用于解決優化問題時，信息素是所要優化問題對應解或對應方案優劣程度，其用適應度函數值衡量，算法每經歷一次循環，就進行一次信息素的更新，一個有限的人工螞蟻群體通過信息素指引相互協作、分享信息，既能獨立地搜索，又能同時找到很多問題的不同解或不同方案，通過比較找出群體當前高質量的解，逐步進化得到問題的全局較優解或較優方案.

將蟻群算法應用于優化問題的基本思路為：螞蟻個體表示待優化問題的潛在可行解，整個螞蟻群體構成待優化問題的解空間.在較優解上螞蟻釋放的信息素量較多，隨著時間的推進，較優解上累積的信息素濃度逐漸增高，較優解位置聚集的螞蟻數量也愈來愈多；較差解上遺留的信息素濃度會逐漸減少最后被遺忘，信息素的揮發機制使得螞蟻個體在移動的時候不會過多局限于以往螞蟻留下的歷史經驗，最終，整個群體中的螞蟻個體會在正反饋的作用下集中到最佳解上[12].

蟻群算法求解優化問題的實現過程如下：設置好蟻群螞蟻數Ant、迭代次數T、信息素揮發系數ρ、轉移概率閾值P0以及算法的搜索范圍(GM模型參數的取值大致范圍).模型參數的取值范圍(即蟻群的搜索范圍)根據具體問題進行適當設定.范圍設置過大，算法把搜索范圍遍歷一次，會降低算法的執行效率；范圍設置過小，沒有把具體問題的最優解包含在內，會造成算法不成熟收斂或者不收斂，得到的是問題的局部最優解或無解.本文在GM模型參數的求解問題上，在參考傳統GM模型近似解的基礎上來設置算法的搜索范圍，這樣有針對性的求解效率會高一些.蟻群算法中螞蟻個體數量必須根據問題的規模適當設置，太小則不能保證群體的多樣性，以致算法性能很差；種群太大盡管可以增加尋優的效率，阻止早熟收斂的發生，但無疑會增加計算量，造成收斂時間太長，表現為收斂速度緩慢.算法對每只螞蟻位置進行隨機初始化，并依據問題定義的適應度函數計算每只螞蟻對應的適應度值Tau(i)，進而比較求出蟻群群體當前最佳適應度值Tau(BestIndex).算法采用以概率為基礎的狀態轉移策略，螞蟻個體按照以找到解的適應度值計算得來的狀態轉移概率選擇前進的方向，按照下式計算每只螞蟻的轉移概率：

P(T,i)=(Tau(BestIndex)-Tau(i))/Tau(BestIndex),

(6)

其中，T表示當前的迭代次數；i表示蟻群中第i個螞蟻個體.當蟻群中的單個螞蟻位置與蟻群中最佳位置相差較遠時，螞蟻轉移概率P(T,i)值較大，大于轉移概率閾值P0，螞蟻應該離開當前位置區域去展開全局探索以避免陷入局部最優；當螞蟻離蟻群當前最佳位置較近，螞蟻轉移概率P(T,i)小于轉移概率閾值P0，該螞蟻則在當前位置鄰域展開局部搜索.每只螞蟻限定在解空間范圍內移動，如果超過邊界條件，按如下方法處理，這樣避免了螞蟻逃逸出解空間的可能性.

X(i，j)>Xjmax時,X(i，j)=Xjmax，X(i，j)

(7)

根據轉移概率更新螞蟻個體的位置、適應度值及其蟻群最優的適應度值，隨著時間的推移，如果蟻群找到當前解比原有解較優越，則用當前較優解替換原有解，原有解就會被遺忘；如果當前解比原有解較差，則之前解得到保留，且解的信息量會因螞蟻留下的信息素得到加強，可行較優解的信息素含量按下式調整：

Tau(i)=(1-Rou)*Tau(i)+F(i),

(8)

參數Rou表示信息素的揮發度；F(i)為當前循環第i只螞蟻找到解對應的適應度值.如此不斷進化迭代直至算法收斂找到問題最優解.信息素的運用使得蟻群算法具有較強的自我學習能力，可根據環境信息素濃度的變化和過去的行為結果對環境變化進行調整，從而實現算法求解能力的再進化.

2.2 自適應調整和精英策略在蟻群算法中的應用

隨著ACO 算法研究的不斷深入，蟻群算法與其他智能方法一樣，易陷入局部最優的缺陷逐漸顯露，人們開始不斷改進蟻群算法提高其算法效率，其中運用自適應策略改進蟻群算法是一個重要的思路.通過自適應改變算法信息素揮發度參數，可以極大保證收斂速度的同時提高全局收斂的能力,當問題規模比較大時，由于信息素揮發度系數的存在，使那些從未被搜索到的候選解的信息量會減少至接近于零，降低了算法的全局搜索能力.另外，當揮發系數較小，較優解留存的信息量比較大，以前搜索過的解被重新選擇的可能性過大，也會影響算法的全局搜索能力，通過增大揮發系數，減少信息量的留存可以提高算法的全局搜索能力，但會使算法的收斂速度降低[13].因此在算法陷入局部極值而停滯時，可以自適應增大信息素揮發系數，降低當前局部最優解的信息素濃度，大大降低當前局部最優解被重新搜索到的可能性，使得算法能重新自動搜索其他候選可行解區域，提高算法的全局收斂能力.有助于算法跳出局部極值的束縛，又可以兼顧算法的全局搜索能力和收斂速度.揮發系數的自適應調整方式如下：

(9)

其中，Rou()表示信息素的揮發系數；α為自適應調整系數，在此取值為1.15.每次循環后信息素更新規則可表述如下：

Tau(i)=(1-Rou(t))*Tau(i)+F(i),

(10)

其中，Tau(i)表示蟻群第i螞蟻找到的解的原有信息素含量；F(i)表示第i只螞蟻找到該解時對應的適應度值，如果該解質量較優，則值較大，表示解的信息量得到較大的增強.

帶精英策略的蟻群算法之所以用精英這個稱謂，是因為遺傳算法中所使用的精英策略.在遺傳算法中，將當前一代中的最適應個體的基因進行突變和重組產生下一代的個體，以此將當前最優個體的優良基因最大限度遺傳到下一代中.類似地，精英螞蟻算法為了使到目前為止所找到的最優解在下一代循環中對螞蟻個體更具有吸引力，在每次循環后給予最優解以額外的信息素增量，以此來突出該解的優良性，從而擴大精英解和普通解的差異性，使得精英解對螞蟻個體的引導性增強.精英策略的運用將螞蟻的搜索行為集中到最優解附近，可以提高解的質量和收斂速度，從而改進算法的性能.按照此策略找到優質解的螞蟻稱為精英螞蟻.精英螞蟻算法中信息素的更新規則如下：

如果第i只螞蟻為精英螞蟻，找到的解為群體當前最優解，解的信息素按如下方式更新.

(10)

Tau(i)=(1-Rou(t))*Tau(i)+F(X(i,1),X(i,2))，

(11)

從上述解的信息素更新的兩種情況來看，精英螞蟻找到解的信息素含量除按正常方式更新外，還按照解的質量給予其信息素含量一個額外的增強，提高了該解對螞蟻個體的吸引力.這樣使得最優解和普通解的信息素量差異進一步增大，引導螞蟻的搜索行動向最優解的領域靠近.增強了對蟻群搜索行為的指導性.

2.3 基于GM(1,1)模型的蟻群算法適應度函數設計

蟻群中的每個螞蟻位置對應優化問題的潛在可行解，根據適應度值進化迭代找到最優螞蟻則找到了對應問題的最優解.在蟻群算法中用適應度值來評價螞蟻尋找到的解的優劣，并作為往后螞蟻個體狀態轉移和信息素更新的依據，使得隨機初始解逐步向最優解進化.由此可見，適應度函數設計是蟻群算法進化尋優的關鍵.

(12)

其中，a,b是待求的GM模型參數，他們是適應度函數的兩個自變量.

自變量的取值范圍(即蟻群的搜索范圍)根據具體問題進行適當設定.范圍設置過大，算法把搜索范圍遍歷一次，會降低算法的執行效率；范圍設置過小，沒有把具體問題的最優解包含在內，會造成算法不成熟收斂或者不收斂，得到的是問題的局部最優解或無解.本文在GM模型參數的求解問題上，在參考傳統GM模型近似解的基礎上來設置算法的搜索范圍.

程序代碼部分刪除.

3 改進的蟻群算法與GM(1,1)融合預測模型的實證分析

當GM(1，1)模型數據序列變化平緩時，低增長情況下,傳統GM(1,1)模型和殘差修正模型有較高的精度，模型偏差較小，擬合和預測非常理想，運用蟻群算法優化參數建立的GM(1，1)模型與它們在精度上相差不大，提高效果不顯著.當數據序列為高增長序列如指數級增長(發展系數|-a|比較大)，尤其是|-a|>0.5時，GM模型精度很差，對使用傳統模型以及殘差修正模型作短期預測都應該慎重，因此該情況下運用仿生智能算法求解模型參數，提升模型精度十分有必要.下面以指數級高增長數據序列的擬合和預測為例，運用提出的自適應精英蟻群算法改進的GM模型來進行數據的擬合和預測，在精度和誤差上與傳統模型和殘差修正模型進行對比，來驗證基GM模型改進的有效性和合理性.

例：某地傳染病暴發，在某周感染人數的日報數據如下，x°=[3,11,28,85,251,736,2 199],從數據的變化趨勢呈現近似指數級增長.傳統GM模型和殘差修正GM模型預測結果和誤差數據如表1所示，可以看出采用傳統GM(1,1)模型和殘差修正模型預測誤差都比較大,預測效果不理想.仍采用此數據序列的擬合、預測探討運用智能方法求解模型參數的有效性和優越性.

下面采用基于自適應精英蟻群算法的GM(1,1)模型來對該指數級增長數據序列進行預測，在參考傳統GM模型求得參數值的基礎上將第1個參數范圍(算法搜索范圍)設置為[-1.5,-0.6]，第2個參數范圍(算法搜索范圍)設置為[0,2.0]，螞蟻個體數目設為100，迭代次數T設為300，在matlab運行自適應精英蟻群算法程序，得到適應度進化曲線如圖1所示，算法收斂相當快.matlab程序求得的GM模型參數分別為：a=-1.090 81，b=1.919 02.得到優化后的GM模型的預測值時間響應式為：

迭代次數

(13)

表1是運用自適應精英蟻群算法與GM融合預測模型對數據序列的擬合預測值、誤差值與傳統GM模型、殘差修正模型的對比.

表1 數據序列預測值及誤差

從改進預測模型的擬合值、殘差、相對誤差和數據變化趨勢來看，自適應精英蟻群算法與GM融合模型預測結果非常理想，在原始數據的擬合上誤差小，而且在后續時間預測數據的變化趨勢與原始數據序列的變化趨勢也非常吻合.傳統GM模型在指數級高增長數據序列的數據擬合上，誤差大，數據變化明顯滯后于實際數據的變化，后續時間預測上，預測數據的變化也明顯不符合指數級高增長的特征.在數據序列高增長、非平穩變化時，殘差修正的應用反而增大GM模型擬合數據的誤差，在后續時間的預測數據變化趨勢明顯大大超前原始數據的增長特征.由此可見傳統GM模型、殘差修正模型非常不適合指數級增長非平穩數據序列的預測和擬合.

為了驗證自適應精英策略用于改進蟻群算法的優越性，在此用該方法求解的GM模型參數與普通粒子群算法、普通蟻群算法求解的GM模型參數在收斂速度、算法運行時間、最終誤差等諸方面進行比較，3種算法性能參數如表2所示.

表2 求解GM(1,1)模型的3種算法性能參數

用普通粒子群算法、普通蟻群算法求解的GM模型參數如圖2所示.用普通粒子群算法求解模型參數歷時最短，但誤差最大；普通蟻群算法求解時間稍長，模型誤差有所減少，但并非最小，還有改進降低的空間；而自適應精英蟻群算法雖然歷時比前兩者都長，但求解的結果是最好的，模型總的誤差平方和是最低的.由此可見，運用不經改進的智能方法求解模型參數，系統總的誤差平方和也明顯高于改進后的方法.從一個側面也反映了運用自適應精英策略改進蟻群算法是成功的，用于優化問題求解具有優越性.

迭代次數

應用結果表明,基于自適應精英蟻群算法的灰色GM模型,對于非平穩高增長的序列,具有較高的擬合與預測精度.對于指數級增長的非平穩序列預測精度提升效果尤為明顯.改進后的模型在適用性上較傳統模型和殘差修正模型具有優越性.同時，與普通的人工智能方法相對比，自適應精英蟻群算法在解決優化問題上，處理能力是較為優秀的.

4 結 論

針對傳統求解GM(1，1)模型的參數的局限性，提出了自適應精英蟻群算法求解模型參數的方法.通過應用結果證明文章提出的方法有較理想的預測效果，尤其數據序列變化非平穩時，傳統GM模型擬合及預測精度較差的情況，改進的融合模型預測效果非常理想.也同時證明了自適應精英策略改進蟻群算法是合理可行的，比普通智能算法具有較強的優化問題解決能力.自適應精英蟻群算法還可以應用于其他領域的優化問題，具有較廣闊的應用前景.