【正文】 記憶不是局部地存在于單個的人工蟻，而是全局地分布在整個問題空間，這就導(dǎo)致了一種間接聯(lián)絡(luò)方式。T＝1 時，經(jīng)過C 的路徑被30 只螞蟻爬過，而路徑BF 和 DF 只被 15 只螞蟻爬過，從而BCD 上的信息素蹤跡的濃度是 BFD 的2倍。蟻群算法就是根據(jù)蟻群覓食活動的規(guī)律，建立的一個利用群體智能進(jìn)行優(yōu)化搜索的模型，相對其它的各類啟發(fā)式搜索算法，蟻群算法具有明顯的優(yōu)越性。第四章：研究了蟻群算法的中各種參數(shù)對算法性能的影響，在對蟻群算法的參數(shù)選擇規(guī)律實驗分析的基礎(chǔ)上，本節(jié)總結(jié)出一種“三步走”選擇蟻群算法最優(yōu)組合參數(shù)的有效方法。 論文研究目的及主要內(nèi)容蟻群算法從其機(jī)理來說是一種天然的組合優(yōu)化方法，在解決組合優(yōu)化問題的應(yīng)用中相對其它的各類啟發(fā)式搜索算法，具有明顯的優(yōu)越性。例如： 研究ACO 用于作業(yè)調(diào)度問題（shop scheduling problems）時發(fā)現(xiàn)：一段時間之后ACO 的性能會由于信息素模式和處理的問題實例而下降，這種現(xiàn)象稱為：secondorder deception或者search bias，它意味著隨著時間的推移找到更好解的可能性越來越小。吳慶洪 [15]等人提出了具有變異特征的蟻群算法,有機(jī)地結(jié)合了2opt方法,提高了算法的搜索速度。1999 年，、 把此前各種基于AS 演化而得的算法歸結(jié)到一個統(tǒng)一的框架中，并提供了抽象而規(guī)范的算法描述，稱為ACO 元啟發(fā)式算法 [14]（Ant Colony Optimization metaheuristic），簡稱為ACO 算法。1995 提出了AntQ 算法 [8，9] 。它是繼模擬退火算法、遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)算法等啟發(fā)式搜索算法 [27]以后的又一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法。對組合優(yōu)化問題的研究，特別是求解復(fù)雜組合優(yōu)化問題方法的探索已成為眾多學(xué)科關(guān)注的焦點，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價值，也在于它們在現(xiàn)實生活中的很多方面有著廣泛的應(yīng)用。目前國外ACO 領(lǐng)域的研究熱點集中在尋優(yōu)原理與數(shù)學(xué)基礎(chǔ)的研究、收斂性研究、并行ACO 算法研究以及利用ACO 解決各類優(yōu)化問題等等。t continue the optimization。其中正反饋使得它能很快搜索到比較好的解；分布計算避免了算法陷入局部收斂而不能繼續(xù)優(yōu)化；而貪心啟發(fā)機(jī)制使它能在尋優(yōu)的早期階段就搜索到可接受的解。因而蟻群算法能夠成功地應(yīng)用于解決許多NP完全的組合優(yōu)化問題。And the constructive greedy heuristic makes it able to search the acceptable solution in the earlier period stage. This thesis introduces the principles of ACO in detail and describes our deep research work in the application of bination optimization problems. We apply ACO to Maximum Clique Problems, which are typical NPplete bination optimization problems. The main contribution of this thesis is as follows: on the understanding of the biology characters of ants, I studied the origins of the ACO algorithm,the present condition of its development,and the applied circumstance. analysed the principle of the ACO algorithm mechanism deeply,and studied its basic mathematics model and the step to carry it out. to the characteristics of Maximum Clique Problem,I gave the solution way of it, using some examples simulated and verified it.4. According to the experiment results,I studied the way of its parameter choice.Key Words: Ant Colony Optimization algorithm Combinatorial OptimizationMaximum Clique Problem Heuristic algorith1引言蟻群優(yōu)化 [1]（ACO）屬于智能仿生算法——螞蟻算法（AA）的范疇，后者是從螞蟻覓食時的路徑選擇機(jī)制中得到啟發(fā)的：個體螞蟻的能力有限，但是多個螞蟻組成的群體卻能相互配合，在食物源和巢穴之間確定最小的路徑。從上個世紀(jì)九十年代后期起國內(nèi)逐漸興起了“螞蟻熱”，利用ACO 解決組合優(yōu)化問題以及通信網(wǎng)絡(luò)路由問題的論文很多，但對算法本身進(jìn)行創(chuàng)新的則很少看見。典型的組合優(yōu)化問題有旅行商問題（traveling salesman problem ）、加工調(diào)度問題（scheduling problem）、01 背包問題（01 knapsack problem）、裝箱問題（bin packing problem）、圖著色問題（graph coloring problem）、聚類問題（clustering problem）以及最大團(tuán)問題（maximum clique problem）和最大割問題（MaxCut problem ）等。雖然與已經(jīng)發(fā)展完備的一些啟發(fā)式算法比較起來，蟻群算法的計算量比較大、搜索時間長、有時候效果并不理想，但是它的成功運用還是激起了人們對蟻群算法的極大興趣，并吸引了一批研究人員從事蟻群算法的研究。該算法建立了AS 與Q學(xué)習(xí)機(jī)制（Qlearning） [10]的聯(lián)系。ACO 算法的優(yōu)點在于：利用了正反饋原理加快進(jìn)化過程；是一種本質(zhì)并行的算法；不同個體之間不斷進(jìn)行信息的交流和傳遞，從而能夠相互協(xié)作，有利于發(fā)現(xiàn)較好的解；由于魯棒性強(qiáng)，故易于解決各種不同的優(yōu)化問題。吳斌、史忠植 [16]在蟻群算法的基礎(chǔ)上提出了相遇算法，其基本思想是在求解TSP問題中，用兩只螞蟻共同完成對一條路徑的搜索，并將相遇算法與采用并行策略的分段算法相結(jié)合提出一種基于蟻群算法的TSP問題分段求解算法，提高搜索速度。 等試圖找出導(dǎo)致算法search bias的原因； [1]針對蟻群算法求解組合優(yōu)化是遇到的second order deception 問題，做了大量的研究工作。本文在詳細(xì)介紹蟻群算法原理的基礎(chǔ)上，對蟻群算法在組合優(yōu)化問題中的應(yīng)用進(jìn)行研究。結(jié)論：總結(jié)了本文的主要內(nèi)容，以及自己在蟻群算法方面所作的研究工作，對自己所做的工作做出了中肯的評價，并且明確了以后的研究方向。它在一系列NP完全組合優(yōu)化問題的求解中取得了卓有成效的結(jié)果，其典型代表有旅行商問題（traveling salesman problem ，TSP）、指派問題 (quadraticassignment problem，QAP) ，作業(yè)調(diào)度（ jobshop）等經(jīng)典組合優(yōu)化問題 [27]。此時，又有30 只螞蟻離開B（和D），于是有20 只螞蟻選擇往C，另外10只螞蟻選擇往F，這樣更多的信息素被留在更短的路徑BCD 上。 （2）全局化信息素更新規(guī)則：在路徑上的信息素，有一部分會被蒸發(fā)散失，這樣沒有被選擇過的路徑信息素越來越少，變得越來越不受歡迎。這種正反饋機(jī)制將指引蟻群找到高質(zhì)量的解。它的性能不因組合優(yōu)化問題的不同而不同； (3)它是一種基于群體的方法(a population based approach)。顯然，可將每個城市都映射為圖中的節(jié)點，城市之間的道路映射為圖中的連接。τ ij (t) 是路過該連接的螞蟻在完成一條路徑后，根據(jù)對所生成解的評價釋放的信息素，解的質(zhì)量越高，信息濃度就越高；η ij (t)則是基于具體的優(yōu)化問題，以及螞蟻當(dāng)前走過的路徑所對應(yīng)的部分解，利用構(gòu)造該優(yōu)化問題解的經(jīng)驗（如最短路問題中的貪婪法則），判斷選擇該連接的優(yōu)劣，不考慮后面的路徑和其他螞蟻的經(jīng)驗。有關(guān)模擬表明其尋優(yōu)性能明顯優(yōu)于前兩種方式。每條路徑都遵循一致的信息素?fù)]發(fā)規(guī)則： 其中Δτ kij (t)為所有螞蟻在路徑（i，j）上留下一定的信息素之和，其定義如下： m 是螞蟻的數(shù)量。如此一來，T + 的信息素將得到增強(qiáng)，從而引導(dǎo)更多的螞蟻向著比較好的路徑上靠攏。正反饋使得它能很快搜索到比較好的解；分布計算避免了算法陷入局部收斂而不能繼續(xù)優(yōu)化；而貪心啟發(fā)機(jī)制使它能在尋優(yōu)的早期階段就搜索到可接受的解。 最大團(tuán)問題最大團(tuán)問題(Maximum Clique Problem，簡記為MCP)是一個著名的組合優(yōu)化問題，這不僅僅因為它最早被證明是NP完全問題 [9]之一，而且因為它在理論和實踐上有著重要的意義，如它在編碼理論、差錯診斷、計算機(jī)圖像、模式匹配、信號傳輸、信息恢復(fù)、生物信息學(xué)等許多領(lǐng)域都有著廣泛的應(yīng)用。最大團(tuán)問題就是要找到具有最多元素數(shù)的子集C 。如圖31 所示：如圖32 所示，在子集類問題（subset problems）中，我們不關(guān)心部分解的順17序，因此部分解表示為集合 ，集合 表示剩下的可以被逐步選擇加入到部分解的節(jié)點，注意這里m n 即 ，并不是所有R中的元素都將被選擇，R 是在滿足相應(yīng)問題的約束條件下，可以被加入部分解集合的組件的集合。子集類問題的蟻群算法，將信息素是留在頂點上的，信息素變量從二維τij 改為一維τ i，節(jié)省了信息素變量的存儲空間，提高了更新過程的運算速度。接著，介紹概率選擇公式：假設(shè) 為t 時刻螞蟻k 構(gòu)造的部分解，則選擇概率 為t 時刻螞蟻k 選擇頂點i p （p ∈ { j +1, j+ 2,..., n }）加入部分解的概率，定義如下：其中， 為候選組件集合。最后，給出新型蟻群算法的偽代碼描述：1 procedure 新型蟻群算法2 設(shè)置參數(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)移概率。 算法的偽代碼描述用蟻群算法思想解決最大團(tuán)問題的算法，這些算法使用信息素和局部啟發(fā)信息來引導(dǎo)螞蟻逐步向部分團(tuán)（partial cliques）中增加頂點而逐步形成最大團(tuán)(Maximal Cliques)。這個算法中，信息素留在圖的邊上，而不是頂點上，將頂點vi 和部分解中頂點相連的邊上的信息素的和作為頂點vi 的信息素；而且該算法不使用局部啟發(fā)信息，僅靠信息素來引導(dǎo)螞蟻搜索，在迭代初期有一定的盲目性。缺點在于，當(dāng)一個圖中的所有頂點的度相差不大時，（DIMACS benchmarks 中的有許多實例的頂點的度相差很小， 其最大度為468，而最小度為431；MANNa45 的最大度為 1031，最小度為1000；Hamming84 和Hamming104 的所有頂點的度是相等的，分別為163，848）η i的取值很接近，它在螞蟻搜索過程中失去指導(dǎo)意義，但當(dāng)頂點的度差別較大時，使用局部啟發(fā)信息能明顯提高搜索的效率。tzle 和Hoos 提出的MaxMin AS（MMAS ） [24]，其主要特點在于：每次迭代中只有獲得最短行程的螞蟻進(jìn)行信息素更新；信息素的取值被限制在[τ min , τ max] 范圍內(nèi)，各路23徑初始化信息素濃度為τ max 。其中， ρ為揮發(fā)系數(shù)，為常數(shù)，可根據(jù)經(jīng)驗給定。n 2)（包括5—6 行O(n) ，7—10 行 O(n2)，11 行O(n)），第13 行的時間復(fù)雜度是O(n)，算法的總的時間復(fù)雜度為O(NC表31 中列出的數(shù)據(jù)是在β=2 ， ρ= ，τ max =4 ，τmin = ，最大循環(huán)次數(shù)為3000，運行25 次得到的結(jié)果。從表31 中的實驗結(jié)果可以看出，只要參數(shù)選擇的比較合適，此算法能較好的解決最大團(tuán)問題。α的大小反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度，其值越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機(jī)性減弱。實驗的相關(guān)參數(shù)為：螞蟻數(shù)量為7 只，最大迭代次數(shù)為3000 次，信息素?fù)]發(fā)度為ρ= ，取啟發(fā)因子α和β不同數(shù)值的組合，運算結(jié)果為運行25組獲得的最優(yōu)解（平均解）進(jìn)行仿真比較，從仿真實驗結(jié)果可以得出：首先β的取值對實驗的結(jié)果影響不大；分析其原因，因為算法中局部啟發(fā)信息ηi 的定義（參見式38）與頂點 i 的度有關(guān)， 中，頂點的最大度為468，最小度