PSO求解約束優(yōu)化問題

1、2021-11-6co-pso1pso求解約束優(yōu)化問題求解約束優(yōu)化問題1）約束優(yōu)化問題(constrained optimization， co) 2）cpso3) 函數(shù)擴展技術(shù)2021-11-6co-pso2構(gòu)造算法構(gòu)造算法為了簡化co問題的尋優(yōu)過程，通常可采用如下的思路去構(gòu)造算法：將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題、將非線性規(guī)劃問題轉(zhuǎn)化為線性規(guī)劃問題、將復(fù)雜問題轉(zhuǎn)化為簡單問題。 2021-11-6co-pso3約束優(yōu)化問題描述約束優(yōu)化問題描述2021-11-6co-pso4約束優(yōu)化問題的求解難點約束優(yōu)化問題的求解難點(1) 優(yōu)化曲面的復(fù)雜性。復(fù)雜的優(yōu)化曲面對約束優(yōu)化帶來的求解難點類似于無約

2、束優(yōu)化問題， (2) 不可行域的存在性。約束的存在，導(dǎo)致決策 變量的搜索空間產(chǎn)生了不可行域。 (3) 滿足約束與優(yōu)化目標的不平衡。2021-11-6co-pso5求解約束極值問題的傳統(tǒng)方法求解約束極值問題的傳統(tǒng)方法可行方向法（feasible direction）、梯度投影法(gradient projection method)、約束集法(active set method)、罰函數(shù)法（penalty function method)等等。這些方法各有不同的適用范圍及局限性，其中大多數(shù)方法需要借助問題的梯度信息，要求目標函數(shù)或約束條件連續(xù)可微，并且常常為滿足嚴格的可行性要求而付出很大的計算代

3、價。2021-11-6co-pso6約束優(yōu)化問題的求解思路約束優(yōu)化問題的求解思路2021-11-6co-pso72.智能約束處理技術(shù)智能約束處理技術(shù)1)無約束化處理 罰函數(shù)法是最常用的約束處理技術(shù)，其基本思想是通過序列無約束最小化技術(shù)（sequential unconstrained minimization technique， sumt），將約束優(yōu)化問題轉(zhuǎn)化為一系列無約束優(yōu)化問題進行求解，其原理簡單，實現(xiàn)方便，對問題本身沒有苛刻要求。2021-11-6co-pso8罰函數(shù)法罰函數(shù)法罰函數(shù)法就是將目標函數(shù)和約束同時綜合為一個罰函數(shù)，典型的罰函數(shù)如下:2021-11-6co-pso9g(x),

4、h(x)常用形式常用形式如何合理設(shè)置罰因子，是利用罰函數(shù)法求解約束優(yōu)化問題的一個瓶頸，也是約束優(yōu)化領(lǐng)域的關(guān)鍵問題。2021-11-6co-pso10定常罰函數(shù)法定常罰函數(shù)法該類方法將罰因子在整個算法流程中設(shè)置為定值，但算法通常因數(shù)值的單一性而效果不佳。分層罰因子法，采用如下罰函數(shù)：2021-11-6co-pso112.動態(tài)罰函數(shù)法動態(tài)罰函數(shù)法在動態(tài)罰函數(shù)法中,罰因子的數(shù)值是時變的，通常隨進化代數(shù)增大而增大。理由：在進化初期采用較小的罰因子，算法將有可能對不可行域進行一定程度的搜索；而進化后期采用較大的罰因子，將使算法的搜索集中在可行域，尋找目標更優(yōu)的可行解。動態(tài)罰函數(shù)2021-11-6co-p

5、so123.退火罰函數(shù)法退火罰函數(shù)法一種基于模擬退火策略的罰函數(shù)法，罰因子每隔一定的進化代數(shù)就隨溫度的減小而增大，到算法后期罰因子則因溫度很低而變得很大。該技術(shù)可認為是一種特殊的動態(tài)罰函數(shù)方法，但可通過控制溫度來調(diào)整罰因子。其中，表示溫度，vi(x)為各約束違反量的函數(shù)。2021-11-6co-pso134.適應(yīng)性罰函數(shù)法適應(yīng)性罰函數(shù)法 適應(yīng)性罰函數(shù)法，把搜索過程中獲得的信息作為反饋，來指導(dǎo)罰因子的調(diào)整。2021-11-6co-pso14非固定多段映射罰函數(shù)法 l通常，所構(gòu)造的廣義目標函數(shù)具有如下形式： 其中f(x)代表原目標函數(shù)；h(k)h(x)稱為懲罰項，h(x)表示懲罰力度, h(k)為

6、懲罰因子。如果在求解co問題的整個過程中固定不變，則稱之為固定罰函數(shù)法（stationary pfm，spfm）；相反則稱之為非固定罰函數(shù)法（non-stationary pfm nspfm）。通常nspfm對co問題的求解結(jié)果總是要優(yōu)于spfm。 2021-11-6co-pso15動態(tài)調(diào)整l其中其中h(k)可以被動態(tài)調(diào)整，可以被動態(tài)調(diào)整，h(x)具體定義如下具體定義如下2021-11-6co-pso164.2.2基于排序的方法基于排序的方法基于排序的約束處理技術(shù)不再進行無約束化處理，而是通過綜合考慮目標函數(shù)值和約束違反的程度來對不同候選解進行比較。 1）隨機排序法2）改進的隨機排序法3）基于

7、可行性規(guī)則的方法2021-11-6co-pso174. 2. 3基于多目標的方法基于多目標的方法多目標優(yōu)化問題通常可描述如下: 對于問題的兩個可行解x1和x2，若下式滿足，則稱解x1支配解x2，記作x1x22021-11-6co-pso18pareto最優(yōu)解最優(yōu)解 給定一個可行解x，若s中不存在支配x的解，則稱x為pareto最優(yōu)解或非支配解(non-dominated solution)或非劣解。所有pareto最優(yōu)解構(gòu)成目標空間的pareto前沿(pareto front) 。2021-11-6co-pso19目標函數(shù)和約束函數(shù)當(dāng)作并列的目標函數(shù)和約束函數(shù)當(dāng)作并列的多個目標多個目標基于多目

8、標的約束處理技術(shù)就是把目標函數(shù)和約束函數(shù)當(dāng)作并列的多個目標來處理。譬如，第4. 1節(jié)描述的約束優(yōu)化問題，可轉(zhuǎn)化為式(4-15）描述的多目標優(yōu)化問題或式(4-16)描述的雙目標優(yōu)化問題。通過采用非支配解的概念來比較解，可使搜索向pare-to前沿方向前進，其中非支配解集中第一個目標函數(shù)值最小且其余目標值均等于0的解就是原約束優(yōu)化問題 的最優(yōu)解。2021-11-6co-pso202.基于支配的選擇技術(shù)基于支配的選擇技術(shù) 一種基于支配的約束處理規(guī)則:(1)可行解總優(yōu)于不可行解;(2)若兩個解均可行，則目標值好的解為優(yōu);(3)若兩個解均不可行且其中一個解為非支配解而另一個解為受支配解，則非支配解為優(yōu);

9、(4)若兩個解均不可行且它們同為非支配解或受支配解，則約束違反量小的解為優(yōu)。2021-11-6co-pso21基于協(xié)進化基于協(xié)進化pso算法的約束優(yōu)化算法的約束優(yōu)化 罰函數(shù)法求解約束優(yōu)化問題的性能取決于兩個關(guān)鍵環(huán)節(jié):(1)罰函數(shù)形式的設(shè)計。罰函數(shù)要綜合考慮約束和目標兩個方面，因此設(shè)計罰函數(shù)時應(yīng)該考慮挖掘不可行解違反約束的信息，設(shè)計有效的約束違反函數(shù)，合理體現(xiàn)可行解與不可行解在綜合評價上的差異。(2）罰因子的選取。罰因子直接平衡約束違反量和目標間的平衡。2021-11-6co-pso22一種基于協(xié)進化模型的微粒群優(yōu)化一種基于協(xié)進化模型的微粒群優(yōu)化設(shè)計思路歸納為，在設(shè)計罰函數(shù)方面，不但考慮不可行解

10、違反約束的總量，而且還利用各不可行解違反約束的個數(shù)這一信息;在罰因子選擇方面，基于協(xié)進化模型，把罰因子也作為尋優(yōu)變量，在搜索過程中利用pso算法自適應(yīng)地進行調(diào)整，使算法最終不僅獲得約束優(yōu)化問題的優(yōu)良解，同時還獲得適合于問題的最佳罰因子。2021-11-6co-pso234. 3 .2 協(xié)進化模型協(xié)進化模型l 協(xié)進化的原理可解釋為，算法采用多個種群，或者將一個種群分為多個部分，各種群在各自獨立進化的同時相互間共享和交互信息，各種群不僅利用從外界獲得的信息來指導(dǎo)自身的搜索，同時還把探索得到的經(jīng)驗與其他種群分享，從而使整個系統(tǒng)協(xié)同進化，直至獲得最優(yōu)解。l本節(jié)的cpso算法采用如圖4. 7所示的協(xié)進化

11、模型。2021-11-6co-pso24協(xié)進化模型示意圖（圖協(xié)進化模型示意圖（圖4.7）2021-11-6co-pso25cpso算法包含兩類種群算法包含兩類種群l一類種群包含m2個子種群swarm1,j(j=1, , m2，子種群規(guī)模均為m1，種群中的每個微粒ai(i=l,k)則表示問題的一個決策解，該類種群用于進化決策解; ，l另一個規(guī)模為m2的種群swarm 2，其每個微粒bjj=1,.,m2)代表一組罰因子。用于計算swarm1 , j中各微粒的罰函數(shù)值(或稱適配值)。2021-11-6co-pso26協(xié)進化的每代進化過程協(xié)進化的每代進化過程swarm1 , j中的每個微粒利用b，表示

12、的罰因子計算適配值，并連續(xù)采用pso算法進化g、代獲得一個新的解的種群swarm1 ,j;然后，根據(jù)swarm1 , j中所有解的優(yōu)劣信息，評價swarm 2中微粒bj的優(yōu)劣，即評價罰因子;當(dāng)swarm 2中所有微粒b，均得到評價后，swarm 2采用pso算法進化一代，從而獲得新的種群swarm 2，即得到m:組新的罰因子。在一代協(xié)進化結(jié)束后swarm1,j(j=1.2,m2)再分別用新的m2組罰因子進行評價，以此類推，直到滿足算法終止準則，例如達到給定的最大協(xié)進化代數(shù)g2。算法通過比較所有swarm1,j得到的歷史最好解，將最優(yōu)者作為最終解輸出，同時算法輸出終止時swarm 2中的最優(yōu)微粒

13、。即最佳罰因子。2021-11-6co-pso27cpso小結(jié)小結(jié)協(xié)進化就是兩類種群的交互進化工程，第一類種群swarm1 ,j用pso算法來進化解向量，第二類種群swarm 2 用pso算法來調(diào)整罰因子。通過協(xié)進化模型下的pso算法，不但算法在解空間進化探索決策解，而且在罰因子空間進化探索罰因子，最終同時獲得最優(yōu)決策解和一組合適的罰因子。2021-11-6co-pso28cpso算法設(shè)計算法設(shè)計1. swarm1 , j的評價函數(shù)罰函數(shù)既是違反約束數(shù)量的函數(shù)，又是違反約束程度的函數(shù)，則其效果要比罰函數(shù)僅為約束數(shù)量的函數(shù)的情況好。基此，采用如下適配值函數(shù)評價swarm1,j中第i個微粒其中，f

14、(x)表示第i個微粒的目標值，sum_viol表示該微粒違反約束的總量，num_ viol表示該微粒違反約束的個數(shù)，w1,w2是由swarm 2中微粒bj對應(yīng)的罰因子。2021-11-6co-pso29sum_ viol按如下公式計算2021-11-6co-pso302. swarm 2的評價函數(shù)的評價函數(shù)swarm 2的每一個微粒b，均代表一組罰因子，即w1和w2。當(dāng)swarm1 ,j進化g1代后，swarm 2的第j個微粒b，采用如下方法進行評價。 (1)若swarm 1 , j中至少有一個可行解，則稱b，為一個有效(valid)微粒，并按下式評價b,2021-11-6co-pso31(2

15、)若swarm1 ,j中沒有可行解(可認為懲罰項太小了)，則稱b，為一個無效( invalid)微粒，并采用下式評價b;2021-11-6co-pso32（3） swarml , j和和swarm 2的進的進化方程化方程l兩類種群中的微粒均采用標準pso算法進行進化。特別地，lswarm 2里的每個微粒表示一組罰因子，即w1和w2, lswarml , j里的每個微粒表示一個決策解向量。2021-11-6co-pso33（4）cpso算法框架算法框架2021-11-6co-pso344. 3 .4 數(shù)值仿真與分析數(shù)值仿真與分析l對于每個測試問題，cpso算法采用如下統(tǒng)一的一組參數(shù)。m1=50,

16、m2 =20,g125,g2 =8,慣性因子ldw法，0.9-0.2, 加速因子c1=c2=2。l另外，swarm1, j中微粒位置的最大值和最小值(即x1,max和x1,min對應(yīng)于各問題變量的取值上下界，swarm 2中微粒位置的最大值和最小值(即x2, max和x2.min設(shè)置為w1max= w2.max=1000. w1min= w2.min=0。l第一個例子的可行域相對較小，算法單獨將罰因子的上下界設(shè)置為w1maxw2max=10000,w1min= w2min =5000。兩類種群中微粒速度的上下界設(shè)置2021-11-6co-pso35該問題來自文獻23 ，焊接條結(jié)構(gòu)如圖4. 9所

17、示。優(yōu)化目標是尋求滿足切應(yīng)力、彎曲應(yīng)力、桿條彎曲載荷pc、末端偏差和邊界條件等約束的4個設(shè)計變量h(x1)、l(x2:) ,c(x2)和b(x4)，使得制造焊接條所需的總費用最小。2021-11-6co-pso362021-11-6co-pso37該設(shè)計問題的數(shù)學(xué)模型描述如下該設(shè)計問題的數(shù)學(xué)模型描述如下:2021-11-6co-pso38其中其中2021-11-6co-pso3924-ga傳統(tǒng)罰函數(shù)傳統(tǒng)罰函數(shù), 25幾何規(guī)劃法幾何規(guī)劃法26基于協(xié)進化模型的基于協(xié)進化模型的ga, 12基于支配選擇機制的基于支配選擇機制的ga2021-11-6co-pso402021-11-6co-pso412.

18、對伸縮繩設(shè)計問題的求解結(jié)果對伸縮繩設(shè)計問題的求解結(jié)果l該問題來自文獻27，伸縮繩結(jié)構(gòu)如圖4. 10所示。優(yōu)化目標是尋求滿足對最小偏差、切應(yīng)力、湍振頻率等一系列約束條件的3個決策變量，即平均卷直徑d(x1 )、線直徑d(x2)和活動卷的數(shù)量p(x3)。使得伸縮繩的重量最小。2021-11-6co-pso42該設(shè)計問題的數(shù)學(xué)模型描述如下該設(shè)計問題的數(shù)學(xué)模型描述如下2021-11-6co-pso432021-11-6co-pso442021-11-6co-pso453.對壓力管設(shè)計問題的求解結(jié)果對壓力管設(shè)計問題的求解結(jié)果l該問題來自文獻29，壓力管結(jié)構(gòu)如圖4. 11所示。優(yōu)化目標是尋求滿足一系列約束

19、條件的4個設(shè)計變量ts(x1，圓柱形管子的厚度)、th(x2，半球形蓋子的厚度)、r(x3，圓柱形管子的內(nèi)徑)和l(x4，圓柱形管子的長度，不包括兩端的蓋子)，使得包括材料、焊接、鑄造等費用在內(nèi)的總費用最少。其中，ts和th均為0. 0625英寸的整數(shù)倍，r和l是連續(xù)變量。l在用cpso算法求解時，ts和th均在實數(shù)空間搜索，只在求解目標函數(shù)值時才近似處理為0. 0625的整數(shù)倍。2021-11-6co-pso462021-11-6co-pso47該問題的數(shù)學(xué)模型描述如下該問題的數(shù)學(xué)模型描述如下2021-11-6co-pso48l cpso算法與如下算法進行比較，包括遺傳自適應(yīng)搜索法30、擴張

20、拉格朗日乘子法29、分支定界法31、基于協(xié)進化模型的ga26、基于支配選擇機制的ga12。表4. 6列出了各種算法求得的最優(yōu)解，表4. 7則給出了統(tǒng)計結(jié)果。2021-11-6co-pso492021-11-6co-pso502021-11-6co-pso514）對標準測試問題的求解結(jié)果）對標準測試問題的求解結(jié)果l13個不同類型的函數(shù)約束優(yōu)化問題，作為標準問題常用于測試各種約束處理技術(shù)的性能和效率。下面，用其中的g04,g08, g09,g11和g12問題進一步檢驗cpsu算法的有效性和魯棒性。lcpso算法對每個測試函數(shù)均獨立運行30次，表4. 8、表4. 9和表4. 10給出了cpso算法所

21、得的最優(yōu)解、平均解和最差解以及學(xué)術(shù)界最具代表性的幾種約束優(yōu)化算法的結(jié)果，包括共形映射法hm2 ,隨機排序法sr3 , smes22, aschea10 , 2021-11-6co-pso522021-11-6co-pso532021-11-6co-pso542021-11-6co-pso55討論討論l其余8個標準問題測試時發(fā)現(xiàn)cpso算法的性能不是太理想，尤其在求解高維問題(g02,20維)時求解結(jié)果與理論最優(yōu)解相差較大，l在求解可行域很小(go1,gos, g07, g13,p值幾乎為0)的問題時經(jīng)常找不到可行解。這說明單一的cpso算法在尋優(yōu)性能上還有待改進，尤其對于強約束優(yōu)化問題。與其他

22、約束處理技術(shù)(如文獻10中的特殊等式約束處理技術(shù))相結(jié)合，有望進一步提高算法性能。2021-11-6co-pso565）算法性能分析與參數(shù)設(shè)置）算法性能分析與參數(shù)設(shè)置l針對三個工程設(shè)計問題，首先考察算法首次獲得最終最優(yōu)解的代數(shù)，即在實驗過程中對第一類種群中所有swarm1 , j的最優(yōu)解進行逐代跟蹤，lcpso算法30次獨立運行的統(tǒng)計結(jié)果如表4. 11所示。由表可見，cpso算法對于三個工程設(shè)計問題能夠快速尋找到最優(yōu)解。2021-11-6co-pso572021-11-6co-pso582021-11-6co-pso592021-11-6co-pso602021-11-6co-pso61l綜合

23、考慮算法搜索質(zhì)量和計算效率，對于5維以內(nèi)的問題，建議m1的取值選擇在50-70之間。l 另外，swarm 2的目的是找到合適的罰因子，由于不是直接在決策解空間進行搜索，因此其種群規(guī)模m2過大并不能給算法性能帶來明顯的提高。考慮到swarm 2中每個微粒為2維向量，遵循pso參數(shù)選擇的原則，m2取20比較合適。l此外，在實驗過程中還發(fā)現(xiàn)g2的增大并不能對搜索的性能有很大改善，因此在cpso算法中，建議g2取值在10左右。2021-11-6co-pso624. 3. 5 cpso算法的改進算法的改進1）改進措施措施1 約束違反量的歸一化處理 為了消除不同約束間尺度上的差別，在計算、sum_viol

24、時按下式對每個約束的違反量進行了歸一化處理經(jīng)這種處理后，不同約束的違反量都被限制在0到1之間。2021-11-6co-pso63措施措施ii 使目標函數(shù)和約束違反量處于同一尺度使目標函數(shù)和約束違反量處于同一尺度引入一個尺度因子，考慮目標與約束違反量之間的平衡，即2021-11-6co-pso64 措施措施lii 用優(yōu)良解替代種群中的個體用優(yōu)良解替代種群中的個體對于可行域很小的問題，僅僅依靠pso 算法對微粒的速度和位置進行更新，往往無法搜索到可行解，還甚至?xí)蝻w行速度過大而使搜索過程中找到的可行微粒丟失。為了盡可能利用可行解，在每代進化過程中可以將搜索到的優(yōu)良解(通常是可行解)替換種群中隨機選

25、取的部分微粒，譬如用當(dāng)前找到的最優(yōu)解替換各swarm1, j種群中隨機選取的10%的個體。盡管可能失去一定的種群多樣性，但可加快進人可行域和找到最優(yōu)解的速度。2021-11-6co-pso652）數(shù)值仿真及分析）數(shù)值仿真及分析2021-11-6co-pso662021-11-6co-pso672021-11-6co-pso68函數(shù)“stretching”技術(shù)函數(shù)“stretching”技術(shù)，用于幫助提高優(yōu)化算法的搜索效率及全局收斂能力.。l函數(shù)“stretching”技術(shù)的實質(zhì)是借助于問題的局部極值點信息，對原始目標函數(shù)進行一種“拉伸”變換，其目的是在優(yōu)化算法的實施過程中，不斷縮小目標函數(shù)的極

26、值范圍，從而降低優(yōu)化問題的搜索難度。具體的變換定義如下： 2021-11-6co-pso69l上述兩種變換式中，x是目標函數(shù)的局部極值點，符合定義式（8.2）；1、2和是三個任意的正數(shù)常量；lsign ()為常見的符號函數(shù)：l也可采用人工神經(jīng)網(wǎng)絡(luò)中常用的線性激勵函數(shù)sigmoid函數(shù)來近似計算2021-11-6co-pso70做法做法1）首先要通過優(yōu)化算法按照常規(guī)的方法對其局部極值點進行搜索。2）當(dāng)算法探測到某一局部極值點之后，再通過8.4與8.5式，對目標函數(shù)進行兩次變換。在整個變換過程中，函數(shù)的解空間根據(jù)已搜索到的局部極值信息，被劃分為兩部分來考慮。一部分為區(qū)域: s1=x | f(x)f

27、(x)2021-11-6co-pso71分析8.4與8.5式可知，區(qū)域s1在整個變換過程中，始終保持原始目標函數(shù)的形態(tài)特征不變，即對于任意xs1，均有g(shù)(x)=f(x)=h(x)，同樣原始目標函數(shù)在區(qū)域中的極值點（包括全局極小點在內(nèi)）也始終保留不變。區(qū)域s2則不同，在兩次變換中，目標函數(shù)經(jīng)歷了不同程度的拉伸。實施8.4式變換后，目標函數(shù)由f(x)變換為g(x)，1( )( )2g xf xxx2021-11-6co-pso72相當(dāng)于原始目標函數(shù)在區(qū)域s2中的每一函數(shù)值均向上進行了拉伸，并且點x越遠離局部極值點x，則其函數(shù)值被拉伸的幅度越大。此次拉伸的結(jié)果，使得區(qū)域中目標函數(shù)的形態(tài)變得平緩，并且其中所包含的部分極值也由此轉(zhuǎn)變?yōu)榉菢O值，這意味著從搜索空間剔除掉了函數(shù)值高于f(x)的部分極值，從而降低了后續(xù)搜索的難度。2021-11-6co-pso