基于粒子群優(yōu)化算法在NP難問題中的應(yīng)用研究*

周廷慰

（蚌埠學(xué)院）

0 引言

尋求最優(yōu)化是人們在科學(xué)研究、工程技術(shù)和經(jīng)濟(jì)管理等領(lǐng)域中經(jīng)常遇到的問題.優(yōu)化問題研究的主要內(nèi)容是在解決某個問題時，如何從眾多的解決方案中選出最優(yōu)化方案.它可以定義為：在一定的約束條件下，求得一組參數(shù)值，使得系統(tǒng)的某項性能指標(biāo)達(dá)到最優(yōu)及最大或最小［1］.傳統(tǒng)的優(yōu)化方法是借助與優(yōu)化問題的不同性質(zhì)，通常分為線性規(guī)劃問題、非線性規(guī)劃問題、整數(shù)規(guī)劃問題和多目標(biāo)規(guī)劃問題等［2］.其中，商旅問題（Traveling Salesman Problem，TSP）是NP 困難問題中比較經(jīng)典的問題之一，同時亦是一個典型的組合優(yōu)化問題［3］.目前，求解TSP 問題的方法主要包括最近鄰與搜索算法、粒子群算法、遺傳算法、蟻群算法以及神經(jīng)網(wǎng)絡(luò)算法等［4－6］.其中，粒子群優(yōu)化算法的研究大致集中在以下四個方向：PSO算法的改進(jìn)、算法的參數(shù)設(shè)置、算法的收斂性以及工作機(jī)制與應(yīng)用［7］.該文通過比較不同智能優(yōu)化算法在NP 難問題中的應(yīng)用研究，分析不同目標(biāo)個數(shù)下最優(yōu)旅游路徑，拓展算法的應(yīng)用特點(diǎn)，為智能優(yōu)化算法的推廣應(yīng)用提供理論支撐.

1 相關(guān)理論概述

1.1 PSO算法求解旅行商問題

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）初始化為一群隨機(jī)粒子（隨機(jī)解），然后通過迭代找到最優(yōu)解.在每一次的迭代中，粒子通過跟蹤兩個“極值”Pbest，Gbest來更新自己.在找到這兩個最優(yōu)值后，粒子通過公式（1）和（2）來更新自己的速度和位置［8］.

式中，i ＝1，2，…，N，N 是此群中粒子的總數(shù).vi是粒子的速度，rand（）介于（0，1）之間的隨機(jī)數(shù)，xi是粒子的當(dāng)前位置，c1和c2是學(xué)習(xí)因子Vmax.算法流程圖如圖1（a）所示.

圖1 求解TSP 算法流程圖

基本步驟流程：

（1）初始化

隨機(jī)生成城市的坐標(biāo)，用點(diǎn)來畫圖，點(diǎn)的顏色為藍(lán)色圓圈.通過每個城市的坐標(biāo)，計算出任意兩個城市的旅費(fèi)，保存在二維數(shù)組Distance中.

（2）初始化粒子群

設(shè)定加速常數(shù)c1、c2，在定義空間R′隨機(jī)產(chǎn)生n個粒子的初始位置（X1，X2，…，Xn）（其中每個元素Xi表示城市I的優(yōu)先級，優(yōu)先級越高，越排在前面）和初始速度（V1，V2，…Vn）形成初始種群Xt和Vt；最大進(jìn)化代數(shù)Tmax，將當(dāng)前進(jìn)化代數(shù)設(shè)為t ＝1.

（3）評價種群Xt，計算每個粒子的適應(yīng)度值

粒子適應(yīng)值的計算fitness ＝Distance［Y1］［Y2］＋Distance［Y2］［Y3］＋…＋Distance［Yn］［Y1］.（其中：Y ＝（Y1，Y2，Y3，…，Yn）表示將粒子坐標(biāo)X ＝（X1，X2，…，Xn）通過優(yōu)先級的比較轉(zhuǎn)換為它所代表的城市路線Y ＝（Y1，Y2，Y3，…，Yn），則粒子適應(yīng)值fitness 即是計算最小旅費(fèi)的函數(shù)）.通過比較每個粒子的最好位置Pbest的適應(yīng)度值與群體的最好位置Gbest的適應(yīng)度值；根據(jù)式（2）更新粒子的位移方向和步長，產(chǎn)生新種群Xt＋1直至達(dá)到最大迭代次數(shù)或最優(yōu)位置，否則轉(zhuǎn)步驟（3）.

協(xié)同粒子群優(yōu)化算法（C－PSO）在PSO算法的基礎(chǔ)上，引入了協(xié)同進(jìn)化與策略與進(jìn)化的思想，將個體與種群相互聯(lián)系，用局部學(xué)習(xí)策略降低局部極值出現(xiàn)的概率［9］.如圖1（b）所示，C－PSO算法在初始化、適應(yīng)度值計算和信息素更新保留了PSO算法的模式，增加了種群中個體精英保留策略，根據(jù)個體適應(yīng)度值大小保留精英，剩余部分進(jìn)行進(jìn)化操作；將進(jìn)化后的新個體與保留精英形成新的種群，從而達(dá)到最優(yōu)個體與不同種群構(gòu)成問題完整解的目的，實現(xiàn)種群信息的協(xié)同進(jìn)化.

1.2 GA算法求解旅行商問題

遺傳算法（Genetic Algarthm，GA）是模擬達(dá)爾文生物進(jìn)化論的自然選擇與遺傳的計算模型，通過自然進(jìn)化過程尋找城市間的最優(yōu)距離［10］，如圖1（c）所示.GA算法的具體步驟如下.

（1）初始化

初始化城市序列的坐標(biāo)，設(shè)置種群規(guī)模k 與變異概率（一般取0.01）以及迭代步數(shù)等參數(shù)（n ＝1000）.

（2）適應(yīng)度計算

用歐式距離計算城市序列中每個個體的適應(yīng)度.

（3）交叉／變異與更新

通過輪盤賭策略根據(jù)適應(yīng)度來選擇個體作為交叉操作的父體，并確定是否對個體進(jìn)行變異，如果需要進(jìn)行變異，側(cè)隨機(jī)選擇個體的兩個城市進(jìn)行交換.最終選擇適應(yīng)度最好的20 個個體直接保留到下一代.

（4）判斷是否終止

根據(jù)設(shè)定迭代次數(shù)進(jìn)行判斷是否達(dá)到最大迭代次數(shù)，如果沒有轉(zhuǎn)到第2 步，反之則輸出適應(yīng)度最好的個體.

1.3 ACO算法求解旅行商問題

蟻群算法（Ant Cologn Optimization，ACO）是一種基于種群尋優(yōu)的啟發(fā)式搜索算法，通過個體間的信息傳遞與搜索完成最短路徑的尋優(yōu)過程［11］.其求解旅行問題的步驟如下.

（1）初始化

如圖1（d）所示，首先進(jìn)行各參數(shù)初始化，包括螞蟻數(shù)量m，信息素因子α，啟發(fā)函數(shù)因子β，信息會發(fā)因子ρ和最大迭代次數(shù)等.

（2）構(gòu)建解空間

對數(shù)量為k（k ＝1，2，3，…，m）個螞蟻進(jìn)行初始位置隨機(jī)化處理，計算各個螞蟻轉(zhuǎn)移至下一個待訪問城市的概率，計算公式如式（3）：

式中，i和j為初始點(diǎn)與終點(diǎn)；ηij（t）為啟發(fā)函數(shù)；τij（t）為時間t時刻，R為訪問過的節(jié)點(diǎn)的集合.

（3）更新信息素

計算螞蟻所經(jīng)過的路程旅游費(fèi)用，記錄最優(yōu)旅游費(fèi)用，并更新各個城市的信息素.

（4）判斷是否終止

判斷抵達(dá)次數(shù)是否大于最大迭代次數(shù)，如果是小于則再次進(jìn)行構(gòu)建解空間，反之則輸入最優(yōu)解.

2 結(jié)果與分析

2.1 數(shù)據(jù)來源與參數(shù)設(shè)置

該文以美國地圖為邊界，采用隨機(jī)數(shù)據(jù)來最大化模擬實際情況，即初始城市的坐標(biāo)數(shù)據(jù)（x，y）為隨機(jī)數(shù).實驗共設(shè)置了5、10、15、20、30 和100個隨機(jī)城市坐標(biāo)點(diǎn)，求解一條經(jīng)過各城市且一次的旅行最低費(fèi)用的路線.分別采用PSO 算法、C－PSO 算法、GA 算法和ACO 算法進(jìn)行求解，運(yùn)行100 次實驗，比較四種算法的魯棒性與實效性.實驗工作平臺：操作系統(tǒng)Windows 7，CPU為i7 4770，3.4GHz，RAM為8.0GB，Matlab R2016a.PSO和C－PSO算法中的慣性權(quán)重因子公共場所ω ＝0.7298，加速系數(shù)C1＝C2＝1.4962；GA算法中的交叉概率和選擇概率均為0.3，變異概率為0.01；ACO算法中的，信息素因子α ＝2，啟發(fā)函數(shù)因子β ＝1，信息素?fù)]發(fā)因子ρ ＝0.2，最大迭代次數(shù)均為1000.

2.2 魯棒性分析結(jié)果

如圖2 所示，為不同問題規(guī)模下最短路徑圖.5個城市的最短路徑為［4，1，5，2，3］；10個城市的最短路徑為［7，5，8，1，6，3，9，2，4，10］；15個城市的最短路徑為［7，4，13，10，11，12，5，3，15，6，2，8，1，9，14］；20個城市的最短路徑為［1，2，5，6，8，9，19，20，16，18，3，13，17，12，7，4，10，11，14，15］；30個城市的最短路徑為［9，10，11，25，29，22，19，24，15，8，17，2，27，26，14，28，7，1，3，4，5，6，12，13，16，18，20，21，23，30］；100個城市的最短路徑為［8，10，27，36，38，41，43，44，48，58，68，75，81，83，89，96，97，98，100，85，37，92，40，72，32，5，13，65，87，26，52，45，6，34，70，49，63，69，51，95，21，64，24，25，22，55，74，53，91，46，56，60，50，99，23，93，84，9，14，90，3，7，67，35，80，1，61，78，16，62，29，4，28，77，39，66，11，82，86，31，19，2，79，18，47，12，15，17，20，30，33，42，54，57，59，71，73，76，88，94］.利用回路排重算法統(tǒng)計四種算法在運(yùn)行100 次后，在不同問題規(guī)模下最短路徑出現(xiàn)比例，即準(zhǔn)確率，結(jié)果見表1.

表1 不同問題規(guī)模下最短路徑的準(zhǔn)確率

圖2 不同問題規(guī)模下最短路徑

從表1可以看出，PSO算法的平均準(zhǔn)確率為68.87%，PSO算法的平均準(zhǔn)確率為69.84%，PSO算法的平均準(zhǔn)確率為64.81%，PSO 算法的平均準(zhǔn)確率為56.88%.隨著城市個數(shù)的增大，各算法的準(zhǔn)確率逐漸降低.其中，PSO 算法和C－PSO算法的準(zhǔn)確率的變化較為平緩，說明算法的魯棒性較好.而GA算法和ACO算法的準(zhǔn)確率隨城市個數(shù)變化較明顯.當(dāng)城市個數(shù)為100 時，ACO 算法的準(zhǔn)確率僅有30.52%.此外，基本PSO算法存在誤差，城市個數(shù)10個時路線基本不交叉，城市個數(shù)15個以上時路線出現(xiàn)交叉，其原因是PSO算法找不到最優(yōu)時會陷入局部極值.而C－PSO算法將基本的粒子群算法和協(xié)同局部搜索相結(jié)合，可以抑制基本的粒子群算法過早陷入局部最優(yōu)解，并能保持較高的收斂速度，同時對粒子迭代過程中的路徑進(jìn)行優(yōu)化，提高算法的求解質(zhì)量和效率.

2.3 運(yùn)行速度分析結(jié)果

為了比較不同算法在TSP 問題求解過程中運(yùn)行速度的情況，剖析問題規(guī)模大小與各算法運(yùn)行時間的關(guān)系.通過測定同一問題規(guī)模下不同算法的運(yùn)行時間（判斷標(biāo)準(zhǔn)：算法開始運(yùn)行到第一次收斂到最小值所需要的時間），分析在不同用時下的最佳算法.該文選擇問題規(guī)模（城市個數(shù)）分別為5、10、15、20、30和100，最大迭代次數(shù)為1000，結(jié)果如圖3所示.

圖3 不同城市規(guī)模的運(yùn)行時間

從圖3可以看出，隨著問題規(guī)模（城市個數(shù)）的增加四種算法的運(yùn)行時間總體呈增大趨勢.當(dāng)城市個數(shù)小于15時，ACO算法的運(yùn)行時間比GA算法的運(yùn)行時間短；當(dāng)城市個數(shù)大于15 時，ACO算法的運(yùn)行時間比GA 算法的運(yùn)行時間長，而PSO算法在不同城市個數(shù)下的運(yùn)行時間均是最短的.四種算法在測試中的總平均運(yùn)行時間分別為1.166 s（PSO）、1.131 s（C－PSO）、2.717 s（GA）和1.516 s（ACO）.當(dāng)城市個數(shù)為100時，PSO算法、GA算法和ACO算法的運(yùn)行時間分別為4.367、4.107、5.625和12.746 s.綜上所述，在問題規(guī)模小時，可以采用PSO算法和ACO算法；在問題規(guī)模大時，可以采用C－PSO算法.

3 結(jié)束語

該文主要以求解NP 難問題中的典型－TSP問題為研究內(nèi)容，對比了粒子群算法、協(xié)同粒子群算法、遺傳算法和蟻群算法的魯棒性與時效性.實驗結(jié)果表明，通過多次迭代能夠找到哈密爾頓回路及最優(yōu)旅游路線，協(xié)同粒子群算法在解決規(guī)模較大的TSP 問題時，與其它算法相比具有更強(qiáng)的搜索能力和效率.隨著城市個數(shù)的增大，各算法的準(zhǔn)確率逐漸降低，運(yùn)行時間延長.其中，PSO算法和C－PSO算法的準(zhǔn)確率的變化較為平緩，說明算法的魯棒性較好.而GA 算法和ACO算法的準(zhǔn)確率隨城市個數(shù)變化較明顯.