【文章內(nèi)容簡介】 由于 PSO 算清華 大學(xué) 2020 屆畢業(yè)論文 第 14 頁 共 43 頁 法概念簡單，容易實現(xiàn)，在被提出的短短幾年時間內(nèi)，得到了人們的很大關(guān)注，同時也獲得了很大的發(fā)展，并在它的基礎(chǔ)上又出現(xiàn)了很多被改進的粒子群優(yōu)化算法，在多個學(xué)科 和工程領(lǐng)域都得到了應(yīng)用。但由于該算法是在對社會模型模擬的基礎(chǔ)上建立的，所以，在該算法提出的初期并不是以數(shù)學(xué)理論為基礎(chǔ)的，但隨著人們的進一步深入研究， PSO 算法的嚴格數(shù)學(xué)基礎(chǔ)就逐步建立起來了。本章是在先介紹基本粒子群算法的基礎(chǔ)上，又介紹了如何將 PSO 算法應(yīng)用到多目標(biāo)優(yōu)化的領(lǐng)域。 基本粒子群算法概述 PSO 算法是一種基于群體的新興演化算法。設(shè)想有這樣一個場景一群鳥在隨機搜索食物不知道食物放在何處，在整個搜索區(qū)域中只有一塊食物。所有的鳥都不知食物在何處，但它們知道自己當(dāng)前的位置距離食物還 有多遠。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的方法就是在目前離食物最近的鳥的周圍區(qū)域搜尋。 粒子群優(yōu)化算法是在鳥群覓食模型中得到啟示，并成功用于解決優(yōu)化問題的。在該算法中，搜索空間中的每一只鳥被看作是優(yōu)化問題中的每一個解，稱之為“粒子”（ particle）或“主體”（ agent），該粒子能通過超維搜索空間“流動”。每個粒子都有自己的位置和速度，還有一適應(yīng)值被優(yōu)化函數(shù)所決定，能知道到目前為止發(fā)現(xiàn)的最好位置（ pbest）和現(xiàn)在的位置 Xi，可看作單個粒子的經(jīng)驗。每個粒子在搜索空間中的位置變化是以個體的社 會心理意向為基礎(chǔ)的，即每一粒子個體都想成功地超過其他個體。每個粒子的經(jīng)驗或知識影響都會影響其相鄰粒子的變化。另外，到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置（ gbest）也能被每個粒子所知道（ gbest 是在 pbest 中的最優(yōu)值），可看作是單個粒子的同伴經(jīng)驗。每個粒子的當(dāng)前位置由下列信息所決定 : 1．當(dāng)前位置； 2．當(dāng)前速度； 3．當(dāng)前位置與自己最好位置之間的距離； 4．當(dāng)前位置與群體最好位置之間的距離。 作為群優(yōu)化的粒子群算法的粒子群可認為是粒子在 D 維空間 內(nèi)，依照一定的規(guī)律傳遞信息，同時，依據(jù)信息的變化改變自身狀態(tài)，具備自組織行為。 各粒子的個體極值構(gòu)成的矩陣： P=（ p1,p2,? ,pn），是粒子群信息的主要來源。從 P 中可以獲得群體最優(yōu)位置全局極值 P 和各個粒子自身經(jīng)驗最優(yōu)位置個體極值 P 的信清華 大學(xué) 2020 屆畢業(yè)論文 第 15 頁 共 43 頁 息。粒子群就是由群體最優(yōu)位置快速收斂形成的，并能在全局極值的鄰域中進行搜索；個體自身經(jīng)驗最優(yōu)位置能保證粒子不要過快收斂到群最優(yōu)，從而避免陷入局部極小點，這樣能使粒在一次迭代中的搜索區(qū)域在個體極值和全局極值之間。 群體間粒子的合作，使得粒子群算法具有高效的搜索性能 。每個粒子不僅能向群體提供信息還能協(xié)助其它粒子進行搜索，所以粒子在進化過程中，能保證搜索和收斂的平衡。 基本 PSO 算法原理 粒子群優(yōu)化算法 PSO 主要是通過每個粒子當(dāng)前的狀和在飛行過程中所經(jīng)歷過的最好位置，以及整個群體所經(jīng)歷過的最好位置來計算粒子下一步運動的方向和速度 [11]和位置的更新公式如下： ? ? ? ?idgdidididid xprcxprcvwV ?????? 2211 （ ） ? ?DdMivxX ididid ?????? 1,1, （ ） 式（ ）、 ()中： d=1,2,? ,D,D 代表第 d 維搜索空間； i=1,2,? ,m,m 是該群體中粒子總數(shù)； Vid為迭代粒子 i 飛行速度矢量的第 d維分量； Pid為粒子 i 個體最好位置 plest 的第 d維分量； Pgd為群體最好位置 gbest 的第 d維分量； C C2為權(quán)重因子； r r2為隨機數(shù)，產(chǎn)生 [0,1]的隨機數(shù)； W 為慣性權(quán)重函數(shù)。 通過（ ）式可以看出，粒子 i 速度的更新主要由三部分組成： 粒子 i 前一時刻的速度； 粒子 i 當(dāng)前位置與自己最好位置間的距離； 粒子 i 當(dāng)前位置與群體最好位置間的距離。 （ ）式為粒子 i 更新位置的坐標(biāo)。粒子 i 下一步的運動位置由式（ ） ,（ ）共同決定。 搜索時，粒子的位置被最大位置和最小位置限制，如果某粒子在某維的位置超出該維的最大位置或最小位置，則該粒子的位置被限制為該維的最清華 大學(xué) 2020 屆畢業(yè)論文 第 16 頁 共 43 頁 大位置或最小位置。同樣，粒子的速度也被最大速度和最小速度所限制，如果當(dāng)前對粒子的加速度導(dǎo)致它在某維的速度超過該維的最大速度或最小速度，則該粒子該維的速度被限制為該維的最大速度或 最小速度。 公式（ ）的第 1 部分由粒子先前速度的慣性引起；第 2 部分表示粒子本身的思考，即粒子本身的信息對自己下一步行為的影響；第 3 部分表示粒子間的信息共享和相互合作，即群體信息對粒子下一步行為的影響。 基本 PS0 算法流程 粒子群優(yōu)化算法具有編程簡單，易實現(xiàn)的特點，粒子群優(yōu)化算法的流程 [12]如下所示。 開始 隨機初始化粒子位置和粒子速度 計算每個粒子的適應(yīng)度 根據(jù)粒子適應(yīng)度更新粒子的速度與位置 根據(jù)公式（ ）和（ ）更新粒子群的速度與位置 NO 是否達到最大迭代次數(shù) 或滿足最小錯誤標(biāo)準(zhǔn)？ YES 結(jié)束 圖 清華 大學(xué) 2020 屆畢業(yè)論文 第 17 頁 共 43 頁 下面給出其實現(xiàn)的具體步驟： 初始化群體參數(shù)； 以目標(biāo)函數(shù)來評價各粒子的初始適應(yīng)值； 根據(jù)式（ ）、（ ）來更新粒子的位置和速度； 再根據(jù)目標(biāo)函數(shù)重新評價各粒子的適應(yīng)值； 比較每個粒的當(dāng)前適應(yīng)值和個體歷史最好適應(yīng)值，把最優(yōu)的的位置做為其個體歷史最好位置； 比較群體中全部粒子的當(dāng)前適應(yīng)值和全局歷史最好適應(yīng)值，把最優(yōu)的的位置做為群體全局歷史最好位置； 若迭代終止條件滿足，則程序終止，輸出搜索結(jié)果。否則，返回步驟 2繼續(xù)搜索 ,進行新一輪迭代。 基本 PSO 算法參數(shù)分析 基本 PSO 的參數(shù)主要有慣性權(quán)值、加速系數(shù)、粒子個數(shù)和迭代次數(shù) [13]。 慣性權(quán)值 w 對 PSO 能否收斂起重要作用，它使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。 w 值大些有利于全局搜索，收斂速度快，但不利于局部搜索，不易得到精確解； w 值小些有利于局部搜索和得到更為精確的解，但收斂速度慢且有時會陷入局部極值而得不到全局最優(yōu)解 [14]。合適的 w 值在搜索精度和搜索速度、全局搜索和局部搜索方面起協(xié)調(diào)作用。 加速系數(shù) c1,c2 加速系數(shù) c1和 c2對 PSO 能否收斂也起重要作用，若加速系數(shù)合適，則有利于算法較快收斂并脫離局部極值。 式（ ）中，若 c1=c2=0，粒子將依靠慣性一直以當(dāng)前的速度飛行，直到達到邊界為止；此時粒子僅僅依靠慣性飛行，沒法從自己的飛行經(jīng)驗和同伴的飛行經(jīng)驗中吸取有用的信息，算法沒有啟發(fā)性，并且搜索區(qū)域有限，這種情況下要想找到最優(yōu)解比較困難，此時的優(yōu)化性能也很差。 當(dāng) c1=0 時粒子沒有認知能力 ，不能從自己的飛行經(jīng)驗吸取有效信息，只有社會部分，所以 c2 又稱為社會參數(shù)；此時收斂速度比基本 PSO 快，但由于不能有效利用自身飛行信息，對復(fù)雜問題優(yōu)化時則比基本 PSO 容易陷入局部極值，優(yōu)化性能也變差。 清華 大學(xué) 2020 屆畢業(yè)論文 第 18 頁 共 43 頁 若 c2=0，則粒子之間沒有社會信息共享，不能從同伴的飛行經(jīng)驗中吸取有效信息，此時只有認知部分，故 c1 又叫認知參數(shù)；此時個體間沒有互享的信息，這樣粒子群體的運行相當(dāng)與單個粒子的運行，要想得到全局最優(yōu)解，機率非常小。 一般情況下，當(dāng) c1=c2= 時能取得比較好的效果，也有人認為 c1 大些而社 會參數(shù) c2 小些，但 c1+c2≤ 4 時能得到更好的結(jié)果。 粒子數(shù)目 粒子數(shù)目對算法的優(yōu)化性能有影響。一般來說，粒子數(shù)目越多，搜索到全局最優(yōu)解的可能性也越大，優(yōu)化性能相對也越好，但是消耗的計算量也越大，計算性能相對下降；群體規(guī)模越小，搜索到全局最優(yōu)解的可能性就越小，但消耗的計算量也越小。當(dāng)然，對于一般問題，使用過多的粒子數(shù)目沒有必要，但是粒子數(shù)目也不能過少，否則體現(xiàn)不出群智能算法的優(yōu)越性。一般地，粒子數(shù)目為 10～ 200 較為合適。 最大允許迭代次數(shù) 當(dāng)慣性權(quán)值 [15]為固定值和最大允許迭代次數(shù)不相關(guān)聯(lián)時，最大允許迭代次數(shù)大些，找到全局最優(yōu)解的可能性也大些，最大允許迭代次數(shù)小了，找到全局最優(yōu)解的可能性也小。只是對于基本 PSO 來說，一旦陷入了局部極值，如果不采用有效措施，迭代次數(shù)再增多優(yōu)化效果也得不到明顯改善，反而浪費計算資源，實際意義不大。一般來說，如果優(yōu)化時還有其他條件來結(jié)束搜索，可以考慮將最大允許迭代次數(shù)設(shè)置得大些。當(dāng)慣性權(quán)值和最大允許迭代次數(shù)相關(guān)聯(lián)時，即慣性權(quán)值隨著迭代的進行逐漸衰減，此時并不是最大允許迭代次數(shù)越大越好，這時候過大的最大允許 迭代次數(shù)反而會使得算法有很長一段時期以較大的慣性權(quán)值來搜索，如果不對粒子速度進行限制，粒子很可能會飛行到無窮遠處，從而得不到全局最好解。所以，當(dāng)慣性權(quán)值和最大允許迭代次數(shù)相關(guān)聯(lián)時，應(yīng)結(jié)合實際情況合理選擇最大允許迭代次數(shù)。 4 基于粒子群算法的電梯群控系統(tǒng)實現(xiàn) 提高對乘客的服務(wù)質(zhì)量和降低系統(tǒng)運行的總損耗是電梯群控系統(tǒng)的主要目的。本文基于群控系統(tǒng)對乘客平均侯梯時間、乘客平均乘梯時間以及電梯能耗等提出的不同要求，采用粒子群優(yōu)化算法對多目標(biāo)問題進行優(yōu)化，建立了電梯群控的系統(tǒng)的清華 大學(xué) 2020 屆畢業(yè)論文 第 19 頁 共 43 頁 多目標(biāo)優(yōu)化模型，并在此基礎(chǔ)上設(shè) 計了滿足多目標(biāo)要求的電梯群控系統(tǒng)調(diào)度算法 [16]及其應(yīng)用程序。 多目標(biāo)電梯群控系統(tǒng)的數(shù)學(xué)模型 電梯群控系統(tǒng)的主要目標(biāo)是縮短乘客平均候梯時間 AWT 和平均乘梯時間ART，降低電梯運行能耗 RPC。 AWT 為一定時間內(nèi)全部候梯時間的平均值，是評價電梯群控系統(tǒng)性能惡劣的重要指標(biāo)之一，計算公式如下： ? ???? pNi wpiTNAWT 11 ?? Tw為候梯時間。 當(dāng)新的呼梯信號發(fā)生時，根據(jù)呼叫發(fā)生的樓層 Fc及方向 Dc與電梯當(dāng)前所在樓 層 F0和方向 D0，可計算電梯到達新的呼梯信號所需的時間，即候梯時間 [17]。設(shè)電梯運行一層的時間為 K1， ?？恳粚拥臅r間為 K2，電梯需響應(yīng)的停靠任務(wù)為 m，電梯同向到達的最遠樓層為 Fmax，電梯反向到達的最遠樓層為 Fmin。 (1) 當(dāng) Dc與 D0相同，且 Fc在 F0前方時，電梯可同向到達呼梯信號 ? ? 210 KmKFFiT cw ????? ? ? (2) 當(dāng) Dc與 D0相同， 且 Fc在 F0后方時，電梯反向運行再同向到達呼梯信號： ? ? ? ? 21m i nm i nm a x0m a x KmKFFFFFFiT cw ????????? ? ? (3) 當(dāng) Dc與 D0相反時，電梯反向運行后到達呼梯信號： ? ? ? ? 21m a x0m a x KmKFFFFiT cw ??????? ? ? (4) 當(dāng) Dc與 D0相同，且 Fc=F0時， Tw（ i)=0。 ART 為一段時間內(nèi)全部乘客乘梯時間的平均值，一般情況下，很難準(zhǔn)確預(yù)測乘客的