【文章內(nèi)容簡(jiǎn)介】 ctedCity=ii。 } } if (nSelectedCity == 1) { for (int i=0。iN_CITY_COUNT。i++) { if (m_nAllowedCity[i] == 1) //城市沒去過 { nSelectedCity=i。 break。 } } }//返回結(jié)果return nSelectedCity。}（3）更新環(huán)境信息素//更新環(huán)境信息素,基本算法//*void CTsp::UpdateTrial(){ //臨時(shí)保存信息素 double dbTempAry[N_CITY_COUNT][N_CITY_COUNT]。 memset(dbTempAry,0,sizeof(dbTempAry))。 //先全部設(shè)置為0//計(jì)算新增加的信息素,保存到臨時(shí)數(shù)組里 int m=0。 int n=0。 for (int i=0。iN_ANT_COUNT。i++) //計(jì)算每只螞蟻留下的信息素 { for (int j=1。jN_CITY_COUNT。j++) { m=m_cAntAry[i].m_nPath[j]。 n=m_cAntAry[i].m_nPath[j1]。 dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength。 dbTempAry[m][n]=dbTempAry[n][m]。 } //最后城市和開始城市之間的信息素 n=m_cAntAry[i].m_nPath[0]。 dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength。 dbTempAry[m][n]=dbTempAry[n][m]。 } //更新環(huán)境信息素 for (i=0。iN_CITY_COUNT。i++) { for (int j=0。jN_CITY_COUNT。j++) { g_Trial[i][j]=g_Trial[i][j]*ROU+dbTempAry[i][j]。 //最新的環(huán)境信息素 = 留存的信息素 + 新留下的信息素 } }}（4）檢查終止條件如果達(dá)到最大迭代次數(shù)，算法終止，輸出最終最優(yōu)解；否則，執(zhí)行（5），輸出當(dāng)前迭代最優(yōu)解，重新初始化所有的螞蟻的路徑矩陣所有元素初始化為0，禁忌表表清空，允許表表中加入所有的城市節(jié)點(diǎn)。隨機(jī)選擇它們的起始位置（也可以人工指定）。在路徑矩陣中加入起始節(jié)點(diǎn)，允許表中去掉該起始節(jié)點(diǎn)，重復(fù)執(zhí)行（2），（3）,(4)步。（5）輸出最優(yōu)值每次迭代結(jié)束，輸出當(dāng)前迭代編號(hào)以及本次迭代中最優(yōu)解螞蟻的路徑長(zhǎng)度。 蟻群算法的參數(shù)分析 從蟻群算法的模型中可以看出，蟻群算法的參數(shù)空間龐大，合適的參數(shù)組合能夠過有全局收喲能力和較快的瘦臉術(shù)的，不合適的參數(shù)組合則會(huì)使得算法收斂較慢或者達(dá)到局部最優(yōu)解。然而，目前對(duì)各參數(shù)該如何選擇也沒有嚴(yán)格的理論依據(jù)，只是根據(jù)經(jīng)驗(yàn)和實(shí)驗(yàn)來選取合適的參數(shù)值?；诖?，國(guó)內(nèi)外許多研究人員在蟻群算法的參數(shù)分析和優(yōu)化組合方面做了大量的工作。對(duì)α、β、ρ、N_ANT_COUNT（N_ANT_COUNT，螞蟻數(shù)量）等參數(shù)的選擇進(jìn)行了初步研究； 螞蟻數(shù)量N_ANT_COUNT螞蟻算法是通過多個(gè)候選解組成的群體進(jìn)化過程來搜索最優(yōu)解，所以螞蟻的數(shù)目N_ANT_COUNT對(duì)一群算法有一定的影響。N_ANT_COUNT大，會(huì)提高蟻群算法的全局搜索能力和穩(wěn)定性，但數(shù)量過大會(huì)導(dǎo)致大量曾被搜索過的路徑上的信息素變化趨于平均，信息正反饋?zhàn)饔脺p弱，隨機(jī)性增強(qiáng)，收斂速度減慢。反之，N_ANT_COUNT小，會(huì)使從來未被搜索到的解上的信息素減小到接近于0，全局搜索的隨機(jī)性減弱，雖然收斂速度加快，但是會(huì)使算法的全局性能降低，穩(wěn)定性變差，出現(xiàn)過早停滯現(xiàn)象。經(jīng)大量的仿真試驗(yàn)獲得：當(dāng)N_ANT_COUNT屬于【*N_CITY_COUNT,09*N_CITY_COUNT】時(shí)（N_CITY_COUNT為城市數(shù)量），蟻群算法的全局收斂性和收斂速度都比較好。 啟發(fā)因子α啟發(fā)銀子α是表示螞蟻在運(yùn)動(dòng)過程中所積累的信息素在知道蟻群搜索中的相對(duì)重要程度，其大小反映了螞蟻在路徑搜索中隨機(jī)因素作用強(qiáng)弱。α越大，螞蟻選擇以前走過的路徑可能性就越大，實(shí)現(xiàn)自催化過程，但搜索的隨機(jī)性減弱；α越小，易使蟻群算法過早陷入局部最優(yōu)。而已有研究證明：對(duì)于小規(guī)模的TSP問題，在蟻群算法的三種模型中α=1時(shí)，解的質(zhì)量和穩(wěn)定性都是最好的。 期望啟發(fā)因子β期望啟發(fā)因子β是表示能見度相對(duì)重要程度的參數(shù)。β的大小反映了螞蟻在路徑搜索過程中確定性因素作用的強(qiáng)弱。而已有研究表明：β過小，講導(dǎo)致螞蟻群體陷入純粹的隨機(jī)搜索，在此情況下很難找到最優(yōu)解；β過大，螞蟻在局部點(diǎn)上選擇局部最短路徑的可能性越大，雖然加快了收斂速度，但減弱了隨機(jī)性，易陷入局部最優(yōu)。對(duì)于TSP問題，不同城市規(guī)模，β的具體取值各有不同。一般β∈【2,5,8】時(shí)，算法的綜合性比較好。 信息素?fù)]發(fā)度ρ在蟻群算法中，人工螞蟻是具有人類記憶功能的，隨著時(shí)間的推移，以前留下的信息將要逐漸消失。如前所述，在算法模型中，參數(shù)ρ表示信息素?fù)]發(fā)度，其大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度；1ρ信息素殘留印子，反映了螞蟻個(gè)體之間相互影響的強(qiáng)弱。研究表明：在其它參數(shù)相同的情況下，信息素?fù)]發(fā)度ρ的大小對(duì)一群算法的收斂性影響非常大，ρ與循環(huán)次數(shù)近似成反比關(guān)系。當(dāng)ρ極小時(shí)，路徑上殘留信息占主導(dǎo)地位，信息正反饋?zhàn)饔孟鄬?duì)較弱，手術(shù)的隨機(jī)性增強(qiáng)，因而蟻群算法的收斂速度很慢。若ρ較大時(shí)，正反饋?zhàn)饔谜贾鲗?dǎo)地位，搜素的隨機(jī)性減弱，導(dǎo)致收斂速度快，但易陷入局部最優(yōu)狀態(tài)。對(duì)于TSP問題，不同的問題規(guī)模，ρ的曲子也不盡相同。一般來說，ρ∈【,】時(shí)，性能的算法較好。 總信息量（DBQ）總信息量DBQ為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)路徑上的信息素總量，在基本一群算法中他是一個(gè)產(chǎn)量。一般的理解是：總信息量DBQ越大，則在螞蟻已經(jīng)走過的路徑上信息素的累積越快，可以加強(qiáng)蟻群搜素時(shí)的正反饋性能，有助于算法的快速收斂。DBQ過小，則信息素濃度增長(zhǎng)太慢，正反饋信息太少，使算法難以收斂。研究表明：在蟻周模型中，由于TSP的規(guī)模不同，路徑長(zhǎng)度各不相同，如果讀不通的TSP使用相同的DBQ值，則信息素總量更新尺度是不同的，最終修改信息素的程度存在很大不穩(wěn)定性。DBQ的取值應(yīng)與說處理的TSP的規(guī)模相對(duì)應(yīng)，確保信息素總量更新在可控制范圍內(nèi)。在小規(guī)模TSP問題中，DBQ=100是大多數(shù)研究學(xué)者認(rèn)為所公認(rèn)的較好值。第3章 改進(jìn)的蟻群算法（1）采用輪盤賭選擇代替了基本框架中通過啟發(fā)式函數(shù)和信息素選擇路徑，改進(jìn)蟻群算法的信息素傳遞參數(shù)，讓整個(gè)算法更快速的找到最優(yōu)解。（2）最大最小優(yōu)化主要作了如下改進(jìn)： A：每次迭代結(jié)束后，只有最優(yōu)解所屬路徑上的信息被更新，從而更好地利用了歷史信息； B：為了避免算法過早收斂于并非全局最優(yōu)的解，將各條路徑可能的外激素濃度限制于【T_min,T_max】,超出這個(gè)范圍的值被強(qiáng)制設(shè)為T_min或者是T_max，可以有效的避免某條路徑上的信息量遠(yuǎn)大于其余路徑，使得所有螞蟻都集中到同一條路徑上，從而使算法不再擴(kuò)散； C：初始時(shí)刻，各條路徑上外激素的其實(shí)濃度設(shè)為T_max，在算法的初始時(shí)刻，P（0p1，信息素政法系數(shù)）取較小值時(shí)，算法有更好的發(fā)現(xiàn)較好解的能力。所有螞蟻完成一次迭代后，按下式對(duì)路徑上的信息作全局更新：τij (t+1)=(1)τij (t)+?τijbest(t), ρ∈(0,1)?τijbest=1Lbest 0, 否則,(如果邊（I,j）包含在最優(yōu)路徑中 允許更新的路徑可以全局最優(yōu)解，或本次迭代的最優(yōu)解。實(shí)踐證明，逐漸增加全局最優(yōu)解的使用頻率，會(huì)使該算法獲得較好的性能。 輪盤賭選擇 輪盤賭選擇基本思想個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中遺傳到下一代群體的概率為：Pi=Fi/i=1nFi 輪盤賭選擇工作過程 設(shè)想群體全部個(gè)體的適當(dāng)性分?jǐn)?shù)由一張餅圖來代表 (見圖)。群體中每一染色體指定餅圖中一個(gè)小塊。塊的大小與染色體的適應(yīng)性分?jǐn)?shù)成比例，適應(yīng)性分?jǐn)?shù)愈高，它在餅圖中對(duì)應(yīng)的小塊所占面積也愈大。為了選取一個(gè)染色體，要做的就是旋轉(zhuǎn)這個(gè)輪子，直到輪盤停止時(shí)，看指針停止在哪一塊上，就選中與它對(duì)應(yīng)的那個(gè)染色體。 舉例：輪盤賭選擇法的選擇概率計(jì)算表個(gè)體1234567891011適應(yīng)度選擇概率累計(jì)概率，則6號(hào)個(gè)體被選中。實(shí)現(xiàn)代碼：//*//輪盤選擇，選擇第一個(gè)大于隨機(jī)數(shù)的點(diǎn) double dbTemp=。 if (dbTotal ) //總的信息素值大于0 { dbTemp=rnd(,dbTotal)。 //取一個(gè)隨機(jī)數(shù) for (int i=0。iN_CITY_COUNT。i++) { if (m_nAllowedCity[i] == 1) //城市沒去過