智能優(yōu)化理論-第10章粒子群優(yōu)化算法

第10章粒子群優(yōu)化算法contents目錄粒子群優(yōu)化算法的基本原理基本粒子群優(yōu)化算法改進的PSO算法離散粒子群優(yōu)化算法粒子群優(yōu)化算法應(yīng)用舉例粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題復習思考題粒子群優(yōu)化算法的基本原理01粒子群優(yōu)化算法(PSO)是通過觀察鳥群捕食行為啟發(fā)而來。在搜索空間中，每個優(yōu)化問題的解被視為一只鳥，即“粒子”。初始化一群粒子，每個粒子都是可行解，并由目標函數(shù)評價其適應(yīng)度值。粒子群優(yōu)化算法的基本原理03設(shè)每個優(yōu)化問題的解是搜索空間的一只鳥，把鳥視為空間中的一個沒有重量和體積的理想化的“質(zhì)點”，稱為粒子。01每個粒子都在解空間中運動，并由一個速度決定其飛行方向和距離。02粒子追隨當前的最優(yōu)粒子在解空間中進行搜索，每一次迭代都跟蹤兩個“極值”來更新自己。粒子群優(yōu)化算法的基本原理010203每個粒子都有一個由被優(yōu)化函數(shù)所決定的適應(yīng)度值，還有一個速度決定它們飛行方向和距離。粒子通過追隨當前的最優(yōu)粒子在解空間中搜索最優(yōu)解，需要性能評價和粒子之間進行全局或局部的信息交流。PSO算法通常具有3種基本的信息拓撲結(jié)構(gòu)：環(huán)形拓撲、星形拓撲、分簇拓撲。粒子群優(yōu)化算法的基本原理粒子群優(yōu)化算法的基本原理01在環(huán)形拓撲結(jié)構(gòu)中，任意一個粒子僅與其鄰域中的兩個粒子交流信息。02在星形拓撲結(jié)構(gòu)中，中心粒子與其他所有粒子之間具有雙向信息交流。其他也有諸如小世界的信息拓撲結(jié)構(gòu)等。03粒子群優(yōu)化算法的基本原理不同的信息拓撲結(jié)構(gòu)具有不同的鄰域定義，體現(xiàn)了不同效率的信息共享能力與社會組織協(xié)作機制。它通過鄰域規(guī)模、鄰域算子和鄰域中的迄今最優(yōu)解，影響PSO算法的性能。基本粒子群優(yōu)化算法02基本粒子群優(yōu)化算法在n維連續(xù)搜索空間中，對粒子群中的第i個粒子或個體進行定義。n維位置向量表示該粒子或個體的當前位置；n維最優(yōu)位置向量表示該粒子或個體迄今所獲得的具有最優(yōu)適應(yīng)度值的位置；n維速度向量表示該粒子或個體的搜索方向。PSO算法中的m個粒子一直在并行地進行搜索運動。每個粒子可認為是一個在搜索空間中飛行的智能體。在每次迭代中，該算法記錄下每個粒子的迄今最優(yōu)位置，并相互交流粒子之間的局部信息，進一步獲得整個粒子群或鄰域的迄今最優(yōu)位置。問題歸結(jié)為每個粒子在n維連續(xù)解空間中如何從一個位置運動到下一個位置。而這可通過將簡單地加上得到。群體中所有粒子所經(jīng)歷過的最優(yōu)位置稱為全局最優(yōu)位置。基本粒子群優(yōu)化算法123若令（單位時間），則有以下位置更新公式為這里，對第i個粒子，在計算出后，應(yīng)對其進行評價，即須計算出相應(yīng)的適應(yīng)度值。PSO算法在根據(jù)上式計算之前，須先確定出，而這可由PSO算法中的速度更新公式給出。基本粒子群優(yōu)化算法01基本PSO算法的實現(xiàn)步驟如下02步驟1：初始化。設(shè)定PSO算法中涉及的各類參數(shù)，包括搜索空間的下限Le和上限He，加速度因子和，算法的最大迭代次數(shù)Tmax?；蚴諗烤龋Ｗ铀俣确秶鶾vmin，vmax]。03隨機初始化搜索點的位置xi和速度vi，設(shè)每個粒子的當前位置為pi，從個體找到的最優(yōu)解中找出種群最優(yōu)解，記錄對應(yīng)于最優(yōu)解的粒子的序號g和其位置pg?；玖Ｗ尤簝?yōu)化算法評價每一個粒子。計算每個粒子的適應(yīng)值，如果該適應(yīng)值優(yōu)于該粒子當前的個體最優(yōu)值，則將pi設(shè)置為該粒子的位置，同時更新個體最優(yōu)值。更新粒子狀態(tài)。根據(jù)式對每一個粒子的速度和位置進行更新。如果則將其置為；如果，則將其置為。基本粒子群優(yōu)化算法步驟3步驟2改進的PSO算法03在PSO算法的迭代過程中，速度值有可能變得非常大，導致性能降低。為了控制速度的增加，通?？刹扇蓚€措施：一是通過增加慣性權(quán)重，二是加入收縮系數(shù)。具有慣性權(quán)重的PSO算法通過增加慣性權(quán)重可以增強算法的全局搜索能力，并通過減小慣性權(quán)重提高局部搜索能力。010203具有速度控制的改進型PSO算法具有速度控制的改進型PSO算法選擇一個合適的慣性權(quán)重有助于PSO算法均衡它的探索能力和開發(fā)能力。在迭代過程中，初始時取較大的值，比如0.9-1.2之間的值，以擴大算法的全局搜索能力。隨著迭代的進行呈線性遞減，以加強迭代后期的局部搜索性能，能夠使算法精確得到全局最優(yōu)解。引入慣性權(quán)重可以消除基本PSO算法對vmax的依賴，并平衡全局和局部搜索能力。隨著時間收斂，粒子的振蕩軌跡幅度會隨時間不斷減少。具有速度控制的改進型PSO算法PSO算法的粒子群規(guī)模或粒子數(shù)m的選擇，需要折中求解質(zhì)量與計算量之間。避免PSO算法的早熟，可增加粒子群的規(guī)模，但也會降低搜索速度。將基本PSO算法中的整個粒子群的迄今最優(yōu)解擴展為考慮粒子鄰域的迄今最優(yōu)解。具有鄰域算子的PSO算法鄰域大小實際描述了信息共享或社會相互作用的范圍，也給出了通信的代價。采用全鄰域似乎更好，因其算法性能與基于環(huán)形拓撲結(jié)構(gòu)的PSO算法相差不大。PSO算法有全局版本和局部版本。全局版本每個粒子的鄰域包含所有個體，而局部版本僅包含與該粒子有直接信息連接的部分個體。具有鄰域算子的PSO算法具有鄰域算子的PSO算法010203全局版本PSO算法收斂速度較快，但是容易陷入局部最優(yōu)，而采用不同的鄰域拓撲結(jié)構(gòu)的局部版本PSO算法更容易找到全局最優(yōu)或次優(yōu)解。如果信息在粒子之間傳遞得太快，則很容易使整個系統(tǒng)出現(xiàn)早熟，即粒子很快聚集到一個局部極值點上；反之，如果信息傳遞得太慢，則因為單個粒子很難迅速得到相距較遠的粒子的信息，使得算法的收斂速度變慢，從而影響計算效率。常見的鄰域結(jié)構(gòu)有星形結(jié)構(gòu)、環(huán)形結(jié)構(gòu)、金字塔結(jié)構(gòu)以及馮·諾依曼結(jié)構(gòu)，如圖10.2所示。星形結(jié)構(gòu)以其中一個粒子為中心，與鄰域中的其他所有粒子相聯(lián)系，而其他粒子不進行信息交換。星形結(jié)構(gòu)在環(huán)形結(jié)構(gòu)中所有粒子排成一個環(huán)，該結(jié)構(gòu)中每個粒子與其相鄰的兩個粒子交換信息，從而有效地保證了種群的多樣性。環(huán)形結(jié)構(gòu)具有鄰域算子的PSO算法離散粒子群優(yōu)化算法04PSO算法在求解離散變量優(yōu)化問題上形成了兩條完全不同的技術(shù)路線。一是以經(jīng)典的連續(xù)型PSO算法為基礎(chǔ)，將離散問題空間映射到連續(xù)粒子運動空間，并適當修改PSO算法來求解。二是針對離散優(yōu)化問題，以PSO算法信息更新的本質(zhì)機理為基礎(chǔ)，重新定義特有的粒子群離散表示方式與操作算子來求解。在計算上，以離散空間特有的、對向量的位操作來取代傳統(tǒng)向量計算；從信息流動機制上看，仍保留了PSO算法特有的信息交換和流動機制。區(qū)別在于前者將實際離散問題映射到粒子連續(xù)運動空間后，在連續(xù)空間中計算和求解；后者則是將PSO算法映射到離散空間，在離散空間中計算和求解。0102030405PSO算法的離散化方法現(xiàn)有文獻對基于連續(xù)空間的DPSO算法的研究居多，形成了針對0-1規(guī)劃問題的二進制PSO算法（BinaryPSO，BPSO），并建立了不同于傳統(tǒng)PSO算法的新計算模式。針對排序組合優(yōu)化問題，在傳統(tǒng)PSO算法上增加一些離散化策略是當前研究常采用的方法。在BPSO算法中，粒子位置的每一維被限制為1或者0，而對速度則不作這種限制。使用速度更新位置時，值越大，粒子的位置越有可能選1，值越小則越接近0?；谶B續(xù)空間的DPSO算法速度更新公式在形式上保持不變，即其中定義在二進制問題空間中的第i個粒子的第j位(bit)以及相應(yīng)的、取值為1或0。每個粒子均對應(yīng)一個長度為n的二進制串，如同遺傳算法一樣，它表示了問題的一個解。粒子的當前速度分量被定義為二進制位取值為1或0的概率，因此必須將概率限制在[0，1]之間?；谶B續(xù)空間的DPSO算法BPSO算法的粒子狀態(tài)更新公式為：式中，Sigmoid函數(shù)可以保證向量的每個分量都在區(qū)間[0，1]內(nèi)；rand()為滿足[0，1]之間均勻分布的隨機數(shù)。試驗結(jié)果表明，對于大多數(shù)測試函數(shù)，BPSO算法都比遺傳算法速度快，尤其是在問題的維數(shù)增加時。為此，該算法引入了Sigmoid函數(shù)進行變換?；谶B續(xù)空間的DPSO算法用基于連續(xù)空間的DPSO算法求解離散問題時，算法生成的連續(xù)解與整數(shù)規(guī)劃問題的目標函數(shù)評價值之間存在多對一的映射。因此該目標函數(shù)不能完全反映PSO算法中連續(xù)解的質(zhì)量。BPSO算法并不直接優(yōu)化二進制變量本身，而是通過優(yōu)化連續(xù)變化的二進制變量為1的概率，達到間接優(yōu)化離散變量的目的?；谶B續(xù)空間的DPSO算法基于連續(xù)空間的DPSO算法整數(shù)規(guī)劃問題的連續(xù)化導致大量冗余解空間與冗余搜索，從而影響了算法的收斂速度。由于連續(xù)空間里的向量計算十分簡單，消耗時間短，因此基于連續(xù)空間的DPSO算法仍能保持較快的運算速度。目前關(guān)于基于離散空間的DPSO算法的研究還比較少。研究者們往往根據(jù)具體問題構(gòu)建相應(yīng)的粒子表達方式，并通過重新定義粒子優(yōu)化算法中的加減法和乘法運算規(guī)則來求解。Clerc針對旅行商問題提出的TSP-DPSO算法和Farzaneh針對0-1規(guī)劃問題提出的離散二進制PSO算法（記為B-PSO）。010203基于離散空間的DPSO算法Clerc重新定義了PSO算法中的“加減法”操作和“乘法”操作，實現(xiàn)了PSO算法向離散空間的映射。重新定義后的粒子狀態(tài)更新公式為：，其中，表示粒子的位置和速度，表示因子和為隨機生成的與位置同維度的向量，向量間的“加減法”定義為對二進制位的“異或”操作，記為，向量間“乘法”定義為對二進制位的“與”操作，記為。基于離散空間的DPSO算法基于離散空間的DPSO算法030201B-PSO算法借鑒免疫機制以避免算法陷入局部最優(yōu)，從其試驗結(jié)果來看，B-PSO算法的效率高于BPSO算法和遺傳算法。B-PSO算法中的粒子速度是與位置同維的二進制向量，粒子的更新計算在離散空間中進行，這與連續(xù)空間的BPSO算法完全不同?；陔x散空間的DPSO算法采用了位操作，雖可能增加單步計算代價，但不存在冗余搜索問題，且對離散問題表達自然，易與其他進化算法結(jié)合。混合PSO算法將PSO算法的基本思想與各種進化計算方法相結(jié)合，發(fā)展各種混合PSO算法，已成為目前的研究熱點之一。PSO算法的最大優(yōu)點是實現(xiàn)簡單，全局搜索能力強，應(yīng)用廣泛。在PSO算法的粒子群中引入遺傳算法中的自然選擇原理，又如與人工免疫算法結(jié)合的免疫PSO算法等。還有與量子計算、混沌方法、耗散結(jié)構(gòu)等相結(jié)合的方法，也層出不窮?；陔x散空間的DPSO算法粒子群優(yōu)化算法應(yīng)用舉例05010405060302Schwefel函數(shù)的全局最大值為，當n=2時，取得該值。利用PSO算法計算Schwefel函數(shù)的近似全局最優(yōu)解。參數(shù)選擇：粒子個數(shù)n=40，學習率=，慣性權(quán)重的初始值為1.0，隨迭代次數(shù)線性遞減。搜索過程如圖10.4所示。平均適應(yīng)度值曲線如圖10.5所示。搜索結(jié)果如表10.1所示。粒子群優(yōu)化算法應(yīng)用舉例粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題06010203以社會交互為基礎(chǔ)的群體智能具有巨大的價值創(chuàng)造能力，特別是在復雜問題的優(yōu)化領(lǐng)域。粒子群優(yōu)化算法應(yīng)用的優(yōu)勢主要體現(xiàn)在非導數(shù)型優(yōu)化、魯棒性、協(xié)作行為和靈活性方面。該算法不需要依賴于目標函數(shù)的導數(shù)信息，而是通過個體之間的社會交互機制尋找最優(yōu)解。粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題粒子群優(yōu)化算法的應(yīng)用優(yōu)勢與存在的主要問題搜索過程陷入局部最優(yōu)值的可能性大大降低，并且基于群體的PSO算法更不容易受到個體失誤的影響。02粒子群優(yōu)化算法最大的優(yōu)勢是它可以工作于動態(tài)環(huán)境中，并且對于GbestPSO算法，粒子最終收斂于全局最佳與個體最佳位置連線上的一點。03增加慣性的權(quán)重，將會增加粒子的速度而導致更多的全局搜索和更少的局部搜索，反之亦然。01調(diào)整適當?shù)膽T性權(quán)值并不是一個簡單的任務(wù)，它與問題相關(guān)。粒子群優(yōu)化算法還缺少堅實的數(shù)學分析基礎(chǔ)，尤其缺少算法收斂條件和參數(shù)調(diào)