凌 哲，李茂軍

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

0 引 言

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

1 狀態(tài)空間模型進(jìn)化算法

1.1 算法概述

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

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

(1)

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

圖1 基于狀態(tài)空間進(jìn)化算法的有選擇閉環(huán)模型

1.2 狀態(tài)轉(zhuǎn)移矩陣的構(gòu)造

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

(2)

其中，0

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

為了實(shí)現(xiàn)種群的多樣性，引入變異操作，將上述矩陣進(jìn)行變換，如下所示：

(3)

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

2 基于改進(jìn)的非均勻變異的狀態(tài)轉(zhuǎn)移矩陣

2.1 矩陣的設(shè)計(jì)

上述的狀態(tài)空間轉(zhuǎn)移矩陣的構(gòu)造僅僅是基于兩個個體間的交叉和單個個體多點(diǎn)變異的狀態(tài)轉(zhuǎn)移矩陣，并且種群的一號個體不能經(jīng)過交叉產(chǎn)生，不能體現(xiàn)自然選擇的特點(diǎn)。

本文以2007-2016年滬深兩市全部A股上市公司為研究樣本。樣本公司的財(cái)務(wù)數(shù)據(jù)均來自CSMAR數(shù)據(jù)庫。

為此將進(jìn)行如下改進(jìn)。

(4)

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

(5)

其中，0

對照上述公式，εi的設(shè)置如下：

(6)

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

2.2 約束處理

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

(7)

(8)

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

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

實(shí)驗(yàn)的仿真平臺為MATLAB 2013a。實(shí)驗(yàn)使用了2個經(jīng)典函數(shù)進(jìn)行測試，如下所示：

(1)Camel函數(shù)。

(9)

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

(2)Rastrigrin函數(shù)。

(10)

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

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

結(jié)果如表1所示。

表1 測試結(jié)果

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

圖2 求解f1優(yōu)化問題時適應(yīng)度函數(shù)值變化曲線

實(shí)驗(yàn)結(jié)果表明，NUMSEA算法在2個函數(shù)的優(yōu)化中明顯優(yōu)于之前所述的SEA算法，算法的收斂速度相對較快，且最優(yōu)值更為接近理論值，并且能在短時間內(nèi)精確定位，充分體現(xiàn)了其高效性。通過50次的測試可以看出，在平穩(wěn)性方面較之前的算法有較大的提升，計(jì)算量上有一定程度的縮減，如果能適當(dāng)調(diào)整其控制參數(shù)，或?qū)⒕哂懈玫娜炙阉髂芰Α?/p>

4 結(jié)束語

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