基于非均勻變異算子的狀態空間進化算法

凌 哲，李茂軍

(長沙理工大學 電氣與信息工程學院，湖南 長沙 410114)

0 引 言

傳統遺傳算法是模擬自然界中生物進化，通過自然選擇機制求解最適度值問題的一類自組織、自適應、自識別的人工智能技術，是人工智能和仿生計算技術相結合的產物，包括模擬了自然界中生物的進化過程的進化算法，模擬自然狀態下某些生物群體群居行為的群體智能算法，為解決復雜程度高的多目標問題開辟了新的道路。但是傳統遺傳算法在實際應用中容易陷入一種早熟收斂的現象，算法控制參數比如迭代次數選擇主要依靠經驗。上述缺點很大程度上限制了遺傳算法的實際應用，如何增加算法的收斂精度以及如何提升算法的收斂速度，是國內外學者積極探討的問題。例如，文獻[1]提出了不同于已有遺傳算法的交叉和變異策略,即通過利用誘導和隨機相結合的交叉和變異算子進行局部微調，使得種群的一部分個體采用誘導變異,其余個體采用隨機變異;對搜索的初始時段采用隨機線性組合交叉,結束時段采用部分確定性誘導交叉。文獻[2]著重從交叉和變異算子的變換出發，通過增加種群的多樣性和選擇性，并且以提高算法全局與局部搜索能力加快收斂速度為目的，設計出了一種新的算法。文獻[3]提出一種采用實數編碼的基于狀態空間模型的進化算法。狀態空間模型的構建不僅能把種群信息以較少的信息量表述出來，而且能夠清楚地表現出在迭代過程中個體的狀態變化。文中算法通過構造一個狀態進化轉移矩陣來替代遺傳算法中的交叉與變異算子功能進而產生一組新的群體，通過選種池的選擇方式產生較優的群體。相較于遺傳算法計算量大、易陷入早熟收斂、全局搜索能力差等缺點[4]，該算法有著計算量小、計算精確度高等優點。并可通過評估轉移矩陣的范數來考察算法的全局收斂性和收斂速度[5-8]，突破了傳統遺傳算法的固有模式。

1 狀態空間模型進化算法

1.1 算法概述

遺傳算法逐漸成為尋找優化方式的路徑，通過交叉、選擇、變異三個算子來篩選出最優值。文中基于離散系統的狀態空間模型，引入遺傳算法的理念，構建基于狀態空間模型的方程[9-11]，即

X'(k+1)=GX(k)

(1)

在該算法中，X(k)表示進化算法中的群體，X(k)為第k代群體，含有N個分量，每個分量均代表了1個個體，每個個體中包括了M個變量(個體是通過實數編碼的方式產生的)。實際上，狀態向量X(k)表示為一個N×M矩陣，矩陣的每一行可視為一個個體，每一個元素表示為變量的實數值。通過基于進化算法中的進化方式來構建狀態轉移矩陣，在此是通過運用遺傳算法中的算子來構建狀態轉移矩陣G。先是通過隨機產生的方式得到初始群體X(0)，在左乘矩陣G得到群體X'(1)，以此類推可到一系列的X'(1)，X'(2)，…。再讓群體X'(k+1)和X(k)同時進入選種池內，選種池是按照物競天擇、適者生存的思想構建的，通過計算兩個群體中2N個個體的適應度函數值，并選擇其中較大的N個個體組成新的X(k+1)群體，然后置為式1中的X(k)，如此循環，直到滿足最后的終止條件。通常建立為如圖1所示的有選擇性的閉環模式。

圖1 基于狀態空間進化算法的有選擇閉環模型

1.2 狀態轉移矩陣的構造

狀態方程G的構造是影響狀態空間算法收斂速度和收斂性的決定因素，也是評價算法好壞的標準。狀態轉移矩陣G的構造可以擬用仿生算法中群體進化的基本方法進行，例如可以模仿遺傳算法的遺傳算子來構造狀態轉移矩陣，也可以采用其他算法或者數學方法[12-14]。對基于傳統的遺傳算法中的遺傳算子構建狀態轉移矩陣做詳細闡述。選擇、變異、交叉是遺傳算法中的基本操作，由于已經有了適應度評判函數，所以只需要在狀態空間轉移方程下體現交叉和變異的特點。對于實數編碼下的情況，交叉操作一般選取個體間的算術均勻交叉方式，其狀態空間轉移矩陣方程為：

(2)

其中，0

父代種群經過左乘形如G1的狀態轉移矩陣后，便實現了遺傳算法中個體的交叉操作。從中可得子代群體的1號個體是由父代群體中的1號個體和n號個體交叉產生，由此可推斷出只要交叉參數不同，其產生的子代也將有所不同[15-17]。但是這里完全沒有實現遺傳算法中變異算子的功能，種群的多樣性得不到較好的維持，算法容易出現早期收斂的現象。

為了實現種群的多樣性，引入變異操作，將上述矩陣進行變換，如下所示：

(3)

其中，β=0.028+0.01rand()(經由實驗確認)，rand()為在[0,1]符合均勻分布的隨機數，父代群體左乘以形如G2的狀態轉移矩陣后，交叉和變異的遺傳算子得以實現[18-19]。

2 基于改進的非均勻變異的狀態轉移矩陣

2.1 矩陣的設計

上述的狀態空間轉移矩陣的構造僅僅是基于兩個個體間的交叉和單個個體多點變異的狀態轉移矩陣，并且種群的一號個體不能經過交叉產生，不能體現自然選擇的特點。

本文以2007-2016年滬深兩市全部A股上市公司為研究樣本。樣本公司的財務數據均來自CSMAR數據庫。

為此將進行如下改進。

(4)

文中在此基礎上改進之前的變異算子，使得種群盡可能地搜索到含有優良基因型的個體，同時為了避免陷入局部搜索的情況，由一個變異點變成三個點，最大程度上能夠達到全局最優解。由于在選種池的操作中，選取2N個體里適度值大的N個個體并按適度值從高到低排列組成新的X(k+1)種群，這樣下一代排列靠前的個體往往是最優個體。

(5)

其中，0

對照上述公式，εi的設置如下：

(6)

采用非均勻變異操作后，在原有最優個體附近區域進行微小搜索，能夠精準快速到達全局最優解，并根據優勝劣汰的自然選擇法則，以一定概率并入了算術交叉算子，使得適應度高的優秀個體能夠以較大概率參與到下一次的迭代過程中。這樣情況下的子代對父代的延伸程度越高，種群多樣性也越高。

2.2 約束處理

在算法的迭代過程中，隨著算法的搜索區域不斷增大，可能導致子代的個體元素不在可行域的范圍之內，故對其約束如下：

(7)

(8)

其中，[Umin,Umax]為變量的取值范圍；ξ表示尋值的精度限定；<>表示向下取整。

3 仿真實驗

實驗的仿真平臺為MATLAB 2013a。實驗使用了2個經典函數進行測試，如下所示：

(1)Camel函數。

(9)

(0.089 8,-0.712 6)為最小值點，最小值為-1.031 628。

(2)Rastrigrin函數。

(10)

有多個極小值點，但只有一個全局最小值0，在(0,0)處。

在本次測試中，設定算法參數中的種群規模大小100，迭代的次數為60，每個測試函數運行50次。為了對比結果，實驗采用兩種算法進行比較，分別為一般狀態轉移矩陣下的狀態空間進化算法(evolutionary algorithm based on state-space model，SEA)和基于改進的非均勻變異轉移矩陣的狀態空間進化算法(state-space evolutionary algorithm based on non-uniform mutation，NUMSEA)。對以上兩個測試函數分別從平均最優解、平均收斂代數、標準差(平均最優解與全局最優解之差)等方面進行比較。

結果如表1所示。

表1 測試結果

圖2和圖3分別顯示了運用文中算法(NUMSEA)對求解上述函數優化問題時所得的最優解對應的適應度函數值隨迭代次數變化的曲線。

圖2 求解f1優化問題時適應度函數值變化曲線

實驗結果表明，NUMSEA算法在2個函數的優化中明顯優于之前所述的SEA算法，算法的收斂速度相對較快，且最優值更為接近理論值，并且能在短時間內精確定位，充分體現了其高效性。通過50次的測試可以看出，在平穩性方面較之前的算法有較大的提升，計算量上有一定程度的縮減，如果能適當調整其控制參數，或將具有更好的全局搜索能力。

4 結束語

為了精準地從大數據環境下樣本化、隨機化的數據中提取有效信息，設計了一種具備伸縮性與并行處理功能的算法。針對一般轉移矩陣下狀態空間進化算法的不足，提出了一種基于非均勻變異的狀態空間進化算法。通過引入改進的非均勻變異算子實現種群多樣化，在一定程度上提高了算法的收斂速度與收斂精度。經過對2個多峰值的經典函數的優化實驗，證明了該算法的可行性與穩定性，表現出了比較突出的尋優性能，縮減了處理數據的時間。雖然仿真實驗結果令人滿意，但是仿真環境是設為一個理想的條件下，并且實驗的次數是有限的。因此，進一步構造更為良好的狀態轉移矩陣，以及驗證算法的全局收斂性和空間遍歷性，仍需要進行不斷研究。