面向遙感影像分類的時延權(quán)重及群體分類PSO改進方法

于國強，宋君陶*，于軍令，滕俊利，張麗麗，林琳

(1.山東省圣達地理信息測繪工程有限公司，山東 威海 264200；2.山東正大地理信息科技集團有限公司，山東 濰坊 261000；3.山東省水利科學研究院，山東 濟南 250014)

0 引言

遙感影像是獲取地球資源與環(huán)境信息的重要手段，廣泛應用于農(nóng)業(yè)、林業(yè)、地質(zhì)、海洋、氣象、水文、軍事、環(huán)保等領(lǐng)域。近年來，山東省大力推進數(shù)字強省建設(shè)，打造具有山東特點的一體化智能監(jiān)測技術(shù)體系和常態(tài)化監(jiān)測機制，這些對山東省遙感影像數(shù)據(jù)生產(chǎn)處理能力提出了更高要求。

遙感數(shù)據(jù)處理具有計算量大、數(shù)據(jù)密集、計算模型復雜等特點，而且近年來隨著遙感數(shù)據(jù)獲取終端的不斷發(fā)展，遙感數(shù)據(jù)的來源更多，數(shù)據(jù)類型更加多樣，數(shù)據(jù)處理模型也更為復雜。為了應對這些挑戰(zhàn)，一些智能化算法在遙感數(shù)據(jù)處理模型解算中得到了應用，其中粒子群算法應用相對廣泛[1-2]。

Kennedy與Eberhart于1995年提出了粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)，該算法受鳥類群或魚類群中生物運動的啟發(fā)，通過模擬運動過程并進行模型構(gòu)建，實現(xiàn)目標的優(yōu)化，PSO是群體智能算法的一種[3-5]。

PSO是一種群體優(yōu)化算法，其通過不斷的迭代來逐步改進候選解的精度，從而實現(xiàn)優(yōu)化的目標。PSO具有參數(shù)少、流程簡單的特點，同時具有較好的魯棒性和收斂性，應用于很多單目標優(yōu)化、多目標優(yōu)化問題。PSO首先設(shè)定一組初始解(即粒子)，然后根據(jù)粒子位置和速度變化數(shù)學公式，在解空間中移動這些粒子，每個粒子運動受個體及群體位置的影響，在整個粒子群群體中，這些位置是逐步向最優(yōu)解逼近的，當粒子群移動的次數(shù)(即迭代次數(shù))到達一定數(shù)量時，能夠獲得滿足精度要求的解，多數(shù)情況下，通過粒子群獲得的是近似解而非準確解，并且每次計算的結(jié)果也是不一致的[6-7]。

PSO不同的參數(shù)會對優(yōu)化結(jié)果產(chǎn)生非常大的影響，所以科學、合理的參數(shù)是PSO算法優(yōu)化的重要內(nèi)容。PSO是一種元啟發(fā)式算法，通過很少的假設(shè)來進行問題優(yōu)化，同時適用于大范圍的解空間。然而PSO的初始模型在解決簡單模型時能夠獲得理想的結(jié)果，由于基礎(chǔ)粒子群算法步驟較為簡單，當面對離散型等相對復雜的模型時，往往容易陷入局部最優(yōu)解，從而無法得到理想的解結(jié)果。本文從遙感數(shù)據(jù)處理模型的特點出發(fā)，通過參數(shù)動態(tài)更新及粒子群群體分類2種策略，提出了一種基于PSO的改進算法，經(jīng)過實驗分析，該算法較基礎(chǔ)粒子群算法具有明顯優(yōu)勢。

1 相關(guān)工作

1.1 PSO算法基礎(chǔ)

PSO算法是基于群體的，個體根據(jù)對環(huán)境的適應度，結(jié)合群體的適應度，移動到更佳的位置。粒子在解空間中以一定的速度飛行，這個速度取決于其自身飛行經(jīng)驗和群體中同伴的飛行經(jīng)驗來動態(tài)調(diào)整。粒子的飛行決定因素，如圖1所示，速度的計算如公式(1)所示，位置的計算如公式(2)所示。

圖1 粒子位置更新示意圖

Vi+1=ω·Vi+c1·γ1·(PBest-Xi)+c2·

γ2·(GBest-Xi)

(1)

Xi+1=Xi+Vi+1

(2)

其中：ω為速度系數(shù);Vi為當前速度;c1為個體最優(yōu)步長系數(shù)(學習因子);γ1為隨機數(shù)(范圍一般為[0,1]);PBest為個體最優(yōu)位置;Xi為個體當前位置;c2為全局最優(yōu)步長系數(shù)(學習因子);γ2為隨機數(shù)(范圍一般為[0,1]);GBest為全局最優(yōu)位置;Vi+1為粒子新的速度;Xi+1為粒子新的位置。

PBest、GBest通過目標函數(shù)進行判斷，即將粒子的新位置代入目標函數(shù)計算新的目標函數(shù)值。

針對基礎(chǔ)粒子群算法的問題，國內(nèi)外很多學者從收斂速度、增加多樣性、全局方法等方面提出了諸多改進策略，總體可以歸納為慣性權(quán)重法、模糊慣性權(quán)重法、壓縮因子法、選擇法、繁殖法、空間鄰域法、鄰域拓撲法、社會趨同法、序列生境技術(shù)法、函數(shù)延伸法等方法[8-14]。本文提出的參數(shù)動態(tài)更新及粒子群種群分類，是從收斂速度、增加多樣性2個方向?qū)SO算法進行改進。

1.2 PSO算法在遙感中的應用

PSO算法提出后，國內(nèi)外很多學者在其基礎(chǔ)上進行了優(yōu)化，并與其他智能化算法或者遙感數(shù)據(jù)處理算法結(jié)合，將其用于遙感數(shù)據(jù)處理工作。

張兵等[7]在解決混合像元分解問題時，為了解決數(shù)據(jù)噪聲引起的端元提取不準確的情況，引入了PSO，并進行了改進，重新定義了速度和位置的更新策略和表示方法，降低誤差對端元提取的影響，有效提高了結(jié)果精度。煙貫發(fā)等[15]基于改進PSO優(yōu)化LSSVM參數(shù)提出了一種懸浮物的遙感反演方法。為解決傳統(tǒng)SVM分類方法的缺陷，丁勝等[16]基于PSO提出了PSO-BSSVM分類模型，大幅提高了分類精度。AN等[17]提出了一種改進的具有互信息相似性度量PSO模板匹配算法，該方法具有良好的魯棒性，在準確性和效率方面均優(yōu)于標準粒子群算法。WANG等[18]基于PSO和CNN提出了一種新的邊緣檢測方法，與Sobel算子和LOG算子相比，該方法取得了較好的檢測效果，且結(jié)果更完整、準確。在利用PSO進行多光譜遙感影像分類時，為解決PSO容易陷入局部最優(yōu)解的問題，LI等[19]提出了改進算法，該算法具有均衡的利用和探索能力，獲得了更好、更穩(wěn)定的分類結(jié)果。Agrawal[20]基于多目標PSO算法提出了一種最優(yōu)神經(jīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)自適應多光譜衛(wèi)星圖像分類方法，該方法比傳統(tǒng)方法具有更大的優(yōu)越性。

PSO具有簡單易用、可調(diào)參數(shù)少的優(yōu)點，雖然存在易提前收斂、陷入局部最優(yōu)解問題，但是經(jīng)過算法改進，在遙感數(shù)據(jù)處理領(lǐng)域得到了廣泛的應用。自PSO算法提出以來，一直得到研究人員、技術(shù)人員的關(guān)注，隨著人工智能算法、遙感技術(shù)的發(fā)展，經(jīng)過改進的PSO算法的應用將更為廣泛。

2 計算法

2.1 算法流程

為了解決標準PSO算法容易出現(xiàn)局部最優(yōu)解，導致解不穩(wěn)定，難以滿足遙感數(shù)據(jù)分類需要的問題。本文從粒子群群體多樣性及動態(tài)速度更新2個方向?qū)SO算法進行了改進。圖2為本文提出改進方法的算法流程圖。

圖2 算法流程圖

Step1：對粒子種群進行初始化，確定粒子的群體類別，即正常粒子或個體粒子，如正常粒子執(zhí)行Step2，個體粒子執(zhí)行Step5；

Step2：對于正常粒子，按照解空間范圍，對粒子的速度、位置進行隨機初始化；

Step3：基于目標函數(shù)，粒子當前位置計算粒子的適應度值；

Step4：判斷當前適應度值是否是個體最優(yōu)，如是則更新個體最優(yōu)位置、最優(yōu)適應度值，否則不更新；

Step5：對于個體粒子，首先按照解空間范圍，對粒子速度、位置進行隨機初始化，并計算適應度值；

Step6：個體粒子不考慮全局最優(yōu)步長，僅通過個體速度和個體最優(yōu)步長，來尋找新的個體位置，并利用目標函數(shù)計算新的適應度值；

Step7：獲得個體粒子的個體最優(yōu)位置、個體最優(yōu)適應度值；

Step8：基于本輪迭代Step4、Step7的所有粒子的個體最優(yōu)值，更新全局最優(yōu)值；

Step9：根據(jù)迭代條件，判斷迭代是否結(jié)束，如滿足則結(jié)束，否則正常粒子執(zhí)行Step10，個體粒子執(zhí)行Step12；

Step10：對于正常粒子選擇一定比例進行變異，如變異則執(zhí)行Step2，未變異執(zhí)行Step11；

Step11：按照速度、位置計算公式，即公式(1)、公式(2)，基于Step4、Step8的結(jié)果，更新粒子個體速度及位置，執(zhí)行Step3；

Step12：對于個體粒子，判斷當前值是否已經(jīng)滿足極值條件，如滿足則執(zhí)行Step5，否則更新個體速度及位置并執(zhí)行Step6。

2.2 改進策略

基礎(chǔ)粒子群在解決復雜離散型問題時，最容易出現(xiàn)的問題是產(chǎn)生局部最優(yōu)解，以及早熟、提前收斂等問題，避免這些問題最直接的方法是增加粒子的數(shù)量來應對陷入局部最優(yōu)問題，增加迭代次數(shù)來應對解的精度問題。但是這種方法帶來的最大問題是粒子群優(yōu)化算法時間復雜度過高，計算量和計算時長大幅增長。

基礎(chǔ)粒子群算法，在迭代的后期，粒子個體對最優(yōu)解提升的貢獻值越來越低，而且存在多數(shù)粒子工作疊加的情況，這就造成了一些粒子在做無用功。在迭代的后期，粒子數(shù)量對整體問題的性價比越來越低。因此，本文的改進策略包括優(yōu)化迭代后期粒子的作用，此外為了避免陷入局部最優(yōu)，增加粒子群的種群類別，通過不同種群不同分工，將粒子工作的側(cè)重點進行區(qū)分，在不損失解精度的前提下，增加粒子在解空間分布的離散度，從而降低陷入局部最優(yōu)解的風險。

將粒子分為3類，如圖3所示，包括正常種群、個體種群2個大類。正常種群的粒子采用傳統(tǒng)粒子群算法進行速度和位置更新，其中在正常種群中又存在變異粒子。個體種群粒子僅考慮個體因素進行速度和位置更新，個體種群會與全體粒子共享最優(yōu)位置及最優(yōu)解信息。

1—個體粒子;2—正常粒子;3—變異粒子圖3 粒子群種群劃分策略

個體種群粒子數(shù)量占全體粒子數(shù)量比例根據(jù)待解問題的不同，比例設(shè)定在50%～70%范圍內(nèi)，個體粒子僅通過個體速度及個體歷史最優(yōu)位置來更新當前速度和位置，但是需要對全局粒子進行信息輸出，即提供個體最優(yōu)解信息。當個體粒子滿足最優(yōu)解極值判斷條件后，該粒子重新進行隨機初始化，然后根據(jù)新的位置重新尋找個體最優(yōu)解。

變異粒子是正常粒子在迭代過程中的變異，粒子變異后，需要重新初始化，變異粒子根據(jù)新的速度和位置進行正常更新，根本上變異粒子是正常粒子的一種，與正常粒子是可以相互轉(zhuǎn)換的。為了避免一些優(yōu)秀的粒子(比如當前最優(yōu)位置的個體)也參與變異，從而降低求解收斂的速度及損失當前區(qū)域最優(yōu)解空間，曾經(jīng)獲得過全局最優(yōu)解的粒子均不參與變異，一直以正常粒子的身份更新。隨著迭代次數(shù)的增加，變異粒子數(shù)量的比例也會越來越高，這就規(guī)避了上文提到的在迭代后期粒子群的數(shù)量，對于求解性價比不高的問題。

采用粒子群分類策略，會減少正常粒子的數(shù)量，勢必影響解收斂的速度和解的精度，雖然可以通過增加迭代次數(shù)來解決這個問題，但是會相應的增加計算量，從而增加任務(wù)的時間成本。為了解決該問題，提出了時延權(quán)重動態(tài)變化的速度更新策略，該策略不但能夠解決粒子群分類造成的問題，還可在迭代后期減少速度步長，從而提高解的精度。

粒子速度時延權(quán)重公示如公式(3)所示。

(3)

其中：WV為粒子速度的權(quán)重；Ic為當前迭代的次數(shù)；Iall為迭代總次數(shù)；qv為權(quán)重系數(shù)。

從公式(3)可以看出，隨著迭代次數(shù)的增加，粒子速度時延權(quán)重值越來越小，在計算粒子速度時，個體速度的影響力也越來越小，此外個體整體速度也會越來越小，這樣就降低了速度的步長，利于迭代后期解精度的提高。

為了改變不同迭代階段個體最優(yōu)步長及全局最優(yōu)步長對解收斂速度及解精度的影響，本文對基礎(chǔ)粒子群算法中的個體最優(yōu)步長系數(shù)、全局最優(yōu)步長系數(shù)，即公式(1)中的c1、c2，進行了動態(tài)調(diào)整。c2時延權(quán)重計算如公式(4)所示，時延權(quán)重計算如公式(5)所示。

(4)

Wc2=1-Wc1

(5)

改進后，粒子速度的計算如公式(6)所示，即公式(1)的改進。

Vi+1=WV·ω·Vi+Wc1·c1·γ1·(PBest-Xi)+Wc2·c2·γ2·(GBest-Xi)

(6)

3 實驗及結(jié)果分析

基于提出的時延權(quán)重及群體分類PSO改進方法，對遙感數(shù)據(jù)分類進行實驗，經(jīng)實驗結(jié)果分析，取得了較為理想的分類結(jié)果。為了精確驗證算法的改進效果，以嚴格的數(shù)學函數(shù)模型作為目標函數(shù)，來對最優(yōu)解進行量化分析。

目標函數(shù)如公式(7)所示，該函數(shù)存在多個凸凹區(qū)域，容易陷入局部最優(yōu)解，如圖4所示。實驗采用的參數(shù)設(shè)置如表1所示。

f(x,y)=20+x2+y2-10·cos(2·π·x)

-10·cos(2·π·y)

(7)

圖4 目標函數(shù)示意圖

表1 參數(shù)值設(shè)置

將粒子個數(shù)分別設(shè)定為30、60、90個，迭代次數(shù)分別設(shè)定為20、40、60、80次，粒子群體正常粒子的比例為60%，個體粒子的比例為40%，正常粒子的變異比例隨著迭代次數(shù)的增加而提高，如公式(8)所示，qm取值0.7。

(8)

實驗對不同粒子數(shù)量及不同迭代次數(shù)進行了組合，并分別進行了10000次實驗，提出的改進算法與基礎(chǔ)算法進行了對比和分析。表2所示，其中帶有星號(*)的數(shù)字為本次提出方法的結(jié)果。圖5通過100×100像素的圖像展示了不同實驗方案的結(jié)果及趨勢，彩色點為局部最優(yōu)解及解精度大于0.05的情況。

表2 實驗結(jié)果統(tǒng)計

通過表2、圖5可以看出，本文提出的方法相對基礎(chǔ)粒子群算法具有明顯優(yōu)勢，在陷入局部最優(yōu)解的次數(shù)上，明顯少于基礎(chǔ)算法，相應精度上也有所提升。通過表2可以看出，在粒子數(shù)60的情況下，本次改進的優(yōu)勢最為明顯，隨著粒子數(shù)及迭代次數(shù)的增加，算法的優(yōu)勢有所降低，但是相對基礎(chǔ)算法，仍具有明顯優(yōu)勢。對運行效率也進行了統(tǒng)計，本次提出的算法雖然相對基礎(chǔ)算法要復雜，但是運算時間沒有明顯增加，基本可以忽略不計。

圖5 實驗結(jié)果對比及趨勢示意圖

4 結(jié)論

從遙感影像分類需求出發(fā)，選擇PSO算法為計算模型，為了解決基礎(chǔ)PSO算法容易陷入局部最優(yōu)解的情況，提出了一種新的參數(shù)動態(tài)更新及群體分類雙策略改進算法。該算法在遙感影像分類中取得了理想的處理結(jié)果，同時對該算法進行了定量分析，實驗結(jié)果相對基礎(chǔ)PSO算法，優(yōu)勢明顯。該算法通過增加粒子種群分類及粒子變異策略，增加了粒子的多樣性，豐富了不同粒子的分工，不同種群粒子在尋找更高精度解或避免陷入局部最優(yōu)解方面各有側(cè)重，有效降低陷入局部最優(yōu)解的比例。此外，算法引入了時延權(quán)重，改善了迭代計算后期，粒子數(shù)量對目標求解的貢獻逐步降低問題，激發(fā)了粒子活力，進一步降低了局部最優(yōu)解的比例。改進的算法在少量粒子個數(shù)及少量迭代次數(shù)的情況下，能夠取得較為理想的目標解，適用于遙感數(shù)據(jù)處理計算量大的場景，具有較好的推廣價值。