第3章粒子群算法及其MATLAB實(shí)現(xiàn)
粒子群算法,也稱(chēng)粒子群優(yōu)化算法(particleswarmoptimization,PSO),是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法(evolutionaryalgorithm,EA)。
這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視,并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。粒子群算法是一種并行算法。
本章主要講解了粒子群算法的原理及其在MATLAB上的運(yùn)用。
學(xué)習(xí)目標(biāo):
■了解粒子群算法的發(fā)展。
■掌握粒子群算法的基本原理。
■熟悉MATLAB粒子群算法工具箱。
■掌握MATLAB在粒子群算法中的運(yùn)用。
3.1粒子群算法基礎(chǔ)
PSO算法屬于進(jìn)化算法的一種,和模擬退火算法相似,它也是從隨機(jī)解出發(fā),通過(guò)迭代尋找最優(yōu)解,它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì),但它比遺傳算法規(guī)則更為簡(jiǎn)單,它沒(méi)有遺傳算法的“交叉”和“變異”操作,它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。
3.1.1粒子群算法的發(fā)展
1995年美國(guó)電氣工程師Eberhart和社會(huì)心理學(xué)家Kenndy基于鳥(niǎo)群覓食行為提出了粒子群優(yōu)化算法(PSO),簡(jiǎn)稱(chēng)粒子群算法。由于該算法概念簡(jiǎn)明、實(shí)現(xiàn)方便、收斂速度快、參數(shù)設(shè)置少,是一種高效的搜索算法。
PSO是模擬鳥(niǎo)群隨機(jī)搜尋食物的捕食行為。假設(shè)在搜索食物區(qū)域里只有一塊食物,所有的小鳥(niǎo)都不知道食物在什么地方,所以Kenndy等認(rèn)為鳥(niǎo)之間存在著互相交換信息,通過(guò)估計(jì)自身的適應(yīng)度值,它們知道當(dāng)前的位置離食物還有多遠(yuǎn),所以搜索目前離食物最近的鳥(niǎo)的周?chē)鷧^(qū)域是找到食物的最簡(jiǎn)單有效的辦法,通過(guò)鳥(niǎo)之間的集體協(xié)作使群體達(dá)到最優(yōu)。
PSO就是從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。在PSO中每個(gè)優(yōu)化問(wèn)題的潛在解都可以想象成搜索空間中的一只鳥(niǎo),稱(chēng)之為“粒子”。粒子主要追隨當(dāng)前的最優(yōu)粒子在解空間中搜索,PSO初始化為一群隨機(jī)粒子(隨機(jī)解),然后通過(guò)迭代找到最優(yōu)解。
在每一次迭代中,粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己,第一個(gè)就是粒子本身所找到的最優(yōu)解,這個(gè)解稱(chēng)為個(gè)體極值pbest,另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解,這個(gè)極值是全局極值gbest。
這兩個(gè)最優(yōu)變量使得鳥(niǎo)在某種程度上朝著這些方向靠近,此外也可以不用整個(gè)種群而只用其中一部分作為粒子的鄰居,那么所有鄰居的極值就是局部極值,粒子始終跟隨這兩個(gè)極值變更自己的位置和速度,直到找到最優(yōu)解。
到目前為止,粒子群算法的發(fā)展得到越來(lái)越多的眾多領(lǐng)域?qū)W者的關(guān)注和研究,成為解決許多問(wèn)題的熱點(diǎn)算法的研究重點(diǎn)。
其中對(duì)PSO算法的改進(jìn)也非常多,有增強(qiáng)算法自適應(yīng)性的改進(jìn)、增強(qiáng)收斂性的改進(jìn)、增加多種群多樣性的改進(jìn)、增強(qiáng)局部搜索的改進(jìn)、與全局優(yōu)化算法相結(jié)合、與確定性的局部?jī)?yōu)化算法相融合等。
以上所述的是對(duì)于算法改進(jìn)的目的的討論,實(shí)際改進(jìn)中應(yīng)用的方法有基于參數(shù)的改進(jìn),即對(duì)PSO算法的迭代公式的形式上做改進(jìn);還有從粒子的行為模式進(jìn)行改進(jìn),即粒子之間的信息交流方式,如拓?fù)浣Y(jié)構(gòu)的改進(jìn)、全局模式與局部模式相結(jié)合的改進(jìn)等;還有基于算法融合的粒子群算法的改進(jìn),算法融合可以引入其他算法的優(yōu)點(diǎn)來(lái)彌補(bǔ)PSO算法的缺點(diǎn),設(shè)計(jì)出更適合問(wèn)題求解的優(yōu)化算法。
目前,粒子群算法的發(fā)展趨勢(shì)如下。
(1)粒子群優(yōu)化算法的改進(jìn)。粒子群優(yōu)化算法在解決空間函數(shù)的優(yōu)化問(wèn)題和單目標(biāo)優(yōu)化問(wèn)題上應(yīng)用得比較多,如何應(yīng)用于離散空間優(yōu)化問(wèn)題和多目標(biāo)優(yōu)化問(wèn)題將是粒子群優(yōu)化算法的主要研究方向。如何充分結(jié)合其他進(jìn)化類(lèi)算法,發(fā)揮優(yōu)勢(shì),改進(jìn)粒子群優(yōu)化算法的不足也是值得研究的。
(2)粒子群優(yōu)化算法的理論分析。粒子群優(yōu)化算法提出的時(shí)間不長(zhǎng),數(shù)學(xué)分析很不成熟和系統(tǒng),存在許多不完善和未涉及的問(wèn)題,對(duì)算法運(yùn)行行為、收斂性、計(jì)算復(fù)雜性的分析比較少。如何知道參數(shù)的選擇和設(shè)計(jì),如何設(shè)計(jì)適應(yīng)值函數(shù),如何提高算法在解空間搜索的效率算法收斂以及對(duì)算法模型本身的研究都需要在理論上進(jìn)行更深入的研究。這些都是粒子群優(yōu)化算法的研究方向之一。
(3)粒子群算法的生物學(xué)基礎(chǔ)。如何根據(jù)群體進(jìn)行行為完善算法,將群體智能引入算法中,借鑒生物群體進(jìn)化規(guī)則和進(jìn)化的智能性也是學(xué)者關(guān)注的問(wèn)題。
(4)粒子群優(yōu)化算法與其他進(jìn)化類(lèi)算法的比較研究。與其他進(jìn)化算法的融合,如何將其他進(jìn)化算法的優(yōu)點(diǎn)和粒子群優(yōu)化算法相結(jié)合,構(gòu)造出有特色有實(shí)用價(jià)值的混合算法是當(dāng)前算法改進(jìn)的一個(gè)重要方向。
(5)粒子群優(yōu)化算法的應(yīng)用。算法的有效性必須在應(yīng)用中才能體現(xiàn),廣泛地開(kāi)拓粒子群優(yōu)化算法的應(yīng)用領(lǐng)域,也對(duì)深入研究粒子群優(yōu)化算法非常有意義。
3.1.2粒子群算法研究?jī)?nèi)容
粒子群算法是一個(gè)非常簡(jiǎn)單的算法,且能夠有效地優(yōu)化各種函數(shù)。從某種程度上說(shuō),此算法介于遺傳算法和進(jìn)化規(guī)劃之間。
此算法非常依賴(lài)于隨機(jī)的過(guò)程,這也是和進(jìn)化規(guī)劃的相識(shí)之處,算法中朝全局最優(yōu)和局部最優(yōu)靠近的調(diào)整非常類(lèi)似于遺傳算法中的交叉算子。
粒子群算法的主要研究?jī)?nèi)容如下。
(1)尋找全局最優(yōu)點(diǎn)。
(2)有較高的收斂速度。
算法還是用了適應(yīng)值的概念,這是所有進(jìn)化計(jì)算方法所共有的特征。
3.1.3粒子群算法的特點(diǎn)
粒子群算法的本質(zhì)是一種隨機(jī)搜索算法,它是一種新興的智能優(yōu)化技術(shù),是群體智能中一個(gè)新的分支,它也是對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。
該算法能以較大的概率收斂于全局最優(yōu)解。實(shí)踐證明,它適合在動(dòng)態(tài)、多目標(biāo)優(yōu)化環(huán)境中尋優(yōu),與傳統(tǒng)的優(yōu)化算法相比較具有更快的計(jì)算速度和更好的全局搜索能力。
其具體特點(diǎn)如下:
(1)粒子群優(yōu)化算法是基于群體智能理論的優(yōu)化算法,通過(guò)群體中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索。與進(jìn)化算法比較,PSO是一種更為高效的并行搜索算法。
(2)PSO與GA有很多共同之處,兩者都是隨機(jī)初始化種群,使用適應(yīng)值來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣程度和進(jìn)行一定的隨機(jī)搜索。但PSO是根據(jù)自己的速度來(lái)決定搜索,沒(méi)有GA的明顯交叉和變異。與進(jìn)化算法比較,PSO保留了基于種群的全局搜索策略,但是其采用的速度位移模型操作簡(jiǎn)單,避免了復(fù)雜的遺傳操作。
(3)由于每個(gè)粒子在算法結(jié)束時(shí)仍然保持著其個(gè)體極值。因此,若將PSO用于調(diào)度和決策問(wèn)題時(shí)可以給出多種有意義的選擇方案。而基本遺傳算法在結(jié)束時(shí),只能得到最后一代個(gè)體的信息,前面迭代的信息沒(méi)有保留。
(4)PSO特有的記憶使其可以動(dòng)態(tài)地跟蹤當(dāng)前的搜索情況并調(diào)整其搜索策略。
(5)PSO有良好的機(jī)制來(lái)有效地平衡搜索過(guò)程的多樣性和方向性。
(6)在收斂的情況下,由于所有的粒子都向最優(yōu)解的方向飛去,所以粒子趨向同一化(失去了多樣性)使得后期收斂速度明顯變慢,以致算法收斂到一定精度時(shí)無(wú)法繼續(xù)優(yōu)化。因此很多學(xué)者都致力于提高PSO算法的性能。
(7)PSO算法對(duì)種群大小不十分敏感,即種群數(shù)目下降時(shí)性能下降不是很大。
3.1.4粒子群算法的應(yīng)用
粒子群算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架,它不依賴(lài)于問(wèn)題的具體領(lǐng)域,對(duì)問(wèn)題的種類(lèi)有很強(qiáng)的適應(yīng)性,所以廣泛應(yīng)用于很多學(xué)科。粒子群算法的一些主要應(yīng)用領(lǐng)域如下。
(1)約束優(yōu)化。隨著問(wèn)題的增多,約束優(yōu)化問(wèn)題的搜索空間也急劇變換,有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。粒子群算法是解決這類(lèi)問(wèn)題的最佳工具之一。實(shí)踐證明,粒子群算法對(duì)于約束優(yōu)化中的規(guī)劃,離散空間組合問(wèn)題的求解非常有效。
(2)函數(shù)優(yōu)化。是粒子群算法的經(jīng)典應(yīng)用領(lǐng)域,也是對(duì)粒子群算法進(jìn)行性能評(píng)價(jià)的常用算例。
(3)機(jī)器人智能控制。機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人工系統(tǒng),而粒子群算法可用于此類(lèi)機(jī)器人群搜索,如機(jī)器人的控制與協(xié)調(diào),移動(dòng)機(jī)器人路徑規(guī)劃。所以機(jī)器人智能控制理所當(dāng)然地成為粒子群算法的一個(gè)重要應(yīng)用領(lǐng)域。
(4)電力系統(tǒng)領(lǐng)域。在其領(lǐng)域中有種類(lèi)多樣的問(wèn)題,根據(jù)目標(biāo)函數(shù)特性和約束類(lèi)型許多與優(yōu)化相關(guān)的問(wèn)題需要求解。PSO在電力系統(tǒng)方面的應(yīng)用如配電網(wǎng)擴(kuò)展規(guī)劃、檢修計(jì)劃、機(jī)組組合等。隨著粒子群優(yōu)化理論研究的深入,它還將在電力市場(chǎng)競(jìng)價(jià)交易等其他領(lǐng)域發(fā)揮巨大的應(yīng)用潛在力。
(5)工程設(shè)計(jì)問(wèn)題。在許多情況下所建立起來(lái)的數(shù)學(xué)模型難以精確求解,即使經(jīng)過(guò)一些簡(jiǎn)化之后可以進(jìn)行求解,也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。現(xiàn)在粒子群算法已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具,在電路及濾波器設(shè)計(jì)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、控制器設(shè)計(jì)與優(yōu)化、任務(wù)分配等方面粒子群算法都得到了有效的應(yīng)用。
(6)生物醫(yī)學(xué)領(lǐng)域。許多菌體的生長(zhǎng)模型即為非線(xiàn)性模型提出了用粒子群算法解決非線(xiàn)性模型的參數(shù)估計(jì)問(wèn)題。還在分子力場(chǎng)的參數(shù)設(shè)定和蛋白質(zhì)圖形的發(fā)現(xiàn)。根據(jù)粒子群算法提出的自適應(yīng)多峰生物測(cè)定融合算法,提高了解決問(wèn)題的準(zhǔn)確性。在醫(yī)學(xué)方面,如醫(yī)學(xué)成像上得到的推廣應(yīng)用等。
(7)通信領(lǐng)域。包括路由選擇及移動(dòng)通信基站布置優(yōu)化,在順序碼分多址連接方式(DSCDMA)通信系統(tǒng)中使用粒子群算法,可獲得可移植的有力算法并提供并行處理能力。比傳統(tǒng)先前的算法有了顯著的優(yōu)越性,還可以應(yīng)用到天線(xiàn)陣列控制和偏振模色散補(bǔ)償?shù)确矫妗?br />
(8)交通運(yùn)輸領(lǐng)域。在物流配送供應(yīng)領(lǐng)域中要求以最少的車(chē)輛數(shù)、最小的車(chē)輛總行程來(lái)完成貨物的派送任務(wù);在交通控制控制領(lǐng)域,城市交通問(wèn)題是困擾城市發(fā)展、制約城市經(jīng)濟(jì)建設(shè)的重要因素。
3.2基本粒子群算法
PSO算法是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬,具有很好的生物社會(huì)背景而易理解、參數(shù)少而易實(shí)現(xiàn),對(duì)非線(xiàn)性、多峰問(wèn)題均具有較強(qiáng)的全局搜索能力,在科學(xué)研究與工程實(shí)踐中得到了廣泛關(guān)注。同時(shí),PSO是一種很好的優(yōu)化工具。
3.2.1基本原理
PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中,每個(gè)優(yōu)化問(wèn)題的潛在解都是搜索空間中的一只鳥(niǎo),稱(chēng)之為粒子。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適值(fitnessvalue),每個(gè)粒子還有一個(gè)速度決定它們“飛行”的方向和距離。然后粒子就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。
粒子位置的更新方式如圖31所示。
圖31每代粒子位置的更新方式
……