【正文】 綜上所述，我們得出： 當α過大：將導致局部最優(yōu)路徑上的信息正反饋作用極強，算法必將出現(xiàn)過早的收斂（停滯）現(xiàn)象，當問題的規(guī)模較大時，在這種情況下所搜索到的通常是局部最優(yōu)解。當α取0 或1 值時，算法收斂速度太慢，算法效率類似于隨機搜索，達到最大迭代次數(shù)時，算法找到的值仍然很不理想，僅為449；當α取5 時，算法的收斂速度很快，但出現(xiàn)了早熟現(xiàn)象，最終只找到了較優(yōu)解53。28圖41， α取值對算法性能的影響圖41 為螞蟻數(shù)量取7 只，最大迭代次數(shù)為1500 次，信息素揮發(fā)度為ρ= ，τmax = 4 ， τmin = ，β=0 ，α分別取0 ，1，2，3，5 時繪制的曲線圖。而當α≤1 時，無論是算法運行25 次中得到的最好的解，還是解平均值，都很差，算法陷入純粹的、無休止的隨機搜索中，在這種情況下一般也很難找到最優(yōu)解。表明25 次中有若干次得到的解很差，是局部最優(yōu)解。也可以考慮重新定義局部啟發(fā)信息ηi，使它和頂點i 在候選集中的度成正比，或者和候選集中與頂點i 有邊相連的頂點在候選集中的度的和成正比。實驗的相關參數(shù)為：螞蟻數(shù)量為7 只，最大迭代次數(shù)為3000 次，信息素揮發(fā)度為ρ= ，取啟發(fā)因子α和β不同數(shù)值的組合，運算結(jié)果為運行25組獲得的最優(yōu)解（平均解）進行仿真比較，從仿真實驗結(jié)果可以得出：首先β的取值對實驗的結(jié)果影響不大；分析其原因，因為算法中局部啟發(fā)信息ηi 的定義（參見式38）與頂點 i 的度有關， 中，頂點的最大度為468，最小度為431，相差太小，其局部啟發(fā)信息ηi相差不大，所以對算法的影響也不大。到目前為止，還沒有數(shù)學上的證明為選取α、β的數(shù)值提供理論上的27依據(jù)，對α、β的取值只能通過試驗的方式進行測試，以獲得最佳取值。蟻群算法的全局尋優(yōu)性能，首先要求蟻群的搜索過程必須有很強的隨機性；而蟻群算法的快速收斂性能，又要求蟻群的搜索過程必須要有較高的確定性。β的大小反映了蟻群在路徑搜索中確定性因素作用的強度，其值越大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大。α的大小反映了蟻群在路徑搜索中隨機性因素作用的強度，其值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機性減弱。 ACO 算法中參數(shù)的研究 啟發(fā)式因子 [27]啟發(fā)式因子α和β分別決定著信息素τij 和局部啟發(fā)信息ηij 的相對重要程度。參數(shù)選擇是否成功也只能通過仿真實驗的結(jié)果來觀察。首先介紹了最大團問題和針對子集類問題的蟻群算法思想，接著將二者結(jié)合提出了最大團問題的新型蟻群算法，通過仿真實驗表明該算法的性能和運算速度較最大團問題的傳統(tǒng)蟻群算法有著明顯的提高。從表31 中的實驗結(jié)果可以看出，只要參數(shù)選擇的比較合適，此算法能較好的解決最大團問題。螞蟻的數(shù)量也決定著求解的能力，螞蟻數(shù)目越多，其平均結(jié)果越好，也越容易找到最優(yōu)解：keller6，同樣是 α=3 時，但螞蟻數(shù)量為7 時找到的最優(yōu)解為55，但當螞蟻數(shù)量增加至30 時，就能找到59；對于brock200_4，當螞蟻數(shù)量增加至50 只時，運行3000 次迭代，能找到最優(yōu)解17；但另一方面螞蟻數(shù)量越多，運算量越大，所用時間也越長。后同）表31：運行結(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ù)的選取直接關系到算法的求解能力，尤其是信息素權重因子α 的選取對結(jié)果的影響非常重要：從表 31 可以看出，對于大多數(shù)例圖當α= 2 或α=3 時就能得到其較優(yōu)解，但對于復雜的例圖keller6，α必須取到3，才能獲得較好的求解能力。為討論研究的方便，此表數(shù)據(jù)為使用已有的與本人算法原理相同的AntClique_V算法的程序運行結(jié)果。表31 中列出的數(shù)據(jù)是在β=2 ， ρ= ，τ max =4 ，τmin = ，最大循環(huán)次數(shù)為3000，運行25 次得到的結(jié)果。由此可見，對于子集類問題使用新型蟻群算法，對其運算速度有一定提高。mn 2)。n 2)（包括5—6 行O(n) ，7—10 行 O(n2)，11 行O(n)），第13 行的時間復雜度是O(n)，算法的總的時間復雜度為O(NC那么衡量這些算法優(yōu)劣的一個24重要指標就是算法的時間復雜度。 算法時間復雜度分析最大團問題最早被證明是NP完全問題之一，即在P≠NP 的假設下，找不到一個算法能保證在多項式時間內(nèi)得到最優(yōu)解。由于在最大團問題中沒有路徑的概念，算法需要滿足：子集C 越優(yōu)秀，其中頂點的被選擇概率越高。其中， ρ為揮發(fā)系數(shù)，為常數(shù)，可根據(jù)經(jīng)驗給定。AntClique_V 和AntClique_E 的信息素更新策略的不同之處在于：AntClique_V 將信息素留在了頂點上，而AntClique_E 將信息素留在了邊上，下面以AntClique_V 為例詳細介紹信息素更新策略：給每個頂點v i 設置一個信息素變量 τ i，各頂點初始化信息素濃度為 τ max ，更新信息素是一次循環(huán)結(jié)束之后，根據(jù)本次循環(huán)所有螞蟻構造的團更新各個頂點上的信息素。其方法是按比例調(diào)整信息素更新：。St252。tzle 和Hoos 提出的MaxMin AS（MMAS ） [24]，其主要特點在于：每次迭代中只有獲得最短行程的螞蟻進行信息素更新；信息素的取值被限制在[τ min , τ max] 范圍內(nèi)，各路23徑初始化信息素濃度為τ max 。ACS 的特點是在螞蟻探索路徑的過程中應用局部更新，同時只對構成最好環(huán)游（當前循環(huán)中最好環(huán)游或者全局最好環(huán)游）的弧集進行全局更新。AntQ 在軌跡更新方式上有了較大改進，它不僅考慮了下一步轉(zhuǎn)移的期望收益，而且包含了當前循環(huán)中最好環(huán)游（iterationbest）或者全局最好環(huán)游（globalbest）的影響。(b) 當選中v i 加入C 后，則 Candidate ←Candidate∩{ vj | (vi,vj)∈E}。缺點在于，當一個圖中的所有頂點的度相差不大時，（DIMACS benchmarks 中的有許多實例的頂點的度相差很小， 其最大度為468，而最小度為431；MANNa45 的最大度為 1031，最小度為1000；Hamming84 和Hamming104 的所有頂點的度是相等的，分別為163，848）η i的取值很接近，它在螞蟻搜索過程中失去指導意義，但當頂點的度差別較大時，使用局部啟發(fā)信息能明顯提高搜索的效率。本文利用公式 38 設η i 的初始值。其中deg(v i ) 為頂點v i 的度；Q 為常量，可22知 ；（本文中實驗數(shù)據(jù)是在Q取為100 時獲得的）。α為信息素權重， β為局部啟發(fā)信息權重，這兩個量均為常量。這個算法中，信息素留在圖的邊上，而不是頂點上，將頂點vi 和部分解中頂點相連的邊上的信息素的和作為頂點vi 的信息素；而且該算法不使用局部啟發(fā)信息，僅靠信息素來引導螞蟻搜索，在迭代初期有一定的盲目性。τ c (v i )為當前部分團C中所有和頂點v i 相連的邊上的信息素之和。不同的概率選擇公式，不同的信息素更新原則構成了不同的蟻群算法。所謂“最優(yōu)解找到了”是指連續(xù)若干次找不到更好的解的，我們認為“最優(yōu)解找到了”。 算法的偽代碼描述用蟻群算法思想解決最大團問題的算法，這些算法使用信息素和局部啟發(fā)信息來引導螞蟻逐步向部分團（partial cliques）中增加頂點而逐步形成最大團(Maximal Cliques)。最大團問題可以看作是求頂點集V 的一個滿足特定條件的子集 C，它的可行解是一個集合，其中元素是沒有順序概念的，針對最大團問題的這些特點，AntClique_V 算法20將最大團問題看作子集類問題，使用針對子集類問題的ACO 思想，在設計算法時需要滿足：子集C 越優(yōu)秀，其中頂點的被選擇概率越高；信息素τ和局部啟發(fā)信息η不留在邊上，而是留在頂點上。針對這些不足及最大團問題的特點，本文使用了最大團問題的新型蟻群算法—AntClique_V，算法做了如下改進： ； ，而是留在頂點上。 最大團問題的新型蟻群算法2022 年Serge Fe 和Christine Solnon提出了用蟻群算法思想解決最大團問題的算法，本文中將這個算法記為：AntClique_E。最后，給出新型蟻群算法的偽代碼描述：1 procedure 新型蟻群算法2 設置參數(shù)，初始化信息素的分布193 while 不滿足結(jié)束條件do4 for 蟻群中的每只螞蟻do5 while 候選集不空do6 根據(jù)選擇概率p(v i)選擇1 個頂點v i 加入部分解子集；7 更新候選組件集合；8 end of while9 end of for10 根據(jù)蟻群中各個螞蟻找到的解的質(zhì)量更新信息素；11 end of while12 輸出找到的最優(yōu)解13 end of procedure這個算法的偽代碼描述中，子集類問題的蟻群算法的特點為：第六行中的概率選擇公式p(v i)是每個頂點被選擇的概率，而不是選擇從頂點i 轉(zhuǎn)移到頂點j 的轉(zhuǎn)移概率。但信息素所包含的信息是全局的，不象η 所代表的是局部性的啟發(fā)信息。這樣的算法是盲目的，不帶任何策略。α和β在算法中分別控制著信息素和局部啟發(fā)信息的比重。接著，介紹概率選擇公式：假設 為t 時刻螞蟻k 構造的部分解，則選擇概率 為t 時刻螞蟻k 選擇頂點i p （p ∈ { j +1, j+ 2,..., n }）加入部分解的概率，定義如下：其中， 為候選組件集合。一般情況下，η i 的值與部分解 或候選組件集合中的元素有關。這樣，在迭代過程中，不需要動態(tài)的修改η i 的值，可提高運算速度。通常，若求最大值，則G (L k) = Q*L k ；若求最小值 G (L k) = Q/L k，其中第k 只螞蟻構造的解的質(zhì)量即L k為目標函數(shù)的值，Q 為常數(shù)，可根據(jù)經(jīng)驗指定值。子集類問題的蟻群算法，將信息素是留在頂點上的，信息素變量從二維τij 改為一維τ i，節(jié)省了信息素變量的存儲空間，提高了更新過程的運算速度。而針對子集類問題的新型蟻群算法將信息素留在頂點上，由每個頂點的信息素和局部啟發(fā)信息確定選擇頂點加入子集（部分解）的概率。由于上述順序類問題和子集類問題的區(qū)別，新型蟻群算法針對子集類問題的特點在傳統(tǒng)蟻群算法的基礎上做了一系列改進，使其更適合解決子集類問題，有人將新型蟻群算法用于解決最大獨立集問題（Maximum Independent Set Problems, MIS），取得了很好的仿真結(jié)果。從集合R 中選擇下一個節(jié)點i p 的概率 由其自身的信息素量τ i p 和局部啟發(fā)信息η i p 決定。如圖31 所示：如圖32 所示，在子集類問題（subset problems）中，我們不關心部分解的順17序，因此部分解表示為集合 ，集合 表示剩下的可以被逐步選擇加入到部分解的節(jié)點，注意這里m n 即 ，并不是所有R中的元素都將被選擇，R 是在滿足相應問題的約束條件下，可以被加入部分解集合的組件的集合。 順序類問題和子集類問題的區(qū)別在順序類問題（ordering problems）中，假設序列 表示問題的一個部分解，集合 表示剩下的節(jié)點，這些節(jié)點必須被逐步選擇加入到部分解中，從而構成問題的一個可行解。針對這兩類組合優(yōu)化問題的不同性質(zhì)，其蟻群算法的實現(xiàn)策略也應有所差別。由于TSP 問題和螞蟻群覓食過程的相似性，蟻群算法最早被應用于TSP 問題。最大團問題就是要找到具有最多元素數(shù)的子集C 。一個團（Clique）是頂點集V 的一個子集，記為C ，C V，要求C 中任意兩個頂點之間有邊相連。因此，將蟻群算法應用于MCP，無論對算法本身或MCP，無論在理論上或?qū)嶋H應用中都很有意義。許