第十章-群集智能與蟻群算法

第十章

群集智能與蟻群算法2013年6月1第1節(jié)群體智能概念

1.群體智能(SwarmIntelligence)2研究意義－群體智能概念

群體智能這個(gè)概念來自對(duì)蜜蜂和螞蟻的觀察。一組相互之間可以進(jìn)行直接通信或者間接通信(通過改變局部環(huán)境)的主體，這組主體能夠合作進(jìn)行分布問題求解。任何啟發(fā)于群居性昆蟲群體和其它動(dòng)物群體的集體行為而設(shè)計(jì)的算法和分布式問題解決裝置都稱為群體智能。群體智能在沒有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題的解決方案提供了基礎(chǔ)。3研究意義－群體智能的特點(diǎn)

分布式：能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài);魯棒性：沒有中心的控制與數(shù)據(jù)，個(gè)體的故障不影響整個(gè)問題的求解;擴(kuò)充性：個(gè)體的增加，系統(tǒng)的通信開銷增加小;簡單性：個(gè)體簡單，實(shí)現(xiàn)也比較簡單。

4研究意義群體智能的研究不僅在多主體仿真、系統(tǒng)復(fù)雜性以及NP問題等方面為人工智能、認(rèn)識(shí)科學(xué)、計(jì)算經(jīng)濟(jì)學(xué)等領(lǐng)域的基礎(chǔ)理論問題的研究開辟了新的研究途徑，同時(shí)也為諸如組合優(yōu)化、機(jī)器人協(xié)作、電信路由控制等實(shí)際工程問題提供了新的解決方法。因此，群體智能的研究具有重要意義和廣闊的應(yīng)用前景。5研究現(xiàn)狀－國外

美國的SDG組織在系統(tǒng)復(fù)雜性方面開展了研究。他們主要通過多主體的仿真來研究系統(tǒng)復(fù)雜性。他們開發(fā)的SWARM軟件包為多學(xué)科進(jìn)行基于多主體的建模提供了一個(gè)基礎(chǔ)平臺(tái)；加州工學(xué)院專門開設(shè)了群體智能的課程；

歐洲聯(lián)盟資助的SWARM-BOTS項(xiàng)目的主要目標(biāo)是研究設(shè)計(jì)和實(shí)現(xiàn)自組織和自裝配的裝置的新途徑。它的理論基礎(chǔ)是群體智能和蟻群算法的近期研究成果，即對(duì)群居性昆蟲和其它動(dòng)物群體的自組織和自裝配能力的研究。6研究現(xiàn)狀－國內(nèi)

國家自然科學(xué)基金在“十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域第一類屬于把握科學(xué)前沿，推動(dòng)源頭創(chuàng)新的項(xiàng)目。其中第7項(xiàng)認(rèn)知科學(xué)及其信息處理的研究內(nèi)容就明確列出了群體智能的進(jìn)化、自適應(yīng)與現(xiàn)場認(rèn)知。相關(guān)項(xiàng)目還有第9項(xiàng)復(fù)雜系統(tǒng)與復(fù)雜性。

7主要研究方向蟻群尋食行為研究，相對(duì)應(yīng)組合優(yōu)化算法和通信網(wǎng)絡(luò)路由控制算法；群體分工和任務(wù)分配行為研究，相對(duì)應(yīng)多主體分工協(xié)作算法；巢穴組織和自組織行為及群體分類行為研究，相對(duì)應(yīng)數(shù)據(jù)分析和圖的分割算法；建巢和自裝配行為研究，相對(duì)應(yīng)模擬建巢算法；群體合作搬運(yùn)行為研究，相對(duì)應(yīng)機(jī)器人合作搬運(yùn)算法。8所需解決的關(guān)鍵問題蟻群算法

效率與理論；由于沒有標(biāo)準(zhǔn)的測試集，除了尋食模型，蟻卵聚類、蟻群分工和蟻巢自裝配等模型都只處于證實(shí)階段理論和實(shí)驗(yàn)

；一個(gè)多主體自組織模型實(shí)驗(yàn)和測試平臺(tái)

；對(duì)于追求效率的實(shí)際問題，如何既保持群體智能系統(tǒng)的靈活性和魯棒性等自組織特征又能保證系統(tǒng)的高效率也是一個(gè)關(guān)鍵問題

；群體智能與分布式智能的智能主體研究相結(jié)合，將產(chǎn)生新的智能主體協(xié)作、建模等算法和機(jī)制，提出網(wǎng)絡(luò)和網(wǎng)格環(huán)境的自適應(yīng)多智能主體系統(tǒng)

。9螞蟻尋找最短路徑原理A）蟻群到達(dá)決策點(diǎn)。B）一些螞蟻選擇上方路徑，一些螞蟻選擇下方路徑。選擇是隨機(jī)的。C）下方短路徑螞蟻到達(dá)相反方向的決策點(diǎn)的時(shí)間早于選擇上方長路徑的螞蟻。D）短路徑上外激素以較高的速度積累。。外激素多的短路徑將吸收更多的螞蟻，反過來，更多的螞蟻在短路徑上會(huì)留下更多的外激素，加上外激素?fù)]發(fā)效應(yīng)，最后，蟻群都選擇了最短路徑。

102.蟻群優(yōu)化算法研究現(xiàn)狀1/7

90年代Dorigo最早提出了蟻群優(yōu)化算法---螞蟻系統(tǒng)（AntSystem,AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問題（TSP）。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在TSP以及許多實(shí)際優(yōu)化問題求解中進(jìn)一步得到了驗(yàn)證。這些AS改進(jìn)版本的一個(gè)共同點(diǎn)就是增強(qiáng)了螞蟻搜索過程中對(duì)最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結(jié)果的ACO是通過引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。11蟻群優(yōu)化算法研究現(xiàn)狀2/7最初提出的AS有三種版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在Ant-cycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。通過與其它各種通用的啟發(fā)式算法相比，在不大于75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴(kuò)展時(shí)，AS的解題能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改進(jìn)方面。較早的一種改進(jìn)方法是精英策略(ElitistStrategy)，其思想是在算法開始后即對(duì)所有已發(fā)現(xiàn)的最好路徑給予額外的增強(qiáng)，并將隨后與之對(duì)應(yīng)的行程記為Tgb(全局最優(yōu)行程)，當(dāng)進(jìn)行信息素更新時(shí)，對(duì)這些行程予以加權(quán)，同時(shí)將經(jīng)過這些行程的螞蟻記為“精英”，從而增大較好行程的選擇機(jī)會(huì)。這種改進(jìn)型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過多則算法會(huì)由于較早的收斂于局部次優(yōu)解而導(dǎo)致搜索的過早停滯。

12蟻群優(yōu)化算法研究現(xiàn)狀3/7

為了進(jìn)一步克服AS中暴露出的問題，提出了蟻群系統(tǒng)(AntColonySystem,ACS)。該系統(tǒng)的提出是以Ant-Q算法為基礎(chǔ)的。Ant-Q將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法Q-learning有機(jī)的結(jié)合了起來。ACS與AS之間存在三方面的主要差異：首先，ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。其中，0<ρ<1是信息素?fù)]發(fā)參數(shù)，是從尋路開始到當(dāng)前為止全局最優(yōu)的路徑長度。13蟻群優(yōu)化算法研究現(xiàn)狀4/7

再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過的路徑再次被選擇的概率。

14蟻群優(yōu)化算法研究現(xiàn)狀5/7在對(duì)AS進(jìn)行直接完善的方法中，MAX-MINAntSystem是一個(gè)典型代表。該算法修改了AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在[MAX，MIN]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。15蟻群優(yōu)化算法研究現(xiàn)狀6/7

另一種對(duì)AS改進(jìn)的算法是Rank-basedVersionAS。與“精英策略”相似，在此算法中總是更新更好進(jìn)程上的信息素，選擇的標(biāo)準(zhǔn)是其行程長度決定的排序，且每個(gè)螞蟻放置信息素的強(qiáng)度通過下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。

16蟻群優(yōu)化算法研究現(xiàn)狀7/7這種算法求解TSP的能力與AS、精英策略AS、遺傳算法和模擬退火算法進(jìn)行了比較。在大型TSP問題中（最多包含132座城市），基于AS的算法都顯示出了優(yōu)于GA和SA的特性。而且在Rank-basedAS和精英策略AS均優(yōu)于基本AS的同時(shí)，前者還獲得了比精英策略AS更好的解。

173.蟻群優(yōu)化算法應(yīng)用現(xiàn)狀1/5隨著群智能理論和應(yīng)用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在離散求解空間和連續(xù)求解空間中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應(yīng)用到其它組合優(yōu)化問題中。比較典型的應(yīng)用研究包括：網(wǎng)絡(luò)路由優(yōu)化、數(shù)據(jù)挖掘以及一些經(jīng)典的組合優(yōu)化問題。

18蟻群優(yōu)化算法應(yīng)用現(xiàn)狀2/5蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。HP公司和英國電信公司在90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（AntColonyRouting,ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗(yàn)與性能，動(dòng)態(tài)更新路由表項(xiàng)。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對(duì)該表項(xiàng)做較大的增強(qiáng)。同時(shí)根據(jù)信息素?fù)]發(fā)機(jī)制實(shí)現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當(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ì)和特性非常相似。19

蟻群優(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)則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過程。按照這樣的方法可實(shí)現(xiàn)對(duì)相似數(shù)據(jù)的聚類。20

蟻群優(yōu)化算法應(yīng)用現(xiàn)狀4/5

ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（GraphColoring）等問題。經(jīng)過多年的發(fā)展，ACO已成為能夠有效解決實(shí)際二次規(guī)劃問題的幾種重要算法之一。AS在作業(yè)流程計(jì)劃（Job-shopScheduling）問題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說明了AS在此領(lǐng)域的應(yīng)用潛力。利用MAX-MINAS解決PAQ也取得了比較理想的效果，并通過實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理PAQ比較早的SA算法更好，且與禁忌搜索算法性能相當(dāng)。利用ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了ACO的工程應(yīng)用價(jià)值。21蟻群優(yōu)化算法應(yīng)用現(xiàn)狀5/5許多研究者將ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無線電頻率自動(dòng)分配、Bayesiannetworks的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。Costa和Herz還提出了一種AS在規(guī)劃問題方面的擴(kuò)展應(yīng)用——圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。22第2節(jié)蟻群優(yōu)化算法概念 2.1蟻群算法原理2.2簡化的螞蟻尋食過程2.3自然蟻群與人工蟻群算法2.4蟻群算法與TSP問題2.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2.6一般蟻群算法的框架2.7蟻群優(yōu)化算法—技術(shù)問題232.1蟻群算法原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。為了說明蟻群算法的原理，先簡要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低.當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。242.2簡化的螞蟻尋食過程1/3螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。25簡化的螞蟻尋食過程2/3本圖為從開始算起，經(jīng)過18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。26

簡化的螞蟻尋食過程3/3

假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。272.3自然蟻群與人工蟻群算法基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如TSP問題。人工蟻群中把具有簡單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。282.4蟻群算法與TSP問題1/3TSP問題表示為一個(gè)N個(gè)城市的有向圖G=（N，A），其中 城市之間距離目標(biāo)函數(shù)為，其中為城市1,2，…n的一個(gè)排列，。29

蟻群算法與TSP問題2/3

TSP問題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1信息素值也稱信息素痕跡。2可見度，即先驗(yàn)值。信息素的更新方式有2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^)的邊增加信息素。30蟻群算法與TSP問題3/3螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來越接近最優(yōu)解。螞蟻在尋找過程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。312.5初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）1/12初始的蟻群算法是基于圖的蟻群算法，graph-basedantsystem,簡稱為GBAS，是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的，課本的參考文獻(xiàn)2。算法步驟如下：STEP0

對(duì)n個(gè)城市的TSP問題，城市間的距離矩陣為，給TSP圖中的每一條弧賦信息素初值，假設(shè)m只螞蟻在工作，所有螞蟻都從同一城市出發(fā)。當(dāng)前最好解是 。32初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）2/12STEP1

（外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻s從起點(diǎn)出發(fā)，用表示螞蟻s行走的城市集合，初始為空集，。STEP2(內(nèi)循環(huán))按螞蟻的順序分別計(jì)算。當(dāng)螞蟻在城市i，若 完成第s只螞蟻的計(jì)算。否則，若，則以概率 ， 到達(dá)j， ；若則到達(dá) 重復(fù)STEP2。33初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）3/12STRP3

對(duì) ，若，按中城市的順序計(jì)算路徑程度；若，路徑長度置為一個(gè)無窮大值（即不可達(dá)）。比較m只螞蟻中的路徑長度，記走最短路徑的螞蟻為t。若，則。用如下公式對(duì)W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。得到新的，重復(fù)步驟STEP1。34初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）4/12在STEP3

中，揮發(fā)因子對(duì)于一個(gè)固定的，滿足并且

經(jīng)過k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。35初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）5/12以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市j的轉(zhuǎn)移。算法中包括信息素更新的過程

1信息素?fù)]發(fā)（evaporation）信息素痕跡的揮發(fā)過程是每個(gè)連接上的信息素痕跡的濃度自動(dòng)逐漸減弱的過程，由表示，這個(gè)揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴(kuò)展。

2信息素增強(qiáng)（reinforcement）增強(qiáng)過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實(shí)現(xiàn)由單個(gè)螞蟻無法實(shí)現(xiàn)的集中行動(dòng)。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)，揮發(fā)過程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。這種增強(qiáng)過程中進(jìn)行的信息素更新稱為離線的信息素更新。在STEP3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。36圖的蟻群系統(tǒng)（GBAS）6/12可以驗(yàn)證，下式滿足：即是一個(gè)隨機(jī)矩陣。四個(gè)城市的非對(duì)稱TSP問題，距離矩陣和城市圖示如下：37

初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）7/12假設(shè)共4只螞蟻，所有螞蟻都從城市A出發(fā)，揮發(fā)因子。此時(shí)，觀察GBAS的計(jì)算過程。矩陣共有12條弧，初始信息素記憶矩陣為：38初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）8/12執(zhí)行GBAS算法的步驟2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個(gè)解是截止到當(dāng)前的最優(yōu)解，碰巧是實(shí)際最優(yōu)解39初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）9/12按算法步驟3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。40初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）10/12重復(fù)外循環(huán)，由于上一次得到的W2已經(jīng)是全局最優(yōu)解，因此按算法步驟3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對(duì)W2路線上的城市信息素進(jìn)行增強(qiáng)，其他的城市信息素進(jìn)行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。41初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）11/12重復(fù)外循環(huán)，由于W2全局最優(yōu)解，GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：42初始的蟻群優(yōu)化算法—基于圖的蟻群系統(tǒng)（GBAS）12/12螞蟻以一定的概率從城市i到城市j進(jìn)行轉(zhuǎn)移，信息素的更新在STEP3完成，并隨K而變化。假設(shè)第K次外循環(huán)后得到信息素矩陣，得到當(dāng)前最優(yōu)解。第K次循環(huán)前的信息素和最優(yōu)解為，經(jīng)過第K次外循環(huán)后，得到。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從到也是隨機(jī)的，是一個(gè)馬爾可夫過程。432.6一般蟻群算法的框架一般蟻群算法的框架和GBAS基本相同，有三個(gè)組成部分：蟻群的活動(dòng)；信息素的揮發(fā)；信息素的增強(qiáng)；主要體現(xiàn)在前面的算法中步驟2和步驟3中的轉(zhuǎn)移概率公式和信息素更新公式。442.7蟻群優(yōu)化算法—技術(shù)問題（1）解的表達(dá)形式與算法的實(shí)現(xiàn)（2）每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定（3）蟻群的規(guī)模和停止規(guī)則（4）信息素的更改45（1）

解的表達(dá)形式與算法的實(shí)現(xiàn)1/4

----解的表達(dá)形式解的表達(dá)形式基于TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個(gè)弧記錄。而對(duì)于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。蟻群算法在解決這類問題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把TSP問題的解法推廣，用于諸多的優(yōu)化問題。諸如車間作業(yè)及下料等問題，他們的共同特點(diǎn)是解以一個(gè)順序表示。TSP問題尋找的是最短回路，而一般優(yōu)化問題中，STEP3中的判斷條件需要根據(jù)實(shí)際問題進(jìn)行修改。46解的表達(dá)形式與算法的實(shí)現(xiàn)2/4

----算法的實(shí)現(xiàn)例：0-1背包問題的解順序表達(dá)形式與算法實(shí)現(xiàn)。設(shè)有一個(gè)容積為b的背包，n個(gè)尺寸分別為，價(jià)值分別為的物品，0-1背包問題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為，其中為的一個(gè)排列。47

解的表達(dá)形式與算法的實(shí)現(xiàn)3/4

----算法的實(shí)現(xiàn)建立有向圖，其中A中共有條弧。初始信息素痕跡定義為。設(shè)第s只螞蟻第k步所走的路線為，表示螞蟻從0點(diǎn)出發(fā)，順序到達(dá)。第步按TSP算法的轉(zhuǎn)移概率公式行走選擇。若則，否則，此螞蟻不再繼續(xù)行走，退回起點(diǎn)。48解的表達(dá)形式與算法的實(shí)現(xiàn)4/4----算法的實(shí)現(xiàn)對(duì)蟻群重復(fù)以上過程，比較m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為t。把GBAS算法中步驟3中的改為，若滿足此條件則替換當(dāng)前最好解為，對(duì)W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。算法中記錄了三個(gè)信息：信息素痕跡；行走路線；和問題的約束條件 ，以確定是否將加入。49（2）每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息1/3算法中需要記憶的信息有三部分。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu)，由此決定的的轉(zhuǎn)移概率為其中T可以看成節(jié)點(diǎn)i的鄰域。50每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----需要記憶的信息2/3第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的記憶，表示螞蟻已經(jīng)行走過的節(jié)點(diǎn)。第三部分為問題的約束條件。在GBAS中，T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件， 來實(shí)現(xiàn)記

憶功能。51每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定----系數(shù)的確定3/3

殘留信息的相對(duì)重要程度和預(yù)見值的相對(duì)重要程度體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對(duì)螞蟻決策的相對(duì)影響。Dorigo在求解TSP問題時(shí)，推薦參數(shù)的最佳設(shè)置為：。52（3）蟻群的規(guī)模和停止規(guī)則一、蟻群大小一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。二、終止條件

1給定一個(gè)外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；

2當(dāng)前最優(yōu)解連續(xù)K次相同而停止，其中K是一個(gè)給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)；

3目標(biāo)值控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。53（4）信息素的更改1/6信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。54信息素的更改2/6離線方式的信息素更新可以進(jìn)一步分為單螞蟻離線更新和蟻群離線更新。蟻群離線更新方式是在蟻群中的m只螞蟻全部完成n城市的訪問（第k-1次蟻群循環(huán)）后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。其中，為第k-1次循環(huán)后的的信息素的痕跡值。單螞蟻離線更新是在第s只螞蟻完成對(duì)所有n個(gè)城市的訪問后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。更新公式為第s+1只螞蟻根據(jù)重新計(jì)算路由表。

55

信息素的更改3/6TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中W為t循環(huán)中m只螞蟻所行走的最佳路線或第t只螞蟻所行走的一條路徑。Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ant-cyclealgotithm）,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。56信息素的更改4/6

GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶m只螞蟻的行走路徑，以進(jìn)行比較選擇最優(yōu)路徑。相對(duì)而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實(shí)際上這種方式等價(jià)于蟻群離線方式中只有一只螞蟻。57

信息素的更改5/6與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為其中，k為螞蟻行走的第k步。58信息素的更改6/6

蟻量算法（ant-quantityalgorithm）的信息素更新為,Q為常量，表示i到j(luò)的距離，這樣信息濃度會(huì)隨城市距離的減小而加大。蟻密算法（ant-densityalgorithm）信息素更新為。以上三種算法中，蟻環(huán)算法效果最好，因?yàn)樗玫氖侨中畔?，而其余兩種算法用的是局部信息。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記。59

蟻群優(yōu)化算法—參考書1智能蟻群算法及應(yīng)用吳啟迪上?？萍汲霭嫔鐝幕窘Y(jié)構(gòu)、算法特點(diǎn)、改進(jìn)方法、突破途徑、實(shí)現(xiàn)模式及應(yīng)用模式等方面進(jìn)行了論述。主要內(nèi)容有蟻群算法的由來、研究成果、應(yīng)用綜述、算法的具體描述及改進(jìn)、算法的典型優(yōu)化問題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。60蟻群優(yōu)化算法—參考書2蟻群算法及其應(yīng)用李士勇哈工大出版社國內(nèi)首部蟻群算法的專著，系統(tǒng)地闡述蟻群算法的基本原理、基本蟻群算法及改進(jìn)算法，蟻群算法與遺傳、免疫算法的融合，自適應(yīng)蟻群算法，并行蟻群算法，蟻群算法的收斂性與理論模型及其在優(yōu)化問題中的應(yīng)用。本書可供人工智能、計(jì)算機(jī)科學(xué)、信息科學(xué)、控制工程、管理工程、交通工程、網(wǎng)絡(luò)工程、智能優(yōu)化算法及智能自動(dòng)化等領(lǐng)域的廣大師生和科技人員學(xué)習(xí)及參考。61

蟻群優(yōu)化算法—參考文獻(xiàn)題目：群智能理論及應(yīng)用電子學(xué)報(bào),2003年S1期

【作者】彭喜元彭宇戴毓豐【關(guān)鍵詞】群智能微粒群算法蟻群算法優(yōu)化算法62基于群體智能的聚類算法CSI的研究CSI聚類算法主要步驟；基本模型簡化：概率轉(zhuǎn)換公式；實(shí)驗(yàn)結(jié)果

。63基于蟻群算法的聚類算法主要步驟：隨機(jī)分布待聚類模式；每只螞蟻計(jì)算當(dāng)前對(duì)象在局部環(huán)境的群體相似度，并通過概率轉(zhuǎn)換函數(shù)得到拾起或放下對(duì)象的概率，以這個(gè)概率行動(dòng)；經(jīng)過群體大量的相互作用，最終得到若干聚類中心；最后收集聚類結(jié)果。

64概率轉(zhuǎn)換公式的簡化基本模型簡化模型65實(shí)驗(yàn)結(jié)果

66電信消費(fèi)數(shù)據(jù)聚類分析實(shí)驗(yàn)結(jié)果比較

67基于群體智能的文檔聚類算法CSIM的研究為了處理聚類過程中出現(xiàn)的散點(diǎn)以及克服算法的一些隨機(jī)因素，更是為了提高算法的效率，我們將基于群體智能的文檔聚類算法與經(jīng)典的K均值算法相結(jié)合，對(duì)算法進(jìn)行了改進(jìn)?；旌纤惴ǖ倪^程是這樣的：首先采用基于群體智能文檔聚類算法對(duì)聚類文檔進(jìn)行處理，得到初始的聚類中心個(gè)數(shù)和聚類中心模板，然后運(yùn)用K均值算法再次聚類。這樣，既保留了群體智能算法的自組織特征，又結(jié)合了K均值算法的高效率，同時(shí)也克服了兩種算法的弱點(diǎn)，如群體智能算法的隨機(jī)性和K均值算法的聚類中心個(gè)數(shù)的參數(shù)預(yù)定及輸入順序敏感。我們將算法縮寫為CSIM。68第3節(jié)改進(jìn)的蟻群算法MacroDorigoGambardella69

帶精英策略的螞蟻系統(tǒng)帶精英策略的螞蟻系統(tǒng)（AntSystemwithelitiststrategy,ASelite）是最早的改進(jìn)螞蟻系統(tǒng)遺傳算法中的精英策略傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致最適應(yīng)個(gè)體的遺傳信息丟失精英策略的思想是保留住一代中的最適應(yīng)個(gè)體螞蟻系統(tǒng)中的精英策略每次循環(huán)之后給予最優(yōu)解以額外的信息素量這樣的解被稱為全局最優(yōu)解（global-bestsolution）找出這個(gè)解的螞蟻被稱為精英螞蟻(elitistants)70

帶精英策略的螞蟻系統(tǒng)信息素根據(jù)下式進(jìn)行更新其中71

帶精英策略的螞蟻系統(tǒng)上式中表示精英螞蟻引起的路徑(i,j)上的信息素量的增加特點(diǎn)：可以使螞蟻系統(tǒng)找出更優(yōu)的解找到這些解的時(shí)間更短精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂是精英螞蟻的個(gè)數(shù)是所找出的最優(yōu)解的路徑長度72

蟻群系統(tǒng)蟻群系統(tǒng)(AntColonySystem,ACS)是由Dorigo和Gambardella在1996年提出的蟻群系統(tǒng)做了三個(gè)方面的改進(jìn)：狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗(yàn)知識(shí)提供了方法全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上在建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)則73蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則一只位于節(jié)點(diǎn)r的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s其中，S根據(jù)下列公式得到74蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則q是在[0,1]區(qū)間均勻分布的隨機(jī)數(shù)q0的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性。上述狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機(jī)比例規(guī)則特點(diǎn)：傾向于選擇短的且有著大量信息素的邊作為移動(dòng)方向75蟻群系統(tǒng)全局更新規(guī)則只有全局最優(yōu)的螞蟻才被允許釋放信息素目的：使螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑的領(lǐng)域內(nèi)全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，使用下式對(duì)所建立的路徑進(jìn)行更新76蟻群系統(tǒng)全局更新規(guī)則為信息素?fù)]發(fā)參數(shù)，0<<1為到目前為止找出的全局最優(yōu)路徑全局更新規(guī)則的另一個(gè)類型稱為迭代最優(yōu)區(qū)別:使用代替，為當(dāng)前迭代(循環(huán))中的最優(yōu)路徑長度這兩種類型對(duì)蟻群系統(tǒng)性能的影響差別很小，全局最優(yōu)的性能要稍微好一些77蟻群系統(tǒng)局部更新規(guī)則類似于蟻密和蟻量模型中的更新規(guī)則螞蟻應(yīng)用下列局部更新規(guī)則對(duì)它們所經(jīng)過的邊進(jìn)行激素更新實(shí)驗(yàn)發(fā)現(xiàn)，可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量，是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑長度局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑78最大-最小螞蟻系統(tǒng)蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進(jìn)算法的性能。但這種搜索方式會(huì)使早熟收斂行為更容易發(fā)生最大-最小螞蟻系統(tǒng)(Max-MinAntSystem,MMAS)能將這種搜索方式和一種能夠有效避免早熟收斂的機(jī)制結(jié)合在一起，從而使算法獲得最優(yōu)的性能79最大-最小螞蟻系統(tǒng)MMAS和AS主要有三個(gè)方面不同：為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解，在每次循環(huán)之后，只有一只螞蟻進(jìn)行信息素更新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻，也可能是找出從實(shí)驗(yàn)開始以來最優(yōu)解的螞蟻為避免搜索的停滯，在每個(gè)解的元素上的的信息素軌跡量的值域范圍被限制在區(qū)間內(nèi)將信息素軌跡初始化為80信息素軌跡更新在MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡經(jīng)修改的軌跡更新規(guī)則如下：表示迭代最優(yōu)解或全局最優(yōu)解的值在蟻群算法中主要使用全局最優(yōu)解，而在MMAS中則主要使用迭代最優(yōu)解81信息素軌跡的限制不管是選擇迭代最優(yōu)還是全局最優(yōu)螞蟻來進(jìn)行信息素更新，都可能導(dǎo)致搜索的停滯。停滯現(xiàn)象發(fā)生的原因：在每個(gè)選擇點(diǎn)上一個(gè)選擇的信息素軌跡量明顯高于其他的選擇。避免停滯狀態(tài)發(fā)生的方法：影響用來選擇下一解元素的概率，它直接依賴于信息素軌跡和啟發(fā)信息。通過限制信息素軌跡的影響，可以很容易地避免各信息素軌跡之間的差異過大。82信息素軌跡的限制MMAS對(duì)信息素軌跡的最小值和最大值分別施加了和的限制，從而使得對(duì)所有信息素軌跡，有MMAS收斂：在每個(gè)選擇點(diǎn)上，其中一個(gè)解元素上的軌跡量為，而所有其他可選擇的解元素上的軌跡量為。若MMAS收斂，通過始終選擇信息素量最大的解元素所構(gòu)造的解將與算法找出的最優(yōu)解相一致83信息素軌跡的限制的選取的選取要基于兩點(diǎn)假設(shè)最優(yōu)解在搜索停滯發(fā)生之前不久被找出對(duì)解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間的相對(duì)差異決定84信息素軌跡的限制在一個(gè)選擇點(diǎn)上選擇相應(yīng)解元素的概率Pdec直接取決于和在每個(gè)選擇點(diǎn)上螞蟻需在avg=n/2個(gè)解元素中選擇螞蟻構(gòu)造最優(yōu)解，需作n次正確的決策85信息素軌跡的初始化在第一次循環(huán)后所有信息素軌跡與相一致通過選擇對(duì)這種類型的軌跡初始化來增加在算法的第一次循環(huán)期間對(duì)新解的探索當(dāng)將信息素軌跡初始化為時(shí)，選擇概率將增加得更加緩慢實(shí)驗(yàn)表明，將初始值設(shè)為可以改善最大-最小螞蟻系統(tǒng)的性能86信息素軌跡的平滑化基本思想：通過增加選擇有著低強(qiáng)度信息素軌跡量解元素的概率以提高探索新解的能力平滑機(jī)制有助于對(duì)搜索空間進(jìn)行更有效的探索87蟻群算法的應(yīng)用88混流裝配線調(diào)度混流裝配線(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號(hào)的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調(diào)度問題(job-shopschedulingproblem,JSP)的具體應(yīng)用之一。89問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號(hào)的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級(jí)SMMAL調(diào)度問題。90問題描述i表示車型數(shù)的標(biāo)號(hào)n表示需要裝配的車型數(shù)m表示裝配線上需要的零部件種類總數(shù)p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號(hào)表示零部件p的理想使用速率j表示車型調(diào)度結(jié)果(即排序位置)的標(biāo)號(hào)D表示在一個(gè)生產(chǎn)循環(huán)中需要組裝的各種車型的總和91問題描述di表示在一個(gè)生產(chǎn)循環(huán)中車型i的數(shù)量bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量表示在組裝線調(diào)度中前j-1臺(tái)車消耗零部件p的數(shù)量和92蟻群算法在SMMAL中的應(yīng)用假設(shè)有3種車型A、B、C排序，每個(gè)生產(chǎn)循環(huán)需A型車3輛，B型車2輛，C型車1輛，則每個(gè)循環(huán)共需生產(chǎn)6輛車。采用下圖的搜索空間定義，列表示6個(gè)排序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態(tài)93簡單SMMAL排序的搜索空間舉例經(jīng)過若干次迭代之后，搜索空間變化，此時(shí)最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)94局部搜索()的計(jì)算局部搜索采用的是貪心策略基本思路：每一步均從當(dāng)前可選擇策略中選取，使目標(biāo)函數(shù)值增加最少的策略，即在確定第j個(gè)位置組裝的車型時(shí)，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個(gè)位置組裝車型i時(shí)各零部件的使用速率最為均勻。95狀態(tài)轉(zhuǎn)移概率狀態(tài)轉(zhuǎn)移概率公式如下96信息素更新規(guī)則LB表示目標(biāo)函數(shù)的下限值表示當(dāng)前目標(biāo)函數(shù)的平均值Zcutr表示當(dāng)前的目標(biāo)函數(shù)值這種動(dòng)態(tài)標(biāo)記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟97實(shí)驗(yàn)數(shù)據(jù)98實(shí)驗(yàn)參數(shù)設(shè)置螞蟻系統(tǒng)螞蟻數(shù)量N_ant=5最大循環(huán)周期Ncmax=400=0.2Q=20000=0.9LB=0.0蟻群系統(tǒng)q0=0.5全局更新規(guī)則中的

和局部更新規(guī)則中的均取0.199實(shí)驗(yàn)參數(shù)設(shè)置最大-最小螞蟻系統(tǒng)選取全局最優(yōu)解帶有精英策略的螞蟻系統(tǒng)精英螞蟻數(shù)量:1只100實(shí)驗(yàn)結(jié)果101實(shí)驗(yàn)結(jié)果分析直接用貪心策略求解結(jié)果：3293.4375螞蟻系統(tǒng)求解SMMAL問題的性能較差對(duì)于這個(gè)具體的問題，帶精英策略的螞蟻系統(tǒng)的求解性能并不好于螞蟻系統(tǒng)蟻群系統(tǒng)的性能相對(duì)于前兩者而言，有了很大幅度的提高最大-最小螞蟻系統(tǒng)的性能最好，大多數(shù)情況下的求解結(jié)果已達(dá)到實(shí)際的最優(yōu)解102實(shí)驗(yàn)界面103實(shí)驗(yàn)界面104蟻群系統(tǒng)在TSP問題中的應(yīng)用10城市TSP問題20城市TSP問題105蟻群系統(tǒng)在TSP問題中的應(yīng)用30城市TSP問題48城市TSP問題106Questions?107第4節(jié)粒子群優(yōu)化粒子群優(yōu)化(ParticleSwarmOptimization,PSO)，又稱微粒群算法，是由J.Kennedy和RCEberhart等于1995年開發(fā)的一種演化機(jī)制。

粒子(particle)”是一個(gè)折衷的選擇,因?yàn)榧刃枰獙⑷后w中的成員描述為沒有質(zhì)量、沒有體積的,同時(shí)也需要描述它的速度和加速狀態(tài)。ParticleSwarmOptimization(PSO)appliestoconceptofsocialinteractiontoproblemsolving.Itwasdevelopedin1995byJamesKennedyandRussEberhart[Kennedy,J.andEberhart,R.(1995).“ParticleSwarmOptimization”,Proceedingsofthe1995IEEEInternationalConferenceonNeuralNetworks,pp.1942-1948,IEEEPress.](/members/payman/swarm/kennedy95-ijcnn.pdf)

108粒子群優(yōu)化

SwarmTopologyInPSO,therehavebeentwobasictopologiesusedintheliteratureRingTopology(neighborhoodof3)StarTopology(globalneighborhood)

I4

I0

I1

I2

I3

I4

I0

I1

I2

I3109特點(diǎn)分布式搜尋

具記憶性組件較少，容易實(shí)現(xiàn)

適合在連續(xù)性的范圍內(nèi)搜尋

110演算法介紹每個(gè)尋優(yōu)的問題解都被想象成一只鳥，我們也稱為“Particle”。所有的Particle都有一個(gè)fitnessfunction以判斷目前的位置之好壞，

每一個(gè)Particle必須賦予記憶性，能記得所搜尋到最佳位置。每一個(gè)Particle還有一個(gè)速度以決定飛行的距離與方向。

111粒子群優(yōu)化:

TheAnatomyofaParticleAparticle(individual)iscomposedof:Threevectors:Thex-vectorrecordsthecurrentposition(location)oftheparticleinthesearchspace,Thep-vectorrecordsthelocationofthebestsolutionfoundsofarbytheparticle,andThev-vectorcontainsagradient(direction)forwhichparticlewilltravelinifundisturbed.IkX=<xk0,xk1,…,xkn-1>P=<pk0,pk1,…,pkn-1>V=<vk0,vk1,…,vkn-1>x_fitness=?p_fitness=?112粒子群優(yōu)化:

TheAnatomyofaParticleAparticle(individual)iscomposedof:Twofitnessvalues:Thex-fitnessrecordsthefitnessofthex-vector,andThep-fitnessrecordsthefitnessofthep-vector.IkX=<xk0,xk1,…,xkn-1>P=<pk0,pk1,…,pkn-1>V=<vk0,vk1,…,vkn-1>x_fitness=?p_fitness=?113速度更新Vid

：每一Particle在第d維之速度i：Particle