06第六章 粒子群優(yōu)化算法

第六章粒子群優(yōu)化算法習題與答案1.填空題粒子群算法的縮寫是，它模擬了自然界中過程而提出。在粒子群算法中，最關鍵的兩個變量分別是和。粒子群算法的每一次迭代之后，都會得到一個局部最優(yōu)解和局部最優(yōu)解。解釋：本題考查粒子群算法的基礎知識。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：PSO，鳥群覓食，位置，速度個體的，群體的下列關于粒子群優(yōu)化算法PSO說法錯誤的是()。PSO是把優(yōu)化問題的一個解抽象成一個粒子。PSO通過粒子位置和速度更新來產(chǎn)生新解，沒有交叉和變異操作。PSO速度更新中的“社會”部分代表向自身學習。學習因子c和c對算法性能的影響很大。12解釋：本題考查粒子群算法的特點。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：C(1)PSO把優(yōu)化問題的一個解抽象成一個粒子。A選項正確。(2)PSO沒有交叉和變異操作，只是通過粒子位置和速度更新來產(chǎn)生新的粒子，B選項正確。PSO的“認知”部分代表向自身學習，“社會”部分代表向群體學習，C選項錯誤。學習因子C1和C2是兩個關鍵參數(shù)，對算法性能的影響很大，D選項正確。下列關于粒子群優(yōu)化算法參數(shù)說法錯誤的是()。學習因子c和c分別代表向自身學習和向群體學習的權(quán)重。12慣性權(quán)重w設計原則應該隨著進化迭代次數(shù)逐漸變小。學習因子c=0，c>0，算法多樣性不足易陷入局部最優(yōu)。12學習因子c>0，c=0，算法收斂速度變慢。12Vmax越大，算法的探索能力越弱，開發(fā)能力越強。解釋：本題考查PSO參數(shù)的作用。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：EC和C分別為“認知”部分代表向自身學習，以及“社會”部分代表向群12體學習。A選項正確。慣性權(quán)重在進化前期應該更大，從而加強算法的探索能力，維護多樣性；在進化后期應該更小，從而加強算法的開發(fā)能力，加快收斂。B選項正確。(3)學習因子c=0，1c>0，只有“社會”部分，收斂加快，易陷入局部最2優(yōu)，C選項正確。(4)學習因子c>0，1C=0，只有“認知”部分，算法收斂速度變慢，D選2項正確。5)Vmax越大，算法搜索空間越廣，算法的探索能力越強，E選項錯誤。請簡述粒子群優(yōu)化算法的操作流程。解釋：本題考查對粒子群優(yōu)化算法的掌握程度。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：步驟1：對實際問題的解進行編碼。步驟2：根據(jù)實際問題構(gòu)造評價問題可能解優(yōu)劣的適應度函數(shù)f(?)。步驟3：對粒子群進行初始化，確定初始種群的大小、終止條件等參數(shù)。步驟4確定初始種群的p(0)和G(0)。i步驟5：計算每個粒子的適應度，確定p(t)和G(t)。i步驟6：判斷是否滿足終止條件。若滿足，G(t)為最優(yōu)解。否則進行第5步。用粒子群算法求解以下無約束優(yōu)化問題：minf(x)=￡[x2一10cos(2兀x)+10]iii=1式中，初值范圍：[-5.12,5.12]n,n=30,目標最優(yōu)值為100。解釋：本題考查PSO求解連續(xù)函數(shù)優(yōu)化問題的步驟。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：步驟1：初始種群粒子數(shù)N=100,粒子維數(shù)為D=30,最大迭代次數(shù)為T=200,學習因子C=C=1.5，慣性權(quán)重最大值為W=0.8，慣性權(quán)重最小值為TOC\o"1-5"\h\z12maxW=0.4，位置最大值為X=5，位置最小值為X=一5，速度最大值為minmaxminV=1，速度最小值為V=-1。maxmin步驟2：初始種群粒子位置x和速度v，粒子個體最優(yōu)位置p和最優(yōu)值P,best粒子群全局最優(yōu)位置g和最優(yōu)值g。best步驟3：根據(jù)式(6.14)計算動態(tài)慣性權(quán)值w,更新位置x和速度值v,并進行邊界條件處理，判斷是否替換粒子個體最優(yōu)位置p和最優(yōu)值p以及粒子群全best局最優(yōu)位置g和最優(yōu)值g。best步驟4：判斷是否滿足終止條件：若滿足，則結(jié)束搜索過程，輸出優(yōu)化值；若不滿足，則轉(zhuǎn)到步驟3繼續(xù)進行迭代優(yōu)化。說明學習因子的作用以及C、C之間的辯證關系。12解釋：本題考查PSO中參數(shù)的作用。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件答案：在下列的更新粒子狀態(tài)的公式中，C與C稱為學習因子。12V(t-1)+Crand()(P(t-1)-X(t-1))i1ii+Crand()(G(t-1)-X(t-1)),IV(t)l<V2iimax-V,V(t)<-VmaximaxV,V(t)>VmaximaxX(t)=X(t-1)+V(t)iii當C>0,C二0時對應“認知模型”，粒子沒有向群體學習的能力；當12C二0,C>0時對應“社會模型”，粒子沒有向自身學習的能力；當C>0,C>01212時對應“完全模型”，粒子同時具備向群體和自身學習的能力。Kennedy通過大量計算得出結(jié)論：“認知模型”只考慮粒子本身的信息，缺少社會信息的交流和共享，所以收斂速度慢；“社會模型”只考慮群體因素，傾向于向群體學習，收斂速度比較快，但容易早熟。通常C與C的取值范圍在0?4之間，為了平衡群12體因素和個體因素對算法的影響，通過深入研究和大量實驗，普遍認為C二C二2效果較好。127.對于TSP問題，已知X(t-1)二｛1,2,3,4,5｝,V(t-1)二｛(3,5),(1,2)｝,iiP(t-1)二｛3,1,5,2,4｝,G(t-1)=｛1,2,3,5,4｝,?=0.6、0=0.4,試求x(t)二?ii解釋：本題考查PSO算法解決TSP問題時的特殊操作。具體內(nèi)容請參考課堂視頻“第6章粒子群優(yōu)化算法”及其課件。答案：PSO算法在解決TSP問題時，通常采用如下操作公式。V(t)=V(t—l)+a(P(t—1)-X(t—1))+0(G(t—1)-X(t—1))TOC\o"1-5"\h\z2iiiiiX(t)二X(t-1)十V(t)iii其中，?和0是人為設定的［0,1］之間常數(shù)，通常限定范圍d+0=1；a(P(t—1)—X(t-1))表示P(t-1)-X(t-1)的交換子序列｛Q,Q,,Q｝中所有交換子iiii12m以概率a被保留，同理0(G(t-1)-X(t-1))表示G(t-1)-X(t-1)的交換子序列中所ii有交換子以概率0被保留。具體操作是針對每一個交換子產(chǎn)生一個［0,1］之間的隨機數(shù)，比較該隨機數(shù)與a的大小，如果該隨機數(shù)小于等于a則保留該交換子；如果該隨機數(shù)大于a則去掉該交換子。因此，a值越大則P(t-1)-X(t-1)保留的交ii換子就越多；同理，0值越大則G(t-1)-X(t-1)保留的交換子就越多。iP(t-1)-X(t-1)的運算過程如下：首先對于X(t-1)的第1維，運算后應該等iii于P(t-1)的第1維，為此應該進行Q=swap(1,3)交換操作，這樣X(t-1)經(jīng)Q操作i1i1后結(jié)果為｛3,2,1,4,5｝;在｛3,2,1,4,5｝中的第2維要想與p(t-1)的第2維相同，必須i進行Q=swap(2,1)的交換操作，這樣得到的運算結(jié)果為｛3,12,4,5｝；以此類推可知還要進行兩個交換子的操作Q二swap(2,5)、Q=swap(4,2)，最后得到的變換結(jié)果與P(t-1)相同，因此P(t-1)-X(t-1)=｛Q,Q,Q,Q｝=｛(1,3),(21),(2,5),(4,2)｝。同理可iii1234知G(t-1)—X(t-1)=｛(4,5)｝。iV(t)和X(t)的運算過程如下：ii在P(t-1)-X(t-1)=｛Q,Q,Q,Q｝中，對于交換子Q隨機產(chǎn)生一個［0,1］之間的ii12341數(shù)，若該隨機數(shù)等于0.4<a，則Q被保留；對于交換子Q若產(chǎn)生的隨機數(shù)等于120.8>a，則Q被去除；以此類推得到最后結(jié)果為a(P(t-1)—X(t-1))=｛(13),2ii(2,5),(4,2)};G(t-1)-X(t-1)中交換子(4,5)產(chǎn)生的隨機數(shù)若為0.2<0，則0(G(t-1)-iX(t-1))={(4,5)}，那么：iV(t)二V(t-1)+a(P(t-1)-X(t-1))+0(G(t-1)-X(t-1))iiiii二{(3,5),(1,2)H{(1,3),(2,5),(4,2)}+{(4,5)}二{(3,5),(1,2),(1,3),(2,5),(4,2),(4,5)}X(t)=X(t-1)十V(t)表示按照v(t)中交換子的排列順序依次對X(t-1)進行交iiiii換操作，因此最終結(jié)果X((t)={4,3,5,2，1}。8.試為慣性權(quán)重設計一種非