面向全局優(yōu)化的混沌粒子群遺傳算法

劉振軍

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

0 引言

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

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

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

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

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

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

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

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

(1)

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

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

Xcd=XLd+z(XUd-XLd)。

(2)

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

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

(3)

(4)

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

(5)

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

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

(6)

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

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

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

2 測(cè)試分析

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

Sphere函數(shù)：

(7)

Rosenbrock函數(shù)：

(8)

Ackley函數(shù)：

(9)

Griewank函數(shù)：

(10)

Rastrigrin函數(shù)：

(11)

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

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

2.1 固定進(jìn)化代數(shù)，評(píng)估算法的收斂速度與收斂精度

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

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

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

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

表1 各算法對(duì)測(cè)試函數(shù)尋找到最優(yōu)解的最小值、均值、最大值、標(biāo)準(zhǔn)差以及尋優(yōu)成功率比較

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

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

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

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

表2 各算法對(duì)測(cè)試函數(shù)搜索到的最優(yōu)值的均值和標(biāo)準(zhǔn)差比較

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

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

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

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

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

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

3 結(jié)論

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

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

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