【正文】 法概念3. 算法模型和收斂性分析4. 算法實(shí)現(xiàn)的技術(shù)問(wèn)題5. 應(yīng)用6. 參考資料33 蟻群優(yōu)化算法概述n 起源n 應(yīng)用領(lǐng)域n 研究背景n 研究現(xiàn)狀n 應(yīng)用現(xiàn)狀34 蟻群優(yōu)化算法起源 20世紀(jì) 50年代中期創(chuàng)立了仿生學(xué)，人們從生物進(jìn)化的機(jī)理中受到啟發(fā)。提出了許多用以解決復(fù)雜優(yōu)化問(wèn)題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問(wèn)題。 20世紀(jì) 90年代意大利學(xué)者 M． Dorigo， V． Maniezzo， A．Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為，提出來(lái)一種新型的模擬進(jìn)化算法 —— 蟻群算法，是群智能理論研究領(lǐng)域的一種主要算法。用該方法求解 TSP問(wèn)題、分配問(wèn)題、 jobshop調(diào)度問(wèn)題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問(wèn)題（特別是離散優(yōu)化問(wèn)題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法．35 蟻群優(yōu)化算法應(yīng)用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問(wèn)題或者能夠轉(zhuǎn)化為優(yōu)化求解的問(wèn)題。現(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信 QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問(wèn)題提供了新的途徑 。36 蟻群優(yōu)化算法研究背景 1/3 群智能理論研究領(lǐng)域有兩種主要的算法：蟻群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已成功應(yīng)用于許多離散優(yōu)化問(wèn)題。微粒群算法也是起源于對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初是模擬鳥(niǎo)群覓食的過(guò)程，但后來(lái)發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 37 蟻群優(yōu)化算法研究背景 2/3與大多數(shù)基于梯度的應(yīng)用優(yōu)化算法不同，群智能依靠的是概率搜索算法。雖然概率搜索算法通常要采用較多的評(píng)價(jià)函數(shù)，但是與梯度方法及傳統(tǒng)的演化算法相比，其優(yōu)點(diǎn)還是顯著的 ，主要表現(xiàn)在以下幾個(gè)方面：1 無(wú)集中控制 約 束，不會(huì)因個(gè) 別 個(gè)體的故障影響整個(gè) 問(wèn)題 的求解，確保了系 統(tǒng) 具 備 更 強(qiáng) 的 魯 棒性 2 以非直接的信息交流方式確保了系 統(tǒng) 的 擴(kuò) 展性 3 并行分布式算法模型，可充分利用多 處 理器 4 對(duì)問(wèn)題 定 義 的 連續(xù) 性無(wú)特殊要求 5 算法 實(shí)現(xiàn)簡(jiǎn)單 38 蟻群優(yōu)化算法研究背景 3/3 群智能方法易于實(shí)現(xiàn)，算法中僅涉及各種基本的數(shù)學(xué)操作，其數(shù)據(jù)處理過(guò)程對(duì) CPU和內(nèi)存的要求也不高。而且，這種方法只需目標(biāo)函數(shù)的輸出值，而無(wú)需其梯度信息。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問(wèn)題的新方法。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。無(wú)論是從理論研究還是應(yīng)用研究的角度分析，群智能理論及其應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。 39 蟻群優(yōu)化算法研究現(xiàn)狀 1/7 90年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（Ant System, AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問(wèn)題（ TSP）。從螞蟻系統(tǒng)開(kāi)始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實(shí)際優(yōu)化問(wèn)題求解中進(jìn)一步得到了驗(yàn)證。這些 AS改進(jìn)版本的一個(gè)共同點(diǎn)就是增強(qiáng)了螞蟻搜索過(guò)程中對(duì)最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結(jié)果的 ACO是通過(guò)引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問(wèn)題中的求解質(zhì)量。40 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。在 Antdensity和 Antquantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在 Antcycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。通過(guò)與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的 TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問(wèn)題規(guī)模擴(kuò)展時(shí)， AS的解題能力大幅度下降。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進(jìn)方面。較早的一種改進(jìn)方法是精英策略 (Elitist Strategy)，其思想是在算法開(kāi)始后即對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為 Tgb(全局最優(yōu)行程 )，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過(guò)這些行程的螞蟻記為 “精英 ”，從而增大較好行程的選擇機(jī)會(huì)。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過(guò)多則算法會(huì)由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過(guò)早停滯。 41 3/7 為了進(jìn)一步克服 AS中暴露出的問(wèn)題，提出了蟻群系統(tǒng) (Ant Colony System, ACS)。該系統(tǒng)的提出是以 AntQ算法為基礎(chǔ)的。 AntQ將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法 Qlearning有機(jī)的結(jié)合了起來(lái)。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。其中， 0ρ1是信息素?fù)]發(fā)參數(shù)， 是從尋路開(kāi)始到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度。42 4/7 再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過(guò)的路徑再次被選擇的概率。 43 5/7 在對(duì) AS進(jìn)行直接完善的方法中， MAXMIN Ant System是一個(gè)典型代表。該算法修改了 AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。44 6/7 另一種對(duì) AS改進(jìn)的算法是 Rankbased Version AS。與 “精英策略 ”相似，在此算法中總是更新更好進(jìn)程上的信息素，選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度 決定的排序，且每個(gè)螞蟻放置信息素的強(qiáng)度通過(guò)下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。 45 7/7 這種算法求解 TSP的能力與 AS、精英策略 AS、遺傳算法和模擬退火算法進(jìn)行了比較。在大型TSP問(wèn)題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。而且在 Rankbased AS和精英策略 AS均優(yōu)于基本 AS的同時(shí)，前者還獲得了比精英策略 AS更好的解。 46 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 1/5 隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問(wèn)題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問(wèn)題中表現(xiàn)突出。 蟻群優(yōu)化算法并不是旅行商問(wèn)題的最佳解決方法，但是它卻為解決組合優(yōu)化問(wèn)題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問(wèn)題中。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問(wèn)題。 47 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。 HP公司和英國(guó)電信公司在 90年代中后期都開(kāi)展了這方面的研究，設(shè)計(jì)了蟻群路由算法（ Ant Colony Routing, ACR）。 每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)榻?jīng)過(guò)了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過(guò)期的路由信息。這樣，在當(dāng)前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時(shí)， ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負(fù)荷量和利用率。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。48 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 3/5 基于群智能的聚類算法起源于對(duì)蟻群蟻卵的分類研究。 Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，