【正文】 反饋?zhàn)饔脴O強(qiáng)，算法必將出現(xiàn)過早的收斂（停滯）現(xiàn)象，當(dāng)問題的規(guī)模較大時(shí)，在這種情況下所搜索到的通常是局部最優(yōu)解。當(dāng)α取0 或1 值時(shí)，算法收斂速度太慢，算法效率類似于隨機(jī)搜索，達(dá)到最大迭代次數(shù)時(shí)，算法找到的值仍然很不理想，僅為449；當(dāng)α取5 時(shí)，算法的收斂速度很快，但出現(xiàn)了早熟現(xiàn)象，最終只找到了較優(yōu)解53。而當(dāng)α≤1 時(shí)，無論是算法運(yùn)行25 次中得到的最好的解，還是解平均值，都很差，算法陷入純粹的、無休止的隨機(jī)搜索中，在這種情況下一般也很難找到最優(yōu)解。也可以考慮重新定義局部啟發(fā)信息ηi，使它和頂點(diǎn)i 在候選集中的度成正比，或者和候選集中與頂點(diǎn)i 有邊相連的頂點(diǎn)在候選集中的度的和成正比。到目前為止，還沒有數(shù)學(xué)上的證明為選取α、β的數(shù)值提供理論上的27依據(jù)，對α、β的取值只能通過試驗(yàn)的方式進(jìn)行測試，以獲得最佳取值。β的大小反映了蟻群在路徑搜索中確定性因素作用的強(qiáng)度，其值越大，螞蟻在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大。 ACO 算法中參數(shù)的研究 啟發(fā)式因子 [27]啟發(fā)式因子α和β分別決定著信息素τij 和局部啟發(fā)信息ηij 的相對重要程度。首先介紹了最大團(tuán)問題和針對子集類問題的蟻群算法思想，接著將二者結(jié)合提出了最大團(tuán)問題的新型蟻群算法，通過仿真實(shí)驗(yàn)表明該算法的性能和運(yùn)算速度較最大團(tuán)問題的傳統(tǒng)蟻群算法有著明顯的提高。螞蟻的數(shù)量也決定著求解的能力，螞蟻數(shù)目越多，其平均結(jié)果越好，也越容易找到最優(yōu)解：keller6，同樣是 α=3 時(shí)，但螞蟻數(shù)量為7 時(shí)找到的最優(yōu)解為55，但當(dāng)螞蟻數(shù)量增加至30 時(shí)，就能找到59；對于brock200_4，當(dāng)螞蟻數(shù)量增加至50 只時(shí)，運(yùn)行3000 次迭代，能找到最優(yōu)解17；但另一方面螞蟻數(shù)量越多，運(yùn)算量越大，所用時(shí)間也越長。為討論研究的方便，此表數(shù)據(jù)為使用已有的與本人算法原理相同的AntClique_V算法的程序運(yùn)行結(jié)果。由此可見，對于子集類問題使用新型蟻群算法，對其運(yùn)算速度有一定提高。n 2)。那么衡量這些算法優(yōu)劣的一個(gè)24重要指標(biāo)就是算法的時(shí)間復(fù)雜度。由于在最大團(tuán)問題中沒有路徑的概念，算法需要滿足：子集C 越優(yōu)秀，其中頂點(diǎn)的被選擇概率越高。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)上的信息素。St252。ACS 的特點(diǎn)是在螞蟻探索路徑的過程中應(yīng)用局部更新，同時(shí)只對構(gòu)成最好環(huán)游（當(dāng)前循環(huán)中最好環(huán)游或者全局最好環(huán)游）的弧集進(jìn)行全局更新。(b) 當(dāng)選中v i 加入C 后，則 Candidate ←Candidate∩{ vj | (vi,vj)∈E}。本文利用公式 38 設(shè)η i 的初始值。α為信息素權(quán)重， β為局部啟發(fā)信息權(quán)重，這兩個(gè)量均為常量。τ c (v i )為當(dāng)前部分團(tuán)C中所有和頂點(diǎn)v i 相連的邊上的信息素之和。所謂“最優(yōu)解找到了”是指連續(xù)若干次找不到更好的解的，我們認(rèn)為“最優(yōu)解找到了”。最大團(tuán)問題可以看作是求頂點(diǎn)集V 的一個(gè)滿足特定條件的子集 C，它的可行解是一個(gè)集合，其中元素是沒有順序概念的，針對最大團(tuán)問題的這些特點(diǎn)，AntClique_V 算法20將最大團(tuán)問題看作子集類問題，使用針對子集類問題的ACO 思想，在設(shè)計(jì)算法時(shí)需要滿足：子集C 越優(yōu)秀，其中頂點(diǎn)的被選擇概率越高；信息素τ和局部啟發(fā)信息η不留在邊上，而是留在頂點(diǎn)上。 最大團(tuán)問題的新型蟻群算法2022 年Serge Fe 和Christine Solnon提出了用蟻群算法思想解決最大團(tuán)問題的算法，本文中將這個(gè)算法記為：AntClique_E。但信息素所包含的信息是全局的，不象η 所代表的是局部性的啟發(fā)信息。α和β在算法中分別控制著信息素和局部啟發(fā)信息的比重。一般情況下，η i 的值與部分解 或候選組件集合中的元素有關(guān)。通常，若求最大值，則G (L k) = Q*L k ；若求最小值 G (L k) = Q/L k，其中第k 只螞蟻構(gòu)造的解的質(zhì)量即L k為目標(biāo)函數(shù)的值，Q 為常數(shù)，可根據(jù)經(jīng)驗(yàn)指定值。而針對子集類問題的新型蟻群算法將信息素留在頂點(diǎn)上，由每個(gè)頂點(diǎn)的信息素和局部啟發(fā)信息確定選擇頂點(diǎn)加入子集（部分解）的概率。從集合R 中選擇下一個(gè)節(jié)點(diǎn)i p 的概率 由其自身的信息素量τ i p 和局部啟發(fā)信息η i p 決定。 順序類問題和子集類問題的區(qū)別在順序類問題（ordering problems）中，假設(shè)序列 表示問題的一個(gè)部分解，集合 表示剩下的節(jié)點(diǎn)，這些節(jié)點(diǎn)必須被逐步選擇加入到部分解中，從而構(gòu)成問題的一個(gè)可行解。由于TSP 問題和螞蟻群覓食過程的相似性，蟻群算法最早被應(yīng)用于TSP 問題。一個(gè)團(tuán)（Clique）是頂點(diǎn)集V 的一個(gè)子集，記為C ，C V，要求C 中任意兩個(gè)頂點(diǎn)之間有邊相連。許多啟發(fā)式算法都曾在它上面做過努力，如模擬退火（Simulated Annealing）、神經(jīng)網(wǎng)絡(luò)（ Neural Networks）、遺傳算法（Geic Algorithm）、禁忌搜索（Tabu Search）等 [27]。將最大團(tuán)問題看作子集類問題，提出了最大團(tuán)問題的新型蟻群算法。 本章小結(jié)蟻群算法（Ant Colony Optimization algorithm ，ACO）是由意大利學(xué)者15 等人在20 世紀(jì)90 年代初通過模擬自然界中螞蟻集體覓食的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法。蟻群算法從其實(shí)現(xiàn)的機(jī)理來看是一種天然的解決組合優(yōu)化問題的方法。蟻群算法的原理是一種基于“正反饋”的增強(qiáng)型學(xué)習(xí)系統(tǒng)：它通過“最優(yōu)路徑上螞蟻數(shù)量的增加→信息素強(qiáng)度增加→后來螞蟻選擇概率增大→最優(yōu)路徑上螞蟻數(shù)量更大增加”達(dá)到最終收斂于最優(yōu)路徑上；蟻群算法是一種分布式的優(yōu)化方法，不僅適合目前的串行計(jì)算機(jī)，而且適合并行計(jì)算機(jī)；蟻群算法是一種全局優(yōu)化的方法，不僅可用于求解單目標(biāo)優(yōu)化問題，而且可用于求解多目標(biāo)優(yōu)化問題，或者是帶有約束條件的優(yōu)化問題。這兩種初始化方法對算法效果沒有顯著影響，也不存在明顯差異。螞蟻的數(shù)量 m 是一個(gè)非常重要的參數(shù)，在此算法中，它是一個(gè)不隨時(shí)間變化的常數(shù)。為了保證對解空間的充分搜索，有必要引入信息素?fù)]發(fā)機(jī)制，否則所有的螞蟻都可能停滯于相同的路徑。在第t 次迭代結(jié)束后，每只螞蟻k 在路徑（i，j）上留下一定的信息素Δτ kij (t)。一般而言，對于適用貪婪法則的問題， β 應(yīng)較大；要加快收斂， α應(yīng)較大。是兩個(gè)可以調(diào)整的參數(shù)，用于控制信息素和局部啟發(fā)信息的相對權(quán)值。在TSP 問題中，η ij (t)可以設(shè)為城市 i 與城市j 之間距離的倒數(shù)；α、β—協(xié)調(diào)連接上的信息素和局部啟發(fā)信息這兩種啟發(fā)信息的因子。在算法迭代過程中，每只螞蟻k (k =1,2,..., n) 根據(jù)概率轉(zhuǎn)換規(guī)則生成一個(gè)有N 步過程的行動(dòng)路線。一般而言，用于解決各種組合優(yōu)化問題的ACO 算法都遵循如下的統(tǒng)一算法框架： procedure 組合優(yōu)化問題的 ACO 算法 設(shè)置參數(shù)，初始化信息素分布；11 while 不滿足結(jié)束條件do for 蟻群中的每個(gè)螞蟻 for 每個(gè)解構(gòu)造步（直到構(gòu)造出完整解） 螞蟻按信息素及啟發(fā)式信息的指引構(gòu)造一步問題的解； 進(jìn)行信息素局部更新（可選）； end of for end of for 以某些已獲得的解為起點(diǎn)進(jìn)行領(lǐng)域（局部）搜索（可選）； 根據(jù)某些已獲得解的質(zhì)量進(jìn)行全局更新信息素； end of while end of procedure下面， 等提出的第一個(gè)ACO 算法—AS 算法（Ant System ）求解旅行商問題（TSP）為例來說明 ACO 算法解決組合優(yōu)化問題時(shí)的算法模型。這個(gè)特征將使它可以將正反饋?zhàn)鳛橐环N搜索機(jī)制，而且它也可以應(yīng)用于并行系統(tǒng)。它可以應(yīng)用于求解多種組合優(yōu)化問題。在蟻群算法中，負(fù)反饋機(jī)制是利用信息素的揮發(fā)（Evaporation）來實(shí)現(xiàn)的。在蟻群算法中是通過虛擬信息素（Virtual Pheromone）來實(shí)現(xiàn)信息正反饋的。信息素更新的實(shí)質(zhì)就是人工螞蟻根據(jù)真實(shí)螞蟻在訪問過的邊上留下的信息素和蒸發(fā)的信息素來模擬真實(shí)信息素?cái)?shù)量的變化，它使得越好的解答得到越多的增強(qiáng)。蟻群算法在優(yōu)化過程中有兩個(gè)重要的規(guī)則： （1）螞蟻在眾多的路徑中轉(zhuǎn)移路線的選擇規(guī)則：螞蟻總是傾向于選擇含有較多信息素的路徑。整個(gè)選路過程9如此往復(fù)，即實(shí)現(xiàn)了隨機(jī)選擇到自適應(yīng)行為的過程。由于此時(shí)路上無信息素，螞蟻就以相同的概率走兩條路中的一條，因而在點(diǎn)B 和點(diǎn)D 各有15 只螞蟻選擇往C ，其余 15 只選擇往F。 蟻群算法基本原理蟻群算法最初隨機(jī)的選擇搜索路徑，隨著對解空間的“了解”，搜索變得有規(guī)8律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。螞蟻個(gè)體之間就是通過這種間接的通信機(jī)制達(dá)到協(xié)同搜索食物最短路徑的目的，它們作為一個(gè)群體所表現(xiàn)出來的行為是一種自催化（autocatalytic）行為，整個(gè)過程具有正反饋的特征。它模擬自然界中螞蟻集體覓食的行為。大量的仿真實(shí)驗(yàn)研究表明，該算法較最大團(tuán)問題的傳統(tǒng)蟻群算法有著更短的運(yùn)行時(shí)間，更強(qiáng)的求解能力。第二章：在介紹了蟻群算法的基本原理的基礎(chǔ)上，以經(jīng)典組合優(yōu)化問題—TSP問題為例，詳細(xì)介紹了其解決組合優(yōu)化問題的基本框架。盡管蟻群算法的嚴(yán)格理論基礎(chǔ)尚未奠定，但這種新興的智能進(jìn)化仿生算法已展現(xiàn)出勃勃生機(jī)。當(dāng)指出，現(xiàn)階段對蟻群算法的研究大多還只是停留在仿真階段，尚未能提出一個(gè)完善的理論分析，對它的有效性也沒有給出嚴(yán)格的數(shù)學(xué)解釋。 目前大量的研究工作注重于ACO 的實(shí)際應(yīng)用，然而，近幾年的研究發(fā)現(xiàn)：ACO 用于解決組合優(yōu)化問題時(shí)，也會(huì)遇到類似進(jìn)化算法中的deception 和bias 現(xiàn)象。該算法根據(jù)優(yōu)化過程中解的分布均勻度，自適應(yīng)地調(diào)整路徑選擇概率策略和信息素更新策略，以求在加速收斂和防止早熟、停滯現(xiàn)象之間取得很好的平衡。該算法利用一些策略來避免算法陷入局部最優(yōu)解。 等提出了一種基于螞蟻等級的ASrenk 算法。MMAS 算法采用了用當(dāng)前找到的最好解來更新信息素指引螞蟻向更高質(zhì)量的解空間搜索的貪婪策略，并對信息素設(shè)立上下限來避免算法的早熟。此外，在信息素的全局更新中采用了精英策略。最初的AS 算法的效果并不理想，但是后續(xù)的研究將蟻群算法和局部搜索以及其它的一些優(yōu)化方法相結(jié)合獲得的許多令人振奮的成果。由于魯棒性強(qiáng)，使得蟻群算法易于解決各種不同的優(yōu)化問題。3蟻群算法（Ant Colony Optimization algorithm ，ACO）是由意大利學(xué)者[1] 等人在20 世紀(jì)90 年代初通過模擬自然界中螞蟻集體覓食的行為而提出的一種基于種群的啟發(fā)式仿生類算法。對于這些NP完全[2，3，9，10] 的組合優(yōu)化問題，至今尚無很好的解析算法，一般采用啟發(fā)式算法來解決。組合優(yōu)化問題 [2，3] 通?？擅枋鰹椋毫瞀?{s 1，s 2，……s n}為所有狀態(tài)構(gòu)成的解空間， C( st) 為狀態(tài) st 對應(yīng)的目標(biāo)函數(shù)值，要求尋求最優(yōu)解 s* ，使得對于任意的s t ∈Ω , C( s*)= min C( st) 。2第一章 緒論 研究背景隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，針對離散變量的優(yōu)化問題被逐漸重視，從而形成了有別于數(shù)學(xué)規(guī)劃的另一類模型， 即組合優(yōu)化（Combinatorial Optimization ）。正反饋使得它能很快搜索到比較好的解；分布計(jì)算避免了算法陷入局部收斂而不能繼續(xù)優(yōu)化；而貪心啟發(fā)機(jī)制使它能在尋優(yōu)的早期階段就搜索到可接受的解。當(dāng)螞蟻移動(dòng)時(shí)，它會(huì)在經(jīng)過的路線上留下這種信息素，從而引導(dǎo)其他螞蟻以更大的概率去選擇相同的路線。Distribute putation avoided the calculate way sink into the part refrain from rash action and can39。 從深層意義上分析蟻群算法機(jī)制的原理，研究其基本的數(shù)學(xué)模型和具體實(shí)現(xiàn)步驟。蟻群算法作為一種新的啟發(fā)式算法，它具有正反饋、自組織、分布式計(jì)算以及結(jié)構(gòu)性的貪心啟發(fā)等特點(diǎn)。對于NP完全的組合優(yōu)化問題，至今尚無很好的解析算法，一般采用啟發(fā)式算法來解決。本文在詳細(xì)介紹蟻群算法原理的基礎(chǔ)上，對蟻群算法在組合優(yōu)化問題中的應(yīng)用進(jìn)行分析和研究，主要將蟻群算法應(yīng)用于求解圖的最大團(tuán)這個(gè)經(jīng)典的NP完全組合優(yōu)化問題，在本文中我主要做了以下工作： 在了解螞蟻的社會(huì)形態(tài)、群體行為等生物學(xué)特征的基礎(chǔ)上，認(rèn)真研究了蟻群算法的思想起源、發(fā)展現(xiàn)狀、以及其應(yīng)用情況。關(guān)鍵詞：蟻群算法 組合優(yōu)化 最大團(tuán) 啟發(fā)式算法IVAbstractMany binatorial optimization problems, which are fundamental and important in science and engineering calculation, are NPplete problems. The solution of these problems has been the key proble