一種非線性因子的粘性二進(jìn)制粒子群算法

摘? 要：為了解決粘性二進(jìn)制粒子群算法在優(yōu)化過程中易陷入局部最優(yōu)、全局搜索能力弱、后期收斂性能差的弊端，提出了一種非線性因子的粘性二進(jìn)制粒子群算法（NFSBPSO）。NFSBPSO算法采用非線性遞減策略優(yōu)化粘性權(quán)重，平衡全局與局部探索能力；同時(shí)，利用混沌策略對(duì)種群進(jìn)行初始化，在每個(gè)迭代過程中對(duì)最差和最優(yōu)粒子進(jìn)行優(yōu)化，以提高種群質(zhì)量，擴(kuò)大種群的全局探索能力。將新算法與3個(gè)對(duì)比算法在基準(zhǔn)函數(shù)上進(jìn)行測(cè)試，實(shí)驗(yàn)表明新的算法能較好地跳出局部最優(yōu)，提高了算法的穩(wěn)定性和收斂能力。

關(guān)鍵詞：非線性因子；混沌策略；粒子優(yōu)化；粘性二進(jìn)制粒子群算法

中圖分類號(hào)：TP301? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：2096-4706（2023）03-0061-05

A Nonlinear Factor Sticky Binary Particle Swarm Optimization

CHENG Qianqian

（Taiyuan Normal University， Jinzhong? 030619， China）

Abstract： In order to solve the disadvantages of sticky binary particle swarm optimization， which is easy to fall into local optimum， weak global search ability and poor late convergence performance in the process of optimization， a nonlinear factor sticky binary particle swarm optimization （NFSBPSO） is proposed. NFSBPSO algorithm uses nonlinear decreasing strategy to optimize the sticky weight and balance the global and local exploration ability. At the same time， the chaos strategy is used to initialize the population， and the worst and best particles are optimized in each iteration process to improve the quality of the population and expand the global exploration ability of the population. The new algorithm is tested on the benchmark function with three comparison algorithms. The experimental results show that the new algorithm can jump out of the local optimum better and improve the stability and convergence ability of the algorithm.

Keywords： nonlinear factor; chaos strategy; particle optimization; sticky binary particle swarm optimization

0? 引? 言

Kennedy等人于1995年提出的粒子群算法（Particle Swarm Optimization， PSO）[1]作為群智能優(yōu)化算法，因其具有參數(shù)少、運(yùn)算簡(jiǎn)單和收斂速度快等特點(diǎn)受到廣大學(xué)者的關(guān)注，此算法多用來(lái)處理連續(xù)函數(shù)的優(yōu)化。針對(duì)離散域上存在的問題，Kennedy等人于1997年進(jìn)一步提出了二進(jìn)制粒子群算法（Binary Particle Swarm Optimization， BPSO）[2]。BPSO算法與PSO算法相比，盡管全局搜索能力較強(qiáng)，但是仍不能很好地收斂到全局最優(yōu)位置，并且算法的隨機(jī)性隨著迭代次數(shù)的漸增而增大，局部搜索能力越來(lái)越弱[3，4]。2019年Nguyen等人所發(fā)表的粘性二進(jìn)制粒子群算法（Stickiness Binary Particle Swarm Optimization， SBPSO）[5]，采用了粘性和翻轉(zhuǎn)的思想，使算法更適用于離散問題，尋優(yōu)的效果更佳。與粒子群算法相似，這些離散粒子群優(yōu)化算法也存在早熟收斂問題[6-8]，相關(guān)學(xué)者針對(duì)這一問題提出了改進(jìn)策略。李真等人[9]提出將灰狼算法與粒子群算法相結(jié)合，增加了粒子的收斂速度；李浩君等人[10]提出慣性權(quán)重和種群多樣性協(xié)同調(diào)整的策略，增強(qiáng)了算法的動(dòng)態(tài)搜索的能力和種群多樣性；孫一凡等人[11]提出了一種粒度散度指標(biāo)，并將模擬退火機(jī)制與粘性二進(jìn)制粒子群算法相結(jié)合，平衡了算法的探索和開發(fā)能力；王皓等人[12]提出了對(duì)粒子進(jìn)行鄰域搜索和擾動(dòng)，加快了收斂速度。邱飛岳等人[13]利用混沌策略和成長(zhǎng)因子來(lái)均衡全局與局部搜索的能力。王越等人[14]提出對(duì)慣性權(quán)重采用一種非線性遞增的方法，將變異算子加入速度公式中，增強(qiáng)了粒子的種群多樣性和尋優(yōu)范圍。

雖然上述研究通過不同的策略對(duì)粒子群算法進(jìn)行了優(yōu)化，但在處理離散問題時(shí)，算法的性能還需要進(jìn)一步的提升。本文從算法易陷入局部最優(yōu)，探索和開發(fā)能力不平衡的問題出發(fā)，利用Logistic混沌策略初始化種群，采用非線性的策略改變粘性權(quán)重，并且對(duì)進(jìn)化過程中對(duì)最差和最優(yōu)粒子進(jìn)行優(yōu)化，提出了一種非線性因子的粘性二進(jìn)制粒子群算法（Nonlinear Factor Stickiness Binary Particle Swarm Optimization， NFSBPSO）。

1? 粘性二進(jìn)制粒子群算法

1.1? 二進(jìn)制粒子群算法

傳統(tǒng)的二進(jìn)制粒子群算法（BPSO）與粒子群算法（PSO）所用的速度更新公式一樣，而BPSO算法將映射函數(shù)應(yīng)用到位置公式上，也就是說將粒子的速度映射到[0，1]區(qū)間，如果映射值小于隨機(jī)數(shù)，則位置取0，反之取1。PSO算法應(yīng)用在連續(xù)域的問題上，而BPSO算法應(yīng)用于處理離散域的問題。式（1）為速度更新公式，式（2）為映射函數(shù)，式（3）為位置更新公式：

（1）

（2）

（3）

其中，j為維度，vij （t+1）為粒子i在t+1次迭代的速度，w為慣性權(quán)重，c1和c2分別為自我和社會(huì)學(xué)習(xí)因子，r1和r2為[0，1]中的隨機(jī)變量，xij （t）為第i個(gè)粒子的當(dāng)前位置；pbestij為個(gè)體歷史最優(yōu)解，gbestij為全局最優(yōu)解；T（vij （t））為映射函數(shù)，表示速度映射的概率值。

為了使PSO算法可以解決離散問題，因此引入了映射函數(shù)，但在離散問題中直接使用PSO的速度和位置公式并不能直觀的描述離散空間的速度和位置，因此有學(xué)者提出了粘性二進(jìn)制粒子群算法。

1.2? 粘性二進(jìn)制粒子群算法

粘性二進(jìn)制粒子群算法（SBPSO）可以更加精準(zhǔn)地描述粒子的運(yùn)動(dòng)狀態(tài)，即粒子的翻轉(zhuǎn)代替為粒子運(yùn)動(dòng)，粒子的翻轉(zhuǎn)速率則為粒子的運(yùn)動(dòng)速率。粘性是指在離散域中，粒子運(yùn)動(dòng)維持當(dāng)前比特位不變的概率值。該算法在解決離散問題中效果比BPSO算法有一定的提升。速度和位置更新公式如式（4）（5）所示。

（4）

（5）

其中，xij（t）的值為0或1，is為粘性權(quán)重，stkij（t）為第i個(gè)粒子的粘性，也就是說當(dāng)粒子剛發(fā)生翻轉(zhuǎn)后，stkij（t）值為1，并使該粒子保持一段時(shí)間的平衡，但粘性值會(huì)隨著迭代次數(shù)的增加而不斷衰減，直至再次翻轉(zhuǎn)或者粘性為0。SBPSO算法采用式（6）動(dòng)態(tài)參數(shù)控制策略來(lái)平衡算法的探索和開發(fā)能力，相關(guān)參數(shù)如式（7）～（9）所示：

（6）

（7）

（8）

（9）

（10）

其中，is+ip+ig=1，，is_u和is_l分別為粘性權(quán)重is的上限和下限，t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)；ustk為粒子的粘性值從1衰減到0所需的迭代次數(shù)，ustk_u和ustk_l分別為ustk的上限和下限。

通過實(shí)驗(yàn)發(fā)現(xiàn)該算法在一定條件下容易陷入局部最優(yōu)。當(dāng)粒子處于全局最優(yōu)的位置時(shí)，翻轉(zhuǎn)概率僅由動(dòng)量和粘性衰減決定，通過大量的迭代使得粘性衰減來(lái)獲得翻轉(zhuǎn)概率，這不僅耽誤了算法尋優(yōu)的進(jìn)程，而且不利于實(shí)現(xiàn)算法探索與開發(fā)之間的平衡。該算法在大型和復(fù)雜的搜索空間上表現(xiàn)良好，但在小型的搜索空間上尋優(yōu)效果并沒有顯著提升，因此，需要對(duì)參數(shù)進(jìn)行非線性的更新機(jī)制。

2? 非線性因子粘性二進(jìn)制粒子群算法

2.1? 非線性因子is

粘性權(quán)重is的大小影響著算法的探索和開發(fā)的能力。當(dāng)is的值較大時(shí)，提高了粒子的翻轉(zhuǎn)概率，有利于探索；當(dāng)is的值較小時(shí)，降低了粒子的翻轉(zhuǎn)概率，有利于開發(fā)，避免陷入局部最優(yōu)。對(duì)于粘性權(quán)重is來(lái)說，線性遞減不能有效的解決所有的尋優(yōu)問題，當(dāng)問題較為復(fù)雜時(shí)，局部搜索能力逐漸降低，找不到所要求的最優(yōu)解。

SBPSO算法采用的典型的線性遞減的策略來(lái)改變粘性權(quán)重的值。但因?yàn)槠湫甭时３植蛔儯苑D(zhuǎn)概率的改變速率持續(xù)性降低，在迭代初期還沒有很好地找到全局最優(yōu)解便會(huì)進(jìn)入局部搜索，從而使算法陷入局部最優(yōu)解。因此，采用指數(shù)函數(shù)? 對(duì)粘性權(quán)重函數(shù)進(jìn)行改進(jìn)。

但是在? 公式中，曲線在最高點(diǎn)維持的時(shí)間較短且粘性權(quán)重的值在迭代結(jié)束后不能收斂到最小值，而當(dāng)t/T為六次冪且系數(shù)為-20時(shí)，最高點(diǎn)和最低點(diǎn)維持的時(shí)間均衡，有利于平衡前后期探索和開發(fā)的能力。

因此，本文提出一個(gè)非線性的is因子（Nonlinear Factor， NF），如式（11）所示，以平衡算法的探索和開發(fā)能力。非線性is曲線圖如圖1所示。

（11）

由圖1可以看出，當(dāng)最大迭代次數(shù)為200次時(shí)，is在前50次迭代過程中能保持在最大值附近，可以更好地進(jìn)行全局搜索，在后50次迭代過程中能保持在最小值附近，以便于迭代前期全局搜索能力與迭代后期局部搜索能力的良好平衡。

2.2? 混沌初始化策略

粘性二進(jìn)制粒子群算法的初始種群是通過隨機(jī)策略生成的，其種群分布較差，質(zhì)量不高。為了提高種群的質(zhì)量，NFSBPSO算法采用Logistic映射進(jìn)行混沌初始化，如式（12）所示：

（12）

其中，μ表示混沌程度，μ的值越大，混沌程度越高；實(shí)驗(yàn)得出，當(dāng)μ=4時(shí)，系統(tǒng)的混沌狀態(tài)最佳。在映射過程中，若xt≥0.5，xt=1；若xt＜0.5，xt=0。

2.3? 粒子優(yōu)化策略

SBPSO算法在迭代過程中所有粒子會(huì)向最優(yōu)粒子位置運(yùn)動(dòng)，造成種群多樣性降低，影響了粒子從局部最優(yōu)跳出。本文通過借鑒最優(yōu)粒子擾動(dòng)策略和最差粒子更新策略來(lái)改進(jìn)NFSBPSO算法，提高算法后期的搜索能力。

2.3.1? 最差粒子更新策略

在粒子群算法中，一直秉承著“優(yōu)勝劣汰”的生存法則，為了提高最差粒子的質(zhì)量，在迭代過程中其進(jìn)行更新操作。最差粒子更新策略就是改進(jìn)種群中適應(yīng)度最糟糕的粒子，目的是增加種群的多樣性，進(jìn)而提高搜索能力。最差適應(yīng)度粒子改進(jìn)公式如式（13）（14）（15）所示：

（13）

（14）

（15）

其中，x_worst表示適應(yīng)度最糟糕的粒子；式（14）中Eworst表示更新后的粒子，也就是在每次迭代完成后，隨機(jī)性地選取三個(gè)不同的粒子進(jìn)行更新。式（15）表示，如果更新后粒子的適應(yīng)度值小于最差粒子，則將最差粒子更新為Eworst；反之保留最差粒子。

2.3.2? 最優(yōu)粒子擾動(dòng)策略

在SBPSO算法中，種群的全局最優(yōu)解會(huì)影響所有粒子朝著最優(yōu)解的方向移動(dòng)，從而導(dǎo)致后期發(fā)生聚集現(xiàn)象，所以本文根據(jù)種群的聚集程度，對(duì)全局最優(yōu)解的位置進(jìn)行擾動(dòng)，從而擴(kuò)大種群的全局搜索能力。

判斷種群聚集程度的公式如式（16）（17）所示：

（16）

（17）

其中，avg_x表示N個(gè)粒子的中心位置，avg_r表示種群中N個(gè)粒子到avg_x的平均距離。若avg_r值較大，表示粒子分布比較散，種群多樣性較強(qiáng)，則對(duì)全局最優(yōu)解產(chǎn)生的干擾較小。若avg_r值較小的話，表示粒子分布比較緊密，導(dǎo)致種群已經(jīng)陷入局部最優(yōu)或者多樣性降低，則對(duì)全局最優(yōu)解產(chǎn)生的干擾較大。

本文采用的擾動(dòng)策略如式（18）（19）所示，對(duì)全局最優(yōu)解產(chǎn)生的擾動(dòng)大小由公式中的指數(shù)函數(shù)所決定，而上文說明了擾動(dòng)大小與avg_r呈負(fù)相關(guān)，因此指數(shù)函數(shù)與avg_r呈負(fù)相關(guān)：

（18）

（19）

其中Nbest（t）代表被干擾后的粒子，如果Nbest（t）的適應(yīng)度值低于被干擾之前的適應(yīng)度值，則被干擾后的粒子為全局最優(yōu)粒子；否則不進(jìn)行更新。

2.4? NFSBPSO算法步驟

本文在粘性二進(jìn)制粒子群算法的基礎(chǔ)上，采取混沌策略、非線性粘性權(quán)重以及粒子優(yōu)化策略，提出了NFSBPSO算法，算法步驟如下：

Step1：采用Logistic混沌策略初始化種群；

Step2：參數(shù)初始化；

Step3：計(jì)算適應(yīng)度值，并對(duì)種群個(gè)體進(jìn)行歷史最優(yōu)解及全局最優(yōu)解的更新；

Step4：更新非線性因子is；

Step5：對(duì)適應(yīng)度值最糟糕的粒子進(jìn)行改進(jìn)；

Step6：針對(duì)粒子的全局最優(yōu)位置進(jìn)行擾動(dòng)，根據(jù)擾動(dòng)后粒子的適應(yīng)度判斷是否需要更換全局最優(yōu)解；

Step7：更新粒子的速度和位置；

Step8：對(duì)算法的終止條件進(jìn)行判斷，如果滿足條件就輸出最優(yōu)解；如果不滿足，則返回步驟3。

3? 仿真實(shí)驗(yàn)

3.1? 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用MATLAB語(yǔ)言編程，Window 10操作系統(tǒng)，Intel（R） Core（TM） i5-6200U CPU 處理器，主頻為2.40 GHz。

3.2? 實(shí)驗(yàn)設(shè)置

本文選取了六種基準(zhǔn)函數(shù)來(lái)對(duì)算法進(jìn)行了性能測(cè)試與評(píng)價(jià)，如表1所示。F1、F2、F3是單峰函數(shù)且只具有一個(gè)最優(yōu)解，可用于判斷算法的收斂性能；F4、F5、F6是多峰函數(shù)且具有多個(gè)局部最優(yōu)解，可以用來(lái)判斷算法跳出局部最優(yōu)解的能力。對(duì)比算法為BPSO算法[2]，SBPSO算法[5]，動(dòng)態(tài)自均衡二進(jìn)制粒子群算法（Dynamic self-equilibrium binary particle swarm optimization， DSEBPSO）[15]。種群規(guī)模N=30，最大迭代次數(shù)T=200。根據(jù)先驗(yàn)經(jīng)驗(yàn)，粘性值上限 ，下限 ；自適應(yīng)因子上限 ，下限 。根據(jù)文獻(xiàn)[5]可知α=2時(shí)，尋優(yōu)效果更佳。

實(shí)驗(yàn)采用以下兩種標(biāo)準(zhǔn)來(lái)評(píng)價(jià)算法的性能：

（1）均值：4個(gè)算法運(yùn)行30次后，獲得最優(yōu)值的均值。

（2）方差：4個(gè)算法運(yùn)行30次后，獲得最優(yōu)值的方差。

3.3? 實(shí)驗(yàn)結(jié)果分析

NFSBPSO算法和三個(gè)對(duì)比算法在六個(gè)基準(zhǔn)函數(shù)上的收斂曲線如圖2所示。

由圖2可知，NFSBPSO算法在收斂速度、跳出局部最優(yōu)解等方面都要比其他算法好。由于迭代時(shí)粘性權(quán)重的非線性調(diào)整，使得單峰函數(shù)在尋優(yōu)過程中適應(yīng)值變化迅速，尋優(yōu)成功率與收斂精度也顯著增加。對(duì)于局部最優(yōu)解較多的多峰函數(shù)問題，該算法使用粒子優(yōu)化策略對(duì)適應(yīng)度值較差的粒子加以改進(jìn)，以提高其種群的多樣性，同時(shí)對(duì)全局最優(yōu)粒子加以干擾，促進(jìn)其跳出局部最優(yōu)從而使得算法能夠做出較好的局部探索。

NFSBPSO算法和三個(gè)對(duì)比算法在六個(gè)基準(zhǔn)函數(shù)上的實(shí)驗(yàn)結(jié)果如表2所示。

單峰函數(shù)僅有一個(gè)局部最優(yōu)解來(lái)檢測(cè)其收斂精度。從表2中可以看出，在單峰函數(shù)F1、F2、F3中，NFSBPSO算法的均值比其他算法好，表明該算法比BPSO、SBPSO以及DSEBPSO算法具有更高的收斂精度。多峰函數(shù)具有多個(gè)局部最優(yōu)解來(lái)評(píng)價(jià)算法是否能夠跳出局部最優(yōu)。從表2中可以看出，在多峰函數(shù)F4、F5、F6中，NFSBPSO算法的均值明顯好于其他算法，表明其具有更強(qiáng)的跳出局部最優(yōu)解能力。整體來(lái)看，NFSBPSO算法的方差在單峰函數(shù)和多峰函數(shù)中，均優(yōu)于其余算法，說明算法的穩(wěn)定性也有了進(jìn)一步的提升。

4? 結(jié)? 論

本文提出的NFSBPSO算法在參數(shù)上采用了非線性策略，使算法在收斂性能上得到了提升。為了均衡算法的探索和開發(fā)能力，在迭代過程中使用最差粒子改進(jìn)策略和最優(yōu)粒子擾動(dòng)策略，提高了算法的尋優(yōu)能力。但在運(yùn)行過程中發(fā)現(xiàn)不斷地優(yōu)化和改進(jìn)使得算法的時(shí)間復(fù)雜度較高，需要在以后的工作中研究改進(jìn)。

參考文獻(xiàn)：

[1] KENNEDY J，EBERHART R. Particle swarm optimization [C]//IEEE International Conference on Neural Networks，Perth：IEEE，1995：1942-1948．

[2] KENNEDY J，EBERHART R C. A discrete binary version of the particle swarm algorithm [C]//International conference on Systems.Orlando：IEEE，1997：4104-4108.

[3] 張鵬威.采用正弦映射與擴(kuò)張算子的二進(jìn)制粒子群優(yōu)化算法 [J].小型微型計(jì)算機(jī)系統(tǒng)，2019，40（6）：1160-1164.

[4] 趙遠(yuǎn)東，方正華.帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法 [J].計(jì)算機(jī)應(yīng)用，2013，33（8）：2265-2268.

[5] NGUYEN B H，XUE B，ANDREAE P，et al. A new binary particle swarm optimization approach：momentum and dynamic balance between exploration and exploitation [J].IEEE Transations on Cyberntics，2021，51（2）：589-603.

[6] 姜磊，劉建華，張冬陽(yáng)，等.一種自適應(yīng)變異二進(jìn)制粒子群算法 [J].福建工程學(xué)院學(xué)報(bào)，2020，18（3）：273-279.

[7] PAN A Q ，WANG L，GUO W A. A diversity enhanced multiobjective particle swarm optimization [J].Information Sciences：An International Journal，2018，436-437：441+465.

[8] 徐浩天，季偉東，孫小晴，等.基于正態(tài)分布衰減慣性權(quán)重的粒子群優(yōu)化算法 [J].深圳大學(xué)學(xué)報(bào)：理工版，2020，37（2）：208-213.

[9] 李真，王帆，王冉珺.一種結(jié)合灰狼算法的粒子群優(yōu)化算法 [J].計(jì)算機(jī)測(cè)量與控制，2021，29（10）：217-222.

[10] 李浩君，張廣，王萬(wàn)良.一種慣性權(quán)重與種群多樣性協(xié)同調(diào)整的二進(jìn)制粒子群優(yōu)化算法 [J].小型微型計(jì)算機(jī)系統(tǒng)，2018，39（3）：529-533.

[11] 孫一凡，張紀(jì)會(huì).基于模擬退火機(jī)制的自適應(yīng)粘性粒子群算法 [J].控制與決策，1-10[2022-09-03].https：//kns.cnki.net/kcms/detail/detail.aspx？dbcode=CAPJ&dbname=CAPJLAST&filename=KZYC20220512001&uniplatform=NZKPT&v=SFfl7Znyzm7G6kYM3mYnqTigMmGf3EFhaf0-oqT7JD8EXhm3pVm_PJiZON1c2qsz.

[12] 王皓，歐陽(yáng)海濱，高立群.一種改進(jìn)的全局粒子群優(yōu)化算法 [J].控制與決策，2016，31（7）：1161-1168.

[13] 邱飛岳，王京京.自適應(yīng)學(xué)習(xí)因子的混沌二進(jìn)制粒子群優(yōu)化算法 [J].浙江工業(yè)大學(xué)學(xué)報(bào)，2020，48（4）：411-417.

[14] 王越，邱飛岳，郭海東.一種帶變異算子的自適應(yīng)慣性權(quán)重二進(jìn)制粒子群優(yōu)化算法 [J].小型微型計(jì)算機(jī)系統(tǒng)，2019，40（4）：733-737.

[15] 李浩君，吳嘉銘，戴海容.基于多維關(guān)聯(lián)本體的學(xué)習(xí)資源推薦方法 [J].浙江工業(yè)大學(xué)學(xué)報(bào)，2021，49（4）：374-383.

作者簡(jiǎn)介：程倩倩（1997—），女，漢族，山西運(yùn)城人，碩士研究生在讀，研究方向：教育軟件開發(fā)技術(shù)。

收稿日期：2022-09-21