基于種群相似度的自適應(yīng)改進(jìn)蟻群算法及應(yīng)用

張松燦，普杰信，司彥娜，孫力帆

1.河南科技大學(xué) 信息工程學(xué)院，河南 洛陽(yáng)471000

2.河南科技大學(xué) 電氣工程學(xué)院，河南 洛陽(yáng)471000

蟻群算法是意大利學(xué)者Dorigo 等受自然界螞蟻群體的覓食行為啟發(fā)而提出的啟發(fā)式搜索算法，具有并行計(jì)算、正反饋、魯棒性好、全局搜索能力強(qiáng)等優(yōu)點(diǎn)[1]，并廣泛用于各種組合優(yōu)化問(wèn)題。經(jīng)過(guò)學(xué)者們的深入研究與不斷探索，蟻群算法在指派問(wèn)題（Assignment Problem）[2]、調(diào)度問(wèn)題（Scheduling Problem）[3]、連續(xù)優(yōu)化（Continuous Optimization）[4]、約束滿足問(wèn)題（Constraint Satisfaction Problems）[5-6]以及參數(shù)優(yōu)化[7]等領(lǐng)域也得到成功應(yīng)用，但是在求解過(guò)程中存在效率低、收斂速度慢及易陷入局部最優(yōu)值等不足。

針對(duì)這些問(wèn)題，許多學(xué)者提出了許多富有成效的改進(jìn)策略，如ACS[8]、MMAS[9]、帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy，ASelite）[10]、基于排序的螞蟻系統(tǒng)（Ant System with elitist strategy and ranking，ASrank）[11]等改進(jìn)算法，但是這些方法是從蟻群的基本框架和結(jié)構(gòu)上進(jìn)行改進(jìn)，依然存在收斂速度與早熟收斂的矛盾。

除前述的結(jié)構(gòu)改進(jìn)外，蟻群算法的參數(shù)對(duì)其優(yōu)化性能有重要的影響，也是蟻群算法的研究熱點(diǎn)。文獻(xiàn)[12]分析了蟻群算法參數(shù)之間的關(guān)系，并針對(duì)所研究問(wèn)題給出了參數(shù)值的優(yōu)化組合。由于蟻群優(yōu)化（Ant Colony Optimization，ACO）算法參數(shù)眾多且存在緊密的耦合作用，通常是根據(jù)實(shí)驗(yàn)者的個(gè)人經(jīng)驗(yàn)和大量的前期實(shí)驗(yàn)給出算法參數(shù)，這種方式效率較低，適應(yīng)能力差。為了避免反復(fù)試湊進(jìn)行參數(shù)取值的耗時(shí)工作，文獻(xiàn)[13]提出一種基于粒子群優(yōu)化（Particle Swarm Optimization，PSO）與ACO 的融合算法，通過(guò)粒子搜索自動(dòng)選取參數(shù)值的優(yōu)質(zhì)組合，仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性，但是在優(yōu)化過(guò)程中，粒子群算法將重復(fù)調(diào)用蟻群算法，時(shí)間開(kāi)銷較大，此外不同的實(shí)例具有不同的最佳參數(shù)組合，算法缺乏適應(yīng)性。文獻(xiàn)[14]通過(guò)粒子群算法來(lái)優(yōu)化螞蟻?zhàn)尤旱膮?shù)，更好地控制螞蟻?zhàn)尤旱拈_(kāi)發(fā)能力和探索能力。針對(duì)多次調(diào)用蟻群算法存在時(shí)間開(kāi)銷較大的問(wèn)題，文獻(xiàn)[15]采用全局異步與精英策略相結(jié)合的信息素更新方式，有效減少蟻群算法被粒子群算法調(diào)用一次所需的迭代代數(shù)，但是選取的參數(shù)缺乏適應(yīng)能力。上述研究均采用靜態(tài)參數(shù)，在算法運(yùn)行前通過(guò)大量實(shí)驗(yàn)找到合適的參數(shù)組合，雖然能取得較好的優(yōu)化結(jié)果，但是參數(shù)與具體問(wèn)題密切相關(guān)，適應(yīng)能力較弱。

事實(shí)上，蟻群算法的優(yōu)化過(guò)程是動(dòng)態(tài)的，不同的運(yùn)行階段有不同的優(yōu)化需求，如起始階段希望在更廣泛的問(wèn)題空間構(gòu)建候選解，增大得到最優(yōu)解的概率，而在優(yōu)化后期，希望加快算法的收斂速度，進(jìn)一步提高解的精度，所以前述的靜態(tài)參數(shù)組合不適合搜索過(guò)程各個(gè)階段。如果在算法運(yùn)行時(shí)能改變算法參數(shù)，適應(yīng)不同的優(yōu)化目標(biāo)，將有助于進(jìn)一步增強(qiáng)算法的優(yōu)化能力。

文獻(xiàn)[16]提出了一種自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)系數(shù)的方法來(lái)平衡算法全局性和收斂速度之間的矛盾。文獻(xiàn)[17-18]通過(guò)設(shè)定迭代閾值，自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)系數(shù)解決全局尋優(yōu)能力與收斂速度的矛盾，在保證算法收斂速度的條件下提高解的全局性。文獻(xiàn)[19]采用參數(shù)自適應(yīng)偽隨機(jī)轉(zhuǎn)移策略，算法前期q0取值較大使得螞蟻根據(jù)全局路徑信息選擇有利路徑，后期q0取值較小有利于螞蟻隨機(jī)搜索，避免算法停滯。文獻(xiàn)[20]采用自適應(yīng)狀態(tài)轉(zhuǎn)移策略和自適應(yīng)信息素更新策略來(lái)改進(jìn)蟻群算法，確保信息素強(qiáng)度與期望在算法進(jìn)化過(guò)程中的相對(duì)重要性，提高了算法的全局搜索能力。卜新蘋等[21]為了提高蟻群算法接受隨機(jī)解的概率，跳出局部最優(yōu)，自適應(yīng)改變算法q0的取值。為了避免陷入局部最優(yōu)，文獻(xiàn)[22]采用動(dòng)態(tài)調(diào)整信息素啟發(fā)因子與期望啟發(fā)因子的策略進(jìn)行算法改進(jìn)，有效減少了螞蟻前期到達(dá)最優(yōu)路徑的迭代次數(shù)，但是動(dòng)態(tài)調(diào)整策略需要人為設(shè)定算法的運(yùn)行狀態(tài)，缺乏靈活性。這些改進(jìn)方法是根據(jù)蟻群算法不同階段的期望目標(biāo)來(lái)動(dòng)態(tài)調(diào)整算法參數(shù)，用較小的計(jì)算負(fù)擔(dān)提高優(yōu)化能力，但是需要事先設(shè)定參數(shù)的調(diào)整規(guī)律，缺乏適應(yīng)能力。

文獻(xiàn)[23]設(shè)定迭代閾值來(lái)判斷是否陷入局部最優(yōu)，進(jìn)而調(diào)整信息素?fù)]發(fā)系數(shù)和信息素濃度，使算法在迭代后期依然具有較強(qiáng)的搜索能力，但是迭代閾值的引入使算法缺乏適應(yīng)能力。文獻(xiàn)[24]提出一種基于聚度的自適應(yīng)動(dòng)態(tài)混沌蟻群算法，在迭代前期利用種群聚度衡量種群的分布情況，自適應(yīng)地更新局部信息素，平衡了多樣性和收斂性之間的矛盾，但是需要人為設(shè)定迭代閾值與聚度閾值，缺乏適應(yīng)能力。文獻(xiàn)[25]采用信息熵描述每一條邊上信息素的不確定性，采用種群信息熵來(lái)衡量算法的進(jìn)化程度，自適應(yīng)地調(diào)整路徑選擇策略和信息素更新策略，但是引入的新參數(shù)增加了參數(shù)整定的復(fù)雜度。

通過(guò)對(duì)蟻群算法優(yōu)化過(guò)程的分析，候選解的分布特征不僅會(huì)隨著迭代數(shù)發(fā)生變化，還與算法的優(yōu)化過(guò)程有關(guān)。一般來(lái)說(shuō)，在優(yōu)化起始階段，由于均勻分布信息素，候選解盡可能地分布在問(wèn)題空間，種群個(gè)體多樣性較好，相似度較低；隨著迭代過(guò)程的進(jìn)行，在正反饋的作用下，候選解快速地集中在最優(yōu)解或次優(yōu)解附近，多樣性變差，個(gè)體間相似度較高。蟻群算法的全局尋優(yōu)性要求蟻群在問(wèn)題空間盡可能地進(jìn)行隨機(jī)搜索，增大找到全局最優(yōu)解的概率，而蟻群算法的快速收斂性要求蟻群盡可能在潛在的較優(yōu)區(qū)域進(jìn)行搜索，二者對(duì)蟻群算法性能的影響既矛盾又密切相關(guān)。為此，提出了一種基于種群相似度的自適應(yīng)改進(jìn)蟻群算法，首先利用種群相似度對(duì)種群多樣性進(jìn)行度量，并根據(jù)優(yōu)化過(guò)程中種群相似度的變化自適應(yīng)地調(diào)整蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則的控制參數(shù)和信息素更新策略，在加快算法收斂速度的同時(shí)防止陷入局部最優(yōu)，有效地平衡了種群多樣性與收斂速度的矛盾。

1 蟻群算法簡(jiǎn)述

蟻群系統(tǒng)[8]是蟻群優(yōu)化算法中的經(jīng)典算法，它改進(jìn)了螞蟻系統(tǒng)（Ant System，AS）的狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新方法，利用最優(yōu)選擇和隨機(jī)選擇相結(jié)合的偽隨機(jī)比例規(guī)則選擇下一個(gè)節(jié)點(diǎn)，信息素更新采用局部和全局更新相結(jié)合的方式，不僅提高了算法多樣性，還加快了算法的收斂速度。

1.1 狀態(tài)轉(zhuǎn)移規(guī)則

狀態(tài)轉(zhuǎn)移規(guī)則是蟻群算法在解空間構(gòu)建候選解的依據(jù)，蟻群系統(tǒng)利用最優(yōu)選擇和隨機(jī)選擇相結(jié)合的偽隨機(jī)方式選擇下一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)選擇規(guī)則如公式（1）和（2）所示：

式中，s表示選擇的下一節(jié)點(diǎn)，τij為邊(i,j)上的信息素值，用來(lái)記錄積累的經(jīng)驗(yàn)信息，ηij=1/dij為從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的啟發(fā)信息，dij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離，allowedk為螞蟻k下一步允許訪問(wèn)的節(jié)點(diǎn)集合，α和β分別表示信息素和啟發(fā)信息在構(gòu)建候選解時(shí)的相對(duì)重要程度。q是[0,1]之間的一個(gè)隨機(jī)數(shù)，q0∈[0,1]是概率選擇的控制參數(shù)。

上式表明，當(dāng)隨機(jī)生成的數(shù)小于q0時(shí)，螞蟻選擇信息素和啟發(fā)式因子綜合因素最大的節(jié)點(diǎn)，否則按照pkij進(jìn)行計(jì)算各個(gè)可行節(jié)點(diǎn)的選擇概率，然后按照輪盤賭方法選擇下一節(jié)點(diǎn)。可知，ACS 通過(guò)參數(shù)q0來(lái)調(diào)整算法探索與利用的比例，當(dāng)q0越大時(shí)，后續(xù)螞蟻越有可能接受先行螞蟻的經(jīng)驗(yàn)，否則去探索未知的問(wèn)題空間。

1.2 全局信息素更新

解構(gòu)建完成后需要進(jìn)行信息素更新。信息素更新是蟻群的信息交流通道，反映了個(gè)體與群體之間智能行為，是蟻群算法最重要的環(huán)節(jié)。蟻群系統(tǒng)只在全局最優(yōu)解上進(jìn)行信息素增強(qiáng)，保證算法對(duì)最優(yōu)解的持續(xù)利用，更新規(guī)則如公式（3）和（4）所示：

式中，ρ是全局信息素?fù)]發(fā)系數(shù)，表示全局最優(yōu)解上的信息素增量，Lgb是全局最優(yōu)路徑的長(zhǎng)度，Tgb是全局最優(yōu)路徑節(jié)點(diǎn)序列。

由上式可知，當(dāng)所有螞蟻完成候選解構(gòu)建任務(wù)后，只有最優(yōu)路徑上的信息素得到加強(qiáng)，增大后續(xù)螞蟻選擇最優(yōu)路徑的概率，提高算法的收斂速度。

1.3 局部信息素更新

在蟻群系統(tǒng)中，除全局信息素更新外，還需要局部信息素更新，以減少已訪問(wèn)路徑被再次選擇的概率，增加對(duì)未訪問(wèn)區(qū)域的探索。螞蟻每選擇一個(gè)新節(jié)點(diǎn)，就按照公式（5）進(jìn)行局部信息素更新。

式中，δ是局部信息素?fù)]發(fā)系數(shù)，τ0是信息素初始值。

2 種群相似度測(cè)量

文獻(xiàn)[26]用個(gè)體間的漢明距離描述種群的相似度。如果個(gè)體間漢明距離小，說(shuō)明個(gè)體離得近，相似度高，否則說(shuō)明個(gè)體相距較遠(yuǎn)，相似度低。然而用漢明距離表示相似度時(shí)存在一些問(wèn)題。對(duì)TSP問(wèn)題來(lái)說(shuō)，個(gè)體由節(jié)點(diǎn)的訪問(wèn)順序組成，并不代表節(jié)點(diǎn)的實(shí)際位置，因此漢明距離并不能描述個(gè)體間的真實(shí)距離；此外，該方法也沒(méi)有考慮問(wèn)題規(guī)模?？紤]到個(gè)體是由節(jié)點(diǎn)的訪問(wèn)順序組成，那么個(gè)體間總會(huì)有一些相同的路徑段，因此可采用個(gè)體間相同路徑段的多少來(lái)描述個(gè)體間的相似度[27]。一般來(lái)說(shuō)，個(gè)體間相同路徑段的數(shù)目越多，說(shuō)明個(gè)體在問(wèn)題空間分布越集中，相似度就越高；反之，個(gè)體在問(wèn)題空間分布更廣，相似度則越低。設(shè)兩個(gè)個(gè)體分別用R1(x1,x2,…,xn)和R2(y1,y2,…,yn)表示，其中n表示個(gè)體的元素?cái)?shù)量。其相似度計(jì)算過(guò)程如下：

（1）建立個(gè)體所代表路徑的連接矩陣

假設(shè)個(gè)體R1對(duì)應(yīng)的連接矩陣用A表示，個(gè)體R2對(duì)應(yīng)的連接矩陣為B，則有：

矩陣A中，如果R1中包含有節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑段，則aij=1，否則aij=0。同理，可建立R2的連接矩陣B。

（2）根據(jù)連接矩陣A、B計(jì)算個(gè)體間相似度

如果兩條路徑重合的邊數(shù)目越多，相似度就越高，反之，相似度就越低。極限情況下，如果兩個(gè)個(gè)體的路線完全一致或者重合，則其相同的邊個(gè)數(shù)為n；如果沒(méi)有相同的邊，則相同的邊個(gè)數(shù)為0。由于TSP問(wèn)題的規(guī)模不同，為使種群相似度具有可比性且能夠用于下文的自適應(yīng)蟻群算法，將計(jì)算出的相似度進(jìn)行歸一化處理，使其始終處于0～1 之間。個(gè)體R1和R2之間的相似度計(jì)算方法如公式（7）：

（3）種群相似度

種群相似度描述了種群中個(gè)體的聚集程度。采用個(gè)體與全局最優(yōu)個(gè)體間的相對(duì)相似度之和的均值來(lái)描述種群的相似度，其計(jì)算方法如公式（8）所示：

其中，m是種群的大小，Rk為種群中的第k個(gè)個(gè)體，Rbest表示種群內(nèi)的最優(yōu)個(gè)體，mean()表示均值計(jì)算。

如果種群相似度高，說(shuō)明個(gè)體集中于最優(yōu)解附近，多樣性較差，反之，個(gè)體分散于解空間，多樣性較好。因此可用種群的相似度來(lái)衡量其多樣性。

3 基于種群相似度的自適應(yīng)改進(jìn)蟻群算法

群智能算法在求解優(yōu)化問(wèn)題時(shí)，都會(huì)遇到多樣性與收斂速度的矛盾，蟻群算法也不例外。加大最優(yōu)解的利用，能加快算法的收斂速度，但是導(dǎo)致解的多樣性變差，易陷入局部最優(yōu)；如果算法傾向于探索問(wèn)題空間，雖然可增強(qiáng)種群的多樣性，增大找到全局最優(yōu)解的可能性，跳出局部最優(yōu)，但會(huì)降低算法的收斂速度。為此提出一種基于種群相似度的自適應(yīng)改進(jìn)蟻群算法（An adaptive improved ant colony algorithm based on population similarity，簡(jiǎn)稱IAACS），利用種群相似度描述種群的多樣性，并根據(jù)迭代過(guò)程中相似度的變化自動(dòng)調(diào)整蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則的控制參數(shù)和信息素更新策略，提高解的質(zhì)量與算法穩(wěn)定性，有效地平衡種群多樣性與收斂速度的矛盾。

3.1 基于相似度的參數(shù)自適應(yīng)調(diào)整

蟻群系統(tǒng)采用偽隨機(jī)比例轉(zhuǎn)移規(guī)則來(lái)構(gòu)建候選解，參數(shù)q0決定蟻群系統(tǒng)采用最優(yōu)選擇方式還是隨機(jī)方式構(gòu)建候選解的概率。q0越大，蟻群系統(tǒng)傾向于最優(yōu)模式構(gòu)建候選解，側(cè)重于最優(yōu)解的利用，候選解比較集中，為避免算法早熟收斂，應(yīng)減小q0的值；q0越小，蟻群系統(tǒng)傾向于隨機(jī)模式構(gòu)建候選解，側(cè)重于未知空間的探索，候選解分布比較分散，為了提高算法的收斂速度，應(yīng)該向信息量較大的路徑上集中以加速進(jìn)化速度，即增大q0。為了有效平衡蟻群算法的收斂速度與多樣性的矛盾，提出一種自適應(yīng)調(diào)整參數(shù)q0的偽隨機(jī)比例策略。具體來(lái)說(shuō)，每次迭代結(jié)束后，蟻群算法根據(jù)相似度自動(dòng)調(diào)整參數(shù)q0的值，同時(shí)為了避免q0過(guò)大或者過(guò)小，還設(shè)定其上下界。

式中，q0min是參數(shù)q0的取值下限，q0max是參數(shù)q0的取值上限，Simi(P)是蟻群的相似度。

3.2 基于相似度的信息素更新策略

蟻群算法具有正反饋的特點(diǎn)，雖然使系統(tǒng)向最優(yōu)解方向迅速進(jìn)化，但是導(dǎo)致種群相似度迅速增大，易陷入局部最優(yōu)，且難以跳出局部最優(yōu)。由于蟻群系統(tǒng)的偽隨機(jī)轉(zhuǎn)移策略，每次迭代所獲得的最優(yōu)解并不相同，可能包含更優(yōu)質(zhì)的解成分，且與全局最優(yōu)解也可能不一致。因此在全局信息素更新時(shí)，不僅考慮全局最優(yōu)解的信息素增強(qiáng)，還應(yīng)對(duì)每次迭代所得到的最優(yōu)解進(jìn)行增強(qiáng)，以提高蟻群的多樣性。據(jù)此提出了根據(jù)蟻群相似度自適應(yīng)調(diào)整信息素的更新策略，更新規(guī)則如公式（10）所示：

式中，ρ是全局信息素?fù)]發(fā)系數(shù)，Simi_pop(t)是蟻群在第t次迭代后的相似度，Δτibij(t)表示迭代最優(yōu)路徑對(duì)應(yīng)的信息素增量，Lib是迭代最優(yōu)路徑的長(zhǎng)度，Tib是迭代最優(yōu)路徑。

在上述的信息素更新策略中，不僅對(duì)每次迭代所得到的最優(yōu)解進(jìn)行信息素更新，而且增強(qiáng)幅度與蟻群的相似度有關(guān)。蟻群的相似度越大，說(shuō)明個(gè)體越集中，應(yīng)加大迭代最優(yōu)解的更新強(qiáng)度，避免早熟收斂，反之，說(shuō)明候選解分布較均勻，減少迭代最優(yōu)解上的更新強(qiáng)度，以加快算法收斂。通過(guò)這種自適應(yīng)信息素更新機(jī)制，使得信息素不會(huì)過(guò)于集中或者分散，從而平衡多樣性和收斂性之間的矛盾。

4 仿真實(shí)驗(yàn)及數(shù)據(jù)結(jié)果分析

由于TSP問(wèn)題已成為測(cè)試智能算法的標(biāo)準(zhǔn)測(cè)試集，因此采用TSPLIB中的測(cè)試算例對(duì)所提出的自適應(yīng)改進(jìn)蟻群算法進(jìn)行仿真實(shí)驗(yàn)，算例名稱后面的數(shù)字表示TSP問(wèn)題的節(jié)點(diǎn)數(shù)量。實(shí)驗(yàn)中對(duì)每個(gè)算例均獨(dú)立測(cè)試10次，取其平均值作為實(shí)驗(yàn)結(jié)果。算法參數(shù)α、β、ρ、δ與q0等參數(shù)取值與文獻(xiàn)[8]保持一致，如表1 所示。信息素初值τ0=(n×Lnn)-1，n為測(cè)試算例的節(jié)點(diǎn)數(shù)量，Lnn是按照最近鄰算法得到的最優(yōu)路徑長(zhǎng)度。蟻群中螞蟻個(gè)數(shù)與算例的節(jié)點(diǎn)數(shù)量相等，最大迭代次數(shù)為500 次，終止條件為達(dá)到設(shè)定迭代次數(shù)。根據(jù)文獻(xiàn)[28]確定q0的取值范圍為[ ]0.4,0.9 。所有蟻群算法均采用3-Opt局部搜索方法[29]來(lái)優(yōu)化蟻群的尋優(yōu)結(jié)果。

表1 算法參數(shù)設(shè)置

4.1 自適應(yīng)改進(jìn)蟻群算法的敏感性分析

參數(shù)q0對(duì)蟻群系統(tǒng)的優(yōu)化性能具有重要的影響。通過(guò)對(duì)比實(shí)驗(yàn)研究自適應(yīng)改進(jìn)蟻群算法的參數(shù)敏感性。首先從最優(yōu)解、標(biāo)準(zhǔn)差、首遇迭代次數(shù)及成功率等指標(biāo)分析改進(jìn)策略對(duì)蟻群系統(tǒng)性能的影響。最優(yōu)解反映了算法的優(yōu)化能力，標(biāo)準(zhǔn)差反映了算法的穩(wěn)定性，首遇迭代次數(shù)是算法首次獲得已知最優(yōu)解所需的平均迭代次數(shù)，成功率是算法多次運(yùn)行中獲得已知最優(yōu)解的比例。為了說(shuō)明改進(jìn)算法的適應(yīng)能力，選擇eil51、kroB100、kroB150 以及kroA2000 等不同規(guī)模的TSP 算例進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2～5所示。為了方便對(duì)比和深入理解q0對(duì)蟻群性能的影響，在表2～5中給出經(jīng)典蟻群系統(tǒng)在不同q0值時(shí)的實(shí)驗(yàn)結(jié)果。同時(shí)還分別給出了算法在優(yōu)化過(guò)程中的參數(shù)q0、相似度的變化以及最優(yōu)路徑的收斂曲線，如圖1～4所示。

由表2和3可看出：對(duì)于小規(guī)模的TSP問(wèn)題，如eil51及kroB100 測(cè)試集，ACS 算法在各個(gè)q0值均獲得最優(yōu)解，同時(shí)改進(jìn)算法也都獲得最優(yōu)解。對(duì)于首遇迭代次數(shù)，eil51 在q0=0.6 時(shí)最小，kroB100 在q0=0.9 時(shí)最??；改進(jìn)算法的首遇迭代次數(shù)在eil51的所有測(cè)試中雖不是最小，但排名也較靠前，在kroB100 測(cè)試中取得最小的首遇迭代次數(shù)。由圖1 和2 的收斂曲線可知，隨著節(jié)點(diǎn)規(guī)模的增大，改進(jìn)算法的首遇迭代次數(shù)逐漸減小，體現(xiàn)出算法的尋優(yōu)能力的提升。由圖1、2 的相似度變化曲線可知，兩種算法的相似度差別不大，改進(jìn)算法的相似度略小于ACS算法。

表2 eil51算例的實(shí)驗(yàn)結(jié)果（已知最優(yōu)解為426）

表3 kroB100算例的實(shí)驗(yàn)結(jié)果（已知最優(yōu)解為22 141）

表4 kroB150算例的實(shí)驗(yàn)結(jié)果（已知最優(yōu)解為26 130）

表5 kroA200算例的實(shí)驗(yàn)結(jié)果（已知最優(yōu)解為29 368）

圖1 eil51算例時(shí)q0、相似度與收斂曲線對(duì)比

圖2 kroB100算例時(shí)q0、相似度與收斂曲線對(duì)比

由表4可知，對(duì)于kroB150測(cè)試集，兩種算法的成功率均為50%。ACS 算法僅在q0=0.9 時(shí)獲得最優(yōu)解，平均值與標(biāo)準(zhǔn)差最小，在其他值時(shí)無(wú)法獲得最優(yōu)解。改進(jìn)算法也獲得最優(yōu)解，雖然其標(biāo)準(zhǔn)差和平均解略大于ACS算法在q0=0.9 時(shí)的值，但在都獲取最優(yōu)解的前提下，改進(jìn)算法的首遇迭代次數(shù)遠(yuǎn)小于ACS 算法，說(shuō)明改進(jìn)算法在具有較好尋優(yōu)能力的前提下，具有較快的收斂速度，圖3（b）的最優(yōu)路徑收斂曲線給出進(jìn)一步的驗(yàn)證。由圖3（a）可知，改進(jìn)算法的相似度好于ACS算法，體現(xiàn)出自適應(yīng)調(diào)整策略的作用。

圖3 kroB150算例時(shí)q0、相似度與收斂曲線對(duì)比

對(duì)于kroA200測(cè)試集，由表5可知，改進(jìn)算法用較少的迭代次數(shù)獲得已知最優(yōu)解，而ACS 算法在各個(gè)q0值均未能取得已知最優(yōu)解。由圖4可知，在整個(gè)迭代過(guò)程中改進(jìn)算法的相似度明顯小于ACS 算法，說(shuō)明自適應(yīng)調(diào)整策略使算法呈現(xiàn)較好的多樣性，同時(shí)改進(jìn)算法解的質(zhì)量?jī)?yōu)于ACS算法。

總的來(lái)說(shuō)，雖然ACS 算法在某個(gè)q0值取得了較好的性能，但是這一參數(shù)值對(duì)于不同的TSP問(wèn)題缺乏適應(yīng)能力，通用性較差。對(duì)于改進(jìn)蟻群算法，只需要設(shè)定參數(shù)變化范圍，在大多數(shù)情況下都均能取得良好的優(yōu)化性能，顯著提高解的質(zhì)量，有效平衡多樣性和收斂速度之間的矛盾，說(shuō)明了自適應(yīng)調(diào)整策略的有效性，同時(shí)自適應(yīng)調(diào)整策略也有效降低了蟻群算法的參數(shù)敏感性，使算法具有更好的適應(yīng)能力。

4.2 改進(jìn)算法性能測(cè)試與分析

圖4 kroA200算例時(shí)q0、相似度與收斂曲線對(duì)比

為了驗(yàn)證自適應(yīng)改進(jìn)蟻群算法的有效性及優(yōu)化能力，選擇與文獻(xiàn)[24]相同的TSP測(cè)試算例進(jìn)行仿真實(shí)驗(yàn)，并與其結(jié)果進(jìn)行對(duì)比。其中，改進(jìn)算法參數(shù)如表1 所示，其他算法參數(shù)見(jiàn)文獻(xiàn)[24]。表6 給出了本文算法與文獻(xiàn)[24]的求解結(jié)果。

由表6 可以看出：在解決較少節(jié)點(diǎn)TSP 問(wèn)題（如eil51、berlin52、st70、eil76 和pr107 等）時(shí)，各算法的搜索能力均很強(qiáng)，但是改進(jìn)算法的平均解，標(biāo)準(zhǔn)偏差優(yōu)于對(duì)比算法，表明改進(jìn)算法不僅尋優(yōu)能力強(qiáng)，而且具有較好的穩(wěn)定性；隨著TSP 問(wèn)題規(guī)模增大（如kroB150 和kroA200）時(shí)，改進(jìn)算法的解質(zhì)量?jī)?yōu)于對(duì)比算法，無(wú)論是最優(yōu)解、最差解、平均解、標(biāo)準(zhǔn)偏差還是誤差，本文算法均顯示出一定優(yōu)勢(shì)。對(duì)于kroB200，雖然所有算法均未能找到已知最優(yōu)解，但是改進(jìn)算法解偏差最小，最差解、平均解、標(biāo)準(zhǔn)偏差也最小，說(shuō)明改進(jìn)算法具有良好的優(yōu)化性能。

利用所設(shè)計(jì)的自適應(yīng)改進(jìn)蟻群算法對(duì)TSPLIB 中eil51、st70、eil76、pr107、ch130、kroA100、kroB150 和kroA200測(cè)試算例進(jìn)行優(yōu)化，各算例所獲得的最優(yōu)路線如圖5所示。

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

本文利用種群相似度對(duì)種群內(nèi)個(gè)體的多樣性進(jìn)行度量，根據(jù)迭代優(yōu)化過(guò)程中種群相似度的變化自動(dòng)調(diào)整蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則的控制參數(shù)和信息素更新策略。通過(guò)狀態(tài)轉(zhuǎn)移規(guī)則控制參數(shù)的自適應(yīng)調(diào)整，使得蟻群算法能夠始終保持一定的探索能力，改進(jìn)的信息素更新策略不僅強(qiáng)化了蟻群對(duì)歷史最優(yōu)解鄰域內(nèi)的搜索，而且使得算法對(duì)迭代最優(yōu)解鄰域進(jìn)行搜索，在加快算法收斂速度的同時(shí)防止陷入局部最優(yōu)，有效地平衡了種群多樣性與收斂速度的矛盾。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。由于蟻群算法參數(shù)多且存在一定的關(guān)聯(lián)性，今后將深入研究算法其他參數(shù)與信息素更新機(jī)制對(duì)優(yōu)化性能的影響，并完善理論模型，提高蟻群算法的適用性。

表6 不同測(cè)試集下的算法性能對(duì)比實(shí)驗(yàn)結(jié)果

圖5 自適應(yīng)改進(jìn)蟻群算法最優(yōu)路線圖