改進的狀態(tài)空間模型遺傳算法及其全局收斂性分析

齊 戰(zhàn),李茂軍,莫 紅,肖雨荷,劉 芾

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

1 引言

進化算法是受生物進化和遺傳過程啟發(fā)的一種自組織、自適應(yīng)的人工智能技術(shù),是解決工程技術(shù)中組合優(yōu)化問題的一種智能算法,在線性、二次、強凸、單峰或其他特定領(lǐng)域中求取給定問題的最優(yōu)解[1].遺傳算法(genetic algorithm,GA)、粒子群優(yōu)化算法(particle swarm optimizer,PSO)、差分進化(differential evolution,DE)、遺傳編程、社會學(xué)習(xí)算法和化學(xué)反應(yīng)算法等都是常見的進化算法,然而進化算法存在早熟收斂等問題,在許多優(yōu)化問題中表現(xiàn)不佳[2],因此許多學(xué)者通過定義并行計算模型[3]、混合算法[4]等來設(shè)計更有效的進化算法.

基于狀態(tài)空間模型遺傳算法(genetic algorithm based on state-space model,GABS)是李茂軍教授在文獻[3]中正式提出的一種新型進化算法,具有參數(shù)設(shè)置少、操作簡單、搜索能力強、計算精度高和收斂速度快等特點.符宏艷等[5]利用GABS有效地解決了電力市場競價問題,跟GA相比能更快的搜索到最優(yōu)解.李雪等[6]將GABS應(yīng)用于公交調(diào)度問題,仿真結(jié)果表明GABS優(yōu)化效果比GA更好.雖然該算法應(yīng)用效果較好,但是該算法的全局收斂性未得到嚴密的數(shù)學(xué)分析.王鼎湘等[7]利用齊次有限馬爾可夫鏈對GABS進行分析,得到了GABS不具有全局收斂性的結(jié)論,并提出一種通過改進GABS的狀態(tài)進化矩陣來確保算法具有全局收斂的方法,但這種改進方法在每一次迭代時都需要更新狀態(tài)進化矩陣,而文獻[5]和文獻[8]仿真結(jié)果表明,在狀態(tài)進化矩陣不變的情況下算法也有很好的尋優(yōu)效果.

狀態(tài)進化矩陣是種群進化的關(guān)鍵操作算子,相比于狀態(tài)進化矩陣每一次迭代都需要更新的情況,狀態(tài)進化矩陣固定不變顯然減少了算法搜索的計算量.本文通過分析GABS在狀態(tài)進化矩陣固定不變情況下的尋優(yōu)過程,為算法建立吸收態(tài)馬爾可夫過程模型,從可達狀態(tài)集的角度證明了GABS不具有全局收斂性.基于此提出了一種改進的狀態(tài)空間模型遺傳算法(modified GABS,MGABS),最后證明并驗證了MGA BS具有全局收斂性.

2 問題描述及GABS

可以將連續(xù)域內(nèi)的一個實數(shù)優(yōu)化問題描述為

GABS是一種基于狀態(tài)空間模型的實數(shù)編碼進化算法,引入進化算法的基本思想[3]:上一代種群通過狀態(tài)進化矩陣的作用產(chǎn)生新的種群,新種群和上一代種群再通過優(yōu)勝劣汰的選擇操作生成下一代種群,整體上使下一代種群更接近問題的最優(yōu)解.算法通過不斷迭代,使種群中的個體不斷朝最優(yōu)解方向進化,最終得到問題的最優(yōu)解或次優(yōu)解.新種群的構(gòu)造算法表達式如下:

式中:X(k)表示第k代種群,它是一個N ×L的矩陣,該矩陣的每一行表示一個個體,每個個體包含L個決策變量,即種群規(guī)模為N,實數(shù)編碼長度為L,將初始種群記為X(0);G是狀態(tài)進化矩陣,其構(gòu)造方式如下:

利用GABS求解式(1)所描述問題的步驟如下:

步驟1在可行域內(nèi)隨機生成種群規(guī)模為N的初始種群X(0);

步驟2依據(jù)式(3)生成狀態(tài)進化矩陣G;

步驟3依據(jù)式(2)來產(chǎn)生新的種群X(k+1),將X(k+1)與X(k)結(jié)合形成選種池;

步驟4計算選種池內(nèi)所有個體的適應(yīng)度;

步驟5在選種池內(nèi)選取適應(yīng)度最高的N個個體組成下一代群體X′(k+1),置X′(k+1)為X(k);

步驟6滿足終止條件,轉(zhuǎn)步驟7,否則轉(zhuǎn)步驟3;

步驟7算法終止.

3 GABS隨機過程及模型

GABS進化搜索與選擇操作的求解過程,從本質(zhì)上可以視為X(k)的狀態(tài)隨機變化過程.GABS屬于連續(xù)優(yōu)化算法,因此,為GABS建立狀態(tài)連續(xù)變化的隨機過程模型,下面給出定義[9].

定義1GABS在第k次迭代的種群記為X(k),稱為GABS對應(yīng)的隨機過程.狀態(tài)空間Y滿足?X(k)∈Y.

定理1GABS所對應(yīng)的隨機過程(?X(k)∈Y)具有馬爾可夫性.

證GABS的狀態(tài)進化矩陣G固定不變,由第k代種群X(k)與G相乘產(chǎn)生新種群X(k+1),從X(k)與X(k+1)形成的選種池中篩選出適應(yīng)度高的個體組成下一代種群X′(k+1).故滿足?Y1?Y和k=0,1,2···,有P{X′(k+1)∈Y1|X(0),···,X(k)}=P{X′(k+1)∈Y1|X(k)}.因此,在第(k+1)代的狀態(tài)X′(k+1)僅由第k代的狀態(tài)X(k)所決定,即具有馬爾可夫性. 證畢.

定義2給定來自狀態(tài)空間Y的隨機過程,Y ?稱為最優(yōu)狀態(tài)空間,滿足Y ??Y,而且對于?X?(k)∈Y ?至少有一個解x?∈X?(k)是優(yōu)化問題的最優(yōu)解.

為了解決GABS 是否具有全局收斂性的問題,引入吸收態(tài)馬爾可夫過程的定義[10-11].

定義3給定一個馬爾可夫過程(?X(k)∈Y),Y ??Y為最優(yōu)狀態(tài)空間,若P{X′(k+1)/∈Y ?|X(k)∈Y ?}=0 (k=0,1,2,···),則稱為吸收態(tài)馬爾可夫過程.定義3說明吸收態(tài)馬爾可夫過程一旦達到了最優(yōu)狀態(tài)空間,即X(k)∈Y ?,那么便一直停留于最優(yōu)狀態(tài)空間.精英保留策略對改進進化算法的全局收斂能力具有重大作用,許多具有精英保留的進化算法是全局收斂的[12-13],這些算法都可以建模為吸收態(tài)馬爾可夫過程.GABS選種池的選擇操作是將上一代種群和新種群中的最優(yōu)個體選擇出來作為下一代種群,自然在每次迭代中保留了當前最優(yōu)解,因此定義3的模型同樣適用于GABS.

定理2GABS對應(yīng)的隨機過程為吸收態(tài)馬爾可夫過程.

證GABS選種池內(nèi)的選擇操作將上一代種群和新種群中的優(yōu)秀個體選擇出來作為下一代種群,因此每一次迭代的最優(yōu)個體都會被選擇并復(fù)制到下一代.所以,GABS一旦在第k次迭代后搜索到最優(yōu)解x?∈X(k),那么第(k+1)次迭代的種群X′(k+1)中也包含最優(yōu)解x?,即x?∈X′(k+1).由定義2 可知X(k)∈Y ?,X′(k+1)∈Y ?,那么可得P{X′(k+1)/∈Y ?|X(k)∈Y ?}=0.由定義3知滿足吸收態(tài)馬爾可夫過程性質(zhì). 證畢.

若GABS在第k次迭代達到最優(yōu)狀態(tài)空間,表示算法搜索到了問題的最優(yōu)解,若=1,表示算法可以迭代無窮多次后收斂于最優(yōu)狀態(tài)空間Y ?,引入GABS全局收斂的定義[11].

GABS突破傳統(tǒng)進化算法的計算模式,通過狀態(tài)進化矩陣的作用產(chǎn)生新種群,搜索新的區(qū)域,再通過選擇操作使得算法朝最優(yōu)解方向搜索,最終搜索得到最優(yōu)解或次優(yōu)解.由于算法搜索方向的單一性和優(yōu)勝略汰的選擇操作使得算法收斂速度非?？?但同時也會存在缺陷,即種群中所有個體往最優(yōu)解方向進化時,便缺少了個體間差異性,易陷入局部最優(yōu).

另外,由引理1知初始種群的上下界限制了后代種群的可達狀態(tài),使得后代種群可達狀態(tài)在初始種群決定的某一確定的區(qū)間內(nèi),但此區(qū)間為可行域的子集,若全局最優(yōu)解不在此區(qū)間內(nèi),那么種群中的個體永遠不可能達到最優(yōu)解的狀態(tài),由定理3知GABS不可能收斂到全局最優(yōu)解.特別的,當全局最優(yōu)點位于可行域的邊界及其附近時,由于隨機生成的初始種群的上下界區(qū)間為[αl,βl]可能是可行域[al,bl]的真子集,那么算法就不可能搜索到位于可行域邊界的全局最優(yōu)解,所以GABS 不具有全局收斂性,導(dǎo)致了GABS 的尋優(yōu)結(jié)果不穩(wěn)定,這是算法的另一個弊端.

綜上,算法是否能搜索到理論最優(yōu)完全取決于迭代時的全局最優(yōu)位置及初始種群的狀態(tài)分布,而且算法易陷入局部最優(yōu).

4 MGABS及其全局收斂性

從可達狀態(tài)集角度得到GSBS不具有全局收斂性,因此針對此算法提出一種特殊變異機制,改進思想是:使得算法在迭代前期擴張GABS的可達狀態(tài)集,無論全局最優(yōu)解在可行域任何位置,算法能夠達到最優(yōu)狀態(tài),且在迭代后期提高算法的收斂精度.提出兩種變異策略:

1) 隨機選出P個適應(yīng)度差的個體并平均分成兩組(若不能均分可將多余個體分到第2組),再將這兩組個體的每一位決策變量分別轉(zhuǎn)移至式(4)指定區(qū)間的隨機位置.具體操作如下:的隨機數(shù),m=1,2,···,P,l=1,2,···,L.

設(shè)總迭代次數(shù)為K,當k≤時,采用策略1),否則采用策略2).在算法迭代前期適用式(4),即在區(qū)間內(nèi)隨機生成的兩組個體分別代替適應(yīng)度差的兩組個體,擴張了算法的可達狀態(tài)集,同時提高了搜索范圍和種群多樣性,避免算法陷入局部最優(yōu).在算法迭代后期適用式(5),提高了種群朝最優(yōu)解搜索的速度,因此提高了算法的收斂精度.

改進GABS的算法步驟如下:

步驟1在可行域內(nèi)隨機生成種群規(guī)模為N的初始種群X(0);

步驟2依據(jù)式(3)生成狀態(tài)進化矩陣G;

步驟3依 據(jù) 式(2)產(chǎn) 生新的 種群X(k+1),將X(k+1)與X(k)結(jié)合形成選種池;

步驟4計算選種池內(nèi)所有個體的適應(yīng)度;

步驟5在選種池內(nèi)選取適應(yīng)度最高的N個個體組成下一代群體X′(k+1),置X′(k+1)為X(k);

步驟6從X(k)中選出適應(yīng)度較差的P個個體,若k≤,采用變異策略1),否則采用變異策略2);

步驟7滿足終止條件,轉(zhuǎn)步驟8,否則轉(zhuǎn)步驟3;

步驟8算法終止.

定義6通過以上步驟改進的GABS稱為改進的狀態(tài)空間模型遺傳算法,簡稱為MGABS.

容易知道定義1-5 對于MGABS 都是適合的,定理1-2 對于MGABS 仍然成立.為了便于描述,稱為MGABS對應(yīng)的隨機過程,稱為MGABS在第k次迭代的可達狀態(tài)集.

引理2MGABS對應(yīng)的隨機過程Y ?為最優(yōu)狀態(tài)空間,則MGABS滿足?k′≥0,當k >k′時,∩Y ?=?.

引理3源于文獻[14-15]研究進化算法時的類似結(jié)論,這里再次證明是為了給出算法全局收斂的一個判斷準則.

定理4MGABS具有全局收斂性.

5 MGABS有效性驗證

5.1 測試函數(shù)

為了更全面了解MGABS在解決各式各樣問題上的性能,本文在不同的測試函數(shù)上測試MGABS,引入16個經(jīng)典測試函數(shù)[16-17]進行測試與分析.這16個測試函數(shù)可分成3組,每組函數(shù)具有不同的特性,以充分測試改進算法的優(yōu)化搜索性能.具體函數(shù)如表1所示,其中:x?是全局最優(yōu)點,f(x?)是全局最小值.函數(shù)f1～f5設(shè)為第1組,函數(shù)f6～f10設(shè)為第2組,函數(shù)f11～f16設(shè)為第3組.

表1 16個測試函數(shù)Table 1 16 benchmark functions

第1組測試函數(shù)是De Jong研究函數(shù)優(yōu)化問題時精選出來的5個測試函數(shù),可全面檢驗改進算法的性能.第2組測試函數(shù)選取5個20維函數(shù),其中函數(shù)f6,f7和f9是非線性多峰函數(shù),具有許多個極小值點;函數(shù)f8,f10則是單峰函數(shù).第3組測試函數(shù)是全局最優(yōu)點位于可行域邊界或邊界附近的一組函數(shù),其中函數(shù)f14,f15和f16的全局最優(yōu)解位于可行域的邊界上,通過第2節(jié)分析可知GABS不具備全局收斂性,是因為它難以搜索到全局最優(yōu)點位于邊界或者邊界附近的函數(shù)的全局最優(yōu)值,所以選取了6個此類函數(shù)來驗證改進算法MGABS的全局搜索能力.

5.2 參數(shù)設(shè)置

為了充分驗證MGABS的有效性和先進性,本文引入其他兩個熱門的全局優(yōu)化進化算法:異構(gòu)綜合學(xué)習(xí)粒子群優(yōu)化算法[18](heterogeneous comprehensive learning particle swarm optimizer,HCLPSO)和改進基于適應(yīng)度的自適應(yīng)差分進化算法[19](enhanced fitness-adaptive differential evolution algorithm,EFADE),兩個算法的代碼均在Suganthan教授的主頁下載.本文所有算法均在MATLAB R2014a環(huán)境下進行測試.

GABS只有種群規(guī)模和進化代數(shù)(總迭代次數(shù))兩個參數(shù),只需設(shè)置好這兩個參數(shù)即可,因此將GABS和MGABS種群規(guī)模均設(shè)為50,進化代數(shù)均設(shè)為200.不管問題的復(fù)雜度和維度如何變化,種群規(guī)模和進化代數(shù)均不變化,以此來增加算法搜索難度.MGABS需要隨機選擇P個適應(yīng)度差的個體并變異,P值將在下一節(jié)討論.為了減少算法的運算時間,開始測試前依式(3)構(gòu)造并生成狀態(tài)進化矩陣再將之存儲于內(nèi)存,測試實驗開始時從內(nèi)存里調(diào)出即可.為了公平地比較4個算法的性能,將HCLPSO的粒子數(shù)設(shè)為50,進化代數(shù)設(shè)為200,最大適應(yīng)度評價次數(shù)(the maximum number of function evaluations,FEs)設(shè)為10000.同將EFADE種群規(guī)模和進化代數(shù)也分別設(shè)為50和200,其他參數(shù)則默認.

5.3 變異個體數(shù)討論

為了更好地平衡算法的搜索能力,變異個體數(shù)P為MGABS重要參數(shù).MGABS種群規(guī)模為50,于是將P值設(shè)置為2,5,10,15,20,25,30,35和40.獨立搜索16個函數(shù)中最具代表性的6個函數(shù)f1,f5,f9,f10,f11,f14各50次,比較平均值和方差,結(jié)果如表2所示.

表2 不同P值討論Table 2 Discussion of differentP values

表2中可以看出,當P值較小時結(jié)果不理想,是由于算法陷入了局部最優(yōu);當P值太大時亦不理想,是變異個體太多影響了收斂的速度和精度.因此對所有函數(shù)而言,P值設(shè)為15～35時具有良好的計算結(jié)果.特別的,當P值設(shè)為20～30時,函數(shù)f1,f5,f9,f10的平均值和方差均優(yōu)于其他的情況.當P值為15時函數(shù)f11的結(jié)果是最好的,而對于函數(shù)f14,P值為35時有較好的優(yōu)化效果.綜上,本文將P值設(shè)為25.

5.4 對比實驗

為了減少算法搜索結(jié)果的隨機性,對于每個測試函數(shù),4種算法均要優(yōu)化搜索50次,使用50次搜索的平均尋優(yōu)值,4種算法尋優(yōu)結(jié)果見表3.其中平均值表示50次搜索結(jié)果的平均尋優(yōu)值,最小值則表示最小尋優(yōu)值,方差表示50 次尋優(yōu)值的方差,時間表示平均運算時間,單位為秒,準確率為50次搜索中找到最優(yōu)解次數(shù)的比例(求解精度設(shè)為10-5).

表3 4種算法搜索函數(shù)的結(jié)果比較Table 3 Comparison of four algorithm search results

從表3可以看出,GABS與MGABS的平均運算時間遠少于其他2個算法.這因為GABS與MGABS兩個算法均利用式(2)進行種群的更新,也即利用矩陣乘法進行并行計算,由于MATLAB的矩陣運算是公認的非常準確、非常迅速,因此算法每一次迭代的運算時間非?？?而其他兩種算法則需要在每一次迭代過程中依據(jù)其各自的更新策略對每個個體進行更新與選擇,因此種群規(guī)模越大,其運算速度越慢,導(dǎo)致運算速度遠不及GABS與MGABS.

第1組測試函數(shù):從表3準確率可以看出,在求解精度為10-5的情況下,除了第4 個存在噪聲的函數(shù)以外,MGABS,HCLPSO和EFADE均能搜索得到第1組函數(shù)的最優(yōu)解,而GABS則表現(xiàn)較差.從平均值和方差的角度來看,EFADE結(jié)果比其他算法更優(yōu),說明其收斂精度是最好的,MGABS的表現(xiàn)比之稍稍遜色.在最小值比較中,MGABS和EFADE獲得3次最好,GABS和HCLPSO獲得2次最好,但GABS其他指標均較差,說明GABS搜索結(jié)果不穩(wěn)定.比較4種算法的結(jié)果表明,EFADE對于第2個函數(shù)優(yōu)化效果是最好的,但其運算時間也是最久的,MGABS則次之,但運算速度非?？?總之,MGABS在非?？斓倪\算速度之下,仍具有較好的運算精度和準確率,HCLPSO與EFADE的運算時間比之多出一個數(shù)量級,因此其綜合性能最優(yōu),但和其他3個算法一樣,對函數(shù)f4的搜索結(jié)果較差,說明4種算法均不具備抗干擾能力.

第2組測試函數(shù):對于所有函數(shù)而言,MGABS優(yōu)化效果是最出色的,這歸功于MGABS的變異策略2,盡管種群規(guī)模和進化代數(shù)較小,算法仍具有非?？斓氖諗克俣群褪諗烤?其他3種算法則陷入局部最優(yōu),搜索函數(shù)的結(jié)果不理想.因此,MGABS對此類復(fù)雜的高維非線性函數(shù)優(yōu)化效果最明顯.

第3組測試函數(shù):從表3數(shù)據(jù)可以看出,MGABS對函數(shù)f12,f14,f15的優(yōu)化效果較好,但由于原算法的限制(不具備全局收斂性),MGABS對其他3個函數(shù)的優(yōu)化結(jié)果則略遜于EFADE,但相比于原算法GABS,其優(yōu)化結(jié)果有了很大的改善,并且其運算時間遠少于EFADE.可以通過增加種群規(guī)模進一步提高MGABS的性能,且運算時間不會有較大的提升.

6 結(jié)論

本文建立了基于狀態(tài)空間模型遺傳算法的數(shù)學(xué)模型,并從理論上分析了它的局限性,從而提出一種改進的狀態(tài)空間遺傳算法,并證明了其具備全局收斂性,測試結(jié)果同時也說明了改進算法的理論是正確有效的,改進的基于狀態(tài)空間模型遺傳算法表現(xiàn)出了運算速度快、收斂速度快、全局搜索能力強、計算精度較高、穩(wěn)定性較好等特點,提高了算法的適應(yīng)性,總體表現(xiàn)優(yōu)于其他算法.本文算法最大的特性是運算時間短,具有較好的應(yīng)用前景,下一步將研究此算法在實時系統(tǒng)中的應(yīng)用.