基于混沌映射的自適應(yīng)退火型粒子群算法

田興華，張紀(jì)會(huì)，李 陽

(青島大學(xué)復(fù)雜性科學(xué)研究所，山東 青島 266071)

0 引言

自然界中的鳥群和魚群的群體行為看似隨意混亂實(shí)則存在一定的規(guī)律，對(duì)各類群體行為的研究及應(yīng)用是近年來的研究熱點(diǎn)。其中最為著名的研究當(dāng)屬生物學(xué)家Craig Reynolds于1987年提出的鳥群聚集模型[1]和Frank Happner于1990年建立的鳥群飛行模型[2]。1995年，美國社會(huì)心理學(xué)家Jammes Kennedy和電氣工程師Russell Eberhart在前人研究基礎(chǔ)上提出了粒子群算法(Particle Swarm Optimization, PSO)[3]。由于該算法結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn)，一經(jīng)提出就立刻引起了進(jìn)化計(jì)算領(lǐng)域?qū)W者們的廣泛關(guān)注，形成一個(gè)研究熱點(diǎn)。Kennedy等學(xué)者于2001年出版了第一部專著《Swarm Intelligence》[4]，隨后關(guān)于粒子群優(yōu)化算法的研究成果大量涌現(xiàn)并在眾多領(lǐng)域得到應(yīng)用。和其它現(xiàn)代優(yōu)化算法一樣，原始粒子群在求解復(fù)雜優(yōu)化問題時(shí)也存在一些缺點(diǎn)，需要根據(jù)待求解問題的特點(diǎn)加以改進(jìn)才能取得良好的搜索效果。為此，許多學(xué)者從不同角度對(duì)PSO算法進(jìn)行了改進(jìn)[5-35]。

從對(duì)算法改進(jìn)的目的來看，有增強(qiáng)算法的自適應(yīng)改進(jìn)、增強(qiáng)收斂性改進(jìn)、增加多種群多樣性的改進(jìn)、增強(qiáng)局部搜索的改進(jìn)、與全局優(yōu)化算法相結(jié)合、與確定性的局部優(yōu)化算法相融合，有自適應(yīng)PSO[21-29]，帶收縮因子的PSO[30]，模糊自適應(yīng)PSO[31]等。從對(duì)算法的改進(jìn)方法來看，有基于參數(shù)的改進(jìn)，即對(duì)PSO算法的迭代公式進(jìn)行改進(jìn)；有從粒子的行為模式進(jìn)行改進(jìn)，即粒子之間的信息交流方式，如拓?fù)浣Y(jié)構(gòu)的改進(jìn)、全局模式與局部模式相結(jié)合的改進(jìn)等；還有基于算法融合的改進(jìn)PSO，算法融合是指引入其他算法的優(yōu)點(diǎn)來彌補(bǔ)原始PSO算法的缺點(diǎn)。有與遺傳算法結(jié)合的PSO[32]，與經(jīng)典優(yōu)化算法相結(jié)合的PSO[33]，與模擬退火算法、神經(jīng)網(wǎng)絡(luò)相結(jié)合以及多目標(biāo)PSO，以及與混沌映射(如Logistic、Cubic和Tent等)相結(jié)合的PSO[34]。

為了進(jìn)一步改進(jìn)PSO的不足，提高其性能，本文在自適應(yīng)PSO和模擬退火算法的基礎(chǔ)上，提出了一種基于混沌映射的自適應(yīng)退火型PSO。主要的改進(jìn)工作體現(xiàn)在：1)在局部最優(yōu)解附近添加混沌擾動(dòng)，使其具有突跳能力，能夠有效提高全局搜索能力。2)對(duì)傳統(tǒng)的慣性因子采用雙重選擇策略，不僅使慣性因子隨著目標(biāo)函數(shù)的變化而變化而且隨著粒子當(dāng)前位置與上一時(shí)刻位置的距離的變化而變化。3)采用線性遞減加速因子來動(dòng)態(tài)調(diào)整自身經(jīng)驗(yàn)和群體經(jīng)驗(yàn)在迭代中的作用。通過數(shù)值實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的性能，結(jié)果表明改進(jìn)的算法的尋優(yōu)能力要優(yōu)于自適應(yīng)PSO和模擬退火PSO。

1 基本PSO的基本原理

假設(shè)在一個(gè)D維搜索空間中，有N個(gè)粒子組成一個(gè)群體，標(biāo)準(zhǔn)PSO算法的數(shù)學(xué)模型為[3]：

vid(t+1)=ωvid(t)+c1r1(t)(pid(t)-xid(t))+c2r2(t)(pgd(t)-xid(t))xid(t+1)=xid(t)+vid(t+1)i=1,2,…,N;d=1,2,…,D

其中，ω為慣性權(quán)重，c1和c2為加速因子，分別代表了粒子自身認(rèn)知參數(shù)和社會(huì)認(rèn)知參數(shù)，r1和r2分別為兩個(gè)相互獨(dú)立的[0,1]之間的服從均勻分布的隨機(jī)變量，pid為粒子i的歷史最好位置，pgd為整個(gè)種群找到的最好位置。PSO迭代公式由三部分構(gòu)成，第一部分為慣性或動(dòng)量部分，反映粒子的運(yùn)動(dòng)習(xí)慣，代表粒子維持自己先前速度的趨勢(shì)。第二部分為認(rèn)知部分，反映了粒子對(duì)自身歷史經(jīng)驗(yàn)的記憶，代表粒子向自身歷史最佳位置逼近的趨勢(shì)。第三部分為社會(huì)部分，反映了粒子間協(xié)同合作與知識(shí)共享的群體歷史經(jīng)驗(yàn)，代表了粒子向群體或鄰域歷史最優(yōu)位置逼近的趨勢(shì)[3]。

2 相關(guān)研究概述

混沌現(xiàn)象是一種非周期的具有漸近自相似有序性的現(xiàn)象。因其具有隨機(jī)性、遍歷性、規(guī)律性的獨(dú)特性質(zhì)，常作為優(yōu)化設(shè)計(jì)領(lǐng)域搜索過程中避免陷入局部極值的一種全局優(yōu)化機(jī)制。近年來，許多學(xué)者把混沌優(yōu)化原理和現(xiàn)代優(yōu)化算法相結(jié)合，取得了一些很好的成果。這類研究基本上可以分成兩類，1)將混沌映射產(chǎn)生的序列取代算法里面的隨機(jī)參數(shù)；2)將混沌映射產(chǎn)生的序列映射到搜索空間，起到局部搜索的作用[18]。

文獻(xiàn)[12]提出將混沌自適應(yīng)粒子群和序貫二次規(guī)劃算法相結(jié)合的方法，在基本PSO算法的基礎(chǔ)上，加入混沌搜索和自適應(yīng)慣性權(quán)重提高全局收斂能力，當(dāng)粒子群體聚集度較高時(shí)，以一定概率對(duì)最優(yōu)粒子進(jìn)行基于Logistic映射的混沌搜索，以使粒子跳出局部最優(yōu)，并且根據(jù)粒子的進(jìn)化速度和聚集度而自適應(yīng)改變慣性權(quán)重，并在PSO算法每一代的迭代過程中，引入SQP策略，提高局部搜索能力。

文獻(xiàn)[13]將cat映射(也稱為Arnold映射)、云模型和PSO結(jié)合的方法，并用于港口作業(yè)量預(yù)測(cè)，其中混沌映射的作用是用來對(duì)最差粒子進(jìn)行改進(jìn)。

為了避免陷入局部最優(yōu)和維持種群多樣性，文獻(xiàn)[14]提出了將局部搜索和頭腦風(fēng)暴算法相結(jié)合的策略，其中局部搜索算法依概率從12個(gè)常用的混沌映射隨機(jī)選擇。

考慮到混沌映射對(duì)初始條件的敏感性可能會(huì)導(dǎo)致算法性能不穩(wěn)定問題，文獻(xiàn)[11]提出了并行混沌局部搜索和和聲搜索相結(jié)合的策略，對(duì)每個(gè)混沌映射，采用多個(gè)不同初始值產(chǎn)生局部混沌搜索，從而達(dá)到消除初值敏感性的目的。

文獻(xiàn)[15]分別利用5種不同的混沌映射和著名的BFGS算法相結(jié)合，通過數(shù)值仿真試驗(yàn)，研究了混沌搜索對(duì)改進(jìn)算法的性能所起的作用，結(jié)果表明混沌映射產(chǎn)生的混沌序列的統(tǒng)計(jì)性能對(duì)算法性能有顯著影響，而且認(rèn)為僅僅通過少量的低維測(cè)試函數(shù)試驗(yàn)結(jié)果來判斷混沌映射在改進(jìn)算法性能方面的優(yōu)劣是不夠的。

文獻(xiàn)[16,17]對(duì)混沌優(yōu)化的工作機(jī)制進(jìn)行了探討，認(rèn)為混沌映射產(chǎn)生的序列的概率密度函數(shù)和李雅普諾夫指數(shù)決定了混沌優(yōu)化的性能，為算法設(shè)計(jì)提供了理論指導(dǎo)。

針對(duì)組合優(yōu)化問題，文獻(xiàn)[18]提出了混沌PSO算法。用混沌搜索實(shí)現(xiàn)對(duì)粒子飛行速度和位置的自適應(yīng)調(diào)整。

從方法上來看，大部分文獻(xiàn)都是利用混沌優(yōu)化嵌入到現(xiàn)代優(yōu)化方法中，利用混沌序列的遍歷性質(zhì)，起到局部搜索作用[19-20]。

3 基于混沌映射的自適應(yīng)退火型粒子群算法

現(xiàn)有的研究成果表明，混沌優(yōu)化可以彌補(bǔ)粒子群算法容易陷入早熟收斂的缺點(diǎn)，基于這種思想我們提出基于混沌映射的自適應(yīng)粒子群算法，算法的具體思想如下。

首先，隨機(jī)產(chǎn)生初始種群；其次，對(duì)傳統(tǒng)的慣性因子采用雙重選擇策略，不僅使慣性因子隨著目標(biāo)函數(shù)的變化而變化，而且隨著粒子當(dāng)前位置與上一時(shí)刻位置的距離的變化而變化，使其自適應(yīng)性更強(qiáng)。當(dāng)粒子目標(biāo)值分散時(shí)，減小慣性權(quán)重，此時(shí)算法局部搜索能力強(qiáng)，從而使群體趨于收斂；粒子目標(biāo)值較為密集時(shí)，增大慣性權(quán)重，使粒子具有較強(qiáng)的探查能力，從而有效地跳出局部最優(yōu)；同時(shí)，對(duì)加速因子做了線性改進(jìn)，在種群尋優(yōu)的初期，粒子主要依靠自身經(jīng)驗(yàn)尋找下一個(gè)位置，在種群發(fā)展的后期，群體經(jīng)驗(yàn)在指導(dǎo)粒子尋找下一個(gè)最優(yōu)位置方面應(yīng)該發(fā)揮更大作用，所以，加速因子采用線性函數(shù)表示。又因?yàn)槟M退火算法在搜索過程中具有突跳的能力，可以有效地避免搜索陷入局部極小解，添加模擬退火算子，以概率接受適應(yīng)度較差的解，增加了種群的多樣性。

具體實(shí)現(xiàn)過程闡述如下：

1)加速因子的設(shè)置：因?yàn)樵诜N群搜索的初期主要依賴自身經(jīng)驗(yàn)，在種群演化的后期群體經(jīng)驗(yàn)發(fā)揮更大的作用，所以加速因子的設(shè)置采用線性函數(shù)表示，設(shè)定c1,c2,C1,C2的大小在[1.95,2.15]之間，根據(jù)式(1)和(2)計(jì)算參數(shù)s1和s2：

s1=C1-(C1-c1)*(t/M)

(1)

s2=C2-(C2-c2)*(t/M)

(2)

其中，當(dāng)前進(jìn)化代數(shù)t=1,…,M，M為最大迭代次數(shù)。

2)慣性因子的設(shè)置：在粒子群算法中慣性權(quán)重是非常重要的參數(shù)，增大ω的值可以提高算法的全局搜索能力，減小ω的值可以提高算法的局部搜索能力。本文采用非線性動(dòng)態(tài)慣性權(quán)重系數(shù)公式來更新慣性因子，使之在[0.4,0.9]之間非線性動(dòng)態(tài)調(diào)整，并添加一個(gè)擾動(dòng)算子。更新方式如下：

(3)

其中，ωmax表示慣性權(quán)重最大值，ωmin表示慣性權(quán)重最小值，t表示當(dāng)前迭代步數(shù)，favg和fmin分別表示當(dāng)前種群對(duì)應(yīng)的目標(biāo)函數(shù)值的平均值和最小值。

3)初始溫度的設(shè)置：初始溫度和降溫方式對(duì)算法有一定的影響，根據(jù)前人的研究經(jīng)驗(yàn)，我們采用模擬退火算法里的公式確定初始溫度[27]：

tk+1=λtk,t0=f(pg)/ln5

(4)

4)粒子的性能評(píng)價(jià)方法：根據(jù)式(5)確定當(dāng)前溫度下各粒子pi的適應(yīng)度值(其中參數(shù)T表示當(dāng)前溫度)。

(5)

5)粒子的位移和速度更新公式：添加擾動(dòng)算子可以使算法在陷入局部最優(yōu)解時(shí)在一定范圍內(nèi)波動(dòng)，降低最優(yōu)解的錯(cuò)失率，提高算法的性能。添加混沌擾動(dòng)策略后，粒子位置更新方式如下：

vi,j(t+1)=ωvi,j(t)+s1r1[pi,j-xi,j(t)]+s2r2[pg,j-xi,j(t)]

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1)+Δvi,j(t+1)

(7)

(8)

通常情況下:α=2且xn≠0.5。因?yàn)楫?dāng)xn=0.5時(shí)混沌序列將會(huì)陷入周期運(yùn)動(dòng)，不具有遍歷性。

6)接收概率的設(shè)置：采用模擬退火算法的接收算子，依概率接受適應(yīng)度較差的解。

(9)

其中，f(xi)和f(xi+1)分別為第i和i+1代粒子的目標(biāo)函數(shù)值(i=0,1,…,N)，P表示接收概率且此概率隨著時(shí)間推移逐漸降低。

綜上所述，我們提出的改進(jìn)的算法步驟及流程是：

1)初始化：隨機(jī)產(chǎn)生初始種群；根據(jù)式(1)和(2)設(shè)置加速因子,根據(jù)式(3)設(shè)置慣性權(quán)重,設(shè)置種群個(gè)數(shù),最大迭代次數(shù)等參數(shù)的取值范圍。

2)根據(jù)式(4)評(píng)價(jià)每個(gè)粒子的適應(yīng)度，存儲(chǔ)粒子的最優(yōu)位置pbest和對(duì)應(yīng)適應(yīng)度值，以及群體最優(yōu)個(gè)體位置gbest和對(duì)應(yīng)適應(yīng)度值。

3)根據(jù)式(6)和(7)更新粒子的位移和速度。

4)將每個(gè)粒子的適應(yīng)度值與粒子的最好位置比較,如果相近,則將當(dāng)前值作為粒子的最好位置。比較當(dāng)前所有的pbest和gbest,并更新gbest。

5)以概率(9)接受適應(yīng)度較差的粒子,返回步驟3)。

6)判斷是否達(dá)到最大迭代次數(shù),若是，則結(jié)束;否則，返回步驟2)。

算法流程圖如圖1所示。

圖1 基于混沌映射的自適應(yīng)退火型粒子群算法流程圖Fig.1 The flow chart of adaptive annealing particle swarm optimization based on chaotic mapping

4 仿真試驗(yàn)與結(jié)果分析

為了驗(yàn)證改進(jìn)的算法的尋優(yōu)能力，選取幾種不同類型的基準(zhǔn)函數(shù)來評(píng)估改進(jìn)的算法，并與自適應(yīng)粒子群算法以及基于模擬退火的算法進(jìn)行對(duì)比，分析改進(jìn)的算法的優(yōu)缺點(diǎn)。

仿真試驗(yàn)安排如下：根據(jù)文獻(xiàn)研究選取10個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行數(shù)值試驗(yàn)，算法由MATLAB 2016軟件實(shí)現(xiàn)，表1給出測(cè)試函數(shù)、搜索空間和測(cè)試函數(shù)的特點(diǎn)。

表1 測(cè)試函數(shù)公式列表

用10個(gè)測(cè)試函數(shù)分別對(duì)3種粒子群優(yōu)化算法，在30維空間上進(jìn)行試驗(yàn)，其中，常用參數(shù)設(shè)置如表2所示，實(shí)驗(yàn)結(jié)果如表3所示。

為了進(jìn)一步比較改進(jìn)的算法的穩(wěn)定性，在30維空間下，群體規(guī)模為100，迭代100次，每個(gè)測(cè)試函數(shù)仿真30次，并對(duì)結(jié)果進(jìn)行方差分析，分析結(jié)果如表4所示。

表2 參數(shù)設(shè)置

表3 結(jié)果對(duì)比

表4 APSO,LPSO與ACPSO算法方差與標(biāo)準(zhǔn)差分析結(jié)果

實(shí)驗(yàn)結(jié)果表明，在種群最大迭代代數(shù)為100的情況下，本文提出的粒子群算法對(duì)于高維函數(shù)f1～f4,f6,f8～f10的尋優(yōu)能力都遠(yuǎn)遠(yuǎn)優(yōu)于自適應(yīng)粒子群算法以及基于模擬退火的算法，尋優(yōu)的速度也明顯提高，并且非常接近全局最優(yōu)解，性能表現(xiàn)良好，方差與標(biāo)準(zhǔn)差很小，性能比較穩(wěn)定，能達(dá)到我們預(yù)期的結(jié)果。對(duì)于f5,f7的運(yùn)行結(jié)果，迭代次數(shù)為100時(shí)的平均尋優(yōu)結(jié)果與基本的自適應(yīng)粒子群算法和基于模擬退火的算法相比性能有所提高，更加逼近理想最優(yōu)，但是沒有達(dá)到理想效果，結(jié)果略差，且方差較大，尋優(yōu)波動(dòng)性明顯。綜上，改進(jìn)的算法能大大提高尋優(yōu)性能，但是對(duì)個(gè)別函數(shù)尋優(yōu)能力較差，所以，改進(jìn)的算法的性能有待進(jìn)一步提高，使其適用于各種函數(shù)。對(duì)于10個(gè)測(cè)試函數(shù)3種粒子群算法的尋優(yōu)收斂軌跡如圖2所示。

圖2 針對(duì)10個(gè)測(cè)試函數(shù)的3種算法的收斂軌跡圖Fig.2 Convergence trajectories of 3 algorithms for 10 test functions

圖3 30次結(jié)果匯總圖Fig.3 Summary of 30 results

圖3結(jié)果表明，算法在f5和f7的表現(xiàn)波動(dòng)較大，在其余測(cè)試函數(shù)的尋優(yōu)結(jié)果都比較平穩(wěn)，說明改進(jìn)的算法性能比較穩(wěn)定。

為了更嚴(yán)謹(jǐn)?shù)貦z驗(yàn)本文算法的有效性，對(duì)上述仿真結(jié)果進(jìn)行如下假設(shè)檢驗(yàn)。分別對(duì)ACPSO與APSO和ACPSO與LPSO進(jìn)行顯著性水平為α=0.05的Wilcoxon符號(hào)秩檢驗(yàn)。Wilcoxon符號(hào)秩檢驗(yàn)用于判斷兩個(gè)配對(duì)總體的分布是否存在顯著性差異(如果ACPSO算法結(jié)果優(yōu)于APSO/LPSO則記為“+”，否則記為“-”，若無明顯差異記為“NA”)。正號(hào)秩總和記為W+，負(fù)號(hào)秩總和記為W-。如果W+和W-相差較小，則認(rèn)為兩組結(jié)果基本相同。顯著性水平為α=0.05，并用SPSS計(jì)算出相應(yīng)的概率p值，如果p≤α，則應(yīng)為兩組數(shù)據(jù)分布不相同，如果p>α，則認(rèn)為兩組數(shù)據(jù)分布相同。檢驗(yàn)結(jié)果如表5和表6所示。

表5 ACPSO和APSO的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果

由表5可以看出ACPSO算法和APSO算法針對(duì)10個(gè)測(cè)試函數(shù)的30次測(cè)試結(jié)果的分布基本不相同，且ACPSO算法的結(jié)果顯著優(yōu)于APSO算法。

表6 ACPSO和LPSO的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果

由表6可以看出，ACPSO算法和LPSO算法對(duì)10個(gè)測(cè)試函數(shù)的30次測(cè)試結(jié)果的分布明顯不相同，且ACPSO算法的結(jié)果顯著優(yōu)于LPSO算法。

5 結(jié)論與展望

本文的改進(jìn)方法充分利用群體演化過程中的信息，挖掘粒子之間的關(guān)系，用來動(dòng)態(tài)調(diào)整粒子自身經(jīng)驗(yàn)與群體經(jīng)驗(yàn)在尋優(yōu)方面的作用，并且在局部最優(yōu)解附近通過混沌擾動(dòng)避免陷入局部最優(yōu)，從而達(dá)到更加逼近理想最優(yōu)解，使算法的性能得到了一定的改善。未來的工作是如何進(jìn)一步完善改進(jìn)算法，使其結(jié)果更為精確，更好地解決不同特點(diǎn)的函數(shù)優(yōu)化問題，并且嘗試用其解決復(fù)雜的實(shí)際工程優(yōu)化問題。