基于QT的粒子群優(yōu)化仿真演示軟件設(shè)計(jì)

王隨 蔣培培 王善民 吉佳紅

摘要：粒子群優(yōu)化（PSO）算法是一種經(jīng)典群智能優(yōu)化算法，為了直觀顯示迭代過程中適應(yīng)度進(jìn)化過程和粒子群位置變化趨勢(shì)，文章設(shè)計(jì)了一個(gè)基于跨平臺(tái)QT的粒子群優(yōu)化仿真演示軟件，使用圖形化控件支持算法參數(shù)編輯和仿真演示。首先介紹了PSO基本原理和算法步驟，然后使用QT控件進(jìn)行了界面設(shè)計(jì)，基于QT類進(jìn)行了算法仿真功能設(shè)計(jì)和演示功能設(shè)計(jì)。經(jīng)過實(shí)驗(yàn)驗(yàn)證，該軟件支持PSO算法參數(shù)編輯，能顯示適應(yīng)度進(jìn)化曲線和粒子群位置演變過程，滿足軟件設(shè)計(jì)的要求。

關(guān)鍵詞：QT；PSO；粒子群優(yōu)化；仿真演示；軟件設(shè)計(jì)

中圖分類號(hào)：TP311 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）29-0045-04

粒子群優(yōu)化算法（Particle Swarm Optimization Algorithm，PSO）是由J.Kennedy和R.C.Eberhart[1-2]在1995年提出的一種群智能優(yōu)化算法。該算法受自然界中鳥群和魚群行為模式啟發(fā)，具有結(jié)構(gòu)簡(jiǎn)單、收斂速度快、計(jì)算量小等特點(diǎn)。經(jīng)過許多學(xué)者研究，PSO目前已在學(xué)術(shù)領(lǐng)域和工程應(yīng)用領(lǐng)域得到廣泛應(yīng)用，例如路徑規(guī)劃[3]、資源調(diào)度[4]、參數(shù)優(yōu)化[5]、網(wǎng)絡(luò)拓?fù)鋬?yōu)化[6]、成本優(yōu)化[7]，成為群智能優(yōu)化領(lǐng)域的一種經(jīng)典算法，也是當(dāng)今研究的熱門問題之一。

本文針對(duì)在國(guó)產(chǎn)化平臺(tái)下進(jìn)行群智能優(yōu)化算法仿真驗(yàn)證和仿真演示的需求，設(shè)計(jì)了一個(gè)基于QT的PSO仿真演示軟件。該軟件能動(dòng)態(tài)顯示每一次迭代后適應(yīng)度進(jìn)化曲線變化情況和種群個(gè)體位置演變過程。QT是一個(gè)開源的跨平臺(tái)開發(fā)工具，由于其靈活性好、移植性強(qiáng)，目前QT在工程應(yīng)用和模擬仿真中都得到廣泛使用，例如單片機(jī)程序[8]、模擬控制系統(tǒng)[9]。基于QT開發(fā)的軟件能方便地移植到國(guó)產(chǎn)化平臺(tái)下。

1 PSO

在基本PSO中，用粒子群模擬優(yōu)化問題在搜索空間中的解，用適應(yīng)度對(duì)粒子位置進(jìn)行評(píng)價(jià)。每個(gè)粒子的位置代表多維搜索空間中一個(gè)解。假設(shè)搜索空間維數(shù)為D，當(dāng)前粒子位置用[Xti]表示，[Xti]表示含有D個(gè)元素的向量，其中i表示第i個(gè)粒子，t表示迭代次數(shù)。

PSO每次迭代搜索需要計(jì)算與更新粒子的速度信息和位置信息。

粒子速度更新公式為：

[Vt+1i=ωVti+c1r1pi-Xti+c2r2pg-Xti] ? ? （1）

粒子位置更新公式為：

[Xt+1i=Xti+Vt+1i] ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中，i表示第i個(gè)粒子，t表示迭代次數(shù)，[Vti]表示第i個(gè)粒子在第t次迭代時(shí)的速度，[Xti]表示第i個(gè)粒子在第t次迭代時(shí)的位置。ω表示慣性權(quán)重，認(rèn)知因子c1和社會(huì)因子c2統(tǒng)稱為加速系數(shù)或?qū)W習(xí)因子，r1和r2是第t次迭代時(shí)生成的[0，1]內(nèi)均勻分布的隨機(jī)數(shù)，[pi]表示第i個(gè)粒子的歷史最佳位置，[pg]表示全局最佳位置。

粒子速度更新方程中，速度的更新由三部分組成：慣性成分、個(gè)體認(rèn)知成分和社會(huì)認(rèn)知成分。其中慣性成分表示粒子當(dāng)前運(yùn)動(dòng)狀態(tài)對(duì)速度更新的影響，慣性權(quán)重決定慣性衰減程度的快慢，使算法對(duì)粒子先前迭代的慣性速度進(jìn)行自適應(yīng)調(diào)整；個(gè)體認(rèn)知部分表示粒子個(gè)體歷史最佳位置對(duì)當(dāng)前速度變化趨勢(shì)的指導(dǎo)作用；社會(huì)認(rèn)知部分表示全局最佳個(gè)體位置對(duì)當(dāng)前速度變化趨勢(shì)的指導(dǎo)作用。學(xué)習(xí)因子c1和c2分別表示個(gè)體認(rèn)知和社會(huì)認(rèn)知對(duì)速度更新影響的比例系數(shù)。搜索初期，粒子擁有較大搜索速度，隨著迭代次數(shù)增加，慣性速度逐漸減小，表示粒子全局搜索能力減弱，搜索精度提高。

粒子位置更新后，通過適應(yīng)度函數(shù)計(jì)算每個(gè)粒子的適應(yīng)度，更新每個(gè)粒子的個(gè)體歷史最佳位置和全局最佳位置。

控制參數(shù)對(duì)PSO算法的性能具有極大影響。參數(shù)c1和r1表示粒子受個(gè)體歷史最優(yōu)的影響程度，c2和r2表示粒子受全局最優(yōu)的影響程度。

PSO遇到兩種情況終止搜索：1）迭代次數(shù)t達(dá)到最大值；2）最佳適應(yīng)度滿足精度要求。

基本PSO算法流程描述如下：

step 1 初始化。隨機(jī)生成粒子種群，包括隨機(jī)的位置和速度。

step 2 計(jì)算每個(gè)粒子適應(yīng)度，更新全局最優(yōu)位置和個(gè)體歷史最優(yōu)位置。

step 3 進(jìn)化迭代。根據(jù)式（1）和（2）更新每個(gè)粒子的速度和位置。

step 4 終止條件判斷。判斷是否滿足搜索終止條件，若滿足則轉(zhuǎn)入step5，否則轉(zhuǎn)入step2。

step 5 迭代終止。輸出結(jié)果并結(jié)束。

基本PSO算法流程圖如圖1所示。

2 PSO仿真演示軟件設(shè)計(jì)

2.1 界面設(shè)計(jì)

Qt是一個(gè)跨平臺(tái)C++應(yīng)用程序開發(fā)工具，可以快速拖動(dòng)控件搭建界面生成GUI程序，可視化界面編輯器Qt Designer支持多種控件的選擇與布局。

PSO仿真演示軟件使用Windows qt 5.6.3開發(fā)，使用Qt提供的圖形界面控件，包括QLabel控件、QLineEidt控件、QListWidget控件、QComboBox控件、QPushButton控件、QChart控件、QChartView控件和QLayout控件。

通過QLineEidt控件輸入PSO算法參數(shù)，包括單次迭代時(shí)間，種群規(guī)模N，最大迭代次數(shù)G，解空間維數(shù)Dim，解空間上限U，解空間下限L，學(xué)習(xí)因子c1，學(xué)習(xí)因子c2，慣性權(quán)重ω，最大速度Vmax，最小速度Vmin；通過QComboBox控件選擇測(cè)試函數(shù)。通過QListWidget控件顯示操控信息提示和PSO每次迭代后全局最佳適應(yīng)度結(jié)果。通過QChart控件和QChartView控件顯示適應(yīng)度進(jìn)化曲線和每次迭代后粒子種群分布情況。通過QLayout控件進(jìn)行界面布局、控件對(duì)齊和控件大小自適應(yīng)控制。

PSO仿真演示軟件界面如圖2所示。

2.2 算法仿真功能設(shè)計(jì)

初始化默認(rèn)的PSO算法參數(shù)。程序啟動(dòng)后在PSO參數(shù)編輯界面填入默認(rèn)的數(shù)值，默認(rèn)數(shù)值為PSO算法常用的參數(shù)數(shù)值。

初始化測(cè)試函數(shù)選項(xiàng)。選取CEC2017基準(zhǔn)測(cè)試函數(shù)作為算法仿真實(shí)驗(yàn)的測(cè)試函數(shù)，包括Sphere函數(shù)、Schwefel 2.22函數(shù)、Schwefel 1.2函數(shù)、Schwefel 2.21函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)、Ackley函數(shù)、Griewank函數(shù)。用QT實(shí)現(xiàn)上述基準(zhǔn)測(cè)試函數(shù)數(shù)值計(jì)算，參數(shù)為元素個(gè)數(shù)可變的數(shù)值數(shù)組。

點(diǎn)擊軟件界面仿真開始按鈕后，算法仿真實(shí)驗(yàn)開始。算法仿真功能流程如下：

step1：獲取界面輸入?yún)?shù)。同時(shí)進(jìn)行邊界值和異常值檢查。當(dāng)出現(xiàn)異常值時(shí)直接退出算法仿真流程。

step2：初始化PSO參數(shù)和測(cè)試函數(shù)參數(shù)。

step3：粒子群初始化位置和速度。采用均勻分布的隨機(jī)數(shù)生成解空間內(nèi)的粒子位置和速度。

step4：檢查是否滿足搜索終止條件。若滿足，則轉(zhuǎn)到step8，否則轉(zhuǎn)到step5。

step5：依次更新每個(gè)粒子速度和位置。先根據(jù)式（1）更新粒子速度，當(dāng)速度大于最大值或小于最小值時(shí)，重新設(shè)置為最靠近的邊界值；根據(jù)式（2）更新粒子位置，同樣判斷粒子每一維的位置信息是否在解空間范圍內(nèi)，若超出解空間范圍則重新設(shè)置為最靠近的邊界值。

step6：依次更新每個(gè)粒子歷史最佳位置和適應(yīng)度。若當(dāng)前粒子適應(yīng)度優(yōu)于該粒子歷史最佳適應(yīng)度，則更新該粒子歷史最佳位置和適應(yīng)度，否則不作處理。

step7：更新全局最佳位置和適應(yīng)度。將上次搜索后的全局最佳適應(yīng)度與本次搜索每個(gè)粒子適應(yīng)度比較，選出本次搜索全局最佳適應(yīng)度。將本次搜索獲得的全局最佳適應(yīng)度加入全局適應(yīng)度數(shù)組中。轉(zhuǎn)到step4。

step8：PSO結(jié)束，輸出最終結(jié)果。

其中，粒子位置信息和速度信息用二維數(shù)組保存，粒子個(gè)體歷史最佳位置用二維數(shù)組保存，粒子個(gè)體歷史最佳適應(yīng)度用一維數(shù)組保存，全局最佳位置用一維數(shù)組保存，全局最佳適應(yīng)度用一維數(shù)組保存。

算法仿真流程step3中，粒子群初始化位置和速度，粒子位置初始化公式為：

[X0i=rand*（U-L）+L] ? ? ? ? ? ? ? ? （3）

粒子速度初始化公式為：

[V0i=rand*（Vmax-Vmin）+Vmin] ? ? ? ? （4）

其中下標(biāo)i表示第i個(gè)粒子，上標(biāo)0表示第0次迭代為初始化數(shù)值，U表示搜索空間上限、L表示搜索空間下限，Vmax表示最大速度、Vmin表示最小速度。

算法仿真功能流程如圖3所示。

2.3 演示功能設(shè)計(jì)

算法演示功能依托于算法仿真功能，在仿真過程中同步進(jìn)行數(shù)據(jù)可視化顯示。在算法仿真實(shí)驗(yàn)運(yùn)行過程中，每次搜索迭代后更新適應(yīng)度進(jìn)化曲線和粒子群分布情況，分別用折線圖和點(diǎn)圖形式顯示。Qt5.6.3提供QChat類用于圖表功能設(shè)計(jì)和顯示，用QScatterSeries類存儲(chǔ)圖表數(shù)據(jù)，用QChartView類提供視圖接口和視圖顯示，用QChat類實(shí)現(xiàn)圖表的坐標(biāo)軸范圍、坐標(biāo)軸刻度、坐標(biāo)軸網(wǎng)格線、標(biāo)題、數(shù)據(jù)類型、顯示類型、數(shù)據(jù)點(diǎn)樣式等顯示設(shè)置。用QChartView類綁定QChat類實(shí)現(xiàn)圖表的數(shù)據(jù)管理和視圖顯示功能。

在算法仿真功能流程的step4中，同步進(jìn)行存儲(chǔ)數(shù)據(jù)的圖形化顯示和信息提示，包括適應(yīng)度進(jìn)化曲線刷新顯示、粒子群分布情況刷新顯示和結(jié)果顯示界面當(dāng)前迭代結(jié)果信息打印顯示。

以一維數(shù)組形式存儲(chǔ)的全局最佳適應(yīng)度信息讀取數(shù)組最后一個(gè)元素，作為最新一次迭代的全局最佳適應(yīng)度，寫入到適應(yīng)度進(jìn)化曲線的數(shù)據(jù)存儲(chǔ)QScatterSeries中，同時(shí)更新對(duì)應(yīng)的QChartView，實(shí)現(xiàn)適應(yīng)度進(jìn)化曲線更新顯示。在表示結(jié)果顯示的QListWidget控件中，同步打印當(dāng)前迭代后最佳適應(yīng)度具體數(shù)值結(jié)果。

將以二維數(shù)組形式存儲(chǔ)的粒子群位置信息取前兩個(gè)維度信息形成N個(gè)點(diǎn)的二維坐標(biāo)Pi （xi， yi），其中Pi 表示點(diǎn)，i表示第i個(gè)粒子，xi表示橫軸坐標(biāo)，yi表示縱軸坐標(biāo)。每次迭代搜索結(jié)束后，將粒子群分布情況的數(shù)據(jù)存儲(chǔ)QScatterSeries中數(shù)據(jù)清空，并寫入當(dāng)前迭代后新的二維坐標(biāo)Pi信息，同時(shí)更新對(duì)應(yīng)的QChartView，實(shí)現(xiàn)粒子群位置分布情況更新顯示。

為了可觀測(cè)算法仿真過程中種群位置動(dòng)態(tài)變化過程，使用QTimer類作為算法迭代定時(shí)器，根據(jù)界面輸入信息，設(shè)置觸發(fā)間隔，即每當(dāng)執(zhí)行到算法仿真功能流程的step4，會(huì)暫停在步驟，直到定時(shí)器喚醒才會(huì)繼續(xù)執(zhí)行后續(xù)判斷和操作。

3 實(shí)驗(yàn)結(jié)果與分析

PSO仿真演示軟件啟動(dòng)后，算法參數(shù)編輯框會(huì)顯示默認(rèn)值。設(shè)置單次迭代時(shí)間、種群規(guī)模N、最大迭代次數(shù)G、測(cè)試函數(shù)類型、搜索空間維數(shù)Dim、搜索空間上限U、搜索空間下限L、學(xué)習(xí)因子c1、學(xué)習(xí)因子c2、慣性權(quán)重ω、最大速度Vmax、最小速度Vmin等參數(shù)后，點(diǎn)擊仿真開始按鈕，軟件開始進(jìn)行PSO仿真實(shí)驗(yàn)。

PSO仿真實(shí)驗(yàn)開始后，每次搜索迭代都會(huì)根據(jù)當(dāng)前最佳適應(yīng)度和當(dāng)前粒子群位置更新軟件右側(cè)的適應(yīng)度進(jìn)化曲線顯示和粒子群分布情況顯示。

點(diǎn)擊暫停按鈕可以暫停算法仿真實(shí)驗(yàn)，同時(shí)暫停按鈕變?yōu)槔^續(xù)按鈕；再次點(diǎn)擊繼續(xù)按鈕，仿真實(shí)驗(yàn)繼續(xù)上次暫停處運(yùn)行。點(diǎn)擊終止按鈕可以人為干涉終止算法仿真實(shí)驗(yàn)。

當(dāng)測(cè)試函數(shù)為Shpere，搜索空間維數(shù)Dim為10，其他參數(shù)為默認(rèn)情況時(shí)，進(jìn)行PSO算法仿真實(shí)驗(yàn)。當(dāng)?shù)螖?shù)t分別為1、30、100、200時(shí)，粒子種群分布情況如圖4所示。

當(dāng)?shù)螖?shù)t達(dá)到最大值時(shí)算法停止搜索，此時(shí)軟件界面和實(shí)驗(yàn)結(jié)果如圖5所示。

4 結(jié)束語

本文通過Windows QT開發(fā)工具，使用QT Designer設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)PSO仿真演示軟件。該軟件可以編輯算法控制參數(shù)和顯示算法仿真實(shí)驗(yàn)過程中每次迭代后的粒子群分布情況。文中首先介紹了PSO基本原理和步驟，然后描述了界面設(shè)計(jì)、算法仿真實(shí)現(xiàn)流程和動(dòng)態(tài)演示流程，對(duì)仿真演示過程進(jìn)行了詳細(xì)說明。最后通過實(shí)驗(yàn)驗(yàn)證，該P(yáng)SO仿真演示軟件很好地進(jìn)行PSO算法仿真和顯示每次迭代搜索后適應(yīng)度進(jìn)化曲線和粒子種群分布情況，仿真演示軟件功能待后續(xù)進(jìn)一步增強(qiáng)。

參考文獻(xiàn)：

[1] Kennedy J，Eberhart R.Particle swarm optimization[C]//Proceedings of 1995 IEEE International Conference on Neural Networks.Piscataway，NJ：IEEE Press，2002：1942-1948.

[2] Shi Y，Eberhart R C.Empirical study of particle swarm optimization[C]// Proceedings of the 1999 Congress on Evolutionary Computation.Piscataway，NJ：IEEE Service Center，1999：1945-1950.

[3] 屈新懷，單笛，孟冠軍.基于靠近目標(biāo)粒子群算法的AGV路徑規(guī)劃[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，45（1）：1-6.

[4] 劉俊賢，王宏強(qiáng)，陶新龍.基于改進(jìn)多目標(biāo)粒子群優(yōu)化算法的雷達(dá)資源分配方法[J].中國(guó)電子科學(xué)研究院學(xué)報(bào)，2022，17（6）：549-556，565.

[5] 朱春夢(mèng)，藍(lán)興英.基于粒子群優(yōu)化算法的化工穩(wěn)態(tài)流程模擬參數(shù)優(yōu)化[J].石油科學(xué)通報(bào)，2022，7（1）：50-60.

[6] 黃紅波，王勇智.基于離散粒子群算法的無線傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化[J].電腦知識(shí)與技術(shù)，2021，17（22）：10-12.

[7] 董翔逸，邵曉根，管瑞林.基于粒子群算法的家庭能量管理系統(tǒng)成本優(yōu)化問題[J].電腦知識(shí)與技術(shù)，2021，17（19）：122-124.

[8] 徐敬.基于QT的Mifare IC卡讀卡器上位機(jī)軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2021，17（33）：124-126.

[9] 許夢(mèng)華.基于Qt的地面模擬飛行控制系統(tǒng)軟件設(shè)計(jì)與實(shí)現(xiàn)[J].電子測(cè)試，2022（1）：29-31，101.

【通聯(lián)編輯：謝媛媛】