變分布的量子行為粒子群優(yōu)化算法求解工程約束優(yōu)化問題

施曉倩，陳祺東，孫 俊，冒鐘杰

（1.江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點建設(shè)實驗室（無錫太湖學(xué)院），江蘇無錫214000；2.人工智能與模式識別國際聯(lián)合實驗室（江南大學(xué)），江蘇無錫214000）

（?通信作者電子郵箱cqd_jnu@hotmail.com）

0 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是一種隨機搜索算法，是群體智能算法中的重要一種，該算法在1995年由Kennedy等［1］提出。在這之后，為了改進粒子群優(yōu)化算法的搜索能力，在基于原始粒子群優(yōu)化算法的基礎(chǔ)上增加策略或改進的算法被先后提出［2-10］，并廣泛運用于交通［11］、軍事工業(yè)［12］、醫(yī)療［13］或其他領(lǐng)域［14-16］。

近十幾年來，大部分學(xué)者主要研究使用群體智能算法來求解無約束的優(yōu)化問題，而對約束優(yōu)化問題的研究則相對較少。約束優(yōu)化問題（Constrained Optimization Problem，COP）是優(yōu)化問題中比較復(fù)雜的問題，這類問題一般可描述為：

其中：X=（X1，X2，…，XD）是D維決策向量，f(X)是目標(biāo)函數(shù)，gj(X)是第j個不等式約束，hk(X)是第k個等式約束，第i維變量Xi的取值范圍為[XMINi，XMAXi]。等式約束一般可將其通過|hk()X|≤ε轉(zhuǎn)換為兩個不等式約束，ε是一個接近于0的閾值，通常取值10-5～10-3。

約束優(yōu)化問題可以描述為在保證變量X滿足式（1）等式和不等式約束的前提下，在變量定義的范圍內(nèi)使得目標(biāo)函數(shù)搜索到最優(yōu)點X*，使得f(X*)最小。若變量X違背一個及以上約束條件，則稱其為不可行解；若變量X滿足所有的約束條件，則稱其為可行解，所有的可行解集合稱為可行域，一般用F表示。X所有可能取值的集合稱為搜索空間，一般用S表示，F(xiàn)?S。

使用粒子群算法求解約束優(yōu)化問題主要的難點在于有效地處理約束條件，一般來說，這些處理方法可分為4種［17］：

1）保留滿足約束條件的個體，即每次迭代只保留在可行域上的點。

2）修復(fù)不滿足約束條件的個體，即用群中粒子滿足約束條件的個體和不滿足約束條件的個體進行雜交處理，直到其滿足所有約束條件。

3）罰函數(shù)法。罰函數(shù)法是處理這類問題最多的方法，一般分為靜態(tài)的罰函數(shù)和動態(tài)罰函數(shù)。

4）混合算法。即將不同的算法結(jié)合來求解約束優(yōu)化問題。

方法1通過每次保留符合條件的粒子的做法，本質(zhì)上是窮舉的方式，時間復(fù)雜度高且浪費計算資源；方法2和方法4有較強的局部搜索能力，然而通過混合算法或者修復(fù)不滿足條件個體的方式增加了許多參數(shù)，調(diào)整參數(shù)難度大，算法的適用性不高。因此，本文采用罰函數(shù)法來求解約束優(yōu)化問題。

在以前的工作中，粒子群優(yōu)化算法被證明是適合求解約束優(yōu)化問題的：文獻［18-19］直接使用經(jīng)典的粒子群優(yōu)化算法求解約束優(yōu)化問題，并取得了很好的效果；文獻［20］使用改進的粒子群優(yōu)化算法RDPSO（Random Drift Particle Swarm Optimization）求解電力優(yōu)化問題；文獻［8］中證明粒子群優(yōu)化算法或者改進的粒子群優(yōu)化算法最終能夠收斂，但是在解決優(yōu)化問題時，由于粒子群優(yōu)化算法的局部搜索能力弱導(dǎo)致不能精確搜索到全局最優(yōu)點；為了改善粒子群優(yōu)化算法的局部搜索能力，文獻［21-22］采用和差分進化或遺傳算法混合的方式來增強粒子群優(yōu)化算法的局部能力；文獻［23-25］通過控制粒子群的多樣性使得算法在一定程度上避免算法陷入局部最優(yōu)。

工程設(shè)計問題是現(xiàn)實生活中常見的約束優(yōu)化問題，很多學(xué)者嘗試用群體智能算法運用到該領(lǐng)域：文獻［26］提出協(xié)同演化的粒子群優(yōu)化算法；文獻［27］使用引力群體算法結(jié)合遺傳算法來求解優(yōu)化問題取得了優(yōu)異的表現(xiàn)；文獻［28］首先使用基于高斯分布的量子行為粒子群優(yōu)化算法求解工程設(shè)計問題，對比原始的也就是基于均勻分布的量子行為算法，該算法的局部能力大大增強，然而該算法的全局搜索能力沒有得到維持。因此，本文提出了一種變分布的基于高斯分布的量子行為粒子群優(yōu)化算法。

本文的貢獻在于：第一，改進的策略簡單但有效，即在迭代過程中不斷縮小搜索的概率空間以此來達到算法從強全局搜索能力到強局部搜索能力的穩(wěn)定遷移。第二，參數(shù)少，相比于結(jié)合遺傳算法或差分進化，或者其他例如Powell等一維搜索算法，該算法只需要調(diào)整兩個參數(shù)即高斯分布的方差和收縮擴張因子來滿足不同問題精度的需求。

1 自適應(yīng)的高斯量子行為粒子群優(yōu)化算法

本章首先介紹經(jīng)典的量子行為粒子群優(yōu)化算法的由來，然后詳細(xì)描述該算法中粒子的更新迭代過程，接著分析該算法的優(yōu)點和不足點，進一步提出本文的算法——自適應(yīng)的基于高斯分布的量子行為粒子群優(yōu)化算法，并將該算法求解工程約束優(yōu)化問題的過程以流程圖的方式給出。

1.1 量子行為粒子群優(yōu)化算法

群體智能算法是模擬自然界群體行為提出的，粒子群優(yōu)化算法是其中的一種。近十幾年來，很多改進的粒子群被提出，并廣泛運用到工程、醫(yī)療、經(jīng)濟管理等領(lǐng)域中。Kennedy在“Swarm Intelligence”中提到粒子群優(yōu)化算法的隨機性代表了算法的智能，根據(jù)他的論述，文獻［2］提出了具有量子行為的粒子群優(yōu)化（Quantum-behaved Particle Swarm Optimization，QPSO）算法。該算法通過模擬量子系統(tǒng)中態(tài)疊加性的強不確定性，使得QPSO算法能夠在迭代過程中仍舊有概率覆蓋整個概率搜索空間，而不是像其他一些粒子群優(yōu)化算法在搜索過程的末尾失去全局搜索能力，停滯在局部最優(yōu)點附近。

QPSO算法步驟如下：

步驟1 在搜索空間中初始化粒子群中粒子的位置，全局最優(yōu)位置和個體最優(yōu)位置；

步驟2 根據(jù)式（6）計算粒子群的平均最優(yōu)位置。

步驟3 根據(jù)式（5）計算收縮擴張因子αt；

步驟4 通過式（7）更新粒子位置并計算粒子的當(dāng)前適應(yīng)值。

步驟5 更新各粒子的個體最優(yōu)位置和群體當(dāng)前的全局最優(yōu)位置；

步驟6 重復(fù)步驟2～5，直至滿足一定的循環(huán)結(jié)束條件。

1.2 自適應(yīng)的高斯量子行為粒子群優(yōu)化算法

得益于引入概率分布使得具有量子行為的粒子群在搜索過程中能夠使粒子能以一定幾率到達搜索空間的任何一個位置，所以算法具有很強的全局搜索能力。然而，這種很強的隨機性也減弱了量子行為的粒子群優(yōu)化算法的局部搜索能力。

圖1展示了算法在搜索過程的末尾階段種群的分布，然而在更新過程中如果問題的全局最優(yōu)點區(qū)域幅度小，對具有量子行為的粒子群優(yōu)化算法來說，由于其包含隨機值變動范圍大，個體極其容易跳過全局最優(yōu)點。因此，文獻［27］將均勻概率分布替換成由標(biāo)準(zhǔn)高斯概率分布產(chǎn)生的隨機數(shù)，使得粒子在更新過程中能夠以較高的概率使更新位置接近吸引子，這種方法能夠提升局部搜索能力尤其是在進化過程的后期，但是其全局搜索能力卻大大減弱。

圖1 全局最優(yōu)附近區(qū)域的種群分布Fig.1 Swarmdistribution near global optimum

因此，本文提出了一種自適應(yīng)的基于高斯概率分布的量子行為粒子群優(yōu)化算法（Adaptive Gaussian Quantum-behaved Particle Swarm Optimizer，AG-QPSO），通過使高斯分布隨時間動態(tài)變化來逐步調(diào)整需求，即從強的全局搜索能力需要逐步轉(zhuǎn)化為強的局部搜索能力需要。如圖2所示，隨著種群的不斷迭代和搜索過程的進行，粒子更新位置范圍（距離吸引子的距離）將不斷收縮減小直到收縮到吸引子，其中Gt代表第t次迭代過程。

其中σ呈線性下降，可以表示為：

其中：N(0，σ2)是均值為0、σ2為標(biāo)準(zhǔn)差的高斯概率分布。σu和σl分別代表初始最大值方差和最小值方差，這兩個參數(shù)可根據(jù)問題調(diào)整。和基于高斯分布的量子行為粒子群優(yōu)化算法不同的是，AG-QPSO不需要使用收縮擴張因子αt來控制種群的搜索過程。使用收縮擴張因子極難控制種群的多樣性（一般會出現(xiàn)種群多樣性的迅速收縮），而通過變高斯的方法控制種群搜索范圍的優(yōu)點是它讓種群多樣性緩慢下降，通過隨時間調(diào)整高斯分布的標(biāo)準(zhǔn)差來實現(xiàn)粒子更新位置的范圍，從而達到自適應(yīng)調(diào)整全局搜索和局部搜索能力。

圖2 AG-QPSO搜索過程中的種群分布變化Fig.2 Changeof swarmdistribution in AG-QPSOsearch process

如圖3所示，當(dāng)標(biāo)準(zhǔn)差σ2越大，高斯概率分布越接近于扁平，從而與標(biāo)準(zhǔn)分布圖4所示的標(biāo)準(zhǔn)均勻近似，因而初始的更新過程具有很強的全局搜索能力。逐步地，隨著標(biāo)準(zhǔn)差變小，隨機值在0附近的概率就越大，也就使得粒子更新的范圍越接近吸引子，因而在搜索過程末尾算法的局部搜索能力越來越強。

圖3 隨方差變化的高斯分布圖Fig.3 Gaussian distribution varyingwith variancechange

圖4 均勻概率分布Fig.4 Uniform probability distribution

1.3 罰函數(shù)法

罰函數(shù)法是處理約束條件常用的一種方式，一般可以描述為：

其中，f(X)是約束優(yōu)化問題的目標(biāo)函數(shù)，如果個體滿足所有的約束條件，則它的適應(yīng)值等于目標(biāo)函數(shù)的值；如果不滿足也就是約束條件大于0時，則當(dāng)前個體的適應(yīng)值等于式（12）的第二個等式，也就是加上了懲罰值。懲罰項由兩個參數(shù)構(gòu)成，r是一個正值，在本文中，它設(shè)定為5000，q是當(dāng)前個體不滿足約束條件的個數(shù)。需要注意的是，所有的約束條件在最初都處理成小于等于0的不等式。

自適應(yīng)高斯分布的量子行為粒子群優(yōu)化算法求解工程約束優(yōu)化問題的流程如5所示。

圖5 基于罰函數(shù)的AG-QPSO算法流程Fig.5 Flowchart of the penalty function based AG-QPSOalgorithm

2 工程優(yōu)化問題描述

2.1 壓力容器設(shè)計問題

在這個問題中，圓柱形容器的兩端安裝著半球形的容器蓋，由兩個縱向焊縫組合形成一個圓柱體，如圖6所示。

圖6 壓力容器設(shè)計問題Fig.6 Design problem of pressure vessel

該問題的目標(biāo)值由4個決策變量決定，分別是：壓力容器的厚度Ts，頭部厚度Th，容器內(nèi)半徑R和容器去掉頭部的長度L。因此，壓力容器設(shè)計問題的優(yōu)化問題模型Y=[Ts，Th，R，L]=[X1，X2，X3，X4]可以描述為：

這個優(yōu)化問題的目標(biāo)是使得材料成本、制作成本、焊接成本的和最小。

2.2 張弦（壓力弦）設(shè)計問題

張弦（壓力弦）設(shè)計問題的目標(biāo)是最小化張弦的重量，如圖7所示。該問題主要有3個決策變量，分別是平均線圈直徑X1、線徑X2和有效線圈數(shù)X3，該問題定義如下：

限制條件為：

圖7 張弦（壓力弦）設(shè)計問題Fig.7 Design problem of tension string

3 實驗結(jié)果與分析

本章首先將AG-QPSO算法運用于解決壓力容器設(shè)計問題和張弦（壓力弦）設(shè)計問題，以驗證算法的能力，然后比較了AG-QPSO算法與其他算法的時間復(fù)雜度。需要說明的是，本文所有的實驗都是在python 2.7環(huán)境下單線程運行的，實驗所用的配置為Intel酷睿雙核CPU，4 GB內(nèi)存。

3.1 參數(shù)設(shè)定

AG-QPSO只需要設(shè)置高斯分布方差的初始值和終值，針對本文中這兩個工程設(shè)計問題，σ2u和σ2l的值分別為5和0.001。實驗中，種群的個數(shù)M為80，最大迭代次數(shù)T為1000，每個問題都運行50輪來驗證。

3.2 壓力容器設(shè)計問題

針對壓力容器設(shè)計問題，文獻［29］結(jié)合外部懲罰函數(shù)或二次規(guī)劃方法實現(xiàn)分支定界過程，變量邊界獨立于設(shè)計約束進行處理，省去了每個分支節(jié)點重新構(gòu)造問題；文獻［30］利用隨機優(yōu)化技術(shù)模擬退火來求解混合離散非線性優(yōu)化問題；文獻［31］提出了一種求解含整數(shù)、離散、零一和連續(xù)變量的機械設(shè)計優(yōu)化問題的混合變量進化規(guī)劃（Mixed Variable Evolutionary Programming，MVEP），該算法改進了混合變量空間的全局搜索和收斂性能；文獻［32］提出了一種求解非線性工程設(shè)計優(yōu)化問題的穩(wěn)健優(yōu)化設(shè)計算法。該算法根據(jù)遺傳算法的原理，使用二元編碼和實數(shù)編碼的組合來處理這些混合變量，簡稱為遺傳自適應(yīng)搜索；文獻［33］提出了一種協(xié)同進化的遺傳算法，并取得了良好的結(jié)果；文獻［27］在量子行為粒子群優(yōu)化算法基礎(chǔ)之上，使用高斯分布替代均勻分布來提高局部搜索能力。

本文將提出的AG-QPSO算法運用到該問題，并取得了顯著的成績。如表1所示，在滿足所有約束條件的情況下，AGQPSO找到的最優(yōu)值為5 885.332 8，其中，表1中的變量g1、g2、g3、g4分別是由約束不等式（14）、（15）、（16）和（17）在決策向量為X=(X1，X2，X3，X4)得到的值。由于算法是在量子行為粒子群的基礎(chǔ)上進行改進，因此，本文首先將該算法與經(jīng)典的PSO、原始的QPSO和在該約束優(yōu)化問題上取得很好結(jié)果 的 G-QPSO（Gaussian Quantum-behaved Particle Swarm Optimization）進行比較，實驗結(jié)果發(fā)現(xiàn)，不管是均值、中值還是最優(yōu)值，AG-QPSO均優(yōu)于其他所有的算法且算法搜索更為穩(wěn)定，如表2所示（50輪結(jié)果計算得到）。與本文之前分析的一樣，粒子群相關(guān)的算法有較強的全局搜索能力，而欠缺局部搜索能力，尤其是面對這類在最優(yōu)點附近搜索區(qū)域極為尖銳的工程約束優(yōu)化問題。

進一步，本文將算法與其他現(xiàn)有算法進行比較，如表3所示，從表中實驗結(jié)果可以看出，本文提出的AG-QPSO算法明顯優(yōu)于其他算法。

表1 壓力容器設(shè)計問題中使用AG-QPSO的最佳結(jié)果Tab.1 Optimal resultsof pressurevessel designproblemusing AG-QPSO

表2 壓力容器設(shè)計問題中PSO、QPSO、G-QPSO和AG-QPSO的對比結(jié)果Tab.2 Comparison resultsof PSO，QPSOand G-QPSOon pressurevessel design problem

表3 壓力容器設(shè)計問題上所提算法與其他算法的比較Tab.3 Comparison of theproposed algorithm and other algorithmson pressurevessel design problem

3.3 張弦（壓力弦）設(shè)計問題

文獻［33］首先采用8種優(yōu)化方法解決張弦設(shè)計問題。文獻［34-37］也用其他優(yōu)化方法解決了這個問題。同樣，本文將AG-QPSO運用到張弦（壓力弦）設(shè)計問題。如表4所示，本文挑選了在算法運行50輪后最優(yōu)的結(jié)果，在滿足所有約束條件的情況下，算法取得了最優(yōu)值0.010 95788的結(jié)果。

表4 張弦（壓力弦）設(shè)計問題中使用AG-QPSO的最佳結(jié)果Tab.4 Optimal results of tension string design problem using AG-QPSO

同樣，與PSO、QPSO、G-QPSO相比，AG-QPSO不管在中值、均值還是最優(yōu)值上都仍舊遠(yuǎn)遠(yuǎn)超過這些算法，而且方差小只有7.663 53×10-17，如表5所示，意味著算法具有很高的魯棒性。

表5 張弦（壓力弦）設(shè)計問題中4種算法的對比結(jié)果Tab.5 Comparison results of four algorithms ontension stringdesign problem

表6展示了之前一些算法在該問題上的最優(yōu)解，可以清晰地看到，相比于之前的一些算法，AG-QPSO在這個問題上表現(xiàn)最優(yōu)。

3.4 時間復(fù)雜度分析

衡量群體智能優(yōu)化算法性能的標(biāo)準(zhǔn)是算法求解問題的精度和算法求解問題的速度。在壓力容器問題和張力弦兩個多約束優(yōu)化問題上的實驗結(jié)果表明，與其他現(xiàn)有的針對多約束優(yōu)化問題的算法相比，AG-QPSO算法求解問題的精度最好。而優(yōu)化算法求解問題速度的比較將通過對算法進行時間復(fù)雜度的分析。因此，本文將重點分析AG-QPSO算法與標(biāo)準(zhǔn)PSO、標(biāo)準(zhǔn)QPSO、G-QPSO和其他一般的混合算法的時間復(fù)雜度。

表6 張弦（壓力弦）設(shè)計問題上所提算法與其他算法的比較Tab.6 Comparison of theproposed algorithmand other algorithmson tension stringdesign problem

在本文中，參考文獻［38］對優(yōu)化算法時間復(fù)雜度的分析，將分為4個方面，即初始化時間復(fù)雜度、算法評估的時間復(fù)雜度、粒子位置更新的時間復(fù)雜度和算法總體的時間復(fù)雜度來進行評判。表7中給出了這五類算法這4個方面的時間復(fù)雜度。

表7 五種算法復(fù)雜度比較Tab.7 Complexity comparison of fivealgorithms

從表7中可以看出，混合算法例如標(biāo)準(zhǔn)PSO結(jié)合遺傳算法由于在粒子位置更新中增加了變異、交叉、選擇操作，因此該算法的粒子位置更新的時間復(fù)雜度相對于其他四種算法更高，與標(biāo)準(zhǔn)PSO算法、標(biāo)準(zhǔn)QPSO算法、G-QPSO算法相比時間復(fù)雜度更高。

由于AG-QPSO算法沒有增加更多的計算過程，因此本文提出的AG-QPSO算法在求解問題的速度上與其他算法是一致的。

4 結(jié)語

本文設(shè)計了一種自適應(yīng)基于高斯分布的量子行為粒子群優(yōu)化算法，用于求解工程設(shè)計問題。首先，本文調(diào)研了許多關(guān)于利用群體智能算法來求解約束優(yōu)化問題的文獻，發(fā)現(xiàn)這些文獻都圍繞提高算法在搜索末尾階段的局部搜索能力來改進算法。然而，這些算法大大增加了算法的時間復(fù)雜度和調(diào)整參數(shù)的難度。因此本文在基于量子行為粒子群優(yōu)化算法的基礎(chǔ)之上，通過改變圍繞吸引點鄰域概率分布，即從簡單的均勻分布到從開始階段利用高方差的高斯分布近似均勻分布到搜索末尾階段利用低方差的高斯分布提高其局部搜索能力，從而使算法穩(wěn)定地從強全局搜索能力到強局部搜索能力遷移。進一步為了驗證算法的求解能力，本文使用該算法測試了壓力容器設(shè)計問題和張弦（壓力弦）設(shè)計問題2個實際工程設(shè)計問題，并與近幾年表現(xiàn)優(yōu)異的算法進行了比較，發(fā)現(xiàn)自適應(yīng)基于高斯分布的量子行為粒子群優(yōu)化算法表現(xiàn)更為突出。

未來，本文考慮到實際問題并不需要考慮求解的時間長短，而更注重結(jié)果的精度，因此，之后本文將考慮采用控制種群多樣性的策略來保持更為穩(wěn)定的全局搜索能力。