螞蟻算法實現(xiàn)圖像分割論文

第PAGEI頁螞蟻算法實現(xiàn)圖像分割摘要模式識別領(lǐng)域圖像分割是圖像處理的底層步驟，它對于圖像識別和圖像理解具有舉足輕重的作用。一個好的圖像分割算法對圖形圖像的處理會有意想不到的效果，因此探索更好的圖像分割算法是圖像處理領(lǐng)域中一個重要的研究方向。通過對螞蟻、蜜蜂和其他群居昆蟲的觀察和研究，人們逐步發(fā)展了群體智能的概念。行為簡單的個體聚合在一起就形成了具有某種智能的群體。群體所擁有的能力超過了個體能力的總合，其原因就是群體間存在著“協(xié)同合作”。本文將通過對螞蟻觀察和基于MARCODORIGO提出的螞蟻算法研究，用于對圖像分割問題的探索。將灰度圖作為螞蟻群落的棲息地、通過讓螞蟻個體具有的感知其周圍有限的范圍環(huán)境的激素狀況和圖像的邊緣情況的簡單能力，依據(jù)螞蟻群覓食的基本原理，實現(xiàn)對圖像的分割。實驗中將對不同種類邊緣圖像的測試，證明該算法能夠處理各種類型的圖像邊緣。通過與傳統(tǒng)處理的對比實驗，證明其能夠在多方面獲得更好的效果。關(guān)鍵詞：螞蟻算法;群體智能;圖像分割;邊緣檢測TheantsystemrealizesimagesegmentationAbstractInpatternrecognitionsystem,imagesegmentationisalow-levelimage-processing.Thistaskisveryimportant,asweknow,sincetheoutputofanimagesegmentationalgorithmcanbefedasinputtohigher-levelprocessingtasks.Acquiringthebetterimagesegmentationalgorithmhasalwaysbeenanimportantsubjectinthisfiled.Sincepeoplehavestudiedthebehavioroftheantcolonyandothersocialinsert,thenotionofsocialintelligencehasbeenintroduced.Peoplefindthatthecolony’scollectivebehaviorexceedsthesumofitsindividualmember’sactions.Themainreasonofthiskindofphenomenonissomethingwecalledsynergy.Thispaperdiscussesthemethodofusingantsystem,whichisalsoasocialintelligencealgorithm,tosolveimagesegmentationproblem.Greylevelimagecanberegardasatopographicmapwheretheimageistheantcolonyhabit.Therespectivegraylevelintensitiesandpheromoneintensitiesareconsideredineachantperceptionofhisneighborhood.Followingtherulesofforagingactivityoftherealants,weobtainedthealgorithmforimagesegmentationproblemsolvedbytheantcolony.Inourexperiments,differenttypesofimageshavebeenusedprovingthatthisalgorithmcancommendablyobtaintheiredge-images.Comparingwiththeresultofthoseclassicalalgorithms,wefoundthatantsystemalgorithmobtainedabetterresultinmanyaspects.Keywords：Antsystem；Socialintelligence；Imagesegmentation目錄摘要 IAbstract II目錄 11緒論 11.1 課題研究的背景簡介 11.2 課題的目的及意義 21.3 傳統(tǒng)邊緣檢測算子 31.4 螞蟻算法的國內(nèi)外研究現(xiàn)狀 61.5 本文的研究內(nèi)容 72螞蟻算法的原理 92.1簡單的螞蟻算法 92.1.1螞蟻覓食過程的研究 92.1.1螞蟻覓食過程的研究 102.2螞蟻的群體智能現(xiàn)象 102.3本章總結(jié) 113螞蟻算法用于圖像分割的算法實現(xiàn) 123.1螞蟻算法用于圖像分割 123.1.1人工螞蟻所處的環(huán)境 123.1.2路徑的選擇 123.2激素的遺留 133.2.1環(huán)境參數(shù)h 133.2.2激素遺留公式 144測試與結(jié)論 154.1蟻數(shù)量參數(shù)的選擇 154.2時間參數(shù)step的選擇 154.3激素權(quán)重參數(shù)的選擇 154.4方向權(quán)重參數(shù)δ選擇 174.5激素遺留參數(shù)p選擇 174.6進(jìn)一步的研究 174.7 本章總結(jié) 185程序的實現(xiàn)流程 195.1初始化 195.2 循環(huán) 195.3 偽算法和部分程序 195.4算法的時間復(fù)雜度 215.5程序及其參數(shù)的說明 21結(jié)論 22參考文獻(xiàn) 23致謝 24附錄1 25附錄2 29第21頁1緒論課題研究的背景簡介群體智能是近年來人工只能領(lǐng)域出現(xiàn)的一個新算法熱點。群居昆蟲以集體的力量，進(jìn)行覓食、御敵、筑巢、這種群體所所表現(xiàn)出來的“智能”，就稱之為“群體智能”(SwarmIntelligence)。如，蜜蜂采蜜和筑巢、螞蟻的覓食和筑巢等[1]。群居昆蟲的集體行為是很復(fù)雜的，它是受簡單規(guī)律支配的昆蟲個體行為的聚合。螞蟻、蜜蜂、白蟻和群居性黃蜂等。個體具有兩種不同的屬性，首先，它們是群體的一個成員，這樣他們就具有社會性，覓食、筑巢是每一只工蟻都要參加的活動。其次，它們又具有獨立性，如每一只螞蟻在尋找食物的時候都是自己單獨行動的。雖然，單看一只螞蟻并不能看出什么高超的技能，但如果以一群相當(dāng)數(shù)量的螞蟻為基礎(chǔ)就會發(fā)現(xiàn)它們的集體能力是非常強(qiáng)大的。螞蟻能筑巢,我們感到很驚訝。而看到人建筑高樓大廈并不感到驚奇。這也許是因為,認(rèn)為人有一個聰明的腦袋,故能設(shè)計建筑高樓大廈。那么,為什么有一個聰明的腦袋,就能完成各種工作,而沒有聰明腦袋的動物就不能完成復(fù)雜的任務(wù),是不是只有“聰明的腦袋”才能完成復(fù)雜的任務(wù)?若是這樣,那么“腦袋”是什么?是否都一定像我們現(xiàn)在看到的那樣?是否可以有其它形式?比如我們可否將整個“蟻群”看成一個“松散的腦袋”我想是可以這樣看的[2]。因為人和螞蟻都是從低等單細(xì)胞生物進(jìn)化而來的。一個分支進(jìn)化成像人這樣的大型動物(包括其中的腦袋),另一分支進(jìn)化成像螞蟻一樣的蟻群的腦袋。兩者的不同在于前者(腦袋)是連通的,后者(蟻群)是離散的。在這樣的看法下,一個螞蟻就相當(dāng)于腦中的一個細(xì)胞(神經(jīng)元),螞蟻之間的信息交流,就相當(dāng)于大腦中各個細(xì)胞之間的聯(lián)接。那么人工智能界用人工神經(jīng)網(wǎng)絡(luò)的技術(shù)來模擬人的大腦中某些功能,我們不就也可以用某種數(shù)學(xué)的模型來模擬"群體智能",用來說明螞蟻筑巢的功能。所不同點在于一個是用固定連接的神經(jīng)網(wǎng)絡(luò)來模擬,另一個是用離散隨機(jī)連接的神經(jīng)網(wǎng)絡(luò)來模擬。我們正是以這種想法為出發(fā)點,提出"群體智能"新的數(shù)學(xué)模型,并研究其基本性質(zhì)。螞蟻算法就是一種群體智能算法。是模仿螞蟻工作方式的一種新的啟發(fā)式算法。生物學(xué)研究表明一群互相協(xié)作的螞蟻能夠找到食物源和巢之間的最短路徑,而單只螞蟻則不能。螞蟻間相互協(xié)作的方法是它們在所經(jīng)過的路上留下一定數(shù)量的信息素(跡),該跡能被其它螞蟻檢測出來,一條路上的跡越多,其它螞蟻將以越高的概率跟隨此路徑,從而該路徑上的跡會被加強(qiáng)。最后最多擁有跡的路徑為最短路徑。計算機(jī)工作著通過對群居昆蟲的模擬，構(gòu)造了一系列對于傳統(tǒng)問題的新的解決方法，這就是模式識別領(lǐng)域中對于群體智能的研究。群體智能中的群體是指“一組相互之間可以進(jìn)行直接通信或者通過改變局部環(huán)境間接通信的主體，這組主體能夠合作進(jìn)行分布問題求解”。所謂群體智能指的是“無智能的主體通過合作表現(xiàn)出智能行為的特征”[3]。群體智能在沒有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題的解決方案提供了基礎(chǔ)。在不同的應(yīng)用中，研究者通過模仿螞蟻的覓食或是打掃巢穴等群體行為進(jìn)行算法設(shè)計，最終達(dá)到實現(xiàn)某種人工智能的目的。這樣的算法都被稱之為螞蟻算法或好似螞蟻系統(tǒng)。1.2課題的目的及意義數(shù)字圖像處理技術(shù)起源于20世紀(jì)20年代，經(jīng)過半個世紀(jì)的發(fā)展，目前已經(jīng)廣泛的用于工業(yè)、醫(yī)療保健、航空航天、軍事、地理等眾多領(lǐng)域。隨著網(wǎng)絡(luò)的普及和互聯(lián)網(wǎng)的高速發(fā)展數(shù)字圖像處理越來越多的人的重視。同時它也在向其他相關(guān)的學(xué)科領(lǐng)域滲透。所謂數(shù)字圖像的處理就是利用數(shù)字計算機(jī)或者其它數(shù)字硬件，對從圖像信息轉(zhuǎn)換而得的電信號進(jìn)行某些數(shù)字運(yùn)算，以提高圖像的實用性。在人工智能領(lǐng)域進(jìn)行圖像處理的目的是希望能由計算機(jī)自動識別和理解圖像。圖像處理中的關(guān)鍵的一步是對包含有大量各式各樣景物信息的原始圖像進(jìn)行分解。分解的最終結(jié)果是該圖像被劃分為一些具有某種特征的最小成分，稱為圖像的基元。相對于整幅圖像來說，這種基元更容易被計算機(jī)快速處理[4]。當(dāng)人們觀察景物時，在視覺系統(tǒng)中對景物進(jìn)行分割的過程是不可缺少的。這個過程的結(jié)果是，人們所看到的景物并不是一個復(fù)雜的整體，而是各種簡單物體的集合。對于圖像的感覺，人類首先是有選擇的去掉圖像的一些結(jié)構(gòu)或物體，而保留了另外的一部分。這種選擇主要是根據(jù)物體的幾何形狀和物體的形象在環(huán)境中的對比決定的。人的大腦很容易的完成了這項工作，將圖像信息進(jìn)行下一步處理。但是在人工智能的數(shù)字圖像領(lǐng)域，這卻不是一項簡單的工作。必須通過某些圖像的特征將其分離出來，然后把這種出來的結(jié)果作為下一步的處理輸入。圖像的特征，是指圖像中可以用作標(biāo)志的屬性。它可分為圖像的統(tǒng)計特征和圖像的視覺特征兩類。圖像的統(tǒng)計特征是指一些人為的定義的特征，需要通過一定的變換處理才能得到，如直方圖、矩、頻譜等；圖像的視覺特征是指人的視覺可以直接感受到的自然特征，如區(qū)域的亮度、紋理或輪廓等。利用這兩類特征把圖像、分解成一系列有意義的目標(biāo)或區(qū)域的過程稱為圖像的分割[5]。圖像的邊緣是圖像的最基本的特征。對于灰度來說，所謂的邊緣，就是指周圍的像素點的灰度有階躍變化或屋頂變化的那些像素的集合。邊緣廣泛的存在于物體于背景之間，物體于物體之間、基元于基元間。因此，它是圖像分割的重要特征。圖像邊緣和圖像輪廓特征的檢測與提取方法，一直是圖形處理與分析技術(shù)中的熱點研究方向。圖像的邊緣檢測，或稱之為圖像分割，作為視覺處理的一個早期階段，有著很長的研究歷史。新理論、新方法的不斷涌現(xiàn)，一方面說明該研究方向本身的重要性，另一方面也反映了它的深度和難度。用螞蟻算法解決圖像分割問題，是從群體智能的角度出發(fā)，希望將群體智能的基本原理應(yīng)用于圖像分割領(lǐng)域，使這一問題產(chǎn)生一種新的解決方法，并期待它能夠獲得較傳統(tǒng)的邊緣檢測算法更為優(yōu)越的處理效果。1.3傳統(tǒng)邊緣檢測算子對于灰度圖像來說，物體的邊緣是由灰度不連續(xù)性所反映的。經(jīng)典的邊緣提取方法是考察圖像的每一個像素在某個領(lǐng)域內(nèi)灰度的變化，利用邊緣領(lǐng)域一階或二階方向?qū)?shù)變化規(guī)律，用簡單的方法檢測邊緣。這種方法稱為邊緣檢測局部算子法[6]。邊緣的種類可以分為兩種：一種稱為階躍性邊緣，它兩邊的像素的灰度值有著顯著的不同；另一種稱為屋頂狀邊緣，它位于灰度值從增加到減少的變化轉(zhuǎn)折點。對于階躍邊緣，二階方向?qū)?shù)在邊緣處呈零交叉；而對于屋頂狀邊緣，二階方向?qū)?shù)在邊緣處取極值[7]。如果一個像素落在圖像中某一個物體的邊界上，那么它的領(lǐng)域?qū)⒊蔀橐粋€灰度級的變化帶。對這種變化最有用的兩個特征是灰度的變化率和方向，它們分別以梯度向量的幅度和方向來表示。這些計算大多都以方向?qū)?shù)掩模求卷積的方法。(1)Roberts邊緣檢測算子Roberts邊緣檢測算子是一種利用局部差分算子尋找邊緣算子。它由公式g(x,y)=(1-1)其中f(x,y)是具有整數(shù)像素坐標(biāo)的輸入圖像，平方跟運(yùn)算使該處理類似于在人類視覺系統(tǒng)中發(fā)生的過程。(2)Sobel邊緣檢測算子如下圖所示的兩個卷積核形成了sobel邊緣算子，圖像中的每個點都用這兩個核作卷積，一個核對通常的垂直邊緣響應(yīng)最大，而另一個對水平邊緣的響應(yīng)最大。兩個卷積的最大值作為該點的輸出位。運(yùn)算結(jié)果得到一幅邊緣幅度圖像。-1-2-1-101000-202121-101水平檢測垂直檢測圖1-1sobel邊緣檢測算子如下圖所示的8個卷積核形成了Krisch邊緣算子。圖像中的每個點都用這幾個核作卷積，每個掩模都對某個特定邊緣方向做出最大響應(yīng)，每個卷積的最大值作為該點的輸出。最大響應(yīng)掩模的序號構(gòu)成了邊緣方向的編碼，以下就為Krisch算子，555-355303-305-3-3-3-3-3-3-3-35-3-3-3-305-305-3-35-355-1-2-1-101000-202121-101-1-2-1-101000-202121-101圖1-2Krisch算子(3)prewitt邊緣檢測算子下圖所示的兩個卷積核形成了Prewitt邊緣算子，圖像中的每個點都用這兩個核作卷積，一個核對通常的垂直邊緣響應(yīng)最大，而另一個對水平邊緣的響應(yīng)最大。兩個卷積的最大值作為該點的輸出位。運(yùn)算結(jié)果得到一幅邊緣幅度圖像。和Sobel邊緣檢測算子差不多。-1-1-110-100020-111110-1圖1-3prewitt邊緣檢測算子(4)高斯-拉普拉斯邊緣檢測算子高斯算子是一個平滑模板，平滑模板的思想是通過將一點和周圍八個點作平均，從而去除突然變化的點，濾掉噪音，其代價是圖像有一定程度的模糊。拉普拉斯算子是一個銳化模板，銳化和平滑恰恰相反，它是通過增強(qiáng)高頻分量來減少圖像中的模糊，故又叫做高通濾波。銳化處理在增強(qiáng)圖像邊緣的同時增強(qiáng)了圖像的噪音。拉普拉斯算子是對二維函數(shù)進(jìn)行運(yùn)算的二階導(dǎo)數(shù)算子。通常使用的拉普拉斯算子如圖所示：0-10-1-1-1-14-1-18-10-10-1-1-1圖1-4高斯-拉普拉斯邊緣檢測算子由于拉普拉斯算子是二階導(dǎo)數(shù)算子，它將邊緣處產(chǎn)生的陡峭的零交叉。因為噪音點對邊緣檢測有一定的影響，所以高斯-拉普拉斯算子是效果較好的邊緣檢測器。它把高斯平滑濾波器和拉普拉斯銳化濾波器結(jié)合在一起，先平滑掉噪音，再進(jìn)行邊緣檢測，所以效果更好。-2-4-4-4-2-4080-4-48248-4-4080-4-2-4-4-4-2圖1-5高斯-拉普拉斯算子上述邊緣算子產(chǎn)生的邊緣看起來很相似。但Robert算子是2*2模板的算子，它對陡峭的低噪音相應(yīng)最好，而后面的都是3*3模板的算子，對灰度漸變和噪音較多的圖像處理的較好。1.2螞蟻算法的國內(nèi)外研究現(xiàn)狀該算法是由意大利學(xué)者M(jìn).Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,稱之為蟻群系統(tǒng)(antcolonysystem),該模型已成功應(yīng)用于求旅行商問題(TSP),二次指派問題,排序問題等ＮＰ-困難的組合最優(yōu)化問題,結(jié)果可與模擬退火,遺傳算法等通用的啟發(fā)式算法相媲美。蟻群算法和局部搜索算法相結(jié)合(稱為混合蟻群算法)應(yīng)用于解二次指派問題和排序問題,得到的結(jié)果可以與專用算法相媲美[8]。通過模仿螞蟻覓食過程而解決的一個比較經(jīng)典的問題是TSP(travelingsalesmanproblem)。TSP是指求一個周游所有指定城市，最后回到出發(fā)點的最短路徑問題。螞蟻算法在解決TSP問題中，先假定所有的城市在同一平面上，每兩個城市之間都有路徑存在，當(dāng)螞蟻經(jīng)過路徑時都會留下一定量的激素。初始化時，m只螞蟻被隨機(jī)的放在n的城市的點上面，螞蟻們在每一個時間步到達(dá)一個新的城市，并且改變各個城市路徑間的激素含量。與此同時隨著時間的改變激素也會有揮發(fā)即激素不停的在減少。螞蟻周游之后激素會在各城市之間留下不同數(shù)量的激素，螞蟻在第二次經(jīng)過時，激素量越大選擇走的概率就越大。當(dāng)然，解決此問題時必須給螞蟻一些其它的功能，如它們能夠確定城市間的遠(yuǎn)近，存貯已經(jīng)走過的城市。這樣，每一只螞蟻前進(jìn)時選擇它沒有到達(dá)過的城市，距離最短的城市，當(dāng)然也是激素遺留最多的城市。針對對稱實例的實驗可以很好的檢測出該算法的優(yōu)越性，而針對不對稱的實例可以考察它對問題的解決能力。通過對于對稱的和不對稱的TSP的研究，我們可以將螞蟻算法和其他的算法進(jìn)行比較而得出螞蟻算法是一種很好的進(jìn)行圖像處理的方法。蟻群系統(tǒng)模型逐漸引起了其它研究者的注意,D.Costa和A.Hertz在M.Dorigo等人研究成果的基礎(chǔ)上,提出了一種求解分配類型問題(assignmenttypeproblem)的一般模型,并用來研究圖著色問題。G.Bilchev、I.C.Parmee研究了求解連續(xù)空間優(yōu)化問題的蟻群系統(tǒng)模型。在國際上，已經(jīng)出現(xiàn)了不少有螞蟻算法或其他群體智能算法實現(xiàn)應(yīng)用的事例。一群螞蟻隨機(jī)出發(fā),遇到垃圾,就將其拉走(拉的方向也是隨機(jī)的),拉垃圾時,若遇到某一堆垃圾時,就放下，放下垃圾后,再次進(jìn)行拉垃圾行為。當(dāng)然還要加了一些限制,才能達(dá)到人們所希望的結(jié)果。另外,螞蟻同心協(xié)進(jìn)行搬運(yùn)食物,是我們見得最多的螞蟻行為,有人以此為藍(lán)本設(shè)計出幾個機(jī)器人共同推盒子的算法。如美國阿爾伯塔大學(xué)設(shè)計出幾個機(jī)器人共同推盒子的實驗。借助螞蟻分工合作的特點(蟻皇管生男育女,工蟻管干活,兵蟻管保衛(wèi))的啟迪,人們設(shè)計了求解任務(wù)分配問題的螞蟻算法,并應(yīng)用于工廠中汽車噴漆問題。如美國西北大學(xué)將螞蟻算法用于卡車廠油漆車間,負(fù)責(zé)給離開裝配線的卡車上漆的工作安排。他們采取工人分組,各組只噴一種顏色,只有當(dāng)某小組任務(wù)特別緊張時,才分配另一小組前去幫助。通過這種設(shè)計后工廠各車間改變顏色的次數(shù)更少,從而提高了整體的生產(chǎn)率。又如美國MCIWorld-com公司一直研究人工螞蟻,并用于管理公司的電話網(wǎng),對用戶記帳收費(fèi)等工作。另外,還設(shè)計"人工螞蟻"打算用于因特網(wǎng)的路由管理。國內(nèi)也有研究者用螞蟻算法求解全國144個城市的最短回路問題,求得的解同其它方法求到得解一樣精確,許多研究機(jī)構(gòu)也進(jìn)行了一些螞蟻算法的研究工作。比如清華大學(xué)提出基于螞蟻算法的擁塞規(guī)避路由算法；重慶大學(xué)研究了基于螞蟻算法的機(jī)器人路徑規(guī)劃問題；上海理工大學(xué)研究了基于螞蟻算法的函數(shù)優(yōu)化問題等等[9]。這說明螞蟻算法不但是求解組合優(yōu)化問題的可行方法,而且是一種很有競爭力的算法。這種群體智能模型具有一下特點：(1)通用性強(qiáng)。同一問題，可以用多種相似的方法解決。(2)健壯性好。應(yīng)用與其它問題是，在解決方案中需要做很少的改動。(3)它是一種基于群體的方法。這使的開發(fā)正反饋的搜索機(jī)制成為可能。1.2本文的研究內(nèi)容本章介紹了群體智能的研究背景，論述了圖像分割在模式在圖像識別領(lǐng)域的地位，討論了本課題研究的目的應(yīng)用意義。簡要介紹了幾種常見的圖像分割算法。在本章最后，介紹了幾個螞蟻算法的實際現(xiàn)狀。本文主要討論將螞蟻算法應(yīng)用于圖像分割問題的基本原理和解決方案。通過模仿螞蟻群體在覓食過程中，釋放激素并依據(jù)激素選擇路徑，從而找到最短路徑這一原理，構(gòu)建了人工螞蟻在數(shù)字圖像背景下的運(yùn)動模型，最終達(dá)到通過人工螞蟻群落的爬行獲得圖像邊緣的目的。通過實驗，對該算法的主要參數(shù)逐一進(jìn)行了測試，并嘗試確定了各個參數(shù)值。通過對具有不同種類邊緣的圖像進(jìn)行測試處理，證明該算法可以處理各種類型的邊緣。與傳統(tǒng)邊緣檢測算法的對比顯示，使用螞蟻算法進(jìn)行圖像邊緣的處理具有一定的優(yōu)勢。2螞蟻算法的原理2.1簡單的螞蟻算法2.1.1螞蟻覓食過程的研究螞蟻覓食的具體過程是這樣的：在覓食的過程中，每一只螞蟻都會在其沿途走過的地方留下一種化學(xué)激素，螞蟻們彼此可以識別這種激素的味道。螞蟻群尋找食物時，首先會派出一些螞蟻分頭在四周游蕩，當(dāng)某只螞蟻搬運(yùn)食物回巢后，其它螞蟻就會沿著激素的味道尋找下去。如果某一路徑上遺留的激素味道越重，那么它就越是容易吸引更多的螞蟻爬向這條路徑。同時，所有的路徑上的激素都會緩慢地隨著時間的流逝而揮發(fā)，在一段足夠長的時間以后，螞蟻中的絕大多數(shù)螞蟻就會沿著最短的路徑往來與蟻穴和食物之間[10]。蟻穴C食物B蟻穴C食物BAD圖2－1簡單的螞蟻算法示意圖如圖示:在圖中，C點為蟻穴，B點為食物所在地，A點為尋找食物途中所經(jīng)過的一點，螞蟻在尋找食物時，即可沿C->A->B路線，也可按C->B的路線尋找食物。在簡單的模型中螞蟻找到食物并按原路返回，那么當(dāng)它們沿著原路返回時，由于CAB比較長，在BC返回時已經(jīng)留下兩次激素，而BAC只返回到D點，于是DAC點僅有一次，當(dāng)螞蟻下次出發(fā)時就回選擇激素量高的，即沿著CB出發(fā)。經(jīng)過一段時間BC上的激素積累多，就會有更多的螞蟻選擇BC，另一方面，由于所有路徑上的激素都隨著時間的推延緩慢的揮發(fā)，而BAC路徑上的螞蟻越來越少，激素也少，漸漸就沒有螞蟻去CAB路徑上了。這樣，最短路徑上的激素積累和螞蟻的爬行是一個正反饋的過程，因此它具有較快的收斂速度；而所有路徑上激素的揮發(fā)又是一個負(fù)反饋的過程，因此它可以保證螞蟻的爬行不會因為偶然因素最終收斂到非常短的路徑上。2.1.2螞蟻覓食過程的研究根據(jù)上述對于螞蟻尋食過程的討論，可以建立一個簡單的尋找最短路徑的螞蟻算法模型：（1）一群螞蟻隨機(jī)出發(fā)，尋找食物；（2）螞蟻爬行過程中，在沿途留下激素；（3）激素隨時間蒸發(fā)；（4）螞蟻選擇路徑的概率與各路徑上的激素濃度成正比。上述模型就是通過模仿螞蟻尋食過程而建立的基本模型。本文所討論的用螞蟻算法解決余下分割的問題，也是在這一基本模型的基礎(chǔ)上展開的。2.2螞蟻的群體智能現(xiàn)象人們觀察到，自然界中每一只螞蟻的頭腦都是很簡單的，但是螞蟻群卻顯示出某種智能。螞蟻群能夠延最短路徑覓食就是這樣一種現(xiàn)象。下面將從群體智能的觀點對此分析。有人提出，螞蟻所組成的群落與神經(jīng)細(xì)胞所形成的大腦結(jié)構(gòu)有某些相似的地方，社會性昆蟲群落通過遺留激素爬行的過程建立路徑或有規(guī)律的交通網(wǎng)絡(luò)。這樣的模式在人腦中被稱之為認(rèn)識圖。但是有本質(zhì)的區(qū)別，比如昆蟲將它們的空間記憶寫在環(huán)境中，而人則完全留在大腦之中。這樣的假設(shè)是一中理想狀況的，但有科學(xué)根據(jù)的比如腦內(nèi)的海馬狀突起中建立認(rèn)知圖的神經(jīng)系統(tǒng)過程來進(jìn)行直接的對比來證明。我們假設(shè)智能有兩種表現(xiàn)形式，一種是生物單體經(jīng)過長期的積累形成現(xiàn)在的所謂的“大腦”的機(jī)能所表現(xiàn)出來的對外界的響應(yīng)，另一種是生物群體經(jīng)過進(jìn)化能夠表現(xiàn)出的對外界刺激的反應(yīng)。且都是生物為了生存對外界的表現(xiàn)的本能。這樣就不難說明螞蟻群落的行為是一種智能行為。此外，心理學(xué)和腦科學(xué)研究指出，感覺是一種整體影響增強(qiáng)的效果。即感覺不僅是由個體的基元構(gòu)成，而更多的是基元間的動態(tài)的相互關(guān)系神經(jīng)網(wǎng)絡(luò)的智能來自于神經(jīng)元的集體行動，每個神經(jīng)元只負(fù)責(zé)很有限的工作。但是神經(jīng)網(wǎng)絡(luò)卻是由數(shù)以萬記的神經(jīng)元組成的，當(dāng)然它們必須是一致的即為了解決問題必需向這個方向努力，這樣以來就表現(xiàn)出不可思議的結(jié)果。所以計算機(jī)雖然運(yùn)算速度很快，但對于圖像的識別卻要比任何人遜色的多。螞蟻智能所表現(xiàn)的不是一只螞蟻、兩只螞蟻的行為，而且單只螞蟻的能力加起來也不能談智能，它必須是在這個群體的所有成員在內(nèi)，而且基于相互協(xié)作的行為。2.3本章總結(jié)本章從螞蟻覓食現(xiàn)象出發(fā)，說明了螞蟻覓食的基本原理，并提出模型對螞蟻群落的群體智能現(xiàn)象進(jìn)行了初步分析和討論，并且將螞蟻算法的模型構(gòu)造出來以便進(jìn)一步的更好的實現(xiàn)螞蟻算法。3螞蟻算法用于圖像分割的算法實現(xiàn)3.1螞蟻算法用于圖像分割3.1.1人工螞蟻所處的環(huán)境如果將數(shù)字圖像視為像素的聚合和組合的話，那么螞蟻算法完全可以看成螞蟻激素的遺留問題，這樣對圖像處理應(yīng)用螞蟻算法完全可行。這樣以來，我們就討論以下螞蟻算法在圖像處理中的實現(xiàn)。我們將一幅圖像視為由像素點構(gòu)成的，而且它們在同一水平面上面每一個點都可以由唯一的坐標(biāo)來確定，顯然這些完全能夠?qū)崿F(xiàn)。像素按行和列整齊排列，圖像邊緣的像素點可視為與其周圍的點相鄰。螞蟻行走時，總是從它所在的一個位置，向與其向鄰的一個位置移動。用于處理圖像的螞蟻帶有四個參數(shù)：其位置的橫坐標(biāo)、縱坐標(biāo)、頭部朝向的橫坐標(biāo)和頭部朝向的縱坐標(biāo)。3.1.2路徑的選擇每只螞蟻對路徑的選擇依據(jù)兩個原則：一、根據(jù)周圍的各點的激素濃度，濃度越大選擇的概率越大。二、根據(jù)當(dāng)前頭部的方向，頭部前方的位置選擇的概率大于選擇后方的概率，盡量避免走回頭路。因此，每一只螞蟻在進(jìn)行下一點的選擇時，首先要進(jìn)行其周圍八個點的激素權(quán)重和方向權(quán)重的計算，然后的到其所在3*3區(qū)域的可能矩陣，最終根據(jù)概率選擇方向。我們用win1來代表激素權(quán)重，用win2來表示方向權(quán)重。那么激素權(quán)重可以表示為：win1=（1+δ/1+δ*ζ）^β(3-1)其中，δ是該像素位置上現(xiàn)有的激素量，常數(shù)β表示控制著每一只螞蟻依據(jù)激素量進(jìn)行隨機(jī)選擇的程度。β值較低是，激素權(quán)重較小，較高是相反。1/δ描述了螞蟻感覺激素的變化能力。較小時，她對周圍環(huán)境的變化不敏感，較大時則相反。方向權(quán)重表示為：11/21/41/211/21/2ant1/121/4ant1/81/41/121/201/121/201/12西北方向正北方向1/41/211/121/41/21/12ant1/21/20ant11/201/121/41/121/41/2東北方向正東方向1/201/121/41/121/201/121/12ant1/21/4ant1/41/41/211/211/2東南方向正南方向1/41/121/201/21/41/121/2ant1/121ant1/2011/21/41/21/41/12西南方向正西方向圖2-1方向模板表格中的數(shù)字對于該螞蟻來說，是該位置的方向權(quán)重值。頭部的最大，依次減少為1/2、1/4、1/12、1/20。假設(shè)螞蟻當(dāng)前位置為ant(i,j)，那么欲選出螞蟻下一個前進(jìn)到的路徑,就要計算其周圍3*3的區(qū)域中每個被選中的概率。但是它計算的結(jié)果還是那一個點的激素權(quán)重和方向權(quán)重的積最大，就為下一個爬向的點，故其計算為：P(i,j)=win1*win2；(3-2)P(i,j)表示螞蟻從位置(i,j)為、位置到下一位置的概率。計算相鄰各點的選擇概率后，螞蟻再根據(jù)這個計算值選擇下一個到達(dá)的點。3.2激素的遺留3.2.1環(huán)境參數(shù)h如果不考慮螞蟻所要進(jìn)行的尋找邊緣的工作的話，那么每只螞蟻只要在其行走的每一個點上面留下固定量的激素，這與自然界螞蟻的習(xí)性是相同的。但自然界中的螞蟻前行的目標(biāo)是存在于某點的食物，通過激素信息傳播的結(jié)果是找到最短路徑，圖像處理中人工螞蟻的目的則是找到圖像的邊緣。為了達(dá)到這個目的，需要在螞蟻遺留的激素中加入其所在環(huán)境的邊緣性質(zhì)，這樣，激素的信息中就包含了環(huán)境的邊緣信息。螞蟻們在通過激素間接交流的同時，就實現(xiàn)了對周圍區(qū)域圖像邊緣信息的交流。由于上述原因，引入激素環(huán)境參數(shù)h，其計算方法如下式(3-3)示：h=a*|m1-m2|/max|m1-m2|+b*|p1^2-p2^2|/max|p1^2-p2^2|+c*S/S_max(3-3)這個公式中，m表示灰度值，p表示標(biāo)準(zhǔn)方差。其中m1表示以螞蟻所在位置為中心的3*3的灰度區(qū)域的平均值，m2表示螞蟻選擇的下一位置為中心的3*3灰度平均值，max|m1-m2|表示當(dāng)螞蟻所在點周圍的8個點分別作為m2的中心點時，計算出來的最大差值，它的結(jié)果與下一位置和當(dāng)前位置之間存在邊緣的可能性的大小成正比。方差表示的與灰度基本類似。S表示兩窗口之間的灰度直方圖的不同，∑|f（1）-f（2）|計算。計算當(dāng)前窗口與下一個位置窗口對應(yīng)的灰度之差的和，表示從灰度直方圖角度看，認(rèn)為下一位置和當(dāng)前位置之間存在邊緣的可能性的大小。式子中的a，b，c為常數(shù)，a+b+c=1，用來調(diào)整以上三方面的各自的權(quán)重，具體的數(shù)值應(yīng)視圖像的灰度情況而定。 3.2.2激素遺留公式由于需要在螞蟻遺留的激素中加入圖像邊緣的信息，所以它們行走時遺留的激素不再時一個定值，而需要公式來計算，如(3-4)示。T=(T0+η+p*h)*k(3-4)其中p為常數(shù)，控制著環(huán)境信息在遺留的激素中的權(quán)重。η是螞蟻爬過一點時留下的激素的基本量。4測試與結(jié)論4.1螞蟻數(shù)量參數(shù)的選擇螞蟻數(shù)量的選擇也是對算法的時間影響很大的，當(dāng)然對處理的結(jié)果有舉足輕重的作用。我們經(jīng)過處理可知，最好的螞蟻數(shù)量在圖像像素的30%左右，當(dāng)螞蟻數(shù)量偏少的時候，處理的圖像上面是成點狀的。太多時處理的效果和30%時是差不多的。所以螞蟻數(shù)量可以在15%到30%最佳。圖4-1和圖4-2很容易得出我們的結(jié)論。4.2時間參數(shù)step的選擇時間參數(shù)step主要控制算法的步數(shù)，所以對算法的處理時間有很大的影響，對處理的結(jié)果的優(yōu)劣程度也有一定的影響。圖像處理初始化完成后。分析測試的結(jié)果可以得出結(jié)論：當(dāng)處理邊緣明顯的圖像時，在初試參數(shù)條件下，當(dāng)setp較小時圖像的處理效果與處理次數(shù)間的關(guān)系比較明顯。而當(dāng)step較大時如150左右處理后得到的圖像邊緣幾乎沒什么變化。但是，隨著step的增加，處理時間呈線形增加。所以，為獲得較快的處理速度，可以選擇setp在100到300作為處理次數(shù)參數(shù)。圖4-3和圖4-4的比較得出上述結(jié)論。4.3激素權(quán)重參數(shù)的選擇在激素權(quán)重的公式中，我們知道win1=（1+δ/1+δ*ζ）^β中對激素權(quán)重影響的有三個因素，其中β的影響為指數(shù)增減的，因此β選擇至關(guān)重要，一般在1.5到4間最佳。ζ視圖形中的灰度情況而定，如果圖像灰度差值較大時最好選擇大一些，較小時小些。一般得出的值在1.0到2.5間。圖4-1螞蟻算法處理圖像1螞蟻數(shù)量為25%全圖像素，步數(shù)為100步圖4-2螞蟻算法處理圖像2螞蟻數(shù)量為10%全圖像素，步數(shù)為100步圖4-3螞蟻算法處理圖像3螞蟻數(shù)量為15%全圖像素，步數(shù)為50步圖4-3螞蟻算法處理圖像4螞蟻數(shù)量為15%全圖像素，步數(shù)為100步4.4方向權(quán)重參數(shù)δ選擇方向權(quán)重完全取決與螞蟻的方向，在這里我們不在做過多的介紹，它的大小描述螞蟻對激素變化的能力。經(jīng)過實驗的驗證選時一般在0.5到2.5間最好。4.5激素遺留參數(shù)p選擇該參數(shù)決定了螞蟻根據(jù)環(huán)境所遺留的激素的量。P的值越大，螞蟻遺留的激素就越多，特別是處于圖像的邊緣的時候，但是p值過大時反而會使處理效果變的差一些。P值一般選在5.5到15左右，由于p與路徑的收斂有很大的關(guān)系因此p選大一些處理會好一些的。但不是越大越好。因為路徑的選擇是基于兩個因素的，它們的關(guān)系時制約的激素權(quán)重大時，方向權(quán)重有影響，所以找到的不一定是最好的。4.6進(jìn)一步的研究本文對于螞蟻算法的研究已經(jīng)基本結(jié)束了，但是在未來還可以對這個算法進(jìn)行進(jìn)一步的研究。討論一些更深的問題，比如對人工螞蟻賦予更多的機(jī)能和更好的處理能力。如螞蟻壽命，螞蟻出錯的概率，隨機(jī)事件對螞蟻的影響，將螞蟻分為針對圖像的特點分為比率不同的蟻群來處理圖像等等。比如，對螞蟻參數(shù)設(shè)一個比較小的隨機(jī)系數(shù)在激素遺留公式里，來表示螞蟻的出錯概率，有如在人工螞蟻的結(jié)構(gòu)方面，我們可以分兩類螞蟻，其中一類可以設(shè)計的讓它對連續(xù)的灰度值相近的像素更為容易選擇，而另一類則對處理的更為綜合一些?；谶@樣的思想，我們?nèi)ピO(shè)計螞蟻，能使螞蟻算法的性能更好。螞蟻算法用于圖像分割技術(shù)方面還不是很成熟，它拓展了人們關(guān)于圖像處理的思路，并且顯示出了很大程度的優(yōu)越性，所以進(jìn)行更深更廣泛的研究是必須的也是必要的。如果螞蟻算法的研究做的足夠深入，那么它將很廣泛的應(yīng)用在社會各個方面。本章總結(jié)本章將算法通過MATLAB實現(xiàn)在圖像的分割上面，并且對個主要參數(shù)進(jìn)行了討論。最后的得到處理圖像。說明螞蟻算法在圖像分割中是可行的，本文對其它算子的討論都是基于以前他人的討論的，沒有做深刻的討論。最后對進(jìn)一步的研究只是自己的一些想法而已。5程序的實現(xiàn)流程5.1初始化數(shù)字圖像中，我們是圖像為像素組成的，那么圖像完全可以看成是一個由像素值組成的矩陣。這時的對圖像的操作就看成了對矩陣的操作。我們選擇用MATLAB來做。初始化的時候，一幅圖像空間存放圖像的信息，第二幅存放激素信息。申請相當(dāng)數(shù)量的螞蟻，將它們隨機(jī)的放置在圖上面，并隨機(jī)的放置方向，然后讀入方向參數(shù)，并將第一幅圖像的灰度轉(zhuǎn)化為激素權(quán)重.具體的看程序。5.2循環(huán)整個算法由兩重循環(huán)組成：處理時間的循環(huán)和處理螞蟻的循環(huán)。時間步和螞蟻數(shù)也是影響算法處理的關(guān)鍵因素，在初始時先循環(huán)步數(shù)，再循環(huán)螞蟻。在每一步里對每一只螞蟻進(jìn)行處理。螞蟻數(shù)量和循環(huán)步數(shù)在初始化時確定，在處理螞蟻時，先讀入其位置所在的3*3區(qū)域的激素值。最后以比率k對激素進(jìn)行揮發(fā)，并把揮發(fā)或的激素值轉(zhuǎn)化為灰度值寫回存放激素的圖像中。5.3偽算法和部分程序開始：初始化:ant←0（ant為螞蟻的數(shù)量）step←0(step為迭代步數(shù))將m個螞蟻隨機(jī)置于n個頂點上;循環(huán):fori←0ton-1dofork←1tomdo計算各螞蟻的目標(biāo)函數(shù)值；按概率選擇頂點j;移動螞蟻k至頂點j;更新當(dāng)前的解；endend程序如下：function[image4,image2]=antcolony(image1)[r,p]=size(image1)；ants=;%螞蟻數(shù)量steps=；%循環(huán)步數(shù)sigma=%激素初始量beta=；T0=；p1=；ka=；delta=；step=；a1=；b=；c=；add_sigma=；image1=zeros(r,p);image2=zeros(r,p);fori=1:rforj=1:pimage2(i,j)=sigma;endendstep=zeros(steps);whilestep<steps%對每一步進(jìn)行循環(huán).%關(guān)于螞蟻的數(shù)組，第三、四列表示螞蟻下一個位置如圖所示%(-1,-1)(-1,0)(-1,1)%(0,-1)(0,0)(0,1)%(1,-1)(1,0)(1,1)ant=zeros(ants,4);forNo=1:antsant(No,1)=mod(round(r*rand(1,1))+1,r);ant(No,2)=mod(round(p*rand(1,1))+1,p);ant(No,3)=round(rand(1,1));ant(No,4)=round(rand(1,1));endforNo=1:ants%對每一只螞蟻進(jìn)行循環(huán)。win_fx=fx(ant,No);%提取方向權(quán)重。win_pher=pick(image2,ant(No,1),ant(No,2));%提取3*3的窗口的對應(yīng)的激素。[fangxiang,P]=Max_P(win_fx,win_pher,delta,beta);%計算下一個點。ant(No,3)=fangxiang(1,1);ant(No,4)=fangxiang(2,1);h=huanjing(image1,ant,No,fangxiang,a1,b,c);image2(ant(No,1),ant(No,2))=T(T0,add_sigma,p1,h,ka);ant(No,1)=mod(ant(No,1)+ant(No,3),r);ant(No,2)=mod(ant(No,2)+ant(No,4),p);%更改參數(shù)。endstep=step+1;end5.4算法的時間復(fù)雜度時間復(fù)雜度為O（m*n），其中m為螞蟻數(shù)，n為循環(huán)的步數(shù)。很容易的看出來程序的復(fù)雜度與步數(shù)和螞蟻的個數(shù)聯(lián)系最為緊密。5.5程序及其參數(shù)的說明以上程序是在BATLAB中實現(xiàn)的，主程序中有七個子程序。它們是fx函數(shù)它用來調(diào)用方向權(quán)重；w_p用來調(diào)用激素權(quán)重；pick用來讀取像素信息；huanjing用來計算螞蟻對周圍環(huán)境的響應(yīng)參數(shù)h；Max_P求取螞蟻爬向的下一個點；T寫入激素值；rgb2gray讀圖像進(jìn)行灰度處理。在程序的運(yùn)行中由于軟件的原因，大約整幅圖像30%的像素，運(yùn)行200步大約需時12個小時（3%像素的螞蟻，運(yùn)行200步用時1小時10分鐘），所以參數(shù)選擇上多數(shù)基于已經(jīng)形成的結(jié)論。當(dāng)然簡單的數(shù)據(jù)都是處理時的數(shù)據(jù)。結(jié)論本論文采用群體智能理論中的螞蟻算法來實現(xiàn)圖像分割的問題。將人工螞蟻放置在數(shù)字圖像上，給螞蟻賦予一定的激素辨別和頭部朝向進(jìn)行下一步路徑選擇的能力，同時進(jìn)行一定量的激素釋放，使螞蟻經(jīng)過一段時間的爬行，最終將行走的路徑收斂到圖像的邊緣上面去，達(dá)到圖像分割的目的。本文的討論是螞蟻算法實現(xiàn)圖像分割的基層，無論對于圖像分割，還是螞蟻算法的討論都是淺薄的，螞蟻算法的研究空間還很大的，由于水平的限制只能做出這么多的努力。有機(jī)會再深入的討論。參考文獻(xiàn)1[英]K.Sugawaraetal.,"ForagingBehaviorofMulti-robotSystemandEmergenceofSwarmIntelligence",Systems,Man,andCybernetics,1999.IEEESMC'99ConferenceProceedings.1999IEEEInternationalConferenceon,Volume:3,1999Page(s):257-262vol32[英]DorigoM,GambardellaLM.Antcolonysystem:Acooperativelearningapproachtothetravelingsalesmanproblem,IEEETrans.EvolutionaryComputation,1997,1(1):53-66.3[英]BillFulkerson,VanParunak,"TheLivingFactory:ApplicationsofArtificialLifetoManufacturing",IEEE19954張鈐.淺談螞蟻算法.計算機(jī)與信息技術(shù).2002,第100期5溫文波,杜維.蟻群算法概述.石油化工自動化,2002年1月,第一期:19-226[英]ColorniA.Distributedoptimizationbyantcoloniest[R].Proc.of1stEuropeanConf.ArtificialLife.7[英]DorigoM,LucaMariaGamberdella.AntColonySystem:ACooperativeLearningApproachtotheTravelingSalesmanProblem[R].TR,IRIDIA,19968[英]WalterJ,Gutjahr.Agraph-basedAntSystemanditsconvergence[J]:FutureGenerationComputerSystem,2000,16:837-888.9熊偉清,余舜潔,趙杰煜.具有分工的蟻群算法及應(yīng)用.模式識別與人工智能.2003年9月,第16卷第3期,328-33210張鈐.淺談螞蟻算法.計算機(jī)與信息技術(shù).2002,第100期致謝在此，我要衷心的感謝我的指導(dǎo)老師，從做設(shè)計的開始金雪松老師就給我很大的幫助和指導(dǎo)。從螞蟻算法的學(xué)習(xí)，到matlab的上機(jī)實踐都是在他的精心指導(dǎo)下進(jìn)行的。老師孜孜不倦的教誨使我收益匪淺。畢業(yè)設(shè)計的完成與父母對我在精神上的支持是分不開的。謹(jǐn)以此論文來表達(dá)對我讀書這么多年給予我?guī)椭娜说母兄x。附錄1ArtificialAntsandMinimumCostPathsIntheprevioussectionwehaveshownthatasetofdifferenceequationscanreproduceratheraccuratelythemeanbehaviorofthecontinuousmodelofDeneubourgetal.Yet,ourgoalistodefinealgorithmsthatcanbeusedtosolveminimumcostproblemsonmorecomplicatedgraphsthanthoserepresentingthedoublebridgeexperiment(see,e.g.,thegraphinfigure1).Withthisgoalinmind,letusconsiderastatic,connectedgraphG=(N,A),whereNisthesetofn=|N|nodesandAisthesetofundirectedarcsconnectingthem.Thetwopointsbetweenwhichwewanttoestablishaminimumcostpatharecalledsourceanddestinationnodes,astypicallydoneintheliteratureonminimumcostpathproblems(whenthecostofarcsisgivenbytheirlength,theminimumcostpathproblemisthesameastheshortest-pathproblem);sometimes,inanalogytotheshortest-path–findingbehaviorofrealants,wewillalsocallthemnestandfoodsource.Unfortunately,ifwetrytosolvetheminimumcostpathproblemonthegraphGusingartificialantswhosebehaviorisastraightforwardextensionofthebehavioroftheantsdescribedintheprevioussection,thefollowingproblemarises:theants,whilebuildingasolution,maygenerateloops.Asaconsequenceoftheforwardpheromonetrailupdatingmechanism,loopstendtobecomemoreandmoreattractiveandantscangettrappedinthem.Butevenifanantcanescapesuchloops,theoverallpheromonetraildistributionbecomessuchthatshortpathsarenolongerfavoredandthemechanismthatinthesimplerdoublebridgesituationmadetheantchoosetheshortestpathwithhigherprobabilitydoesnotworkanymore.Becausethisproblemisduetoforwardpheromonetrailupdating,itmightseemthatthesimplestsolutiontothisproblemwouldbetheremovaloftheforwardupdatingmechanism:inthiswayantswouldrelyonlyonbackwardupdating.Still,thisisnotasolution:aswassaidbefore(seesection1.1.2,butseealsoexercise1.1attheendofthischapter),iftheforwardupdateisremovedthesystemdoesnotworkanymore,noteveninthesimplecaseofthedoublebridgeexperiment.Wethereforeneedtoextendthecapabilitiesoftheartificialantsinawaythat,whileretainingthemostimportantcharacteristicsofrealants,allowsthemtosolveminimumcostpathproblemsongenericgraphs.Inparticular,artificialantsaregivenalimitedformofmemoryinwhichtheycanstorethepartialpathstheyhavefollowedsofar,aswellasthecostofthelinkstheyhavetraversed.Viatheuseofmemory,theantscanimplementanumberofusefulbehaviorsthatallowthemtoeffcientlybuildsolutionstotheminimumcostpathproblem.Thesebehaviorsare(1)probabilisticsolutionconstructionbiasedbypheromonetrails,withoutforwardpheromoneupdating;(2)deterministicbackwardpathwithloopeliminationandwithpheromoneupdating;and(3)evaluationofthequalityofthesolutionsgeneratedanduseofthesolutionqualityindeterminingthequantityofpheromonetodeposit(notethatwhileinthesimplecaseofminimumcostpathsearchanestimateofthesolutionqualitycanbemadebytheantalsoduringthesolutionconstruction,thisisnotnecessarilytrueinotherproblems,inwhichtheremaynotexistaneasywaytoevaluatepartialsolutions).Additionally,weshowthatbytakingintoaccountpheromoneevaporation,whichwasnotnecessarytoexplainrealants’behavior,performancecanbegreatlyimproved.Inthefollowingwebrieflyexplainhowtheabove-mentionedants’behavior,aswellaspheromoneevaporation,isimplementedinanalgorithmthatwecallSimple-ACO(S-ACOforshort).Itshouldbenotedthat,althoughitrepresentsasignificantsteptowardthedefinitionofaneffcientalgorithmforthesolutionofminimumcostproblemsongraphs,S-ACOshouldbetakenforwhatitis:adidactictooltoexplainthebasicmechanismsunderlyingACOalgorithms.Probabilisticforwardantsandsolutionconstruction.S-ACOantscanbethoughtofashavingtwoworkingmodes:forwardandbackward.Theyareinforwardmodewhentheyaremovingfromthenesttowardthefood,andtheyareinbackwardmodewhentheyaremovingfromthefoodbacktotheirnest.Onceanantinforwardmodereachesitsdestination,itswitchestobackwardmodeandstartsitstravelbacktothesource.InS-ACO,forwardantsbuildasolutionbychoosingprobabilisticallythenextnodetomovetoamongthoseintheneighborhoodofthegraphnodeonwhichtheyarelocated.(GivenagraphG=（A，T）twonodesi,j∈Nareneighborsifthereexistsanarc（i,j)∈NTheprobabilisticchoiceisbiasedbypheromonetrailspreviouslydepositedonthegraphbyotherants.Forwardantsdonotdepositanypheromonewhilemoving.This,togetherwithdeterministicbackwardmoves,helpsinavoidingtheformationofloops.Deterministicbackwardantsandpheromoneupdate.Theuseofanexplicitmemoryallowsananttoretracethepathithasfollowedwhilesearchingthedestinationnode.Moreover,S-ACOantsimprovethesystemperformancebyimplementingloopelimination.Inpractice,beforestartingtomovebackwardonthepaththey1.3ArtificialAntsandMinimumCostPaths11memorizedwhilesearchingthedestinationnode(i.e.,theforwardpath),S-ACOantseliminateanyloopsfromit.Whilemovingbackward,S-ACOantsleavepheromoneonthearcstheytraverse.Pheromoneupdatesbasedonsolutionquality.InS-ACOtheantsmemorizethenodestheyvisitedduringtheforwardpath,aswellasthecostofthearcstraversedifthegraphisweighted.Theycanthereforeevaluatethecostofthesolutionstheygenerateandusethisevaluationtomodulatetheamountofpheromonetheydepositwhileinbackwardmode.Makingpheromoneupdateafunctionofthegeneratedsolutionqualitycanhelpindirectingfutureantsmorestronglytowardbettersolutions.Infact,bylettingantsdepositahigheramountofpheromoneonshortpaths,theants’pathsearchingismorequicklybiasedtowardthebestsolutions.Interestingly,thedependen