劉振軍

(唐山學(xué)院 基礎(chǔ)教學(xué)部，河北 唐山 063000)

0 引言

在科學(xué)和工程的眾多領(lǐng)域，優(yōu)化方法得到了廣泛應(yīng)用。然而，對于全局優(yōu)化問題，研究者尚未找到一種高效通用并被普遍接受的算法。利用啟發(fā)式算法求解全局優(yōu)化問題，成為近年來理論研究和實際應(yīng)用的熱點與趨勢。遺傳算法(Genetic Algorithm，GA)[1]、粒子群算法(Particle Swarm Optimization，PSO)[2]屬于啟發(fā)式算法，具有并行性、廣泛的可適用性和較強的魯棒性，并且操作簡單，易于實現(xiàn)，然而二者存在一個共同的問題即全局優(yōu)化效率還有待提高。GA是通過模擬達爾文生物進化論中自然選擇和遺傳學(xué)機理的生物進化過程來搜索最優(yōu)解的一種計算模型，它通過染色體共享信息，獲得較好的全局搜索性能，但由于缺乏有效的局部搜索機制，導(dǎo)致其在接近最優(yōu)解時收斂緩慢，甚至?xí)霈F(xiàn)收斂停滯現(xiàn)象，從而陷入局部最優(yōu)解。PSO是基于群集智能理論的優(yōu)化算法，它通過種群中粒子間的合作與競爭行為優(yōu)化搜索，保留了基于種群的全局搜索策略，具有記憶性，而且收斂速度快。然而，PSO在搜索過程中也比較容易陷入局部最優(yōu)解，從而較難搜索到全局最優(yōu)解。而且，PSO與GA各自的改進算法[3-6]在計算效率與精度方面雖然都有不同程度的提高，但仍不能滿足實際應(yīng)用的需要。因此，很多學(xué)者針對PSO和GA兩種算法的特點，揚長避短，開展了將兩種算法結(jié)合起來形成混合算法的研究工作[7-11]。

混沌運動作為非線性動力學(xué)的一個本質(zhì)特征，具有遍歷性、偽隨機性等特點[12]，能在一定范圍內(nèi)按其自身的規(guī)律不重復(fù)地遍歷所有狀態(tài)。正是這些特性，使其在搜索過程中可以避免陷入局部最優(yōu)解。很多研究者已將混沌搜索成功地運用到智能優(yōu)化算法中[13-15]。通常的混沌優(yōu)化方法是采用一維混沌映射作為混沌序列發(fā)生器，然后將其產(chǎn)生的混沌序列映射到設(shè)計空間進行尋優(yōu)搜索。

實際上，已經(jīng)有研究者采用不同的策略將混沌序列運用到粒子群算法中。Xiang等[16]和Meng等[17]在PSO中分別使用了分段線性混沌映射和Logistic混沌映射產(chǎn)生的混沌序列進行了混沌搜索。Jiang等[18-19]運用混沌映射序列改進了PSO中的參數(shù)：以慣性權(quán)重w和粒子速度更新式中的隨機數(shù)r1與r2。為了加快算法的收斂速度，Liu等[20]在PSO中加入了局部混沌搜索與自適應(yīng)慣性權(quán)重。Gandomi等[21]運用混沌映射序列代替加速PSO算法(APSO)[22]中的主要參數(shù)，進一步提高了算法搜索到全局最優(yōu)解的能力。Renato等[23]在PSO搜索最優(yōu)解發(fā)生停滯時，引入混沌跳躍，使其能夠跳出局部極值點。

本文綜合GA和PSO的優(yōu)點以及混沌運動的特性，對GA與PSO的混合算法加以改進，提出了混沌粒子群遺傳算法(CPSO-GA)，以提高全局優(yōu)化效率。為了考察算法的計算性能及其搜索全局最優(yōu)解的精度，本文通過五個高維非線性基準函數(shù)對算法進行測試和分析。

1 混沌粒子群遺傳算法(CPSO-GA)

在混沌優(yōu)化算法中，普遍使用的一維混沌映射是Logistic映射。當μ=4時，Logistic映射處于混沌狀態(tài)，混沌序列服從兩端大、中間小的Chebyshev分布[24]，不能均勻地遍歷整個搜索空間，可能會導(dǎo)致算法的收斂速度較慢或陷入局部最優(yōu)解。

盡管Tent映射與Logistic映射具有拓撲共軛關(guān)系，但是它們的混沌序列的概率分布不同。Tent映射經(jīng)過Bernoulli位移轉(zhuǎn)換以后可表示為：

zn-1=g(zn)=(2zn)mod1。

(1)

Tent混沌序列服從均勻分布，全局優(yōu)化的尋優(yōu)效果比Logistic映射要好[24]。因此，本文選用Tent映射產(chǎn)生均勻分布的混沌序列，以備混沌粒子群遺傳算法之需。

對于無約束優(yōu)化問題，在混沌優(yōu)化中混沌變量z與設(shè)計變量Xc之間存在如下所示的映射關(guān)系：

Xcd=XLd+z(XUd-XLd)。

(2)

式中，Xcd是Xc的第d個分量；XU與XL是優(yōu)化設(shè)計變量的上界與下界，均是D維向量，d=1，2，…，D。

在Jia等[25]提出的算法中采用了混沌局部搜索，方程式為：

(3)

(4)

文獻[4]已給出定理——PSO進化過程與粒子的速度無關(guān)，并展示了詳細證明。本文采用文獻[4]中的粒子更新方法，將粒子的速度更新與粒子更新兩式合并成一個方程：

(5)

式中，i=1，2，…，n，n為種群個數(shù)；d=1，2，…，D；Pi表示種群中第i個粒子；Pg表示種群中最優(yōu)的粒子；c1與c2是加速常數(shù)；r1與r2是[0，1]區(qū)間中的隨機數(shù)。

為了改善粒子群遺傳算法的全局優(yōu)化性能，根據(jù)式(4)設(shè)計點的迭代形式，結(jié)合表達式(5)，本文采用下式來更新粒子：

(6)

在改進的粒子更新式(6)中，第一項表示過去對現(xiàn)在的影響，通過縮放因子a調(diào)節(jié)影響程度，a越大，其影響程度越大；第二項表示粒子對當前本身最優(yōu)位置的靠近，依賴程度取決于參數(shù)1-a和混沌變量z；第三項表示粒子對當前群體最優(yōu)位置的靠近，依賴程度也取決于1-a和z，通過它們實現(xiàn)粒子間的信息共享與合作。從a的表達式可以看出，隨著進化代數(shù)逐漸增加，a呈非線性下降趨勢，到進化后期對粒子本身的影響程度減小，而對個體極值與群體極值的影響程度逐漸增大，亦即在進化前期局部搜索能力較強，而進化后期全局搜索能力增強。在后兩項中，不同的混沌變量取值，可以增加粒子的多樣性，并使粒子從不同的方向靠近個體極值與群體極值，避免陷入局部極值點。從a的表達式還可以看出，m取值越大，收縮的速度越慢，因此m=6比較合適。

本文提出的混沌粒子群遺傳算法(CPSO-GA)的流程如圖1所示。該算法中粒子的初始化采用的是Tent混沌映射的點序列；交叉、變異、選擇的操作均采用實數(shù)編碼機制，其中為了增加粒子的多樣性，在交叉操作中將粒子分別與個體極值和群體極值交叉。

圖1 混沌粒子群遺傳算法流程圖

2 測試分析

為了測試CPSO-GA的性能，將其與GA，PSO，PSO-GA進行比較，選用五個高維非線性基準函數(shù)[23-24]進行計算分析，表達式如下：

Sphere函數(shù)：

(7)

Rosenbrock函數(shù)：

(8)

Ackley函數(shù)：

(9)

Griewank函數(shù)：

(10)

Rastrigrin函數(shù)：

(11)

Sphere函數(shù)和Rosenbrock函數(shù)是單峰函數(shù)。其中，Sphere函數(shù)的最優(yōu)點是x*=(0，0，…，0)，最優(yōu)值是f*=0；Rosenbrock函數(shù)的最優(yōu)點是x*=(1，1，…，1)，最優(yōu)值是f*=0。Ackley函數(shù)、Griewank函數(shù)和Rastrigrin函數(shù)均是多峰函數(shù)，有無窮多個局部極小點、一個全局極小點，且最優(yōu)點均是x*=(0，0，…，0)，最優(yōu)值均是f*=0。

當目標函數(shù)的維數(shù)越高、自變量范圍越大、目標精度越高時，其優(yōu)化難度就越大。本文對算法的性能評估采用如下方法：①固定進化代數(shù)，評估算法的收斂速度與收斂精度；②在目標函數(shù)調(diào)用次數(shù)相接近的情況下，將函數(shù)最優(yōu)值的均值和標準差與文獻中已有算法的結(jié)果進行比較；③固定收斂精度值，評估算法達到該精度時所需要調(diào)用目標函數(shù)的次數(shù)。

2.1 固定進化代數(shù)，評估算法的收斂速度與收斂精度

本次測試參數(shù)設(shè)置如下：種群規(guī)模為30；最大迭代代數(shù)為500；交叉概率pc=0.9；變異概率pm=0.1；加速常數(shù)c1=c2=2；慣性權(quán)重w由0.9減小到0.4；個體極值需要擾動的停滯代數(shù)閾值T=3。本文的函數(shù)適應(yīng)度取以10為底的對數(shù)，同時，為了避免真數(shù)為0和縱坐標范圍過大，給函數(shù)適應(yīng)度加上10-25作為截止值。

圖2為五個函數(shù)在各算法中的適應(yīng)度進化曲線，從中可以看出，PSO-GA，CPSO-GA解決高維無約束優(yōu)化問題的能力均好于GA[1]和PSO[2]。其中，CPSO-GA的實現(xiàn)過程與PSO-GA類似，僅在粒子更新時采用式(5)。CPSO-GA的收斂精度和收斂速度最好，均能找到最優(yōu)解與最優(yōu)值，甚至可以達到目標的精確解，一般進化代數(shù)在200代以內(nèi)就能夠找到全局最優(yōu)解，收斂速度很快。

圖2 f1-f5在四種算法中的適應(yīng)度進化曲線

表1給出了各算法對測試函數(shù)搜索到的最優(yōu)值的最小值、均值、最大值、標準差以及尋優(yōu)成功率的比較結(jié)果，該表中的結(jié)果均是各算法經(jīng)過100次獨立運算后得到的各數(shù)值的均值，其中尋優(yōu)成功率是指搜索到的最優(yōu)解和理論解的誤差在0.001之內(nèi)的次數(shù)與總的運算次數(shù)之比。從表1可以看出，GA和PSO對五個測試函數(shù)均不能搜索到全局最優(yōu)值；PSO-GA的尋優(yōu)成功率較高，尋找到全局最優(yōu)值的精度也比較高；而CPSO-GA能夠100%地尋找到全局最優(yōu)值，尋優(yōu)的精度也很高，其中f4和f5已找到精確的最優(yōu)值，說明該算法具有很好的收斂性。本文所有程序均用Matlab編寫，其計算精度是10-308，若小于此精度，函數(shù)值默認為0。

表1 各算法對測試函數(shù)尋找到最優(yōu)解的最小值、均值、最大值、標準差以及尋優(yōu)成功率比較

圖2和表1表明，同其他算法相比，CPSO-GA的性能最好。算法在進化過程中，每一代計算出的最優(yōu)解逐漸向問題的真實解靠近。這是因為粒子在更新時，受到上一代粒子的影響，同時也受到上一代局部和全局最優(yōu)解的影響。更新的粒子及時糾正局部與全局最優(yōu)解，最后局部與全局最優(yōu)解逐漸向問題的真實解靠近，并收斂到問題的真實解。而且當利用具有混沌運動特性的混沌序列更新粒子時，粒子的多樣化進一步加強，于是粒子從不同方向靠近問題的真實解，由此縮短了收斂進程。本文提出的算法綜合了PSO與GA兩種算法的優(yōu)點，且在搜索時加入了混沌序列，能夠快速改變搜索方向，這也是CPSO-GA收斂準確以及收斂較快的原因。

2.2 目標函數(shù)調(diào)用次數(shù)相接近，計算函數(shù)最優(yōu)值的均值和標準差

PSO-GA和CPSO-GA在每代更新時所要調(diào)用目標函數(shù)的次數(shù)較多，亦即計算量較大，此時采用相同的種群數(shù)和相同的最大迭代代數(shù)與其他算法比較便失去了公平性。因此，為了比較公平地評估兩種算法的性能，本文在總的目標函數(shù)調(diào)用次數(shù)相接近的基礎(chǔ)上，將這兩種算法尋找到的最優(yōu)值的均值、標準差等數(shù)值與文獻中算法尋找到的相應(yīng)數(shù)值作比較，結(jié)果如表2與表3所示。

表2中來自文獻的四種算法PSO-w[26]，UPSO[27]，F(xiàn)IPS[28]，CDPSO[5]均是沒有加入混沌運動特性的PSO的改進算法。用六種算法對f1，f3，f4和f5四個函數(shù)進行測試，函數(shù)維數(shù)為10，為了使總的目標函數(shù)調(diào)用次數(shù)相接近，其中PSO-w，UPSO，F(xiàn)IPS，CDPSO四種算法采用的種群粒子數(shù)為10，最大迭代代數(shù)為3 000，則總的目標函數(shù)調(diào)用次數(shù)是3×104；PSO-GA和CPSO-GA兩種算法采用的種群粒子數(shù)為10，最大迭代代數(shù)是900，則總的目標函數(shù)調(diào)用次數(shù)在2.9×104～3×104之間。每種算法獨立運行100次。從表2可以看出，PSO-GA對函數(shù)f1可以搜索到精確解，而對其他三個函數(shù)搜索效果略差一些；CPSO-GA算法對不同的函數(shù)都比較容易跳出局部極小點、收斂到全局最優(yōu)點，搜索到最優(yōu)解的精度最高，表明其性能優(yōu)于其他幾種算法。

表2 各算法對測試函數(shù)搜索到的最優(yōu)值的均值和標準差比較

表3 各算法對測試函數(shù)搜索到最優(yōu)值的均值比較

表3中CPSO-I-CPSO-VI六種算法是文獻中提出的混沌PSO算法。用八種算法對f1-f5五個函數(shù)進行測試，函數(shù)維數(shù)為30，為了使總的目標函數(shù)調(diào)用次數(shù)接近，其中CPSO-I-CPSO-VI六種算法采用的種群粒子數(shù)為30，最大迭代代數(shù)為5 000，則總的目標函數(shù)調(diào)用次數(shù)是1.5×105；PSO-GA，CPSO-GA兩種算法采用的種群粒子數(shù)為30，最大迭代代數(shù)是1 000，則總的目標函數(shù)調(diào)用次數(shù)在9.4×104～1.0×105之間。每種算法獨立運行100次。從表3可以看出，PSO-GA，CPSO-GA兩種算法對測試函數(shù)搜索到的最優(yōu)值的均值比CPSO-I-CPSO-VI六種算法要好、精度要高，其中CPSO-GA對f1，f4和f5均能搜索到目標函數(shù)的最優(yōu)值，對f2搜索到的最優(yōu)值的精度也比較高。

表2和表3也說明，無論是與不加混沌序列的改進PSO比較，還是與幾種混沌PSO比較，在總的目標函數(shù)調(diào)用次數(shù)接近時，CPSO-GA具有最好的全局搜索性能和最高的收斂精度，亦即更準確地搜索到全局最優(yōu)解。

2.3 固定收斂精度，評估需調(diào)用目標函數(shù)的次數(shù)

在實際的問題優(yōu)化中，我們不僅想得到較準確的優(yōu)化結(jié)果，而且要盡可能減小算法的計算量，因此，在達到可接受解的條件下，減少目標函數(shù)的調(diào)用次數(shù)顯得尤為重要。選用FIPS[28]，CLPSO[29]，CDPSO[5]三種算法，然后與CPSO-GA在目標函數(shù)調(diào)用次數(shù)上加以比較。用f1，f3，f4和f5四個函數(shù)作為測試算例，設(shè)定函數(shù)維數(shù)是30，種群粒子數(shù)是20。FIPS，CLPSO和CDPSO各算法獨立運行30次，而CPSO-GA獨立運行100次，得到的達到函數(shù)閾值時所調(diào)用的目標函數(shù)次數(shù)的均值如表4所示。此表說明對單峰和多峰值的測試函數(shù)，CPSO-GA收斂速度比其他算法更快，達到函數(shù)閾值所調(diào)用的目標函數(shù)次數(shù)最少。CPSO-GA綜合了PSO和GA的優(yōu)點，并利用混沌運動的特性，使全局優(yōu)化能力增強，而且收斂速度加快，甚至計算幾代就能獲得比較精確的解，大大降低了計算量。盡管在算法計算結(jié)果比較過程中，規(guī)定了相同的函數(shù)維數(shù)、種群粒子數(shù)以及函數(shù)閾值，但由于所編寫程序不盡相同，因此在處理某些細節(jié)問題上采用的策略也有所不同，可能會造成計算結(jié)果的差異。

表4 各算法達到函數(shù)閾值時所調(diào)用目標函數(shù)次數(shù)的均值比較

3 結(jié)論

GA和PSO均是基于自然界生物進化理論的隨機搜索算法。本文結(jié)合GA和PSO的優(yōu)點以及混沌運動的特性，提出了改進的混合算法CPSO-GA，并使用五個高維非線性函數(shù)作為測試函數(shù)測試此混合算法的性能。

數(shù)值試驗及分析結(jié)果表明，在固定進化代數(shù)情況下，CPSO-GA能100%地找到最優(yōu)解，其收斂效果及尋優(yōu)能力要好于PSO-GA，GA，PSO以及文獻中所提出的算法；在所調(diào)用目標函數(shù)次數(shù)接近時，與其他文獻中提出的算法相比，PSO-GA與CPSO-GA兩種算法均能夠得到較好的收斂結(jié)果，收斂速度也很快；在固定收斂精度的情況下，CPSO-GA進化程度和收斂速度很快，并能有效擺脫局部極小點，且調(diào)用目標函數(shù)次數(shù)最少，從而大大降低了計算量。

本文提出的CPSO-GA具有PSO的可記憶性、GA的信息共享與全局收斂性，其更新粒子能夠及時糾正每一代局部與全局最優(yōu)解，而且利用混沌運動的特性加大了粒子的多樣性，這不僅擴大了搜索空間，加快了其向全局最優(yōu)解收斂的速度，而且提高了最優(yōu)解的精度。CPSO-GA不需要計算目標函數(shù)梯度等信息，僅通過生物的進化機制來尋優(yōu)，操作簡單，易于實現(xiàn)，因此，將之應(yīng)用于實際工程中可以很好地解決優(yōu)化問題。