【正文】 頂點(diǎn)vi 和部分解中頂點(diǎn)相連的邊上的信息素的和作為頂點(diǎn)vi 的信息素；而且該算法不使用局部啟發(fā)信息，僅靠信息素來引導(dǎo)螞蟻搜索，在迭代初期有一定的盲目性。在新型蟻群算法中，信息素留在了頂點(diǎn)上，而不再是邊上，同時(shí)增加了局部啟發(fā)來引導(dǎo)螞蟻，AntClique_V 算法概率選擇公式如下：其中，τ i 為頂點(diǎn)v i 上的信息素的強(qiáng)度。α為信息素權(quán)重， β為局部啟發(fā)信息權(quán)重，這兩個(gè)量均為常量。η i為頂點(diǎn)v i 上的局部啟發(fā)信息。其中deg(v i ) 為頂點(diǎn)v i 的度；Q 為常量，可22知 ；（本文中實(shí)驗(yàn)數(shù)據(jù)是在Q取為100 時(shí)獲得的）。 η i 的定義方法有很多種，例如： 可以等于Candidate 集合中與v i 有邊相連的頂點(diǎn)數(shù)；也可以等于頂點(diǎn)v i 的度。本文利用公式 38 設(shè)η i 的初始值。這樣定義η i 的優(yōu)點(diǎn)在于：沒有和 Candidate 集合關(guān)聯(lián)，不需反復(fù)計(jì)算；同時(shí)可以為其限定一個(gè)范圍 。缺點(diǎn)在于，當(dāng)一個(gè)圖中的所有頂點(diǎn)的度相差不大時(shí)，（DIMACS benchmarks 中的有許多實(shí)例的頂點(diǎn)的度相差很小， 其最大度為468，而最小度為431；MANNa45 的最大度為 1031，最小度為1000；Hamming84 和Hamming104 的所有頂點(diǎn)的度是相等的，分別為163，848）η i的取值很接近，它在螞蟻搜索過程中失去指導(dǎo)意義，但當(dāng)頂點(diǎn)的度差別較大時(shí)，使用局部啟發(fā)信息能明顯提高搜索的效率。最后，說明候選組件集合Candidate 的確定方法：(a) 隨機(jī)選擇一個(gè)頂點(diǎn)v f 加入C 后，Candidate ←{v i| (vf, vi)∈E}。(b) 當(dāng)選中v i 加入C 后，則 Candidate ←Candidate∩{ vj | (vi,vj)∈E}。 信息素策略信息素策略有很多種：在最早提出的螞蟻系統(tǒng)（Ant System） [27]中,提出了三種信息素更新方式，分別稱之為：antquantity system，antdensity system，antcyclesystem，它們的差別在于表達(dá)式 的不同：在antquantity 算法中，從城市i 到j(luò)的螞蟻在路徑上殘留的信息量為一個(gè)常量；在antdensity 算法中，殘留的信息量會(huì)隨著城市間距離的不同而變化；在antcycle 算法中，從城市i 到j(luò) 的螞蟻在路徑上殘留的信息量與該次循環(huán)中所獲得解的優(yōu)劣有關(guān)，更新規(guī)則會(huì)讓較優(yōu)的解上對(duì)應(yīng)的信息量逐漸增大。AntQ 在軌跡更新方式上有了較大改進(jìn)，它不僅考慮了下一步轉(zhuǎn)移的期望收益，而且包含了當(dāng)前循環(huán)中最好環(huán)游（iterationbest）或者全局最好環(huán)游（globalbest）的影響。ACS [26]是在AS 以及AntQ 的基礎(chǔ)上而提出的。ACS 的特點(diǎn)是在螞蟻探索路徑的過程中應(yīng)用局部更新，同時(shí)只對(duì)構(gòu)成最好環(huán)游（當(dāng)前循環(huán)中最好環(huán)游或者全局最好環(huán)游）的弧集進(jìn)行全局更新。本章提到的兩個(gè)最大團(tuán)問題的蟻群算法的信息素策略都是采用St252。tzle 和Hoos 提出的MaxMin AS（MMAS ） [24]，其主要特點(diǎn)在于：每次迭代中只有獲得最短行程的螞蟻進(jìn)行信息素更新；信息素的取值被限制在[τ min , τ max] 范圍內(nèi)，各路23徑初始化信息素濃度為τ max 。通過這種極限控制，可以防止個(gè)別路徑的信息素濃度被過度增強(qiáng)，從而避免算法過早停滯。St252。tzle 和Hoos 還進(jìn)一步提出了信息素平滑機(jī)制， 以更好地阻止算法停滯。其方法是按比例調(diào)整信息素更新：。于是信息素濃度已經(jīng)很高的路徑所能夠得到的信息素增強(qiáng)將小于信息素濃度較小的路徑，這將有助于更好路徑的搜索。AntClique_V 和AntClique_E 的信息素更新策略的不同之處在于：AntClique_V 將信息素留在了頂點(diǎn)上，而AntClique_E 將信息素留在了邊上，下面以AntClique_V 為例詳細(xì)介紹信息素更新策略：給每個(gè)頂點(diǎn)v i 設(shè)置一個(gè)信息素變量 τ i，各頂點(diǎn)初始化信息素濃度為 τ max ，更新信息素是一次循環(huán)結(jié)束之后，根據(jù)本次循環(huán)所有螞蟻構(gòu)造的團(tuán)更新各個(gè)頂點(diǎn)上的信息素。信息素的更新分為兩步： (a) 信息素?fù)]發(fā)，在自然環(huán)境中，螞蟻留在路上的信息素會(huì)隨時(shí)間的推移而揮發(fā)，這個(gè)步驟就是模擬揮發(fā)現(xiàn)象。其中， ρ為揮發(fā)系數(shù)，為常數(shù)，可根據(jù)經(jīng)驗(yàn)給定。(b) 增加信息素，當(dāng)螞蟻?zhàn)哌^某條路徑時(shí)，就會(huì)在該路徑上留下信息素，該路徑上的信息素量就會(huì)增加。由于在最大團(tuán)問題中沒有路徑的概念，算法需要滿足：子集C 越優(yōu)秀，其中頂點(diǎn)的被選擇概率越高。所以，對(duì)螞蟻找到的最大團(tuán)Cbest、 Cbetter 中的頂點(diǎn)的信息素進(jìn)行增加，增加量為： |Cbest|為目前為止找到的最優(yōu)解；| C better |為本次循環(huán)中所有螞蟻找到的最優(yōu)解。 算法時(shí)間復(fù)雜度分析最大團(tuán)問題最早被證明是NP完全問題之一，即在P≠NP 的假設(shè)下，找不到一個(gè)算法能保證在多項(xiàng)式時(shí)間內(nèi)得到最優(yōu)解。人們不得不嘗試用一些并不一定可以求解到最優(yōu)解的算法的啟發(fā)式算法，來求解這類問題。那么衡量這些算法優(yōu)劣的一個(gè)24重要指標(biāo)就是算法的時(shí)間復(fù)雜度。設(shè)NC 表示算法的最大循環(huán)次數(shù)，圖的頂點(diǎn)數(shù)為n ，蟻群中螞蟻數(shù)量為m ，則最大團(tuán)問題的新型蟻群算法—AntClique_V 的時(shí)間復(fù)雜度為（算法的偽代碼描述見 節(jié)）：第2 行的時(shí)間復(fù)雜度是O(n)，第4—12 行的時(shí)間復(fù)雜度是O(mn 2)（包括5—6 行O(n) ，7—10 行 O(n2)，11 行O(n)），第13 行的時(shí)間復(fù)雜度是O(n)，算法的總的時(shí)間復(fù)雜度為O(NCmn 2)。而最大團(tuán)問題的傳統(tǒng)蟻群算法AntClique_E其總的時(shí)間復(fù)雜度也為O(NCmn 2)，但其中第11 、13 行的時(shí)間復(fù)雜度是O(n 2)。由此可見，對(duì)于子集類問題使用新型蟻群算法，對(duì)其運(yùn)算速度有一定提高。 實(shí)驗(yàn)結(jié)果及結(jié)論下面用DIMACS benchmarks 中的部分實(shí)例來測(cè)試最大團(tuán)問題的新型算法AntClique_V。表31 中列出的數(shù)據(jù)是在β=2 ， ρ= ，τ max =4 ，τmin = ，最大循環(huán)次數(shù)為3000，運(yùn)行25 次得到的結(jié)果。（由于本人程序未能達(dá)到預(yù)想的效果，實(shí)際運(yùn)行結(jié)果所得最優(yōu)解與已知最優(yōu)解有差距。為討論研究的方便，此表數(shù)據(jù)為使用已有的與本人算法原理相同的AntClique_V算法的程序運(yùn)行結(jié)果。以它為例討論算法的原理。后同）表31：運(yùn)行結(jié)果AntClique_V7 只螞蟻 30 只螞蟻圖例已知最優(yōu)解 α=2 α=3 α=2 α=3 34 34() 34() 34() 34() 44 44() 44() 44() 44() =57 56() 56() 57() 56()MANN_a27 126 126() 126() 126() 126()MANN_a45 345 344() 343() 344() 343()brock200_2 12 12() 12() 12() 12()brock200_4 17 16() 16() 16() 16()brock400_2 29 25() 25() 25() 25()brock400_4 33 25() 25() 25() 25()brock800_2 24 21() 20() 21() 20()brock800_4 26 20() 21() 21() 21()Hamming84 16 16() 16() 16() 16()25Hamming104 40 34() 36() 35() 40()Keller4 11 11() 11() 11() 11()Keller5 27 27() 27() 27() 27()Keller6 =59 49() 55() 51() 59()p_hat300_1 8 8() 8() 8() 8()p_hat300_2 25 25() 25() 25() 25()p_hat300_3 36 36() 36() 36() 36()p_hat700_1 11 11() 11() 11() 11()p_hat700_2 44 44() 44() 44() 44()p_hat700_3 =62 62() 62() 62() 62()通常在ACO 算法中，其參數(shù)的選取直接關(guān)系到算法的求解能力，尤其是信息素權(quán)重因子α 的選取對(duì)結(jié)果的影響非常重要：從表 31 可以看出，對(duì)于大多數(shù)例圖當(dāng)α= 2 或α=3 時(shí)就能得到其較優(yōu)解，但對(duì)于復(fù)雜的例圖keller6，α必須取到3，才能獲得較好的求解能力。相反的，對(duì)于brock800_4，當(dāng)α=3 時(shí)，運(yùn)行25 ，這說明信息素作用過強(qiáng)，有時(shí)會(huì)導(dǎo)致早熟。螞蟻的數(shù)量也決定著求解的能力，螞蟻數(shù)目越多，其平均結(jié)果越好，也越容易找到最優(yōu)解：keller6，同樣是 α=3 時(shí)，但螞蟻數(shù)量為7 時(shí)找到的最優(yōu)解為55，但當(dāng)螞蟻數(shù)量增加至30 時(shí)，就能找到59；對(duì)于brock200_4，當(dāng)螞蟻數(shù)量增加至50 只時(shí)，運(yùn)行3000 次迭代，能找到最優(yōu)解17；但另一方面螞蟻數(shù)量越多，運(yùn)算量越大，所用時(shí)間也越長(zhǎng)?？偟恼f來當(dāng)圖形復(fù)雜時(shí)，應(yīng)適當(dāng)增加螞蟻數(shù)量。從表31 中的實(shí)驗(yàn)結(jié)果可以看出，只要參數(shù)選擇的比較合適，此算法能較好的解決最大團(tuán)問題。 本章小結(jié)本章主要用一種針對(duì)子集類問題的蟻群算法思想解決經(jīng)典的組合優(yōu)化問題—最大團(tuán)問題。首先介紹了最大團(tuán)問題和針對(duì)子集類問題的蟻群算法思想，接著將二者結(jié)合提出了最大團(tuán)問題的新型蟻群算法，通過仿真實(shí)驗(yàn)表明該算法的性能和運(yùn)算速度較最大團(tuán)問題的傳統(tǒng)蟻群算法有著明顯的提高。26第四章 蟻群算法的參數(shù)研究蟻群算法運(yùn)算結(jié)果的好壞，在很大程度上取決于參數(shù)的選擇，然而目前參數(shù)的選擇還沒有理論依據(jù)，一般人們都是根據(jù)經(jīng)驗(yàn)來給定參數(shù)的。參數(shù)選擇是否成功也只能通過仿真實(shí)驗(yàn)的結(jié)果來觀察。本章我們就以最大團(tuán)問題的蟻群算法為例，研究蟻群算法中參數(shù)的選擇，并提出使用動(dòng)態(tài)局部啟發(fā)信息η的改進(jìn)策略。 ACO 算法中參數(shù)的研究 啟發(fā)式因子 [27]啟發(fā)式因子α和β分別決定著信息素τij 和局部啟發(fā)信息ηij 的相對(duì)重要程度。它們?cè)谙伻核阉髦懈髯运鸬淖饔眉认嚓P(guān)又矛盾。α的大小反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度，其值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機(jī)性減弱。α值過大會(huì)使蟻群的搜索過早陷于局部最優(yōu)。β的大小反映了蟻群在路徑搜索中確定性因素作用的強(qiáng)度，其值越大，螞蟻在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大。雖然搜索的收斂速度加快，但螞蟻在最優(yōu)路徑的搜索過程中隨機(jī)性減弱，也易于陷入局部最優(yōu)。蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過程必須有很強(qiáng)的隨機(jī)性；而蟻群算法的快速收斂性能，又要求蟻群的搜索過程必須要有較高的確定性。因此，兩者對(duì)蟻群算法性能的影響是互相配合、密切相關(guān)的。到目前為止，還沒有數(shù)學(xué)上的證明為選取α、β的數(shù)值提供理論上的27依據(jù)，對(duì)α、β的取值只能通過試驗(yàn)的方式進(jìn)行測(cè)試，以獲得最佳取值。在下面的仿真分析中，實(shí)驗(yàn)所用的實(shí)例為DIMACS benchmarks ，它有500 個(gè)頂點(diǎn)，112332 條邊，是一個(gè)比較難的實(shí)例圖，很多算法都不能找到其最優(yōu)解57。實(shí)驗(yàn)的相關(guān)參數(shù)為：螞蟻數(shù)量為7 只，最大迭代次數(shù)為3000 次，信息素?fù)]發(fā)度為ρ= ，取啟發(fā)因子α和β不同數(shù)值的組合，運(yùn)算結(jié)果為運(yùn)行25組獲得的最優(yōu)解（平均解）進(jìn)行仿真比較，從仿真實(shí)驗(yàn)結(jié)果可以得出：首先β的取值對(duì)實(shí)驗(yàn)的結(jié)果影響不大；分析其原因，因?yàn)樗惴ㄖ芯植繂l(fā)信息ηi 的定義（參見式38）與頂點(diǎn) i 的度有關(guān)， 中，頂點(diǎn)的最大度為468，最小度為431，相差太小，其局部啟發(fā)信息ηi相差不大，所以對(duì)算法的影響也不大。改進(jìn)辦法：可以考慮在頂點(diǎn)度相差不大時(shí)，純粹使用信息素指導(dǎo)螞蟻搜索，這樣可以提高運(yùn)算速度；而在頂點(diǎn)度相差較大時(shí)，由信息素和局部啟發(fā)信息聯(lián)合指引螞蟻搜索。也可以考慮重新定義局部啟發(fā)信息ηi，使它和頂點(diǎn)i 在候選集中的度成正比，或者和候選集中與頂點(diǎn)i 有邊相連的頂點(diǎn)在候選集中的度的和成正比。其次， α過大或過小時(shí)，搜索結(jié)果均不理想：從實(shí)驗(yàn)數(shù)據(jù)中可以看到，當(dāng)α≥5 時(shí)，雖然算法運(yùn)行25 次中總能找到的較優(yōu)解55甚至最優(yōu)解57，但是運(yùn)行25 次得到的25 個(gè)解的平均值就下降了許多。表明25 次中有若干次得到的解很差，是局部最優(yōu)解。這種情況下算法的穩(wěn)定性明顯降低了。而當(dāng)α≤1 時(shí)，無論是算法運(yùn)行25 次中得到的最好的解，還是解平均值，都很差，算法陷入純粹的、無休止的隨機(jī)搜索中，在這種情況下一般也很難找到最優(yōu)解。在本算法中，α的最佳取值范圍在2~3。28圖41， α取值對(duì)算法性能的影響圖41 為螞蟻數(shù)量取7 只，最大迭代次數(shù)為1500 次，信息素?fù)]發(fā)度為ρ= ，τmax = 4 ， τmin = ，β=0 ，α分別取0 ，1，2，3，5 時(shí)繪制的曲線圖。從圖中可以明顯看出隨著α取值的增大，算法的收斂速度逐步提高。當(dāng)α取0 或1 值時(shí)，算法收斂速度太慢，算法效率類似于隨機(jī)搜索，達(dá)到最大迭代次數(shù)時(shí)，算法找到的值仍然很不理想，僅為449；當(dāng)α取5 時(shí)，算法的收斂速度很快，但出現(xiàn)了早熟現(xiàn)象，最終只找到了較優(yōu)解53。而當(dāng)α取2 或3 時(shí)，算法的結(jié)果較好。綜上所述，我們得出： 當(dāng)α過大：將導(dǎo)致局部最優(yōu)路徑上的信息正反饋?zhàn)饔脴O強(qiáng)，算法必將出現(xiàn)過早的收斂（停滯）現(xiàn)象，當(dāng)問題的規(guī)模較大時(shí)，在這種情況下所搜索到的通常是局部最優(yōu)解。當(dāng)α過?。簞t蟻群算法必然陷入純粹的、無休止的隨機(jī)搜索中（即不停滯），29在這種情