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

關(guān)鍵詞：非線性種群縮減；人工蜂群算法；聚類(lèi)；排名；旅行商問(wèn)題

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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］提出的一種建立在蜜蜂自組織型和群體智能基礎(chǔ)上的優(yōu)化算法。由于其參數(shù)簡(jiǎn)單、易于求解和性能優(yōu)異等特點(diǎn)［2］，在解決諸多實(shí)際優(yōu)化問(wèn)題中被成功應(yīng)用，如路徑規(guī)劃、負(fù)荷調(diào)度、系統(tǒng)設(shè)計(jì)以及工程優(yōu)化等［3～7］。但是，基本ABC算法也存在不足之處，由于其擅長(zhǎng)探索而不擅長(zhǎng)開(kāi)發(fā)，往往收斂速度較慢［8］。為了更好地平衡探索和開(kāi)發(fā)，加快它的收斂速度，相關(guān)學(xué)者對(duì)其在初始化策略、種群劃分及調(diào)節(jié)、搜索策略及參數(shù)自適應(yīng)、多策略協(xié)同、鄰域結(jié)構(gòu)、多維改進(jìn)以及概率選擇等方面進(jìn)行了大量的改進(jìn)研究。

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

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

1 基本ABC

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

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

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

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

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

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

pi=fiti∑SNj=1fitj（4）

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

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

2.1 動(dòng)機(jī)

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

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

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

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

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

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

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

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

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

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

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

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

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

a）隨機(jī)選取K個(gè)互不相同的個(gè)體作為聚類(lèi)中心;

b）計(jì)算所有個(gè)體到這K個(gè)個(gè)體的歐氏距離;

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

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

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

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

2.4 時(shí)間復(fù)雜度分析

將融入U(xiǎn)PSR和CIR的ABC與基本ABC在各搜索階段對(duì)比進(jìn)行時(shí)間復(fù)雜度分析。

a）初始化階段。對(duì)種群的初始化，ABC-UPSR+CIR與ABC相同，時(shí)間復(fù)雜度為O（SN×D）；對(duì)食物源的適應(yīng)度值的計(jì)算，ABC-UPSR+CIR與基本ABC相同，時(shí)間復(fù)雜度為O（SN×D）；ABC-UPSR+CIR初始種群進(jìn)行K-means聚類(lèi)，時(shí)間復(fù)雜度為O（SN×K）。

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)

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

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

3.1 有效性檢驗(yàn)

3.1.1 均值和標(biāo)準(zhǔn)差

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

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

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

3.1.2 收斂圖

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

3.2 適應(yīng)性檢驗(yàn)

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

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

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

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

3.4 種群多樣性分析

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

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

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

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

pi=Mi/M（9）

d）種群熵值計(jì)算。

H=-∑Mi=1pilnpi（10）

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

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

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

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

3.6 TSP應(yīng)用問(wèn)題檢驗(yàn)

3.6.1 TSP描述

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

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

b）距離或成本。對(duì)于任意兩個(gè)城市——城市i和j（i≠j），都有一個(gè)與之相關(guān)的非負(fù)距離或成本d（i，j），

這個(gè)距離可以代表兩個(gè)城市之間的實(shí)際距離、時(shí)間、費(fèi)用等等，該屬性具有對(duì)稱(chēng)性，即d（i，j）=d（j，i）。

c）目標(biāo)。旅行推銷(xiāo)員的目標(biāo)是找到一條從出發(fā)城市出發(fā)，訪問(wèn)每個(gè)城市一次，然后返回出發(fā)城市的路徑，使得路徑的總距離或成本最小，這個(gè)路徑就被稱(chēng)為T(mén)SP的解。

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

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

3.6.2 求解TSP的ABC算法

1）解的編碼 假設(shè)某個(gè)TSP實(shí)例中有n個(gè)城市，那么n對(duì)應(yīng)的就是解的維數(shù)（D=n），因此每個(gè)解每一維都由從1到n的數(shù)字組成，每個(gè)數(shù)字代表了城市的編號(hào)。根據(jù)TSP的性質(zhì)可知，任何一個(gè)解的任意兩維對(duì)應(yīng)的城市編號(hào)不可以相同，表示將每個(gè)城市訪問(wèn)且僅訪問(wèn)一次，并最終回到起點(diǎn)。因此，解的編碼由式（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(mài)（11）

其中：Xi代表一個(gè)n維解，包含了n個(gè)互不相同的城市編號(hào)序列。

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

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

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

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

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

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

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

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

b）若vGi，j超過(guò)最大城市編號(hào)，那么肯定存在至少一個(gè)城市編號(hào)在vGi當(dāng)中沒(méi)有出現(xiàn)，因此從中隨機(jī)選擇并替換vGi，j即可。

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

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

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

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

3.6.3 實(shí)驗(yàn)結(jié)果與對(duì)比分析

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

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

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

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

進(jìn)一步選擇burma14、bayg29、oliver30、eil51實(shí)例繪制路徑圖，且將實(shí)例中坐標(biāo)位置按照一定比例進(jìn)行縮放，便于觀察對(duì)比，結(jié)果如圖7所示。

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

4 結(jié)束語(yǔ)

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

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

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

參考文獻(xiàn)：

［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］朱武.基于種群自適應(yīng)策略的差分演化算法及其應(yīng)用研究［D］.上海：東華大學(xué)，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ìn)化算法［J］.計(jì)算機(jī)科學(xué)，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］李瑞，徐華，楊金峰，等.改進(jìn)近鄰人工蜂群算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題［J］.計(jì)算機(jī)應(yīng)用研究，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］趙明，焦劍如，宋曉宇，等.維適應(yīng)人工蜂群算法的研究［J］.小型微型計(jì)算機(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］禹博文，游曉明，劉升.引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，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］陳峰.人工蜂群算法及其應(yīng)用研究［D］.廣州：華南理工大學(xué)，2014.（Chen Feng.Research on artificial bee colony algorithm and its applications［D］.Guangzhou：South China University of Technology，2014.）