基于分區(qū)個體排名的非線性種群縮減的人工蜂群算法

摘 要：針對人工蜂群算法（ABC）探索性強而開發(fā)性弱，從而導致收斂速度慢的問題，提出了一種基于分區(qū)個體排名的非線性種群縮減策略（UPSR-CIR）。首先，該策略設計長尾非線性種群規(guī)?？s減函數(shù)，在前期保持大種群充分探索，中期快速縮減使得后期保持小種群加強開發(fā)，同時為后期分配相對較多計算資源以加速收斂；其次，為確保種群多樣性，采用K-means聚類通過間隔一定代數(shù)對種群進行動態(tài)分區(qū)，并以分區(qū)為單位進行種群縮減；同時，種群按分區(qū)縮減時，按照分區(qū)內最優(yōu)個體在整個種群排名確定刪除個體數(shù)量，為排名高的潛能分區(qū)保留相對較多的計算資源來進一步加強開發(fā)。采用22個基準測試函數(shù)在ABC及其變體上對UPSR-CIR進行實驗對比分析，結果表明UPSR-CIR表現(xiàn)出更高的求解精度、穩(wěn)定性和收斂速度，同時對于ABC變體具有普適性。最后采用12個經(jīng)典旅行商問題（TSP）案例進一步驗證UPSR-CIR在實際應用問題上的實用性和優(yōu)越性。

關鍵詞：非線性種群縮減；人工蜂群算法；聚類；排名；旅行商問題

中圖分類號：TP18 文獻標志碼：A 文章編號：1001-3695（2024）10-020-3021-11

doi：10.19734/j.issn.1001-3695.2024.02.0045

Artificial bee colony algorithm with unlinear population size reduction based on cluster individual rank

Zhao Ming，Liu Shanzhi，Song Xiaoyu，Shen Xiaopeng

（School of Computer Science & Engineering，Shenyang Jianzhu University，Shenyang 110168，China）

Abstract：Aiming at the problem that ABC has strong exploration but weak exploitation，which leads to slow convergence speed，this paper proposed an unlinear population size reduction strategy based on cluster individual rank（UPSR-CIR）.Firstly，the strategy designed the long-tail unlinear population size reduction function which maintained a large population to explore fully in the early stage，and reduced the population size rapidly in the middle stage，so as to maintain a small population to strengthen exploitation in the late stage，while allocating relatively more computing resources for the late stage to accelerate convergence.Secondly，to ensure the diversity of the population，it used K-means clustering dynamically to divide the population into clusters every a certain number of generations，and carried out the population size reduction in the unit of cluster.At the same time，when the population size reducing in the unit of cluster，it determined the number of individuals deleted according to the rank of the best individual in the cluster，so as to reserve relatively more computing resources for the potential cluster with higher rank to further strengthen exploitation.This paper used 22 benchmark test functions to compare and analyze the UPSR-CIR on ABC and its variants.The results show that the UPSR-CIR exhibits higher solution accuracy，stability and convergence speed.It is also universally applicable to ABC variants.Finally，this paper also used 12 classical TSP cases to validate the practicality and superiority of the UPSR-CIR strategy on real application problem.

Key words：unlinear population size reduction;artificial bee colony algorithm;clustering;rank;traveling salesman problem

0 引言

人工蜂群算法（ABC）是Karaboga等人［1］提出的一種建立在蜜蜂自組織型和群體智能基礎上的優(yōu)化算法。由于其參數(shù)簡單、易于求解和性能優(yōu)異等特點［2］，在解決諸多實際優(yōu)化問題中被成功應用，如路徑規(guī)劃、負荷調度、系統(tǒng)設計以及工程優(yōu)化等［3～7］。但是，基本ABC算法也存在不足之處，由于其擅長探索而不擅長開發(fā)，往往收斂速度較慢［8］。為了更好地平衡探索和開發(fā)，加快它的收斂速度，相關學者對其在初始化策略、種群劃分及調節(jié)、搜索策略及參數(shù)自適應、多策略協(xié)同、鄰域結構、多維改進以及概率選擇等方面進行了大量的改進研究。

文獻［9］提出了一種新的初始解生成策略，該策略保存了過去每次實驗產(chǎn)生的初始解，并且在每次重新產(chǎn)生初始解時以一定的概率重新使用它們，該策略有效減少了產(chǎn)生初始解所用的函數(shù)評估次數(shù)。文獻［10］在雇傭蜂階段將整個種群劃分為兩個不同的子種群，并對不同的子種群采用不同的搜索策略。文獻［11］提出了一種調節(jié)雇傭蜂和跟隨蜂數(shù)量的機制，進一步在雇傭蜂階段和跟隨蜂階段分別采用了兩個參數(shù)自適應的微分搜索方程。文獻［12］考慮了局部最優(yōu)解、鄰域最優(yōu)解和迭代最優(yōu)解的優(yōu)勢，提出了一種在雇傭蜂階段和跟隨蜂階段的臨時解搜索策略。文獻［7］提出了一種基于鄰域搜索的多策略協(xié)作，將當前種群和鄰域中的最優(yōu)個體信息分別應用于雇傭蜂和跟隨蜂的搜索，在此基礎上進一步引入修正率對解的各個維度進行隨機擾動。文獻［13］引入最大熵上位計算連續(xù)函數(shù)的維交互，以指導雇傭蜂和跟隨蜂搜索方程的適應選擇。文獻［14］引入了一種維度內存機制實現(xiàn)多維更新。文獻［15］在跟隨蜂階段采用一種定制的雙型精英引導開發(fā)機制，通過一種新的輪盤賭選擇概率計算范式來調節(jié)有希望的精英蜜源的開發(fā)強度。文獻［6］使用貝葉斯估計的概率計算方式代替原來的選擇概率計算方式。從以上相關研究可以看出，對于影響ABC性能的組成要素上，相關學者都已經(jīng)進行了大量改進研究，但對于種群規(guī)模這一算法核心參數(shù)的調節(jié)尚未見到系統(tǒng)研究。而近年來，其他群體智能優(yōu)化算法尤其是差分進化算法（differential evolution algorithm，DE）的研究學者發(fā)現(xiàn)，算法初期需要大規(guī)模種群覆蓋整個搜索空間，后期需要縮小種群規(guī)模來節(jié)約計算資源，加強后期開發(fā)能力［16］。與此同時為了避免陷入局部最優(yōu)，需要在搜索過程中保持種群多樣性［16］。因而關于種群的規(guī)模和調節(jié)方面，有了一些研究成果。為了提高收斂速度和優(yōu)化效果，文獻［17］針對SHADE算法提出了線性種群規(guī)模縮減的L-SHADE算法，每代種群個體按照適應度由大到小排序，以線性規(guī)律縮減排序靠后的適應度小的個體，實驗結果表明L-SHADE明顯優(yōu)于SHADE。為了提升Self-adaptive DE算法的優(yōu)化效果，文獻［18］提出了種群折半縮減的dynNP-DE，當算法迭代到一定次數(shù)時，把相對優(yōu)秀的個體放入前一半，把后一半的個體刪除，實驗結果發(fā)現(xiàn)該算法在高維問題上表現(xiàn)得非常好。為了保護pr-DE算法的種群多樣性，文獻［19］將K-means聚類法應用于pr-DE算法進而提出了Dapr-DE算法，在種群中隨機選擇一些核心向量，其余個體距離哪個核心向量近就將該個體劃分給那個核心向量從而形成聚類，然后根據(jù)聚類情況計算熵值來調整每個聚類的大小，實驗表明K-means有助于在種群縮減過程中防止種群多樣性的大量丟失。

本文在以上相關研究的基礎上，根據(jù)ABC善于探索而不善于開發(fā)的特點對其進行種群規(guī)?？s減策略的深入研究。首先，根據(jù)大種群有利于探索而小種群有利于開發(fā)的理論，受sigmoid函數(shù)啟發(fā)，提出了長尾非線性種群規(guī)?？s減函數(shù)，前期利用大種群確保全面探索解空間，中期快速進行種群縮減以便后期充分利用小種群進行開發(fā)以加速收斂，同時為了充分彌補ABC開發(fā)不足這一缺點，利用長尾效應為后期小種群分配更多計算資源;其次，由于種群規(guī)?？s減會導致多樣性損失從而求解容易陷入局部最優(yōu)，利用K-means聚類算法對種群進行分區(qū)，在種群規(guī)?？s減時以分區(qū)為單位進行個體移除，相對于以整個種群為單位該方法能夠通過確保分區(qū)對解空間的覆蓋來保護多樣性;最后，在確定分區(qū)移除個體數(shù)量時應考慮為更具潛能的分區(qū)保留更多開發(fā)可能，為最優(yōu)個體在種群中排名較高的分區(qū)保留相對于其他分區(qū)較多的個體以實現(xiàn)保留相對較多的計算資源分配。

1 基本ABC

ABC模擬蜂群的智能覓食行為，包括雇傭蜂、跟隨蜂和偵查蜂［20］三種蜜蜂。雇傭蜂主要承擔蜂群的覓食工作，它們會在原食物源的附近尋找更好的食物源，并通過擺尾舞與跟隨蜂分享食物源的質量等信息；每只跟隨蜂則會通過雇傭蜂所提供的信息，選擇一個特定的食物源進行進一步開發(fā)；當某個食物源連續(xù)若干代沒有得到改進時，該食物源對應的雇傭蜂就會變?yōu)閭刹榉?，并隨機尋找新的食物源?；続BC包括初始化階段、雇傭蜂階段、跟隨蜂階段和偵查蜂階段四個階段。在初始化階段，創(chuàng)建包括SN個解的初始種群P，對應食物源的初始位置，其中SN表示食物源的數(shù)量。在搜索空間上，每個初始解x0i=（x0i，1，x0i，2，…，x0i，D）均采用式（1）隨機產(chǎn)生。

x0i，j=xL，j+rand（0，1）×（xU，j-xL，j）（1）

其中：i=1，2，…，SN，j=1，2，…，D，D表示搜索空間的維數(shù)；xL，j和xU，j分別是第j維的下界和上界;rand（0，1）表示［0，1］的隨機實數(shù)。食物源的質量對應優(yōu)化問題解的適應度，適應度越大，對應解的質量就越好。食物源的適應度值采用式（2）進行計算。

fiti=11+fiif fi≥01+|fi|otherwise（2）

其中：fiti和fi是食物源xi的適應度值和目標函數(shù)值。

初始化階段之后，ABC變成了雇傭蜂階段、跟隨蜂階段和偵查蜂階段的循環(huán)，直到滿足終止條件為止。在雇傭蜂階段，食物源與雇傭蜂為一一對應的關系，即一個食物源對應一個雇傭蜂。每只雇傭蜂都保留了它之前搜索過程中的最優(yōu)解，并且在保留的最優(yōu)解的鄰域搜索候選解。如果搜索到的新解適應度值不低于原來保留的解，原來的解就會被新的解所取代；否則，原來的解就會被保留下來。對食物源xi產(chǎn)生候選食物源vi時，雇傭蜂使用的搜索方程為

vGi，j=xGi，j+i，j×（xGi，j-xGk，j）（3）

其中：G表示代數(shù)；k從{1，2，…，SN}當中隨機選擇并且k≠i，j從{1，2，…，D}當中隨機選擇；i，j是［-1，1］的隨機實數(shù)。當雇傭蜂完成搜索過程，就會與跟隨蜂分享食物源的質量信息和位置。在跟隨蜂階段，每只跟隨蜂會根據(jù)食物源對應的選擇概率以輪盤賭的方式隨機選擇一個食物源，共有SN只跟隨蜂，食物源選擇概率的計算方法如式（4）所示。

pi=fiti∑SNj=1fitj（4）

其中：pi為食物源xi的選擇概率，顯然食物源的適應度值越大，選擇概率就越大。在跟隨蜂選擇一個食物源后，采用式（3）產(chǎn)生一個候選食物源，并采用與雇傭蜂一樣的方式進行貪婪選擇。當所有跟隨蜂完成搜索過程時，如果一個食物源的質量沒有在預定的循環(huán)次數(shù)（limit）內得到改善，該食物源對應的雇傭蜂就會變成偵查蜂并采用式（1）隨機尋找新的食物源取代原來的食物源。最后，當算法循環(huán)達到最大函數(shù)評估次數(shù)（MAX_NFE）時，算法終止循環(huán)并輸出搜索到的最優(yōu)解信息。

2 基于分區(qū)個體排名的非線性種群縮減

2.1 動機

由于大種群有利于探索小種群且有利于開發(fā)［16］，受到sigmoid非線性函數(shù)的啟發(fā)，設計ABC的非線性種群規(guī)模縮減函數(shù)，在前期保持大種群以實現(xiàn)對解空間全局進行充分探索，中期種群規(guī)?？焖俜蔷€性縮減，后期保持小種群以便更加充分利用計算資源加強開發(fā)。同時，考慮到ABC開發(fā)能力差導致收斂速度慢這一弱點，適當為后期的小種群搜索分配更多的計算資源，進而形成了長尾非線性種群規(guī)?？s減函數(shù)，從而更好地平衡ABC的探索與開發(fā)能力。

在縮減的過程中如何盡可能維持多樣性以避免陷入局部最優(yōu)，這是種群縮減應考慮并必須解決的核心問題，也是算法能否找到全局最優(yōu)的一個核心影響因素。在確定了整個種群的規(guī)?？s減策略后，利用K-means聚類通過間隔一定代數(shù)對種群進行動態(tài)分區(qū)，同時以分區(qū)為單位進行種群縮減，通過確保分區(qū)覆蓋更好地保護種群多樣性以確保全局探索性。在種群按分區(qū)縮減時，還應考慮各分區(qū)進化潛能的區(qū)別，對更有希望的區(qū)域應保留相對較多的個體，因而對分區(qū)按照其范圍內最優(yōu)個體在整個種群的排名確定刪除個體數(shù)量，從而為更有潛質的分區(qū)保留相對較多的計算資源以便加大對其的開發(fā)。

2.2 非線性種群縮減策略（UPSR）

原始sigmoid函數(shù)圖像為非線性單調遞增，如式（5）所示，原圖像如圖1所示。

S（x）=11+e-x（5）

顯然，sigmoid函數(shù)無法直接應用于ABC的非線性單調遞減的種群縮減，因此將函數(shù)進行一系列對稱、平移以及縮放，最終變形如式（6）所示。

SNG=SNmin+（SNmax-SNmin）×（11+e20×NFEGMAXNFE-10）（6）

其中：SNG代表G代雇傭蜂和跟隨蜂的種群規(guī)模;SNmin和SNmax分別代表種群規(guī)模的下限和上限;NFEG表示G代前已耗用函數(shù)評估次數(shù)。種群規(guī)模隨著搜索過程變化的圖像如圖2所示（以SNmin=30，SNmax=100，MAX_NFE=150000為例）。根據(jù)圖2不難發(fā)現(xiàn)，算法前期、中期和后期使用的計算資源大體相同，前期保持大種群充分探索，中期快速進行縮減，后期保持小種群加強開發(fā)從而加速收斂?？紤]到ABC本身探索性強而開發(fā)性弱，進一步對三個階段的計算資源分配進行調整，適當縮短前期并擴大后期，以便讓算法更加側重于后期開發(fā)來加快收斂，因而將縮減函數(shù)由式（6）調整為式（7），種群規(guī)模隨著搜索過程變化的圖像如圖3所示。

SNG=SNmin+（SNmax-SNmin）×11+e25×NFEGMAX_NFE-10（7）

對式（7）進行深入分析，SN初始為SNmax（此時NFE為0），在NFEG/MAX_NFE為1/4時，SN為0.98SNmax+0.02SNmin（由SNmin+0.98（SNmax-SNmin）計算得），與SNmax差距微小，也就是在搜索前期種群規(guī)模基本維持在最大規(guī)模；隨著搜索繼續(xù)，NFEG/MAX_NFE持續(xù)增長，種群規(guī)模開始快速下降，在NFEG/MAX_NFE為1/2時，SN為0.08SNmax+0.92SNmin（由SNmin+0.08（SNmax-SNmin）計算得），非常接近于SNmin，實現(xiàn)了搜索的中期種群規(guī)模的快速縮減；而后直至搜索結束，種群規(guī)模維持在SNmin，表明搜索階段的后期種群規(guī)模最小。可見，這三個階段NFE即計算資源的分配比例為1∶1∶2（由1/4∶（1/2-1/4）∶（1-1/2）計算得），也就是為后期分配計算資源達到整體的一半，對種群規(guī)模的調節(jié)控制實現(xiàn)了長尾效應。

2.3 基于分區(qū)個體排名的移除（CIR）

通過聚類可以將當前種群中相似的個體聚集成分區(qū)，不同的分區(qū)可以代表解空間的不同區(qū)域。在種群縮減時從不同的區(qū)域刪除個體，相對于從整個種群中進行個體刪除，能夠更好地保留種群對解空間的覆蓋。因此，每間隔c代采用K-means基于歐氏距離對種群進行聚類，動態(tài)反映種群分區(qū)情況。在確定種群縮減數(shù)量后，基于每個分區(qū)最優(yōu)個體在整個種群中的排名確定各分區(qū)刪除個體數(shù)量，使得最優(yōu)個體排名靠前的分區(qū)相對保留較多個體，以保留較多計算資源從而保證對潛能區(qū)域的開發(fā)。

基于歐氏距離的K-means算法具體步驟如下：

a）隨機選取K個互不相同的個體作為聚類中心;

b）計算所有個體到這K個個體的歐氏距離;

c）找到每個個體距離最近的聚類中心，并將該個體劃分給距離最近的聚類中心形成類簇。

每代通過式（7）確定本代種群規(guī)模后，采用式（8）確定本代每個分區(qū)的個體縮減數(shù)量。

deleteSNGk=（SNG-1-SNG）×rank（bestGk）/∑Kk=1rank（bestGk）（8）

其中：deleteSNGk表示第k個分區(qū)的個體縮減數(shù)量（k=1，…，K）；SNG-1-SNG表示G代種群縮減數(shù)量；rank（bestGk）表示G代種群中第k個分區(qū)的最優(yōu)個體在整個種群當中按照適應度從大到小的排名。從式（8）可以看出，某個分區(qū)的最優(yōu)個體在整個種群中的排名越高，表示該分區(qū)存在全局最優(yōu)的可能性就越大，就越需要對其加強開發(fā)，因而為其縮減較少的個體以保留相對較多的計算資源。在確定每個分區(qū)的個體縮減數(shù)量后，以輪盤賭選擇的方式選擇分區(qū)個體進行刪除，既有利于保護種群多樣性，同時傾向于刪除沒有潛力的個體。

2.4 時間復雜度分析

將融入UPSR和CIR的ABC與基本ABC在各搜索階段對比進行時間復雜度分析。

a）初始化階段。對種群的初始化，ABC-UPSR+CIR與ABC相同，時間復雜度為O（SN×D）；對食物源的適應度值的計算，ABC-UPSR+CIR與基本ABC相同，時間復雜度為O（SN×D）；ABC-UPSR+CIR初始種群進行K-means聚類，時間復雜度為O（SN×K）。

b）人工蜂搜索階段。ABC-UPSR+CIR在每間隔c代對種群進行K-means聚類，時間復雜度為O（SN×K）；ABC-UPSR+CIR算法在每代計算本代種群規(guī)模，時間復雜度為O（1）；ABC-UPSR+CIR算法計算每個聚類最優(yōu)個體在整個種群中的排名，時間復雜度為O（SN+SN×K），即O（SN×K）；ABC-UPSR+CIR計算每個聚類縮減個體數(shù)量，時間復雜度為O（K）；ABC-UPSR+CIR對每個聚類按照適應度輪盤賭刪除個體，時間復雜度為O（SN）。此后的雇傭蜂搜索和跟隨蜂搜索，ABC-UPSR+CIR與ABC相同，時間復雜度分別為O（SN）。

c）偵查蜂搜索階段。ABC-UPSR+CIR與ABC相同，時間復雜度為O（SN）。

通過以上分析可以看出，ABC-UPSR+CIR與ABC相比較，整個算法在各階段額外增加的時間復雜度量級分別為O（SN×K）、O（1）、O（K）和O（SN），由于K的建議取值為D/10，所以ABC-UPSR+CIR的時間復雜度最大量級仍為O（SN×D），與ABC相同。整個ABC-UPSR+CIR的流程如圖4所示。

3 實驗設計

本文主要進行六個實驗：實驗1驗證非線性種群縮減策略（UPSR）以及基于分區(qū)個體排名的個體移除策略（CIR）對于ABC的有效性，將其與線性種群縮減策略（LPSR）和折半種群縮減策略（dynNP）進行對比分析，并分別采用多次運行求解結果的均值和標準差評價求解精度和穩(wěn)定性，進一步繪制收斂圖評價收斂性；實驗2驗證兩者對其他ABC變種算法的普適性，將它們分別融入兩個近年來性能良好的ABC變體ARABC［21］、DFSABC_elite［22］和DAABC［23］，分別采用多次運行求解結果均值和標準差對比分析原算法與新算法的求解精度和穩(wěn)定性；實驗3驗證參數(shù)K-means聚類數(shù)量K對ABC性能的影響，分別對其設置不同的初值后，采用多次運行求解結果均值和標準差來分析它對算法求解精度和穩(wěn)定性的影響，并給出建議設置；實驗4分析融入UPSR和CIR兩個策略后的ABC在種群多樣性方面的特性，基于種群熵［19］指標對求解各階段種群的多樣性進行計算，并將其與基本ABC對比；實驗5分析融入UPSR和CIR的ABC在不同階段的尋優(yōu)能力，輸出前期大種群探索階段、中期種群快速縮減階段及后期小規(guī)模開發(fā)階段算法多次運行的求解結果均值與標準差，并將其與基本ABC對比分析性能變化；實驗6采用應用問題對UPSR和CIR進行進一步有效性驗證，對比分析ABC和融入兩個策略的改進ABC在求解經(jīng)典TSP時的求解精度和穩(wěn)定性，分別采用多次運行求解得到的平均NqaKQQQS6AY0b8cnz/CzbQ==路徑長度、最優(yōu)路徑長度、最差路徑長度和偏差率作為評價標準，并進一步繪制對應點坐標路徑圖進行直觀對比。

實驗1～5使用的測試集為DFSABC_elite所提出的測試集［22］，共包含了22個測試函數(shù)，基準函數(shù)如表1所示。其中，f1-f6和f8為連續(xù)單峰函數(shù)，f7是非連續(xù)階躍函數(shù)，f9為噪聲函數(shù)。f10為Rosenbrock函數(shù)（維數(shù)D≤3時為單峰函數(shù)，維數(shù)D>3時為多峰函數(shù)），f11～f22為多峰函數(shù)，并且它們的局部最優(yōu)點隨著問題規(guī)模的增加呈指數(shù)增加。實驗3使用的測試集為不同規(guī)模的經(jīng)典TSP實例，共包含12個，城市數(shù)最少為14，最多為150，分別為burma14、bayg29、oliver30、att48、eil51、eil76、pr76、st70、gr96、eil101、ch130和ch150。實驗平臺采用英特爾酷睿i5-7300HQ CPU，基準速度為2.50 GHz，使用Windows 10操作系統(tǒng)，編程語言為C++，編譯器為CodeBlocks GNU GCC。

3.1 有效性檢驗

3.1.1 均值和標準差

本實驗使用了均值和標準差兩個評價指標，均值越小，說明算法的求解精度越高；標準差越小，說明算法的穩(wěn)定性越好。實驗參數(shù)設置如下：D=30，MAX_NFE=5000×D，SNmax=3×D，SNmin=D，limit=200，K=D/10，聚類間隔代數(shù)c=100，運行次數(shù)runtime=30。實驗結果如表2所示，表中從左至右依次為無種群縮減的ABC（NPSR）、種群規(guī)模線性縮減的ABC（LPSR）、基于分區(qū)個體排名進行移除的種群規(guī)模線性縮減的ABC（LPSR+CIR）、種群規(guī)模折半縮減的ABC（dynNP）、基于分區(qū)個體排名進行移除的種群規(guī)模折半縮減的ABC（dynNP+CIR）、種群規(guī)模非線性縮減的ABC（UPSR）、基于分區(qū)個體排名進行移除的種群規(guī)模非線性縮減的ABC（UPSR+CIR）。

由表2可以看出，NPSR、LPSR、LPSR+CIR、dynNP、dynNP+CIR、UPSR和UPSR+CIR分別在1、2、3、2、6、13和10個函數(shù)上取得了最優(yōu)。并且由表2可以看出，UPSR與UPSR+CIR在其他不是表現(xiàn)最佳的函數(shù)上與最佳結果相比數(shù)量級相同或僅僅相差一個數(shù)量級，說明性能差異不大。從以上結果及分析可以看出，相對于無種群縮減的ABC，分別加入線性縮減策略、折半縮減策略和非線性縮減策略后，在22個函數(shù)上的求解均值及標準差全部減小，說明這三種種群縮減策略都能夠顯著提高ABC的求解精度和穩(wěn)定性。為了進一步精確對比各種縮減策略以及它們融入CIR后的性能差異，依據(jù)表2中的數(shù)據(jù)進行兩兩相關的Wilcoxon秩和檢驗，結果如表3所示。

從表3可以看出，對于線性縮減策略和折半縮減策略，非線性縮減策略的求解性能顯著優(yōu)越（p_value遠小于0.05）。加入CIR策略后，線性縮減策略和折半縮減策略的求解性能進一步顯著提升（p_value遠小于0.05）。與加入CIR策略的線性縮減和折半縮減對比，加入CIR的非線性縮減策略的性能具有顯著優(yōu)越性（p_value遠小于0.05）。

3.1.2 收斂圖

繪制ABC融入各種種群策略后在每個函數(shù)上的收斂圖，如圖5所示，其中橫軸為函數(shù)評估次數(shù)，縱軸為目標函數(shù)值的對數(shù)。從圖5可以看出，UPSR與UPSR+CIR策略在絕大多數(shù)測試函數(shù)上的收斂速度均快于其他種群縮減策略。并且值得注意的是，在收斂速度上尤其是在算法后期收斂速度上，UPSR與UPSR+CIR策略都表現(xiàn)得十分優(yōu)秀，明顯優(yōu)于其他現(xiàn)有種群縮減策略。這也再次說明了非線性種群縮減策略與基于分區(qū)個體排名的非線性種群縮減策略可以更好地平衡ABC的探索與開發(fā)能力，同時證明了它們在搜索后期對種群多樣性有更好的保護作用。

3.2 適應性檢驗

實驗公共參數(shù)設置與2.6節(jié)相同，ARABC、DFSABC_elite和DAABC三個算法的其他參數(shù)設置源于其提出文獻，實驗結果如表4所示，表4最后一行為Wilcoxon秩和檢驗結果。從表4可以看出，融入UPSR和CIR的ARABC、DFSABC_elite和DAABC與原算法對比，性能顯著提升（p_value遠小于0.05），說明本文提出的兩個策略對于其他ABC變體具有普適性。

3.3 參數(shù)敏感性分析

為了驗證本文引入?yún)?shù)K-means聚類數(shù)量K對ABC-UPSR+CIR性能的影響，分別設置K為2、D/10、D/5和D進行實驗，其他參數(shù)設置同2.6節(jié)，實驗結果如表5所示。

從表5可以看出，當K增大到D/5后，對f11和f12的求解性能顯著下降，沒有求得全局最優(yōu)值；K為D/10時，雖然表現(xiàn)最優(yōu)的函數(shù)數(shù)量為8，小于K為2時的12，但表現(xiàn)不是最優(yōu)的函數(shù)求解結果與K為2時差距不大?？紤]到隨著問題維數(shù)D的增加，算法應適度隨之增加聚類個數(shù)以便以較多的分區(qū)覆蓋搜索空間，因此本文建議K的取值為D/10。

3.4 種群多樣性分析

種群熵是衡量算法種群多樣性的一個重要指標，計算熵H的方法如下［19］：設當前種群有NP個個體，算法進化過程中迄今得到的最優(yōu)個體和最差個體的適應度值分別為fmax，和fmin。

a）解空間表示。εmin=（1-δ）×fmin，εmax=（1+δ）×fmax，δ=0.1，則解空間S可以用［εmin，εmax］表示，區(qū)間長度λ=εmax-εmin。

b）解空間分割。把區(qū)間［εmin，εmax］分成M（M=NP）個小區(qū)間［εmin+λ（i-1）/M，εmax+λ（i-1）/M］，統(tǒng)計每一區(qū)間的個體數(shù)Ni（i=1，2，…，M）。

c）計算個體出現(xiàn)在第i個區(qū)間的概率pi。

pi=Mi/M（9）

d）種群熵值計算。

H=-∑Mi=1pilnpi（10）

種群熵越大說明種群多樣性越大，算法越傾向于探索；種群熵越小說明種群多樣性越小，算法越傾向于收斂和開發(fā)。本文從22個函數(shù)中選出具有代表性的函數(shù)，其中包括2個單峰函數(shù)和2個多峰函數(shù)，以500×D次函數(shù)評價為間隔，繪制種群熵隨之變化的曲線，如圖6所示?？梢钥闯觯N群熵隨著函數(shù)評價次數(shù)的增加整體上呈現(xiàn)下降趨勢，說明種群隨著搜索的進行，不斷地收斂；ABC-UPSR與ABC-UPSR+CIR由于種群規(guī)?？s減損失一部分多樣性，尤其在搜索的中后期隨著種群規(guī)模的快速下降，多樣性不如種群規(guī)模不變的ABC，但總體損失不大；此外，ABC-UPSR+CIR的種群熵明顯略高于ABC-UPSR，這說明基于聚類的CIR策略在移除個體時更好地保護了種群多樣性。

3.5 階段尋優(yōu)能力分析

為了驗證具有UPSR+CIR策略的ABC能夠在搜索各階段表現(xiàn)出更好的尋優(yōu)能力，在實驗1的基礎上，

分別輸出NFE為37 500、75 000以及110 000時（分別對應前期大種群探索階段結束、中期種群快速縮減階段結束以及后期小規(guī)模開發(fā)階段中間），ABC和ABC-UPSR+CIR求解每個測試函數(shù)獲得的均值和標準差，結果如表6所示。從表6可以看出，相比于ABC，ABC-UPSR+CIR的求解精度和穩(wěn)定性，在所有的22個函數(shù)上無論在前期、中期和后期均表現(xiàn)更優(yōu)，充分說明了UPSR+CIR策略在各階段都能表現(xiàn)出更好的尋優(yōu)能力。

3.6 TSP應用問題檢驗

3.6.1 TSP描述

TSP（traveling salesperson problem）是一個經(jīng)典的組合優(yōu)化問題，通常用來描述如下情境：假設有一個旅行推銷員，他需要訪問一系列城市，并最終回到出發(fā)城市，保證每個城市都會被訪問并且僅被訪問一次，同時確?？傂谐套疃蹋?4］，形式化描述如下：

a）城市集合。有一個包含n個城市的集合，通常用C={1，2，…，j，…，n}表示，j代表城市編號。

b）距離或成本。對于任意兩個城市——城市i和j（i≠j），都有一個與之相關的非負距離或成本d（i，j），

這個距離可以代表兩個城市之間的實際距離、時間、費用等等，該屬性具有對稱性，即d（i，j）=d（j，i）。

c）目標。旅行推銷員的目標是找到一條從出發(fā)城市出發(fā)，訪問每個城市一次，然后返回出發(fā)城市的路徑，使得路徑的總距離或成本最小，這個路徑就被稱為TSP的解。

TSP被認為是NP難問題，目前沒有已知的多項式時間算法可以解決所有實例。對于小規(guī)模問題，可以使用精確方法（如窮舉法或分支定界法）找到最優(yōu)解；

對于大規(guī)模問題，通常需要使用智能優(yōu)化算法來尋找近似最優(yōu)解。TSP在物流規(guī)劃、電路設計、DNA測序、旅游路線規(guī)劃等很多領域具有重要應用價值。

3.6.2 求解TSP的ABC算法

1）解的編碼 假設某個TSP實例中有n個城市，那么n對應的就是解的維數(shù)（D=n），因此每個解每一維都由從1到n的數(shù)字組成，每個數(shù)字代表了城市的編號。根據(jù)TSP的性質可知，任何一個解的任意兩維對應的城市編號不可以相同，表示將每個城市訪問且僅訪問一次，并最終回到起點。因此，解的編碼由式（11）表示。

Xi={Xi，0，Xi，1，…，Xi，j，…，Xi，u，…，Xi，n-1}Xi，j∈{1，2，…，n}Xi，j≠Xi，uj，u∈{0，1，…，n-1}，j≠u（11）

其中：Xi代表一個n維解，包含了n個互不相同的城市編號序列。

2）初始化階段 初始化的過程本質上就是生成隨機解的過程，隨機生成SNmax個互不相同解，本文將初始種群大小設置為3×n，以便覆蓋整個搜索空間。

每個初始解中的每個城市編號均以隨機選擇的方式生成，假設一個初始解中隨機選擇的第一個城市編號為i，那么這個初始解中第二個城市編號就從{1，2，…，i-1，i+1，…，n}當中隨機選擇一個城市編號j，第三個城市編號就從{1，2，…，i-1，i+1，…，j-1，j+1，…，n}當中隨機選擇，以此類推，直到所有的城市編號都被選擇一次。

值得注意的是，城市的數(shù)量n越大，初始解的數(shù)量也越大。如果某個TSP有n個城市，那么就有（n-1）！/2個解［25］。因此，3×n個解當中存在相同解的概率可以由式（12）計算。

P=C23n1（（n-1）！/2）2（12）

由式（12）不難看出，僅當n=10時，概率P值約為千萬分之一。當n取更大值時，P值會更加接近0。因此在大多數(shù)TSP實例中，不必考慮初始解重復的可能性問題。

3）適應度函數(shù)計算 在TSP中，解的路徑長度與它的目標函數(shù)值相對應。一個合法的解序列就是一個旅行商需要依次經(jīng)過的城市序列。在計算了某個解對應的路徑長度后，計算適應度的方法與基本ABC相同。解的路徑長度越長，它的函數(shù)值就越大，適應度值就越小，質量就越差。

4）雇傭蜂階段 本文在解決TSP時，雇傭蜂所使用的搜索方程與基本ABC相同。需要特別說明的是，在使用式（3）生成vGi，j以后，需要對vGi，j進行解的合法性檢查與校正，避免其存在不符合約束條件的情況。vGi，j中共包含了n個元素，可能存在的不合理情況以及處理方式如下：

a）若vGi，j為負值，僅需對其取絕對值進行校正即可。此外，若vGi，j為非整型數(shù)值，則對其向下取整即可。

b）若vGi，j超過最大城市編號，那么肯定存在至少一個城市編號在vGi當中沒有出現(xiàn)，因此從中隨機選擇并替換vGi，j即可。

c）若vGi，j=vGi，u（j≠u），即存在重復的城市編號，這與TSP中每個城市訪問且僅訪問一次產(chǎn)生了矛盾。顯然如果一個城市編號重復出現(xiàn)兩次，則至少存在一個城市編號未出現(xiàn)，因此找到?jīng)]有出現(xiàn)城市編號來隨機替換即可。

5）跟隨蜂階段 跟隨蜂所采用的搜索方程與雇傭蜂相同，并采用與雇傭蜂相同的合法性檢查和校正方法。本文中跟隨蜂選擇食物源的方法與基本ABC相同，即輪盤賭選擇方式。

6）偵查蜂階段 偵查蜂也是在某個解（即路徑）連續(xù)limit次沒有得到更新時，如果這個解不是當前全局最優(yōu)解就拋棄這個解，并且隨機產(chǎn)生新的可行解進行替換。

7）種群縮減與個體移除 將UPSR-CIR融入基本ABC應用于優(yōu)化TSP，并且與無種群縮減策略的ABC進行實驗對比，UPSR-CIR策略的詳細過程在之前已經(jīng)有詳細介紹，本小節(jié)恕不贅述。

3.6.3 實驗結果與對比分析

將求解TSP的基本ABC和融入UPSR-CIR的ABC分別在12個經(jīng)典TSP實例上進行實驗驗證分析，并對比兩者多次求解獲得的平均路徑長度、最優(yōu)路徑長度、最差路徑長度以及偏差率，并且給出每個算法求得的最優(yōu)路徑。其中，路徑長度反映了求解的質量，偏差率反映了解之間的離散程度；路徑長度越小說明解的質量越高，偏差率越小說明算法的穩(wěn)定性越好。偏差率的計算方法如式（13）所示。

偏差率=（求解每個實例獲得的最優(yōu)路徑長度-該實例已知最優(yōu)路徑長度）該實例已知最優(yōu)路徑長度×100%（13）

本實驗中MAX_NFE設置為10000×D，其余實驗參數(shù)設置與4.2節(jié)相同。實驗結果如表7所示。對表7中的實驗結果進行匯總，列出每個算法在平均路徑長度、最優(yōu)路徑長度、最差路徑長度以及偏差率表現(xiàn)最好的TSP實例，結果如表8所示。

由表8可以看出，融入UPSR-CIR的ABC在平均路徑長度、最優(yōu)路徑長度、最差路徑長度以及偏差率上均在大多數(shù)實例上優(yōu)于基本ABC，可見本文UPSR-CIR策略的有效性以及在實際應用問題上的適用性。

進一步選擇burma14、bayg29、oliver30、eil51實例繪制路徑圖，且將實例中坐標位置按照一定比例進行縮放，便于觀察對比，結果如圖7所示。

從圖7可以看出，加入UPSR-CIR策略的ABC在求解經(jīng)典TSP實例時表現(xiàn)出明顯的優(yōu)勢，其求得的路徑圖比基本ABC更優(yōu)。這是由于UPSR-CIR策略充分利用了大種群的探索優(yōu)勢以及小種群的開發(fā)優(yōu)勢，保護了種群多樣性進而更好地平衡了探索與開發(fā)能力，避免了計算資源的不必要浪費。

4 結束語

為了平衡ABC的探索性和開發(fā)性，提高它的收斂速度，本文利用大種群有利于探索而小種群有利于開發(fā)的原理，設計了非線性種群縮減策略UPSR；為了在保持種群多樣性的同時進一步增加開發(fā)性，通過K-means動態(tài)分區(qū)確保對搜索空間的覆蓋，同時根據(jù)分區(qū)個體排名確定分區(qū)移除個體數(shù)量，形成了基于分區(qū)個體排名的個體移除策略CIR。

在22個基準測試函數(shù)上的對比分析實驗結果表明，相對于其他種群縮減策略，UPSR-CIR在ABC上表現(xiàn)出更好的求解質量、更強的穩(wěn)定性和更快的收斂速度；對于ARABC、DFSABC_elite和DAABC三個ABC變體，UPSR-CIR性能的優(yōu)越性表現(xiàn)出了普適性；而后對聚類數(shù)量做了參數(shù)敏感性分析并且證明了本文選擇的聚類數(shù)量的合理性；并且在算法不同階段通過實驗證明了UPSR-CIR策略的優(yōu)越性；最后，在12個TSP經(jīng)典實例上的實驗結果進一步表明UPSR-CIR策略具有實際應用價值。

在后續(xù)研究中，在差分進化等其他智能優(yōu)化算法上進一步驗證分析UPSR-CIR策略的適用性，并在多目標以及離散多約束等工程優(yōu)化問題方面進一步拓展其實際應用領域。

參考文獻：

［1］Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：artificial bee colony（ABC）algorithm［J］.Journal of Global Optimization，2007，39（3）：459-471.

［2］Etminaniesfahani A，Gu H，Salehipour A.ABFIA：a hybrid algorithm based on artificial bee colony and Fibonacci indicator algorithm［J］.Journal of Computation Science，2022，61：101651.

［3］Cui Yibing，Hu Wei，Rahmani A.A reinforcement learning based artificial bee colony algorithm with application in robot path planning［J］.Expert Systems with Application，2022，203：117389.

［4］Ni Xinrui，Hu Wei，F(xiàn)an Qiaochu，et al.A Q-learning based multi-strategy integrated artificial bee colony algorithm with application in unmanned vehicle path planning［J］.Expert Systems with Application，2024，236：121303.

［5］Sutar M，Jadhav H T.A modified artificial bee colony algorithm based on a non-dominated sorting genetic approach for combined economic-emission load dispatch problem［J］.Applied Soft Computing，2023，144：110433.

［6］Wang Chunfeng，Shang Pengpeng，Shen Peiping.An improved artificial bee colony algorithm based on Bayesian estimation［J］.Complex & Intelligent Systems，2022，8（6）：4971-4991.

［7］Li Xing，Zhang Shaoping，Yang Le，et al.Neighborhood-search-based enhanced multi-strategy collaborative artificial bee colony algorithm for constrained engineering optimization［J］.Soft Computing：A Fusion of Foundations，Methodologies and Applications，2023，27（19）：13991-14017.

［8］Ye Tingyu，Wang Wenjun，Wang Hui，et al.Artificial bee colony algorithm with efficient search strategy based on random neighborhood structure［J］.Knowledge-Based Systems，2022，241：108306.

［9］Gao Hao，F(xiàn)u Zheng，Pun C M，et al.An efficient artificial bee colony algorithm with an improved linkage identification method［J］.IEEE Trans on Cybernetics，2020，52（6）：4400-4414.

［10］Xu Minyang，Wang Wenjun，Wang Hui，et al.Multipopulation artificial bee colony algorithm based on a modified probability selection model［J］.Concurrency and Computation：Practice and Experience，2021，33（13）：e6216.

［11］Cui Yibing，Hu Wei，Ahmed R.Improved artificial bee colony algorithm with dynamic population composition for optimization problems［J］.Nonlinear Dynamics，2022，107（1）：743-760.

［12］Thirugnanasambandam K，Rajeswari M，Bhattacharyya D，et al.Direc-ted artificial bee colony algorithm with revamped search strategy to solve global numerical optimization problems［J］.Automated Software Engineering，2022，29（1）：13.

［13］Zhao Fuqing，Wang Zhenyu，Wang Ling，et al.An exploratory landscape analysis driven artificial bee colony algorithm with maximum entropic epistasis［J］.Applied Soft Computing，2023，137：110139.

［14］Naser C，Miri M，Rashki M.An adaptive artificial neural network for reliability analyses of complex engineering systems［J］.Applied Soft Computing，2023，132：109866.

［15］Yu Haibo，Kang Yaxin，Kang Li，et al.Bi-preference linkage-driven artificial bee colony algorithm with multi-operator fusion［J］.Complex & Intelligent Systems，2023，9（6）：6729-6751.

［16］朱武.基于種群自適應策略的差分演化算法及其應用研究［D］.上海：東華大學，2013.（Zhu Wu.Research on differential evolution algorithm based on population adaptive strategy and its applications［D］.Shanghai：Donghua University，2013.）

［17］Tanabe R，F(xiàn)ukunaga A S.Improving the search performance of shade using linear population size reduction［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2014：1658-1665.

［18］Brest J，Mauec M S.Population size reduction for the differential evolution algorithm［J］.Applied Intelligence，2007，29：228-247.

［19］單天羽，管煜旸.基于種群多樣性的可變種群縮減差分進化算法［J］.計算機科學，2018，45（Z2）：160-166.（Shan Tianyu，Guan Yuyang.Differential evolution algorithm with adaptive population size reduction based on population diversity［J］.Computer Science，2018，45（Z2）：160-166.）

［20］李瑞，徐華，楊金峰，等.改進近鄰人工蜂群算法求解柔性作業(yè)車間調度問題［J］.計算機應用研究，2024，41（2）：438-443.（Li Rui，Xu Hua，Yang Jinfeng，et al.Improved algorithm of near-neighbor artificial bee colony for flexible job-shop scheduling［J］.Application Research of Computers，2024，41（2）：438-443.）

［21］Cui Laizhong，Li Genghui，Wang Xizhao，et al.A ranking-based adaptive artificial bee colony algorithm for global numerical optimization［J］.Information Sciences，2017，417：169-185.

［22］Cui Laizhong，Li Genghui，Lin Qiuzhen，et al.A novel artificial bee colony algorithm with depth-first search framework and elite-guided search equation［J］.Information Sciences，2016，367-368：1012-1044.

［23］趙明，焦劍如，宋曉宇，等.維適應人工蜂群算法的研究［J］.小型微型計算機系統(tǒng)，2024，45（3）：562-569.（Zhao Ming，Jiao Jianru，Song Xiaoning，et al.Research on improved adaptive artificial bee colony algorithm［J］.Journal of Chinese Computer Systems，2024，45（3）：562-569.）

［24］禹博文，游曉明，劉升.引入動態(tài)分化和鄰域誘導機制的雙蟻群優(yōu)化算法［J］.計算機應用研究，2023，40（10）：3000-3006.（Yu Bowen，You Xiaoming，Liu Sheng.Dual-ant colony optimization algorithm with dynamic differentiation and neighborhood induction mechanism［J］.Application Research of Computers，2023，40（10）：3000-3006.）

［25］陳峰.人工蜂群算法及其應用研究［D］.廣州：華南理工大學，2014.（Chen Feng.Research on artificial bee colony algorithm and its applications［D］.Guangzhou：South China University of Technology，2014.）