劉書勇，劉 峰

(哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001)

0 引言

蟻群優(yōu)化(Ant Colony Optimization, ACO)算法是由Dorigo等[1]從自然界螞蟻覓食中獲取靈感而提出的一種啟發(fā)式全局優(yōu)化算法,廣泛地應(yīng)用于旅行商問題(Travelling Salesman Problem,TSP),但其容易陷入局部最優(yōu)且存在收斂速度較慢等問題。由于其具備較強(qiáng)的魯棒性,易與其他算法相結(jié)合[2],因此作為眾多學(xué)者的算法改進(jìn)的焦點(diǎn)。劉雨青等[3]對(duì)信息素更新策略進(jìn)行改進(jìn),張玉茹等[4]對(duì)路徑規(guī)劃算法進(jìn)行改進(jìn),基于傳統(tǒng)ACO算法進(jìn)行更新。Stodola等[5]融合模擬退火思想,提高解的質(zhì)量。Zhang等[6]采用反向路徑構(gòu)造方法,避免陷入過早成熟現(xiàn)狀,但增加了信息素更新的復(fù)雜性。徐巍等[7]融入遺傳算法突變因子強(qiáng)化傳統(tǒng)蟻群的局部變異性。陳琴等[8]引入禁忌搜索算法思想,增強(qiáng)全局搜索能力。Caprio等[9]引入模糊數(shù),切換概念進(jìn)行權(quán)重優(yōu)化,以快速達(dá)到收斂狀態(tài),但是在蟻群的分工協(xié)作上略有不足。馮振輝等[10]引入了一種不依賴于信息素搜索路徑的擴(kuò)展螞蟻,實(shí)現(xiàn)抑制算法向局部最優(yōu)的收斂速度,但降低了算法搜索的速度。文獻(xiàn)[11-12]將蟻群劃分多級(jí)蟻態(tài),以提高優(yōu)質(zhì)解與非優(yōu)質(zhì)解路徑上的信息素濃度差距,證明了分級(jí)思想應(yīng)用于ACO的可行性。

基于此,本文引入人工蜂群(Artificial Bee Colony,ABC)分級(jí)思想[13],提出了一種多級(jí)蟻態(tài)蟻群改進(jìn)(Multistage State Ant Colony Optimization,MSACO)算法,主要工作如下:

①基于適應(yīng)度算子將蟻群分為王蟻、被雇傭蟻與非雇傭蟻;

②提出一種限制因子動(dòng)態(tài)平衡蟻態(tài);

③引入加權(quán)因子改進(jìn)信息素更新模型;

④提出一種應(yīng)用于局部?jī)?yōu)化的鄰域因子與固定鄰域優(yōu)化算法。

1 ACO算法

真實(shí)世界中的螞蟻在移動(dòng)中會(huì)釋放信息素,當(dāng)遇到未經(jīng)過的岔路口時(shí)會(huì)隨機(jī)選擇,并釋放與路徑長(zhǎng)度有關(guān)的信息素[14]。隨著移動(dòng)次數(shù)的增加,蟻群會(huì)偏向于選擇信息素濃度高的方向進(jìn)行移動(dòng),意味著選擇該路徑會(huì)經(jīng)過更少的路程,因此信息素濃度與路徑長(zhǎng)度成反比。后來的螞蟻再次路過該岔路口時(shí),會(huì)有更大的幾率被選擇,最優(yōu)路徑上的信息素濃度逐漸增大,較其他路徑上的信息素濃度差距變大,直到找到全局最優(yōu)的覓食路徑。

針對(duì)于TSP,蟻群算法對(duì)基本的覓食行為進(jìn)行改進(jìn)。初始化信息素濃度如式(1)所示:

(1)

式中:τij(0)為節(jié)點(diǎn)i到節(jié)點(diǎn)j邊上的信息素初始濃度,τ0為信息素濃度常數(shù)。

設(shè)定禁忌表強(qiáng)制螞蟻進(jìn)行合法周游,在每次迭代開始前,會(huì)隨機(jī)將m只螞蟻隨機(jī)分配在n個(gè)節(jié)點(diǎn)上作為初始位置。隨后進(jìn)行算法核心的迭代操作,可概括為兩部分:路徑構(gòu)建與信息素更新。

1.1 路徑構(gòu)建

ACO算法模型規(guī)定在每次迭代中,當(dāng)前第k只螞蟻從節(jié)點(diǎn)i移動(dòng)的下一個(gè)節(jié)點(diǎn)j的是基于偽隨機(jī)概率規(guī)則的輪盤賭算法選擇的,如式(2)所示:

(2)

本文提出的MSACO算法延用了ACO用于構(gòu)建路徑時(shí)所采用的偽隨機(jī)規(guī)則,其優(yōu)勢(shì)在于:在算法初期,基于路徑上的信息素濃度與期望啟發(fā)式,可以快速構(gòu)建有效路徑,通過修正啟發(fā)式因子改變信息素對(duì)路徑規(guī)劃的引導(dǎo)能力,α值越大,信息素濃度對(duì)路徑選擇起著越關(guān)鍵的作用;通過修正期望啟發(fā)因子改變期望度對(duì)于路徑規(guī)劃的引導(dǎo)能力,β值越大,螞蟻會(huì)以越大的概率轉(zhuǎn)移到距離短的城市,如果節(jié)點(diǎn)過于密集則適當(dāng)增大期望啟發(fā)因子,會(huì)生成更加優(yōu)質(zhì)的路線。

1.2 信息素更新

ACO算法模型規(guī)定在算法每次迭代后都會(huì)對(duì)所有路徑上的信息素濃度進(jìn)行更新,包括信息素?fù)]發(fā)與信息素補(bǔ)充,如式(3)～式(4)所示:

依據(jù)不同的增量方式可以將信息素更新模型劃分為:蟻周模型(Ant-Cycle Model)、蟻量模型(Ant-Quantity Model)與蟻密模型(Ant-Density Model)這3類[15]。

①蟻周模型:在第k只螞蟻完成一次迭代操作之后,會(huì)對(duì)線路上所有路徑上的信息素濃度進(jìn)行更新,信息素增量與本次搜索的整體路線有關(guān),因此屬于全局信息更新,如式(5)所示:

(5)

②蟻量模型:在蟻群前進(jìn)過程中每完成一步移動(dòng)之后會(huì)對(duì)單步路徑上的信息素濃度進(jìn)行更新,信息素增量與單步路徑有關(guān),屬于局部信息更新,如式(6)所示:

(6)

③蟻密模型:與蟻量模型類似,也屬于局部信息更新,但是信息素增量固定,如式(7)所示:

(7)

2 MSACO算法

2.1 引入分級(jí)策略

2.1.1 ABC算法分級(jí)策略

ABC算法是由Karaboga等[16]提出的一種新穎的基于群智能的全局優(yōu)化算法,其直觀背景來源于蜂群的采蜜行為,蜜蜂根據(jù)各自分工執(zhí)行相應(yīng)工作,并實(shí)現(xiàn)信息的共享和交流,從而找到問題的最優(yōu)解[17]。該算法的三大角色,分別為蜜源、被雇傭的蜜蜂和未被雇傭的蜜蜂。蜜源即為吸引蜜蜂采蜜的地方,相當(dāng)于優(yōu)化問題的可行解。被雇傭的蜜蜂也稱為引領(lǐng)蜂。有多少個(gè)蜜源就對(duì)應(yīng)著多少個(gè)引領(lǐng)蜂。引領(lǐng)蜂具有記憶功能,將自己搜索到的蜜源信息進(jìn)行存儲(chǔ),并以一定的概率分享給跟隨蜂。非雇傭蜂有2種,分別為偵察蜂和跟隨蜂,偵查蜂會(huì)在搜索空間中尋找新蜜源,而跟隨蜂會(huì)隨機(jī)選擇引領(lǐng)蜂的蜜源進(jìn)行跟隨或者進(jìn)行局部?jī)?yōu)化。

2.1.2 引入適應(yīng)度分級(jí)算子

傳統(tǒng)ACO算法中的蟻群個(gè)體根據(jù)式(2)構(gòu)建路徑、式(3)更新信息素,并不能充分體現(xiàn)啟發(fā)式算法的多樣性,因此本文通過引入ABC算法的分級(jí)策略,發(fā)揮引領(lǐng)蜂即被雇傭蜂能夠?qū)ふ覂?yōu)良蜜源的作用,采用非雇傭蜂偵查新蜜源跳出局部最優(yōu)的策略,二者相輔相成,構(gòu)建完整的蜂巢系統(tǒng)。

基于以上思想,本文將傳統(tǒng)蟻群劃分為被雇傭蟻、非雇傭蟻與王蟻。被雇傭蟻對(duì)應(yīng)被雇傭蜂,采用ACO路徑規(guī)劃策略尋找路徑,集中優(yōu)勢(shì)路徑使用高濃度動(dòng)態(tài)的信息素增量進(jìn)行更新策略,用以加速算法的收斂速度。非雇傭蟻對(duì)應(yīng)非雇傭蜂,負(fù)責(zé)偵查新食物源,使算法能夠盡量避免陷入局部最優(yōu)的狀態(tài),保證了算法的多樣性。王蟻用以累計(jì)保存最優(yōu)解,采用最高加權(quán)系數(shù)的信息素更新策略,用以突出最優(yōu)解路徑與非最優(yōu)解路徑的上的信息素濃度的差距,能夠加快算法的收斂速度。在ABC算法中,基于適應(yīng)度算子計(jì)算目標(biāo)函數(shù)權(quán)值對(duì)應(yīng)的適應(yīng)度fit用以判斷該蜜源的優(yōu)劣,本文借鑒適應(yīng)度的概念,將其作為蟻群分級(jí)的指標(biāo),用以平衡算法的多樣性與收斂速度。適應(yīng)度算子如式(8)～式(9)所示:

式中:distancek為當(dāng)前第k只螞蟻探索路徑的歐氏距離,distanceaverage為蟻群探索的所有路徑的平均距離,fitk為當(dāng)前第只螞蟻探索的路徑適應(yīng)度,采用指數(shù)級(jí)擴(kuò)展,這種變換的基本思想來源于模擬退火(Simulated Annealing,SA)[18]過程,經(jīng)變換后fitk的大小范圍鎖定在(0,1),使得復(fù)制的強(qiáng)度就趨向于那些具有最大適應(yīng)度的個(gè)體。

根據(jù)fitk將蟻群劃分為3個(gè)等級(jí)typek,適應(yīng)度最高的即為本次迭代的最優(yōu)解,授予其王蟻身份king,在剩余螞蟻分配中,本文提出一種限制因子LIMIT,適應(yīng)度在LIMIT和最高適應(yīng)度fitmax范圍內(nèi)時(shí)授予其被雇傭蟻身份hired,其余均為非雇傭蟻身份non-hired。

要注意如果LIMIT值過小,則被雇傭蟻數(shù)量占比更多,在初期算法未收斂,由于被雇傭蟻采用ACO路徑規(guī)劃策略產(chǎn)生食物源,非雇傭蟻數(shù)量過少,使算法喪失了一部分局部?jī)?yōu)化策略,可能會(huì)使得收斂速度變慢。如果LIMIT值過大,則非雇傭蟻占比更多,被雇傭蟻數(shù)量過少會(huì)導(dǎo)致算法獲取有效解迅速變少?gòu)亩顾惴焖龠_(dá)到假收斂狀態(tài),喪失了算法的動(dòng)態(tài)多樣性。因此LIMIT數(shù)值選擇尤為重要,本文通過大量的實(shí)驗(yàn)驗(yàn)證,當(dāng)LIMIT=0.37時(shí),能夠有效地平衡在算法初期未收斂與算法中期已收斂2種狀態(tài)下的多級(jí)蟻群的身份,此時(shí)算法效果最優(yōu)。

2.1.3 動(dòng)態(tài)多級(jí)的概念

在蟻群執(zhí)行完每次迭代操作以后都會(huì)對(duì)其身份進(jìn)行重新分配。王蟻身份特殊,數(shù)量唯一,且用于保存最優(yōu)解,在每次迭代操作中都會(huì)有固定數(shù)量的王蟻,所以適應(yīng)度算子主要用來分配被雇傭蟻與非雇傭蟻身份。在算法初期路徑規(guī)劃當(dāng)中,要盡可能地探索新的路徑即食物源,此時(shí)算法處于萌初狀態(tài),所以要分配較多的被雇傭蟻用來探索新的食物源作為參考,以被雇傭蟻為主,非雇傭蟻為輔。在算法逐漸成熟即逐漸收斂時(shí),被雇傭蟻們尋找的路徑逐漸趨于相同,被雇傭蟻尋找的路徑將再無意義,因?yàn)榇藭r(shí)已經(jīng)獲取到當(dāng)前能夠獲取到的假最優(yōu)解,要盡量分配較多的非雇傭蟻用于對(duì)現(xiàn)有食物源進(jìn)行局部?jī)?yōu)化,以非雇傭蟻為主,被雇傭蟻為輔,使得本算法在信息素濃度成熟的狀態(tài)下能夠快速地尋找更優(yōu)解并且使算法更快地跳出假收斂狀態(tài)。要始終動(dòng)態(tài)維持多級(jí)蟻態(tài)的蟻群是本文進(jìn)行尋找最優(yōu)解策略的關(guān)鍵,以下動(dòng)態(tài)分級(jí)具體步驟:

①當(dāng)iteration=1時(shí),采用ACO算法的路徑規(guī)劃策略作用于整體蟻群構(gòu)建路徑,計(jì)算相應(yīng)適應(yīng)度,對(duì)蟻群進(jìn)行分級(jí),并進(jìn)行信息素更新;

②當(dāng)iteration>1時(shí),王蟻與被雇傭蟻仍然會(huì)沿用ACO算法的路徑規(guī)劃策略進(jìn)行構(gòu)建路徑行為,通過輪盤賭算法產(chǎn)生食物源。非雇傭蟻會(huì)隨機(jī)選擇王蟻與被雇傭蟻生成的食物源,進(jìn)行局部?jī)?yōu)化生成產(chǎn)生一些新的食物源,采用貪婪思想選擇最優(yōu)解作為該非雇傭蟻的食物源。在所有非雇傭蟻執(zhí)行完尋找新食物源的操作后,蟻群中所有螞蟻全部獲取了新的食物源, 重新計(jì)算相應(yīng)的適應(yīng)度,重新為其賦予相應(yīng)的身份,再進(jìn)行信息素更新,執(zhí)行下一次迭代,直到迭代結(jié)束得到最優(yōu)解。

2.2 改進(jìn)信息素更新模型

為了特化多級(jí)蟻態(tài)蟻群對(duì)算法的導(dǎo)向作用,本文借鑒了精英蟻群的信息素加權(quán)更新策略[19],并引入了適應(yīng)度算子,提出了一種改進(jìn)的信息素更新模型,如式(10)所示:

由式(10)可知,本文算法的信息素更新策略采用全局更新模式,基于加權(quán)因子與適應(yīng)度算子用以區(qū)分最優(yōu)解與優(yōu)質(zhì)解,僅更新王蟻與被雇傭蟻偵查路徑上的信息素濃度用以擴(kuò)大優(yōu)質(zhì)解與非優(yōu)質(zhì)解的信息素濃度差距,拋棄非優(yōu)質(zhì)解僅保留優(yōu)質(zhì)解能夠加快尋找最優(yōu)解的速度。雖然可能會(huì)因此導(dǎo)致算法更快地陷入局部最優(yōu),但是非雇傭蟻的存在正是為了能夠使算法快速跳出這種狀態(tài)而設(shè)計(jì),這也是人工蜂群的思想。非雇傭蟻并不增加信息素而僅僅進(jìn)行局部?jī)?yōu)化,同時(shí)王蟻與被雇傭蟻的路徑規(guī)劃并沒有因?yàn)榉枪蛡蛳亗刹榈姆莾?yōu)質(zhì)解導(dǎo)致的信息素濃度差異而受到影響,從而維持了算法的多樣性。

雖然在初期進(jìn)行信息素更新時(shí)能夠迅速拉開差距,但是隨著信息素?fù)]發(fā),信息素濃度趨于平整,在節(jié)點(diǎn)數(shù)量多的區(qū)域內(nèi)尤為嚴(yán)重,會(huì)使得此領(lǐng)域內(nèi)無法進(jìn)入收斂狀態(tài),因此額外加入加權(quán)因子μ1、μ2,還需要合理配置μ1、μ2的比例。如果比例過大,會(huì)使得當(dāng)前最優(yōu)解上的信息素濃度較其他路徑上的信息素濃度過于夸張,算法快速進(jìn)入到收斂階段,影響算法的最優(yōu)解精度。如果比例過小,會(huì)使得加權(quán)改進(jìn)不明顯反而會(huì)減緩算法收斂速度。因此,本文經(jīng)過大量實(shí)驗(yàn)驗(yàn)證,當(dāng)μ1=1.5、μ2=1時(shí)算法效果最好,故作為本文改進(jìn)信息素更新策略的加權(quán)因子。

2.3 引入固定鄰域優(yōu)化算法

本文在針對(duì)局部?jī)?yōu)化操作提出了一種融合2-opt、3-opt和插入算子的固定鄰域優(yōu)化算法。

2.3.1 變異算子

① 2-opt算子

在一條長(zhǎng)度為n的節(jié)點(diǎn)序列中隨機(jī)找到2個(gè)不同的節(jié)點(diǎn)x1與x2,逆轉(zhuǎn)x1與x2之間的節(jié)點(diǎn)序列并保持其他段節(jié)點(diǎn)序列順序保持不變,得到一條新節(jié)點(diǎn)序列即為所求,2-opt路徑重組過程如圖1所示。

圖1 2-opt路徑重組過程Fig.1 2-optimization path reorganization process

② 3-opt算子

在一條長(zhǎng)度為n的節(jié)點(diǎn)序列中隨機(jī)找到3個(gè)不同的節(jié)點(diǎn)x1、x2、x3切開重組,產(chǎn)生8種新的節(jié)點(diǎn)序列, 再采用貪用貪婪思想選擇最優(yōu)解即為所求,3-opt路徑重組過程如圖2所示。

圖2 3-opt路徑重組過程Fig.2 3-optimization path reorganization process

③ 插入算子

在長(zhǎng)度為n的節(jié)點(diǎn)序列中隨機(jī)找到2個(gè)不同的節(jié)點(diǎn)x1、x2,其中規(guī)定x1序列小于x2的序列,將x2插入到原有的序列后的新節(jié)點(diǎn)序列即為所求,插入算子路徑重組過程如圖3所示。

圖3 插入算子路徑重組過程Fig.3 Insertion operator path reorganization process

2.3.2 固定鄰域概念

本文提出的算法規(guī)定被雇傭蟻會(huì)隨機(jī)選擇王蟻與被雇傭蟻尋找的食物物源進(jìn)行局部?jī)?yōu)化偵查出更加優(yōu)質(zhì)的食物源。傳統(tǒng)的變異算子作用域是整個(gè)區(qū)域,如果區(qū)域很大,雖然在一定程度上增加了被選擇節(jié)點(diǎn)的組合方式,增加了變異幾率,但是因?yàn)榉秶珡V而導(dǎo)致變異的有效率很低。為了進(jìn)一步提高產(chǎn)生較為優(yōu)質(zhì)的解,本文提出一種固定鄰域優(yōu)化算法。

非雇傭蟻在隨機(jī)偵查的食物源中隨機(jī)找到一個(gè)節(jié)點(diǎn)作為鄰域中心點(diǎn),以固定半徑范圍,尋找相對(duì)鄰域中心點(diǎn)的有效偵查點(diǎn),將其作為固定鄰域優(yōu)化算法的搜索解空間,并采用基于3種變異算子的算法對(duì)其進(jìn)行優(yōu)化,在通過貪婪思想選擇最優(yōu)解作為該非雇傭蟻的食物源。

基于此,本文提出了一種鄰域因子ε為固定鄰域半徑,采用測(cè)試旅行商問題庫(kù)(TSP Libarary, TSPLIB)中的公開數(shù)據(jù)集bayg29、oliver30、att48、eil51、eil76,eil101和ch130用以驗(yàn)證,本文算法測(cè)試數(shù)據(jù)集相應(yīng)的ε值如表1所示。

表1 實(shí)驗(yàn)中使用的TSPLIB數(shù)據(jù)集及其ε值Tab.1 The TSPLIB datasets and ε values used inthe experiment

2.3.3 局部?jī)?yōu)化功能組成

本文提出的固定鄰域優(yōu)化算法由兩部分功能組成:

① 鄰域搜索。隨機(jī)確定某個(gè)節(jié)點(diǎn)作為鄰域搜索中心點(diǎn),基于表1對(duì)應(yīng)ε為半徑尋找有效點(diǎn)。

② 組合變異算子優(yōu)化。根據(jù)有效點(diǎn)數(shù)量采取不同的變異算子,若數(shù)量為1即有效半徑內(nèi)除中心點(diǎn)外沒有其他的有效點(diǎn),則直接返回不進(jìn)行局部?jī)?yōu)化,若數(shù)量大于或等于2,則進(jìn)行插入算子變異優(yōu)化,且數(shù)量等于2時(shí),額外進(jìn)行2-opt算子變異優(yōu)化,其他情況下,進(jìn)行3-opt算子變異優(yōu)化。

2.4 MSACO算法流程

以下為本文MSACO算法的執(zhí)行步驟:

步驟1:初始化相應(yīng)參數(shù):α、β、τ、η、ρ、Qm、iteration、iterationmax、LIMIT、μ1、μ2、ε;

步驟2:執(zhí)行第一次迭代,將m只螞蟻隨機(jī)放置在m個(gè)節(jié)點(diǎn);

步驟3:按照式(2)構(gòu)建原始食物源;

步驟4:按照適應(yīng)度分級(jí)算子式(8)、式(9)計(jì)算相應(yīng)的適應(yīng)度,對(duì)螞蟻進(jìn)行分級(jí),按照式(10)進(jìn)行信息素更新操作;

步驟5:執(zhí)行第一次迭代,將王蟻和被雇傭蟻隨機(jī)放置在m個(gè)節(jié)點(diǎn);

步驟6:王蟻和被雇傭蟻按照式(2)構(gòu)建食物源;

步驟7:非雇傭蟻隨機(jī)選擇一條王蟻或被雇傭蟻偵查的食物源;

步驟8:非雇傭蟻采用本文提出的固定鄰域優(yōu)化算法對(duì)該食物源進(jìn)行局部?jī)?yōu)化,得到最優(yōu)解將其做為該非雇傭蟻的食物源;

步驟9:按照式(8)～式(9)計(jì)算所有等級(jí)螞蟻偵查食物源的適應(yīng)度;

步驟10:按照適應(yīng)度分級(jí)算子對(duì)螞蟻進(jìn)行動(dòng)態(tài)重新分級(jí),按照式(10)進(jìn)行信息素更新操作;

步驟11:本次迭代操作結(jié)束,iteration自增1。若iteration

3 實(shí)驗(yàn)測(cè)試分析

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定

本實(shí)驗(yàn)的硬件環(huán)境:CPU為Intel(R) Core(TM) i7-9750H CPU @ 2.60 GHz 12線程;軟件環(huán)境:Windows 10平臺(tái)PyCharm 2021.3.3本文算法基于以上配置進(jìn)行實(shí)驗(yàn),對(duì)公開TSPLIB庫(kù)中的bayg29、oliver30、att48、eil51、eil76、eil101和ch130共計(jì)7個(gè)不同規(guī)模的數(shù)據(jù)集進(jìn)行仿真求解。與傳統(tǒng)ACO算法、ABC算法以及文獻(xiàn)[4]提出的一種結(jié)合貪婪算法思想的蟻群改進(jìn)(Greedy Algorithm-Ant Colony Optimization,GA-ACO)算法進(jìn)行對(duì)比,在公共參數(shù)設(shè)定方面與文獻(xiàn)[4]保持一致,即α=1.0、β=3.0、ρ=0.5、m=城市數(shù)量。由于本文對(duì)信息素更新策略進(jìn)行優(yōu)化,所以在Q取值上與ACO和文獻(xiàn)[4]不同,本文算法中Q=2,其他算法中Q=106。以下是本文提出一些特殊因子的參數(shù)設(shè)定:適應(yīng)度加權(quán)因子μ1=1.5、μ2=1.0,鄰域因子ε如表1所示。文獻(xiàn)[4]中的特殊因子的參數(shù)設(shè)定與文獻(xiàn)[4]所提出的數(shù)值保持一致:間接期望啟發(fā)式因子γ=3。ABC算法設(shè)定蜜源nPop=城市數(shù)量。采用以上參數(shù)設(shè)定方式將取20次連續(xù)實(shí)驗(yàn),且規(guī)定迭代上限iterationmax=500,作為研究結(jié)果進(jìn)行分析驗(yàn)證。

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

實(shí)驗(yàn)數(shù)據(jù)如表2所示,其中各種數(shù)據(jù)集理論最優(yōu)非整數(shù)解均來源于文獻(xiàn)[20]?？梢钥闯鲈谛∫?guī)模的數(shù)據(jù)集bayg29、oliver30和att48中,MSACO與GA-ACO處理能力相差不大,但從平均誤差來看MSACO略優(yōu)于GA-ACO,二者都能夠獲取到理論最優(yōu)解,均優(yōu)于傳統(tǒng)ACO算法和ABC算法。在處理eil51數(shù)據(jù)集中,GA-ACO平均誤差較MSACO少0.11%,可以證明貪婪思想更適用于這種節(jié)點(diǎn)比較擁擠的小型數(shù)據(jù)集。但隨著數(shù)據(jù)集的節(jié)點(diǎn)數(shù)量增加,GA-ACO處理這種中型規(guī)模數(shù)據(jù)集TSP能力不足,eil76、eil101和ch130均未到達(dá)最優(yōu)解且距離較大。而本文提出的MSACO在這3類數(shù)據(jù)集均能達(dá)到理論最優(yōu)解,且所有比較指標(biāo)均優(yōu)于GA-ACO。在eil101數(shù)據(jù)集能夠收斂到640.211 6,較理論最優(yōu)解減少0.33%,ch130數(shù)據(jù)集能夠收斂到6 110.722 2,較理論最優(yōu)解減少了0.002%。相應(yīng)的平均誤差均小于1%,比其他對(duì)比算法更加穩(wěn)定。由此可以看出本文提出的MSACO在處理中小型TSP時(shí),明顯優(yōu)于傳統(tǒng)ACO算法與GA-ACO算法,充分證明了該算法的有效性。傳統(tǒng)ABC算法在處理小數(shù)據(jù)bayg29、oliver30時(shí)可以獲取理論最優(yōu)解,但隨著數(shù)據(jù)集規(guī)模增大,節(jié)點(diǎn)數(shù)量增多,獲取最優(yōu)路線的效率也在同步下降,誤差均高于2%,偵查蜂無法獲取有效突變蜜源,導(dǎo)致算法無法跳出局部最優(yōu)。而GA-ACO算法采用本文提出的固定鄰域優(yōu)化算法,可以有效地避免上述問題,與ABC算法相比最優(yōu)解提升約3%,平均值減少約3%。

表2 ACO、ABC、GA-ACO、MSACO在不同數(shù)據(jù)集下的最優(yōu)解與平均值數(shù)據(jù)對(duì)比Tab.2 Comparison of optimal solutions and average values of ACO, ABC,GA-ACO and MSACO under different datasets

本文MSACO算法在各種數(shù)據(jù)集得到的最優(yōu)路線如圖4所示,所有路線均達(dá)到理論最優(yōu)路線標(biāo)準(zhǔn),其中eil101、ch130均超越了理論最優(yōu)路線的最短非整數(shù)距離。MSACO、GA-ACO、ACO以及ABC在各種數(shù)據(jù)集下獲取最優(yōu)解的對(duì)比收斂曲線圖如圖5所示。總體來看,傳統(tǒng)ACO算法在本次對(duì)比試驗(yàn)的參數(shù)設(shè)定下并沒有達(dá)到收斂狀態(tài),因此并不作為對(duì)比試驗(yàn)分析的重點(diǎn),僅取其遍歷中獲取過的最優(yōu)解作為全局最優(yōu)解。迭代次數(shù)最大值為500,ABC算法依據(jù)分級(jí)更新蜜源機(jī)制平均300代內(nèi)收斂,而MSACO算法平均100代以內(nèi)就趨近于收斂狀態(tài),收斂曲線趨于平滑曲線,其初始構(gòu)建路徑距離普遍較GA-ACO算法過大,這是因?yàn)镚A-ACO算法采用貪婪思想改進(jìn)路徑規(guī)劃算子,較MSACO采用的是傳統(tǒng)ACO規(guī)劃路徑算子能夠有效地在初始階段獲取更為優(yōu)質(zhì)的路線。雖然初始路徑更優(yōu),但也在一定程度上降低了路徑的變異性。在100代以內(nèi),MSACO算法能夠快速地搜索更為優(yōu)質(zhì)的路徑,在100～200代,MSACO與GA-ACO均趨于成熟,如何快速地跳出局部最優(yōu)則是通過各自的局部?jī)?yōu)化算法實(shí)現(xiàn)。GA-ACO的收斂曲線變化跨度大且更新迭代間隔次數(shù)較長(zhǎng),而MSACO收斂曲線趨于平滑,路徑更新的迭代周期更短,這是因?yàn)橐牍潭ㄠ徲蛩枷胨圆拍芨焯鼍植孔顑?yōu)的假收斂狀態(tài),借此驗(yàn)證了本文提出的固定鄰域優(yōu)化算法的有效性。在200～500代,GA-ACO普遍沒有變化,而MSACO則可以進(jìn)一步優(yōu)化路徑。在數(shù)據(jù)集eil76、eil101和ch130中,此時(shí)算法以非雇傭蜂為主,雖然減少了算法的多樣型,但針對(duì)已經(jīng)成熟的算法,采用不考慮信息素濃度與路徑的影響的固定鄰域優(yōu)化算法能夠進(jìn)一步優(yōu)化局部信息。

圖4 MSACO在各種數(shù)據(jù)集下的最優(yōu)路徑展示圖Fig.4 Optimal path of MSACO under various datasets

(g)ch130

ACO、ABC、GA-ACO和MSACO在所有測(cè)試集中的最優(yōu)解的算法收斂運(yùn)行時(shí)間與收斂迭代次數(shù)如表3所示。由于傳統(tǒng)ACO算法基于本文對(duì)比實(shí)驗(yàn)參數(shù)設(shè)定下并沒有進(jìn)入收斂狀態(tài),所以以默認(rèn)迭代次數(shù)為最高迭代次數(shù)、運(yùn)行時(shí)間為迭代500代的總體時(shí)間。

表3 ACO、ABC、GA-ACO和MSACO在不同數(shù)據(jù)下達(dá)到收斂最優(yōu)解時(shí)的迭代次數(shù)與運(yùn)行時(shí)間 Tab.3 Iteration times and running time when ACO,ABC,GA-ACO and MSACO reach the convergentoptimal solution under different data

從總體來看,MSACO算法在各個(gè)參數(shù)指標(biāo)均優(yōu)于ACO算法和ABC算法,以下對(duì)比以GA-ACO、MSACO為主。在應(yīng)用于小型數(shù)據(jù)集bayg29、oliver30和att48,MSACO較GA-ACO相比運(yùn)行時(shí)間降低約50%、迭代收斂次數(shù)減少約43%。應(yīng)用與中小型數(shù)據(jù)集eil51、eil76,MSACO較GA-ACO相比運(yùn)行時(shí)間降低約60%、迭代收斂次數(shù)減少約50%。應(yīng)用于中大型數(shù)據(jù)集eil101、ch130,雖然MSACO的收斂迭代次數(shù)明顯高于GA-ACO的收斂迭代次數(shù),但從表3可知MSACO獲得的最優(yōu)解均優(yōu)于GA-ACO的最優(yōu)解,而且迭代收斂時(shí)間與GA-ACO相比約減少超過50%,這是因?yàn)樵谒惴ㄟM(jìn)入成熟后期,非雇傭蟻數(shù)量比重最大,采用本文提出的固定鄰域優(yōu)化算法對(duì)王蟻的最優(yōu)路徑進(jìn)行局部?jī)?yōu)化,因此在算法后期依然能保持算法的變異性。而GA-ACO隨著數(shù)據(jù)集規(guī)模的增大,運(yùn)行時(shí)間也隨之快速增大,這是因?yàn)樵谠撍惴ㄖ忻恳恢晃浵伨獔?zhí)行路徑規(guī)劃與局部路徑優(yōu)化操作,雖然采用了結(jié)合貪婪思想的改進(jìn)路徑規(guī)劃模式,在算法前期能夠快速構(gòu)建更為優(yōu)質(zhì)的初始路徑所以在小規(guī)模數(shù)據(jù)集中可以快速有效獲取全局最優(yōu)路徑,但是在中大型數(shù)據(jù)集中,會(huì)嚴(yán)重增加運(yùn)行時(shí)間,而本文提出的MSACO算法則是引入適應(yīng)度算子動(dòng)態(tài)分配蟻群的身份與數(shù)量,各種螞蟻各司其職,因此能夠大大減少運(yùn)行時(shí)間?；诖?數(shù)據(jù)集規(guī)模越大,運(yùn)行時(shí)間的優(yōu)化效率越趨于明顯。

4 結(jié)束語

本文基于ABC分級(jí)思想將蟻群劃分為三蟻態(tài)蟻群。為平衡各級(jí)螞蟻身份,維持算法的多樣性,引入了適應(yīng)度算子進(jìn)行動(dòng)態(tài)分級(jí)。為加強(qiáng)各級(jí)螞蟻對(duì)算法的導(dǎo)向作用,對(duì)信息素更新模型進(jìn)行改進(jìn)。在快速引導(dǎo)算法趨于收斂狀態(tài)期間,為避免算法陷入局部最優(yōu),引入了融合2-opt、3-opt和插入算子的固定鄰域優(yōu)化算法。經(jīng)過仿真TSP數(shù)據(jù)集,成功驗(yàn)證了分級(jí)思想在蟻群算法中的實(shí)用性,加權(quán)改進(jìn)信息素更新模型的適用性,局部尋優(yōu)的有效性。下一步的研究方向包括:

①對(duì)路徑規(guī)劃算子進(jìn)行改進(jìn),使其能夠在初期便能獲取到更為優(yōu)質(zhì)的路徑,進(jìn)一步優(yōu)化收斂曲線;

②在維持原有求解能力的情況下,進(jìn)一步減少算法的運(yùn)行時(shí)間、獲取最優(yōu)解的迭代次數(shù)。