基于精英高斯學習的改進魚群粒子群混合算法

康朝海, 王博宇, 楊永英

(1. 東北石油大學 電氣信息工程學院, 黑龍江 大慶 163318； 2. 大慶油田礦區(qū)服務事業(yè)部 物業(yè)管理一公司, 黑龍江 大慶 163000)

0 引 言

在現實生活中, 許多數學和工程問題都可以簡化成在可行域內的高維函數尋優(yōu)問題, 如磨礦過程控制[1], 車輛調度[2], 控制器參數整定[3]等。對此如人工魚群算法[4], 粒子群算法[5], 蟻群算法[6]等群智能算法被廣泛應用解決此類問題。

人工魚群算法(AFSA： Artificial Fish Swarm Algorithm)是由李曉磊等[4]于2002年基于自然環(huán)境中魚類行為提出的一種仿生智能優(yōu)化群算法。該算法具有對搜索空間適應能力強, 全局尋優(yōu)能力良好, 操作實現簡單且魯棒性較好等優(yōu)點。目前人工魚群算法除了用于求解函數尋優(yōu)問題, 還應用于其他多個領域, 并取得一定成果, 如故障診斷[7]、 圖像檢測識別[8]、 路徑規(guī)劃[9]和網絡覆蓋優(yōu)化[10]等。但該算法前期全局搜索盲目性大、 后期收斂速度慢、 雖然能尋找到最優(yōu)值所在的大致區(qū)域但很難找到高精度的最優(yōu)值。

粒子群算法(PSO： Particle Swarm Optimization)是Kennedy等[5]于1995年通過對聚集生物覓食行為研究后提出的一種群體智能優(yōu)化算法。該算法具有參數少, 易于實現, 計算速度快, 局部搜索能力強等優(yōu)點。目前已應用于眾多領域, 如電力系統(tǒng)優(yōu)化[11]、 模式識別[12]和目標跟蹤[13]等。但該算法存在全局搜索性能差、 易陷入局部最優(yōu)、 迭代時易出現停滯現象等缺點。

筆者根據優(yōu)勢互補的改進思想, 用人工魚群算法的全局搜索性好的優(yōu)點克服粒子群算法全局搜索性能差的缺點, 同時用粒子群局部搜索能力強的優(yōu)點克服人工魚群算法局部搜索性能差的缺點, 提出一種魚群粒子群混合算法。將兩種算法的優(yōu)點相結合, 解決全局搜索與局部搜索平衡欠佳的問題, 并對2種算法本身存在的初始種群分布不均、 搜索效率欠佳和最終結果精度低的問題采取對應的改進措施。

1 基本人工魚群算法與標準粒子群算法

1.1 基本人工魚群算法

通過觀察自然界中的魚類生活習性, 發(fā)現魚群通常會向營養(yǎng)豐富的區(qū)域移動, 通過模擬魚群這一行為特點, 以實現全局尋優(yōu), 即基本人工魚群算法。該算法通過模擬魚類的覓食、 聚群、 追尾、 隨機等行為在搜索區(qū)域中進行尋優(yōu)。4種行為的位置更新公式如下

其中S表示人工魚最大移動步長,Xi為人工魚當前所在的位置,Xj為視野范圍內食物濃度最高的位置。

1.2 標準粒子群算法

標準粒子群算法是一種典型的群體智能優(yōu)化算法, 其思想源自于對鳥群覓食模型的研究與行為模擬。算法的搜索機理就是隨機初始化一個粒子種群, 每個粒子通過追隨局部最優(yōu)粒子和全局最優(yōu)粒子的位置實現自我位置的更新, 這種基于最優(yōu)引導的粒子更新機制貫穿整個算法, 隨種群的不斷迭代, 粒子群逐漸向最優(yōu)解靠攏, 直至最終找到最優(yōu)解。每個粒子通過

2 基于精英高斯學習的改進魚群粒子群混合算法

人工魚群算法和粒子群算法都具有結構簡單、 容易實現且調節(jié)參數少的優(yōu)點, 因此易于組成混合算法。通過學者們的大量研究, 目前主要有兩類算法混合思想： 一類是基于融合思想; 將其中一種算法的公式或操作引入到另一種算法中, 達到全局搜索與局部搜索兼顧的目的[14,15]； 另一類是基于組合思想, 初期用魚群負責全局的粗搜索, 確定最優(yōu)值的大致區(qū)域, 后期用粒子群算法負責精搜索, 提升最終解的精度[16,17]。筆者采用第2類改進思想并對混合算法進行改進。

2.1 改進的魚群算法

2.1.1 均勻初始化

針對魚群算法隨機初始化在一定程度上會導致部分初始個體距離過密, 在維度空間上的某些區(qū)域分布不均, 進而影響算法在初期搜索全局搜索效率的缺點, 筆者采用一種維度空間均勻初始化的方法對種群進行初始化操作。與采用Logistic混沌映射和Tent映射進行初始化相比, 均勻初始化減少不必要的約束條件和循環(huán)操作次數, 保障初始種群在空間內均勻分布的同時, 提高初期搜索效率。其操作方法如下。

1) 根據種群個體總數, 子空間內種群密度系數ρ以及種群個體在各個維度分量的上界Xmax與下界Xmin, 將整個種群所在的空間均勻劃分為K個子空間。

2) 在每個子空間內, 隨機生成M個種群個體, 通過

建立歐氏距離矩陣, 根據該矩陣及子空間內種群密度系數ρ, 若Dij<ρ‖Xmax-Xmin‖, 則表明xi與xj兩個個體距離過近, 剔除其中1個體根據歐式距離矩陣并重新生成一個新的個體代替這個舊個體。其中Dij表示M個種群個體中任意兩個體xi=(xi1,xi2,…,xin)與xj=(xj1,xj2,…,xjn)的空間歐式距離,n為種群個體的維數。

3) 最后由這K×M個種群個體構成初始種群, 完成種群初始化。

2.1.2 分組搜索方式

為克服基本人工魚群算法全局搜索盲目性大, 搜索效率低的不足, 同時強化魚群算法部分的全局尋優(yōu)能力。筆者通過一定概率向每次迭代結果反饋較好的方向進行引導[18]和動態(tài)種群協(xié)作[19,20]相結合的方式, 采用仿照蛙跳算法的分組方式進行分組, 同時對組內優(yōu)秀個體和一般個體使用不同的位置更新公式, 以及視野和步長的動態(tài)調整策略。對優(yōu)秀個體使用冪函數型自適應函數調整視野及步長, 且對位置更新公式引入全局最優(yōu)值的擾動變量； 對一般個體使用線性函數型調整, 且對位置更新公式引入組內最優(yōu)值的擾動變量。此種方法的優(yōu)點如下。

1) 分組操作可提高并行搜索效率, 同時通過不同組之間的種群個體之間的混合重新分組, 實現不同子群間的信息交流, 提高全局搜索能力。

2) 蛙跳算法的分組方式與根據種群平均適應度值分組相比, 具有更好種群豐富度和全局性[21,22]。

3) 采用不同的優(yōu)秀個體進行引導, 可增加全局搜索對可行域的覆蓋, 提高搜索的遍歷性。

4) 冪函數型和線性函數型調整策略的引入, 可使優(yōu)秀個體更快收斂的同時保證一般個體探索性, 在保障全局搜索能力的同時降低算法的運行時間。

具體的實現方法如下。

1) 分組方式。對初始魚群所有N條人工魚, 按適應度值從小到大排序, 將排好序的人工魚個體分成m組, 每組含p條人工魚, 滿足N=mp, 分組方法為： 第1條人工魚放入第1組, 第2條人工魚放入第2組, 類推第m條放入第m組, 第m+1條放入第1組, 依次類推直到劃分完畢。每次迭代之后均按此方法排序分組。

2) 視野和步長的動態(tài)調整。對于每組內的所有個體, 定義前20%的個體為優(yōu)秀個體, 其余的為一般個體。對優(yōu)秀個體, 其視野及步長調整如下

S=VA

(6)

對于組內剩余個體, 其步長及視野調整如式(6)和下式所示

其中Vmax表示視野初始值,Vmin表示視野終止值,iter表示當前迭代次數,Gmax表示最大迭代次數,A∈[0.5,1]的隨機數。

3) 組內個體位置更新公式。以聚群行為為例, 優(yōu)秀個體位置更新公式及其他個體更新公式, 形式如下

其中Xi為人工魚的位置狀態(tài),Xc為但組內人工魚的中心位置,XB為組內最優(yōu)人工魚的位置狀態(tài),R為擾動影響因子調節(jié)全局或組內最優(yōu)值對移動方向的影響大小, 對于優(yōu)秀個體時XG為全局最優(yōu)人工魚的位置狀態(tài), 對于其他個體時XG為組內最優(yōu)人工魚的位置狀態(tài)。對追尾行為和覓食行為的公式改進方式與聚群行為相同。

2.2 改進的精英高斯學習策略

針對粒子群算法迭代時易出現最優(yōu)值停滯和最終結果精度低的問題, 筆者采用一種改進精英高斯學習跳出停滯狀態(tài), 從而提高最終結果的精度。精英高斯學習[23]是以引入高斯分布為基礎, 在原有的最優(yōu)個體上隨機選取某一維加上一個高斯隨機擾動項, 且其他維度上保持不變, 從而得到一個新個體, 若新個體適應度值優(yōu)于原來的個體, 則保留新個體, 否則不保留。其學習方式如下

Pd=Pd+(Xmax-Xmin)Gaussian(μ,σ2)

(9)

d=random(1,D)

(10)

其中P表示最優(yōu)個體的位置狀態(tài),d表示該個體的一個隨機維度,Xmax和Xmin為維度分量的上界和下界,μ為高斯分布的均值,σ2為高斯分布的方差,D為總維數。

精英高斯學習也存在變異結果隨機性較大, 導致變異的成功率不高[24], 以及在對最優(yōu)個體進行學習時, 過多的盲目學習對收斂精度提升不穩(wěn)定且影響算法的運行速度[25]等缺點。針對以上不足, 筆者在已有的精英高斯學習基礎上進行以下兩個方面的改進。

1) 調整精英高斯學習的調用時機和適用個體。當全局最優(yōu)值連續(xù)3代無變化時, 對全局最優(yōu)個體和本次迭代中最優(yōu)的前10%個體進行精英高斯學習,在擴大學習對象的同時降低多次學習對整體算法運行速度的影響。

2) 對精英群體進行有方向的學習。先對個體的所有維度逐一進行高斯學習, 并對每一個維度的結果匯總排序, 選出排名前dbest個維度作為學習方向, 之后對該個體這dbest個維度進行T次高斯學習取最優(yōu)值, 最優(yōu)值優(yōu)于全局最優(yōu)則替換, 否則不保留, 其他精英個體同樣采用此方法處理。通過對學習方向的確定, 降低隨機學習過程中的不確定性, 提高精英高斯學習的執(zhí)行效率。

2.3 混合算法的步驟

綜上所述, 基于精英高斯學習的改進魚群粒子群混合算法的步驟如下。

Step1 設置混合算法中的各個參數。

Step2 根據2.1節(jié)改進進行種群位置初始化。

Step3 對種群進行適應度計算并排序分組。

Step4 各組內的前20%優(yōu)秀個體和普通個體, 各自按照視野及步長的動態(tài)調整策略和改進的位置更新公式, 進行聚群、 追尾和覓食等行為。

Step5 判斷是否達到全局最優(yōu)值小于10-4或迭代次數達到最大迭代次數的結束條件, 滿足則將全局最優(yōu)值和公告板中各組前20%個體作為粒子群算法部分的初始粒子, 執(zhí)行Step6； 否則, 繼續(xù)執(zhí)行Step3。

Step6 按照粒子群更新公式更新粒子, 尋找全局最優(yōu)值。

Step7 判斷全局最優(yōu)值是否連續(xù)3代無變化, 滿足則按照對全局最優(yōu)值和本次迭代最優(yōu)的前10%個體進行改進的精英高斯學習； 否則繼續(xù)執(zhí)行Step6。

Step8 判斷是否達到最大迭代次數終止條件, 滿足則輸出最終的全局最優(yōu)值； 否則, 繼續(xù)執(zhí)行Step6。

3 數值仿真實驗

3.1 標準測試函數及參數設置

為證明筆者改進算法的優(yōu)化效果, 選取表1中的6個標準函數進行仿真實驗測試對比, 其中Sphere和Rosenbrock為單峰函數, Griewank, Rastringin, Schaffer和Ackley均為復雜的多峰函數。

表1 標準測試函數

與此同時引入標準粒子群算法PSO, 基本人工魚群算法AFSA以及文獻[14]提出的粒子群改進魚群算法PSO-FSA進行對比, 各算法的參數設置如表2所示, 其中步長按式(6)變化, 慣性權重因子ω按如下所示

ω(t)=[-iter(ωmax-ωmin)/Gmax]+ωmax

(11)

其中ωmax表示慣性權重因子ω的最大值,ωmin表示慣性權重因子的最小值,iter表示當前迭代次數,Gmax表示最大迭代次數。

表2 算法參數設置

3.2 筆者算法與其他算法結果對比分析

為準確比較算法的尋優(yōu)性能, 將各算法的最大迭代次數設為1 000, 種群規(guī)模大小設為81, 維數為30, 4種算法各自獨立運行30次, 并通過實驗數據和平均尋優(yōu)結果(適應度值)迭代曲線兩種方式說明。表3列出了各算法分別獨立運行30次尋優(yōu)結果的平均值和30次獨立運行中出現過的最好結果, 標準差及平均耗時。圖1為各算法平均尋優(yōu)結果(適應度值)的迭代曲線對比圖, 橫坐標表示迭代次數, 縱坐標為更直觀顯示, 取平均尋優(yōu)結果以10為底的對數值。

圖1 標準函數適應度值對數迭代曲線對比Fig.1 The standard function fitness value log iteration curve comparison

函數性能指標PSOAFSAPSO-FSA筆者算法Sphere平均值8.74×10-31.93×10-43.14×10-78.92×10-9最好結果7.82×10-51.20×10-55.22×10-82.05×10-10標準差1.43×10-22.09×10-41.53×10-71.70×10-9平均耗時/s7.4339.3769.4678.536Rosenbrock平均值3.50×1003.08×10-43.65×10-31.04×10-5最好結果1.04×1002.69×10-64.38×10-51.14×10-6標準差2.28×1005.41×10-44.13×10-31.05×10-5平均耗時/s8.68612.54110.42310.505Griewank平均值1.48×1002.00×10-21.62×10-41.38×10-6最好結果1.23×10-11.15×10-38.40×10-51.09×10-6標準差2.46×10-11.29×10-21.32×10-41.10×10-6平均耗時/s8.97715.35011.76511.098Rastringin平均值7.67×10-14.94×10-22.91×10-32.00×10-5最好結果6.57×10-15.24×10-51.29×10-64.35×10-7標準差6.80×10-25.41×10-34.13×10-42.38×10-5平均耗時/s10.64014.95712.45312.488Schaffer平均值1.07×10-17.35×10-24.26×10-24.12×10-3最好結果7.82×10-21.22×10-29.72×10-35.30×10-5標準差2.67×10-26.12×10-23.44×10-23.61×10-4平均耗時/s11.05416.19313.91214.031Ackley平均值3.44×10-31.44×10-36.81×10-52.02×10-5最好結果1.57×10-34.00×10-41.16×10-55.64×10-6標準差1.51×10-31.20×10-37.28×10-51.39×10-5平均耗時/s9.78315.0809.84110.082

由圖1和表3可知, 對于高維標準函數的極值尋優(yōu), 在相同的種群規(guī)模和迭代次數下, 標準粒子群算法除了在Sphere函數上能相對收斂, 在其他5個標準函數上均無法收斂到全局最優(yōu)值?；救斯~群算法相比于粒子群算法, 在6個標準函數上尋優(yōu)精度均優(yōu)于標準粒子群算法, 但對于復雜的多峰函數其收斂速度相對較慢且易出現停滯現象, 即全局最優(yōu)值在多次迭代過程中無明顯變化, 導致其尋優(yōu)精度無法提升, 在一定程度上影響算法的計算穩(wěn)定性。粒子群改進魚群算法, 由于引入了粒子群算法的相關概念對魚群算法的行為模式進行優(yōu)化, 與前兩種算法相比, 除了在Rosenbrock函數上, 尋優(yōu)精度略遜于魚群算法, 在其他標準函數上尋優(yōu)精度和收斂速度均有所提升, 尤其是在Sphere, Griewank和Rastringin函數上相對明顯。筆者算法通過采用分組魚群的執(zhí)行策略與帶有高斯學習粒子群算法的結合, 通過圖2曲線可看出, 在算法前期適應度值下降速度明顯優(yōu)于其他3種算法, 說明分組魚群算法部分能較快的尋找到全局最優(yōu)值所在的大致區(qū)域, 在算法后期由于高斯學習的引入, 減少了停滯的迭代次數的同時提高了尋優(yōu)精度, 對于算法計算的穩(wěn)定性, 通過表3對比可見, 其提升也較為明顯, 尤其是在Griewank和Sphere函數上較為顯著。

3.3 均勻初始化和分組策略及精英高斯學習的影響分析

為體現均勻初始化, 分組策略和改進精英高斯學習對改進算法的影響程度, 在與3.2節(jié)相同的實驗條件下, 分別在無均勻初始化, 無分組策略和無高斯學習的條件下, 以典型的復雜多峰函數Griewank測試其在不同維度下的影響程度。表4列出了在不同維度下根據上述3種條件, 分別獨立運行30次的尋優(yōu)結果平均值, 圖2為其平均尋優(yōu)結果(適應度值)的迭代曲線對比圖, 橫坐標表示迭代次數, 縱坐標取尋優(yōu)結果平均值以10為底的對數值。

圖2 不同維度下適應度值對數迭代曲線對比Fig.2 The fitness value log iteration curve of the fitness value in different dimensions

維數完整筆者算法無均勻初始化無分組策略無精英高斯學習37.40×10-39.80×10-39.72×10-39.96×10-3152.71×10-53.20×10-42.91×10-31.03×10-2304.01×10-67.43×10-61.64×10-52.22×10-2

由表4和圖2可見, 均勻初始化在3維時, 對算法前期的收斂速度影響較為明顯, 而在15維和30維時, 其對前期的收斂速度和最終的尋優(yōu)精度影響有限。分組策略部分, 不論是低維還是高維, 對算法前期的收斂速度影響最大, 且維度越高影響越明顯, 同時由于執(zhí)行魚群算法迭代部分的次數是固定值, 前期收斂速度慢, 搜索盲目性大使混合算法中魚群算法部分的尋優(yōu)精度不足, 導致其向粒子群算法部分提供的優(yōu)秀初始種群的質量下降, 影響到最終的尋優(yōu)精度。精英高斯學習部分對最優(yōu)值的影響最大, 其主要幫助最優(yōu)個體跳出迭代過程中的停滯, 避免其陷入早熟, 同時加快算法后期的收斂速度和最終的收斂精度。

綜上所述, 筆者對算法的改進是可行有效的, 均勻初始化在高維時影響較小, 但在低維時配合分組策略可提高前期的收斂速度和精度, 而分組策略和精英高斯學習的結合, 在任何維度對算法的整體運行效率和最終尋優(yōu)精度提升顯著。

4 結 語

筆者針對基本人工魚群算法和粒子群算法對高維問題的尋優(yōu)能力進行了研究, 在混合算法的組合思想基礎上, 提出一種改進魚群粒子群混合算法。算法前期, 針對魚群算法部分存在初始種群個體分布不均, 搜索盲目性大效率低的問題, 通過均勻初始化進行種群初始化, 優(yōu)化種群分布, 然后采用仿照蛙跳算法的分組方式對種群進行分組, 同時對組內優(yōu)秀個體和一般個體使用不同的位置更新公式, 以及視野和步長的動態(tài)調整策略, 解決了全局搜索的方向性差和運行效率低的問題；算法后期, 針對粒子群算法迭代最優(yōu)值停滯, 收斂精度低的問題, 引入一種改進的精英高斯學習操作, 通過調整調用時機和適用范圍, 并利用對嘗試性學習的結果排序分析確定學習方向, 提升高斯學習的有效性, 減少了迭代過程中的停滯, 解決了算法收斂慢精度低的問題。最后通過標準測試函數測試與其他3種算法的性能比較以及各改進部分的獨立影響分析, 證明筆者的算法是可行的。