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

第PAGEI頁(yè)螞蟻算法實(shí)現(xiàn)圖像分割摘要模式識(shí)別領(lǐng)域圖像分割是圖像處理的底層步驟，它對(duì)于圖像識(shí)別和圖像理解具有舉足輕重的作用。一個(gè)好的圖像分割算法對(duì)圖形圖像的處理會(huì)有意想不到的效果，因此探索更好的圖像分割算法是圖像處理領(lǐng)域中一個(gè)重要的研究方向。通過(guò)對(duì)螞蟻、蜜蜂和其他群居昆蟲的觀察和研究，人們逐步發(fā)展了群體智能的概念。行為簡(jiǎn)單的個(gè)體聚合在一起就形成了具有某種智能的群體。群體所擁有的能力超過(guò)了個(gè)體能力的總合，其原因就是群體間存在著“協(xié)同合作”。本文將通過(guò)對(duì)螞蟻觀察和基于MARCODORIGO提出的螞蟻算法研究，用于對(duì)圖像分割問(wèn)題的探索。將灰度圖作為螞蟻群落的棲息地、通過(guò)讓螞蟻個(gè)體具有的感知其周圍有限的范圍環(huán)境的激素狀況和圖像的邊緣情況的簡(jiǎn)單能力，依據(jù)螞蟻群覓食的基本原理，實(shí)現(xiàn)對(duì)圖像的分割。實(shí)驗(yàn)中將對(duì)不同種類邊緣圖像的測(cè)試，證明該算法能夠處理各種類型的圖像邊緣。通過(guò)與傳統(tǒng)處理的對(duì)比實(shí)驗(yàn)，證明其能夠在多方面獲得更好的效果。關(guān)鍵詞：螞蟻算法;群體智能;圖像分割;邊緣檢測(cè)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 課題研究的背景簡(jiǎn)介 11.2 課題的目的及意義 21.3 傳統(tǒng)邊緣檢測(cè)算子 31.4 螞蟻算法的國(guó)內(nèi)外研究現(xiàn)狀 61.5 本文的研究?jī)?nèi)容 72螞蟻算法的原理 92.1簡(jiǎn)單的螞蟻算法 92.1.1螞蟻覓食過(guò)程的研究 92.1.1螞蟻覓食過(guò)程的研究 102.2螞蟻的群體智能現(xiàn)象 102.3本章總結(jié) 113螞蟻算法用于圖像分割的算法實(shí)現(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測(cè)試與結(jié)論 154.1蟻數(shù)量參數(shù)的選擇 154.2時(shí)間參數(shù)step的選擇 154.3激素權(quán)重參數(shù)的選擇 154.4方向權(quán)重參數(shù)δ選擇 174.5激素遺留參數(shù)p選擇 174.6進(jìn)一步的研究 174.7 本章總結(jié) 185程序的實(shí)現(xiàn)流程 195.1初始化 195.2 循環(huán) 195.3 偽算法和部分程序 195.4算法的時(shí)間復(fù)雜度 215.5程序及其參數(shù)的說(shuō)明 21結(jié)論 22參考文獻(xiàn) 23致謝 24附錄1 25附錄2 29第21頁(yè)1緒論課題研究的背景簡(jiǎn)介群體智能是近年來(lái)人工只能領(lǐng)域出現(xiàn)的一個(gè)新算法熱點(diǎn)。群居昆蟲以集體的力量，進(jìn)行覓食、御敵、筑巢、這種群體所所表現(xiàn)出來(lái)的“智能”，就稱之為“群體智能”(SwarmIntelligence)。如，蜜蜂采蜜和筑巢、螞蟻的覓食和筑巢等[1]。群居昆蟲的集體行為是很復(fù)雜的，它是受簡(jiǎn)單規(guī)律支配的昆蟲個(gè)體行為的聚合。螞蟻、蜜蜂、白蟻和群居性黃蜂等。個(gè)體具有兩種不同的屬性，首先，它們是群體的一個(gè)成員，這樣他們就具有社會(huì)性，覓食、筑巢是每一只工蟻都要參加的活動(dòng)。其次，它們又具有獨(dú)立性，如每一只螞蟻在尋找食物的時(shí)候都是自己?jiǎn)为?dú)行動(dòng)的。雖然，單看一只螞蟻并不能看出什么高超的技能，但如果以一群相當(dāng)數(shù)量的螞蟻為基礎(chǔ)就會(huì)發(fā)現(xiàn)它們的集體能力是非常強(qiáng)大的。螞蟻能筑巢,我們感到很驚訝。而看到人建筑高樓大廈并不感到驚奇。這也許是因?yàn)?認(rèn)為人有一個(gè)聰明的腦袋,故能設(shè)計(jì)建筑高樓大廈。那么,為什么有一個(gè)聰明的腦袋,就能完成各種工作,而沒(méi)有聰明腦袋的動(dòng)物就不能完成復(fù)雜的任務(wù),是不是只有“聰明的腦袋”才能完成復(fù)雜的任務(wù)?若是這樣,那么“腦袋”是什么?是否都一定像我們現(xiàn)在看到的那樣?是否可以有其它形式?比如我們可否將整個(gè)“蟻群”看成一個(gè)“松散的腦袋”我想是可以這樣看的[2]。因?yàn)槿撕臀浵伓际菑牡偷葐渭?xì)胞生物進(jìn)化而來(lái)的。一個(gè)分支進(jìn)化成像人這樣的大型動(dòng)物(包括其中的腦袋),另一分支進(jìn)化成像螞蟻一樣的蟻群的腦袋。兩者的不同在于前者(腦袋)是連通的,后者(蟻群)是離散的。在這樣的看法下,一個(gè)螞蟻就相當(dāng)于腦中的一個(gè)細(xì)胞(神經(jīng)元),螞蟻之間的信息交流,就相當(dāng)于大腦中各個(gè)細(xì)胞之間的聯(lián)接。那么人工智能界用人工神經(jīng)網(wǎng)絡(luò)的技術(shù)來(lái)模擬人的大腦中某些功能,我們不就也可以用某種數(shù)學(xué)的模型來(lái)模擬"群體智能",用來(lái)說(shuō)明螞蟻筑巢的功能。所不同點(diǎn)在于一個(gè)是用固定連接的神經(jīng)網(wǎng)絡(luò)來(lái)模擬,另一個(gè)是用離散隨機(jī)連接的神經(jīng)網(wǎng)絡(luò)來(lái)模擬。我們正是以這種想法為出發(fā)點(diǎn),提出"群體智能"新的數(shù)學(xué)模型,并研究其基本性質(zhì)。螞蟻算法就是一種群體智能算法。是模仿螞蟻工作方式的一種新的啟發(fā)式算法。生物學(xué)研究表明一群互相協(xié)作的螞蟻能夠找到食物源和巢之間的最短路徑,而單只螞蟻則不能。螞蟻間相互協(xié)作的方法是它們?cè)谒?jīng)過(guò)的路上留下一定數(shù)量的信息素(跡),該跡能被其它螞蟻檢測(cè)出來(lái),一條路上的跡越多,其它螞蟻將以越高的概率跟隨此路徑,從而該路徑上的跡會(huì)被加強(qiáng)。最后最多擁有跡的路徑為最短路徑。計(jì)算機(jī)工作著通過(guò)對(duì)群居昆蟲的模擬，構(gòu)造了一系列對(duì)于傳統(tǒng)問(wèn)題的新的解決方法，這就是模式識(shí)別領(lǐng)域中對(duì)于群體智能的研究。群體智能中的群體是指“一組相互之間可以進(jìn)行直接通信或者通過(guò)改變局部環(huán)境間接通信的主體，這組主體能夠合作進(jìn)行分布問(wèn)題求解”。所謂群體智能指的是“無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特征”[3]。群體智能在沒(méi)有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解決方案提供了基礎(chǔ)。在不同的應(yīng)用中，研究者通過(guò)模仿螞蟻的覓食或是打掃巢穴等群體行為進(jìn)行算法設(shè)計(jì)，最終達(dá)到實(shí)現(xiàn)某種人工智能的目的。這樣的算法都被稱之為螞蟻算法或好似螞蟻系統(tǒng)。1.2課題的目的及意義數(shù)字圖像處理技術(shù)起源于20世紀(jì)20年代，經(jīng)過(guò)半個(gè)世紀(jì)的發(fā)展，目前已經(jīng)廣泛的用于工業(yè)、醫(yī)療保健、航空航天、軍事、地理等眾多領(lǐng)域。隨著網(wǎng)絡(luò)的普及和互聯(lián)網(wǎng)的高速發(fā)展數(shù)字圖像處理越來(lái)越多的人的重視。同時(shí)它也在向其他相關(guān)的學(xué)科領(lǐng)域滲透。所謂數(shù)字圖像的處理就是利用數(shù)字計(jì)算機(jī)或者其它數(shù)字硬件，對(duì)從圖像信息轉(zhuǎn)換而得的電信號(hào)進(jìn)行某些數(shù)字運(yùn)算，以提高圖像的實(shí)用性。在人工智能領(lǐng)域進(jìn)行圖像處理的目的是希望能由計(jì)算機(jī)自動(dòng)識(shí)別和理解圖像。圖像處理中的關(guān)鍵的一步是對(duì)包含有大量各式各樣景物信息的原始圖像進(jìn)行分解。分解的最終結(jié)果是該圖像被劃分為一些具有某種特征的最小成分，稱為圖像的基元。相對(duì)于整幅圖像來(lái)說(shuō)，這種基元更容易被計(jì)算機(jī)快速處理[4]。當(dāng)人們觀察景物時(shí)，在視覺(jué)系統(tǒng)中對(duì)景物進(jìn)行分割的過(guò)程是不可缺少的。這個(gè)過(guò)程的結(jié)果是，人們所看到的景物并不是一個(gè)復(fù)雜的整體，而是各種簡(jiǎn)單物體的集合。對(duì)于圖像的感覺(jué)，人類首先是有選擇的去掉圖像的一些結(jié)構(gòu)或物體，而保留了另外的一部分。這種選擇主要是根據(jù)物體的幾何形狀和物體的形象在環(huán)境中的對(duì)比決定的。人的大腦很容易的完成了這項(xiàng)工作，將圖像信息進(jìn)行下一步處理。但是在人工智能的數(shù)字圖像領(lǐng)域，這卻不是一項(xiàng)簡(jiǎn)單的工作。必須通過(guò)某些圖像的特征將其分離出來(lái)，然后把這種出來(lái)的結(jié)果作為下一步的處理輸入。圖像的特征，是指圖像中可以用作標(biāo)志的屬性。它可分為圖像的統(tǒng)計(jì)特征和圖像的視覺(jué)特征兩類。圖像的統(tǒng)計(jì)特征是指一些人為的定義的特征，需要通過(guò)一定的變換處理才能得到，如直方圖、矩、頻譜等；圖像的視覺(jué)特征是指人的視覺(jué)可以直接感受到的自然特征，如區(qū)域的亮度、紋理或輪廓等。利用這兩類特征把圖像、分解成一系列有意義的目標(biāo)或區(qū)域的過(guò)程稱為圖像的分割[5]。圖像的邊緣是圖像的最基本的特征。對(duì)于灰度來(lái)說(shuō)，所謂的邊緣，就是指周圍的像素點(diǎn)的灰度有階躍變化或屋頂變化的那些像素的集合。邊緣廣泛的存在于物體于背景之間，物體于物體之間、基元于基元間。因此，它是圖像分割的重要特征。圖像邊緣和圖像輪廓特征的檢測(cè)與提取方法，一直是圖形處理與分析技術(shù)中的熱點(diǎn)研究方向。圖像的邊緣檢測(cè)，或稱之為圖像分割，作為視覺(jué)處理的一個(gè)早期階段，有著很長(zhǎng)的研究歷史。新理論、新方法的不斷涌現(xiàn)，一方面說(shuō)明該研究方向本身的重要性，另一方面也反映了它的深度和難度。用螞蟻算法解決圖像分割問(wèn)題，是從群體智能的角度出發(fā)，希望將群體智能的基本原理應(yīng)用于圖像分割領(lǐng)域，使這一問(wèn)題產(chǎn)生一種新的解決方法，并期待它能夠獲得較傳統(tǒng)的邊緣檢測(cè)算法更為優(yōu)越的處理效果。1.3傳統(tǒng)邊緣檢測(cè)算子對(duì)于灰度圖像來(lái)說(shuō)，物體的邊緣是由灰度不連續(xù)性所反映的。經(jīng)典的邊緣提取方法是考察圖像的每一個(gè)像素在某個(gè)領(lǐng)域內(nèi)灰度的變化，利用邊緣領(lǐng)域一階或二階方向?qū)?shù)變化規(guī)律，用簡(jiǎn)單的方法檢測(cè)邊緣。這種方法稱為邊緣檢測(cè)局部算子法[6]。邊緣的種類可以分為兩種：一種稱為階躍性邊緣，它兩邊的像素的灰度值有著顯著的不同；另一種稱為屋頂狀邊緣，它位于灰度值從增加到減少的變化轉(zhuǎn)折點(diǎn)。對(duì)于階躍邊緣，二階方向?qū)?shù)在邊緣處呈零交叉；而對(duì)于屋頂狀邊緣，二階方向?qū)?shù)在邊緣處取極值[7]。如果一個(gè)像素落在圖像中某一個(gè)物體的邊界上，那么它的領(lǐng)域?qū)⒊蔀橐粋€(gè)灰度級(jí)的變化帶。對(duì)這種變化最有用的兩個(gè)特征是灰度的變化率和方向，它們分別以梯度向量的幅度和方向來(lái)表示。這些計(jì)算大多都以方向?qū)?shù)掩模求卷積的方法。(1)Roberts邊緣檢測(cè)算子Roberts邊緣檢測(cè)算子是一種利用局部差分算子尋找邊緣算子。它由公式g(x,y)=(1-1)其中f(x,y)是具有整數(shù)像素坐標(biāo)的輸入圖像，平方跟運(yùn)算使該處理類似于在人類視覺(jué)系統(tǒng)中發(fā)生的過(guò)程。(2)Sobel邊緣檢測(cè)算子如下圖所示的兩個(gè)卷積核形成了sobel邊緣算子，圖像中的每個(gè)點(diǎn)都用這兩個(gè)核作卷積，一個(gè)核對(duì)通常的垂直邊緣響應(yīng)最大，而另一個(gè)對(duì)水平邊緣的響應(yīng)最大。兩個(gè)卷積的最大值作為該點(diǎn)的輸出位。運(yùn)算結(jié)果得到一幅邊緣幅度圖像。-1-2-1-101000-202121-101水平檢測(cè)垂直檢測(cè)圖1-1sobel邊緣檢測(cè)算子如下圖所示的8個(gè)卷積核形成了Krisch邊緣算子。圖像中的每個(gè)點(diǎn)都用這幾個(gè)核作卷積，每個(gè)掩模都對(duì)某個(gè)特定邊緣方向做出最大響應(yīng)，每個(gè)卷積的最大值作為該點(diǎn)的輸出。最大響應(yīng)掩模的序號(hào)構(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邊緣檢測(cè)算子下圖所示的兩個(gè)卷積核形成了Prewitt邊緣算子，圖像中的每個(gè)點(diǎn)都用這兩個(gè)核作卷積，一個(gè)核對(duì)通常的垂直邊緣響應(yīng)最大，而另一個(gè)對(duì)水平邊緣的響應(yīng)最大。兩個(gè)卷積的最大值作為該點(diǎn)的輸出位。運(yùn)算結(jié)果得到一幅邊緣幅度圖像。和Sobel邊緣檢測(cè)算子差不多。-1-1-110-100020-111110-1圖1-3prewitt邊緣檢測(cè)算子(4)高斯-拉普拉斯邊緣檢測(cè)算子高斯算子是一個(gè)平滑模板，平滑模板的思想是通過(guò)將一點(diǎn)和周圍八個(gè)點(diǎn)作平均，從而去除突然變化的點(diǎn)，濾掉噪音，其代價(jià)是圖像有一定程度的模糊。拉普拉斯算子是一個(gè)銳化模板，銳化和平滑恰恰相反，它是通過(guò)增強(qiáng)高頻分量來(lái)減少圖像中的模糊，故又叫做高通濾波。銳化處理在增強(qiáng)圖像邊緣的同時(shí)增強(qiáng)了圖像的噪音。拉普拉斯算子是對(duì)二維函數(shù)進(jìn)行運(yùn)算的二階導(dǎo)數(shù)算子。通常使用的拉普拉斯算子如圖所示：0-10-1-1-1-14-1-18-10-10-1-1-1圖1-4高斯-拉普拉斯邊緣檢測(cè)算子由于拉普拉斯算子是二階導(dǎo)數(shù)算子，它將邊緣處產(chǎn)生的陡峭的零交叉。因?yàn)樵胍酎c(diǎn)對(duì)邊緣檢測(cè)有一定的影響，所以高斯-拉普拉斯算子是效果較好的邊緣檢測(cè)器。它把高斯平滑濾波器和拉普拉斯銳化濾波器結(jié)合在一起，先平滑掉噪音，再進(jìn)行邊緣檢測(cè)，所以效果更好。-2-4-4-4-2-4080-4-48248-4-4080-4-2-4-4-4-2圖1-5高斯-拉普拉斯算子上述邊緣算子產(chǎn)生的邊緣看起來(lái)很相似。但Robert算子是2*2模板的算子，它對(duì)陡峭的低噪音相應(yīng)最好，而后面的都是3*3模板的算子，對(duì)灰度漸變和噪音較多的圖像處理的較好。1.2螞蟻算法的國(guó)內(nèi)外研究現(xiàn)狀該算法是由意大利學(xué)者M(jìn).Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,稱之為蟻群系統(tǒng)(antcolonysystem),該模型已成功應(yīng)用于求旅行商問(wèn)題(TSP),二次指派問(wèn)題,排序問(wèn)題等ＮＰ-困難的組合最優(yōu)化問(wèn)題,結(jié)果可與模擬退火,遺傳算法等通用的啟發(fā)式算法相媲美。蟻群算法和局部搜索算法相結(jié)合(稱為混合蟻群算法)應(yīng)用于解二次指派問(wèn)題和排序問(wèn)題,得到的結(jié)果可以與專用算法相媲美[8]。通過(guò)模仿螞蟻覓食過(guò)程而解決的一個(gè)比較經(jīng)典的問(wèn)題是TSP(travelingsalesmanproblem)。TSP是指求一個(gè)周游所有指定城市，最后回到出發(fā)點(diǎn)的最短路徑問(wèn)題。螞蟻算法在解決TSP問(wèn)題中，先假定所有的城市在同一平面上，每?jī)蓚€(gè)城市之間都有路徑存在，當(dāng)螞蟻經(jīng)過(guò)路徑時(shí)都會(huì)留下一定量的激素。初始化時(shí)，m只螞蟻被隨機(jī)的放在n的城市的點(diǎn)上面，螞蟻們?cè)诿恳粋€(gè)時(shí)間步到達(dá)一個(gè)新的城市，并且改變各個(gè)城市路徑間的激素含量。與此同時(shí)隨著時(shí)間的改變激素也會(huì)有揮發(fā)即激素不停的在減少。螞蟻周游之后激素會(huì)在各城市之間留下不同數(shù)量的激素，螞蟻在第二次經(jīng)過(guò)時(shí)，激素量越大選擇走的概率就越大。當(dāng)然，解決此問(wèn)題時(shí)必須給螞蟻一些其它的功能，如它們能夠確定城市間的遠(yuǎn)近，存貯已經(jīng)走過(guò)的城市。這樣，每一只螞蟻前進(jìn)時(shí)選擇它沒(méi)有到達(dá)過(guò)的城市，距離最短的城市，當(dāng)然也是激素遺留最多的城市。針對(duì)對(duì)稱實(shí)例的實(shí)驗(yàn)可以很好的檢測(cè)出該算法的優(yōu)越性，而針對(duì)不對(duì)稱的實(shí)例可以考察它對(duì)問(wèn)題的解決能力。通過(guò)對(duì)于對(duì)稱的和不對(duì)稱的TSP的研究，我們可以將螞蟻算法和其他的算法進(jìn)行比較而得出螞蟻算法是一種很好的進(jìn)行圖像處理的方法。蟻群系統(tǒng)模型逐漸引起了其它研究者的注意,D.Costa和A.Hertz在M.Dorigo等人研究成果的基礎(chǔ)上,提出了一種求解分配類型問(wèn)題(assignmenttypeproblem)的一般模型,并用來(lái)研究圖著色問(wèn)題。G.Bilchev、I.C.Parmee研究了求解連續(xù)空間優(yōu)化問(wèn)題的蟻群系統(tǒng)模型。在國(guó)際上，已經(jīng)出現(xiàn)了不少有螞蟻算法或其他群體智能算法實(shí)現(xiàn)應(yīng)用的事例。一群螞蟻隨機(jī)出發(fā),遇到垃圾,就將其拉走(拉的方向也是隨機(jī)的),拉垃圾時(shí),若遇到某一堆垃圾時(shí),就放下，放下垃圾后,再次進(jìn)行拉垃圾行為。當(dāng)然還要加了一些限制,才能達(dá)到人們所希望的結(jié)果。另外,螞蟻同心協(xié)進(jìn)行搬運(yùn)食物,是我們見得最多的螞蟻行為,有人以此為藍(lán)本設(shè)計(jì)出幾個(gè)機(jī)器人共同推盒子的算法。如美國(guó)阿爾伯塔大學(xué)設(shè)計(jì)出幾個(gè)機(jī)器人共同推盒子的實(shí)驗(yàn)。借助螞蟻分工合作的特點(diǎn)(蟻皇管生男育女,工蟻管干活,兵蟻管保衛(wèi))的啟迪,人們?cè)O(shè)計(jì)了求解任務(wù)分配問(wèn)題的螞蟻算法,并應(yīng)用于工廠中汽車噴漆問(wèn)題。如美國(guó)西北大學(xué)將螞蟻算法用于卡車廠油漆車間,負(fù)責(zé)給離開裝配線的卡車上漆的工作安排。他們采取工人分組,各組只噴一種顏色,只有當(dāng)某小組任務(wù)特別緊張時(shí),才分配另一小組前去幫助。通過(guò)這種設(shè)計(jì)后工廠各車間改變顏色的次數(shù)更少,從而提高了整體的生產(chǎn)率。又如美國(guó)MCIWorld-com公司一直研究人工螞蟻,并用于管理公司的電話網(wǎng),對(duì)用戶記帳收費(fèi)等工作。另外,還設(shè)計(jì)"人工螞蟻"打算用于因特網(wǎng)的路由管理。國(guó)內(nèi)也有研究者用螞蟻算法求解全國(guó)144個(gè)城市的最短回路問(wèn)題,求得的解同其它方法求到得解一樣精確,許多研究機(jī)構(gòu)也進(jìn)行了一些螞蟻算法的研究工作。比如清華大學(xué)提出基于螞蟻算法的擁塞規(guī)避路由算法；重慶大學(xué)研究了基于螞蟻算法的機(jī)器人路徑規(guī)劃問(wèn)題；上海理工大學(xué)研究了基于螞蟻算法的函數(shù)優(yōu)化問(wèn)題等等[9]。這說(shuō)明螞蟻算法不但是求解組合優(yōu)化問(wèn)題的可行方法,而且是一種很有競(jìng)爭(zhēng)力的算法。這種群體智能模型具有一下特點(diǎn)：(1)通用性強(qiáng)。同一問(wèn)題，可以用多種相似的方法解決。(2)健壯性好。應(yīng)用與其它問(wèn)題是，在解決方案中需要做很少的改動(dòng)。(3)它是一種基于群體的方法。這使的開發(fā)正反饋的搜索機(jī)制成為可能。1.2本文的研究?jī)?nèi)容本章介紹了群體智能的研究背景，論述了圖像分割在模式在圖像識(shí)別領(lǐng)域的地位，討論了本課題研究的目的應(yīng)用意義。簡(jiǎn)要介紹了幾種常見的圖像分割算法。在本章最后，介紹了幾個(gè)螞蟻算法的實(shí)際現(xiàn)狀。本文主要討論將螞蟻算法應(yīng)用于圖像分割問(wèn)題的基本原理和解決方案。通過(guò)模仿螞蟻群體在覓食過(guò)程中，釋放激素并依據(jù)激素選擇路徑，從而找到最短路徑這一原理，構(gòu)建了人工螞蟻在數(shù)字圖像背景下的運(yùn)動(dòng)模型，最終達(dá)到通過(guò)人工螞蟻群落的爬行獲得圖像邊緣的目的。通過(guò)實(shí)驗(yàn)，對(duì)該算法的主要參數(shù)逐一進(jìn)行了測(cè)試，并嘗試確定了各個(gè)參數(shù)值。通過(guò)對(duì)具有不同種類邊緣的圖像進(jìn)行測(cè)試處理，證明該算法可以處理各種類型的邊緣。與傳統(tǒng)邊緣檢測(cè)算法的對(duì)比顯示，使用螞蟻算法進(jìn)行圖像邊緣的處理具有一定的優(yōu)勢(shì)。2螞蟻算法的原理2.1簡(jiǎn)單的螞蟻算法2.1.1螞蟻覓食過(guò)程的研究螞蟻覓食的具體過(guò)程是這樣的：在覓食的過(guò)程中，每一只螞蟻都會(huì)在其沿途走過(guò)的地方留下一種化學(xué)激素，螞蟻們彼此可以識(shí)別這種激素的味道。螞蟻群尋找食物時(shí)，首先會(huì)派出一些螞蟻分頭在四周游蕩，當(dāng)某只螞蟻搬運(yùn)食物回巢后，其它螞蟻就會(huì)沿著激素的味道尋找下去。如果某一路徑上遺留的激素味道越重，那么它就越是容易吸引更多的螞蟻爬向這條路徑。同時(shí)，所有的路徑上的激素都會(huì)緩慢地隨著時(shí)間的流逝而揮發(fā)，在一段足夠長(zhǎng)的時(shí)間以后，螞蟻中的絕大多數(shù)螞蟻就會(huì)沿著最短的路徑往來(lái)與蟻穴和食物之間[10]。蟻穴C食物B蟻穴C食物BAD圖2－1簡(jiǎn)單的螞蟻算法示意圖如圖示:在圖中，C點(diǎn)為蟻穴，B點(diǎn)為食物所在地，A點(diǎn)為尋找食物途中所經(jīng)過(guò)的一點(diǎn)，螞蟻在尋找食物時(shí)，即可沿C->A->B路線，也可按C->B的路線尋找食物。在簡(jiǎn)單的模型中螞蟻找到食物并按原路返回，那么當(dāng)它們沿著原路返回時(shí)，由于CAB比較長(zhǎng)，在BC返回時(shí)已經(jīng)留下兩次激素，而BAC只返回到D點(diǎn)，于是DAC點(diǎn)僅有一次，當(dāng)螞蟻下次出發(fā)時(shí)就回選擇激素量高的，即沿著CB出發(fā)。經(jīng)過(guò)一段時(shí)間BC上的激素積累多，就會(huì)有更多的螞蟻選擇BC，另一方面，由于所有路徑上的激素都隨著時(shí)間的推延緩慢的揮發(fā)，而BAC路徑上的螞蟻越來(lái)越少，激素也少，漸漸就沒(méi)有螞蟻去CAB路徑上了。這樣，最短路徑上的激素積累和螞蟻的爬行是一個(gè)正反饋的過(guò)程，因此它具有較快的收斂速度；而所有路徑上激素的揮發(fā)又是一個(gè)負(fù)反饋的過(guò)程，因此它可以保證螞蟻的爬行不會(huì)因?yàn)榕既灰蛩刈罱K收斂到非常短的路徑上。2.1.2螞蟻覓食過(guò)程的研究根據(jù)上述對(duì)于螞蟻尋食過(guò)程的討論，可以建立一個(gè)簡(jiǎn)單的尋找最短路徑的螞蟻算法模型：（1）一群螞蟻隨機(jī)出發(fā)，尋找食物；（2）螞蟻爬行過(guò)程中，在沿途留下激素；（3）激素隨時(shí)間蒸發(fā)；（4）螞蟻選擇路徑的概率與各路徑上的激素濃度成正比。上述模型就是通過(guò)模仿螞蟻尋食過(guò)程而建立的基本模型。本文所討論的用螞蟻算法解決余下分割的問(wèn)題，也是在這一基本模型的基礎(chǔ)上展開的。2.2螞蟻的群體智能現(xiàn)象人們觀察到，自然界中每一只螞蟻的頭腦都是很簡(jiǎn)單的，但是螞蟻群卻顯示出某種智能。螞蟻群能夠延最短路徑覓食就是這樣一種現(xiàn)象。下面將從群體智能的觀點(diǎn)對(duì)此分析。有人提出，螞蟻所組成的群落與神經(jīng)細(xì)胞所形成的大腦結(jié)構(gòu)有某些相似的地方，社會(huì)性昆蟲群落通過(guò)遺留激素爬行的過(guò)程建立路徑或有規(guī)律的交通網(wǎng)絡(luò)。這樣的模式在人腦中被稱之為認(rèn)識(shí)圖。但是有本質(zhì)的區(qū)別，比如昆蟲將它們的空間記憶寫在環(huán)境中，而人則完全留在大腦之中。這樣的假設(shè)是一中理想狀況的，但有科學(xué)根據(jù)的比如腦內(nèi)的海馬狀突起中建立認(rèn)知圖的神經(jīng)系統(tǒng)過(guò)程來(lái)進(jìn)行直接的對(duì)比來(lái)證明。我們假設(shè)智能有兩種表現(xiàn)形式，一種是生物單體經(jīng)過(guò)長(zhǎng)期的積累形成現(xiàn)在的所謂的“大腦”的機(jī)能所表現(xiàn)出來(lái)的對(duì)外界的響應(yīng)，另一種是生物群體經(jīng)過(guò)進(jìn)化能夠表現(xiàn)出的對(duì)外界刺激的反應(yīng)。且都是生物為了生存對(duì)外界的表現(xiàn)的本能。這樣就不難說(shuō)明螞蟻群落的行為是一種智能行為。此外，心理學(xué)和腦科學(xué)研究指出，感覺(jué)是一種整體影響增強(qiáng)的效果。即感覺(jué)不僅是由個(gè)體的基元構(gòu)成，而更多的是基元間的動(dòng)態(tài)的相互關(guān)系神經(jīng)網(wǎng)絡(luò)的智能來(lái)自于神經(jīng)元的集體行動(dòng)，每個(gè)神經(jīng)元只負(fù)責(zé)很有限的工作。但是神經(jīng)網(wǎng)絡(luò)卻是由數(shù)以萬(wàn)記的神經(jīng)元組成的，當(dāng)然它們必須是一致的即為了解決問(wèn)題必需向這個(gè)方向努力，這樣以來(lái)就表現(xiàn)出不可思議的結(jié)果。所以計(jì)算機(jī)雖然運(yùn)算速度很快，但對(duì)于圖像的識(shí)別卻要比任何人遜色的多。螞蟻智能所表現(xiàn)的不是一只螞蟻、兩只螞蟻的行為，而且單只螞蟻的能力加起來(lái)也不能談智能，它必須是在這個(gè)群體的所有成員在內(nèi)，而且基于相互協(xié)作的行為。2.3本章總結(jié)本章從螞蟻覓食現(xiàn)象出發(fā)，說(shuō)明了螞蟻覓食的基本原理，并提出模型對(duì)螞蟻群落的群體智能現(xiàn)象進(jìn)行了初步分析和討論，并且將螞蟻算法的模型構(gòu)造出來(lái)以便進(jìn)一步的更好的實(shí)現(xiàn)螞蟻算法。3螞蟻算法用于圖像分割的算法實(shí)現(xiàn)3.1螞蟻算法用于圖像分割3.1.1人工螞蟻所處的環(huán)境如果將數(shù)字圖像視為像素的聚合和組合的話，那么螞蟻算法完全可以看成螞蟻激素的遺留問(wèn)題，這樣對(duì)圖像處理應(yīng)用螞蟻算法完全可行。這樣以來(lái)，我們就討論以下螞蟻算法在圖像處理中的實(shí)現(xiàn)。我們將一幅圖像視為由像素點(diǎn)構(gòu)成的，而且它們?cè)谕凰矫嫔厦婷恳粋€(gè)點(diǎn)都可以由唯一的坐標(biāo)來(lái)確定，顯然這些完全能夠?qū)崿F(xiàn)。像素按行和列整齊排列，圖像邊緣的像素點(diǎn)可視為與其周圍的點(diǎn)相鄰。螞蟻行走時(shí)，總是從它所在的一個(gè)位置，向與其向鄰的一個(gè)位置移動(dòng)。用于處理圖像的螞蟻帶有四個(gè)參數(shù)：其位置的橫坐標(biāo)、縱坐標(biāo)、頭部朝向的橫坐標(biāo)和頭部朝向的縱坐標(biāo)。3.1.2路徑的選擇每只螞蟻對(duì)路徑的選擇依據(jù)兩個(gè)原則：一、根據(jù)周圍的各點(diǎn)的激素濃度，濃度越大選擇的概率越大。二、根據(jù)當(dāng)前頭部的方向，頭部前方的位置選擇的概率大于選擇后方的概率，盡量避免走回頭路。因此，每一只螞蟻在進(jìn)行下一點(diǎn)的選擇時(shí)，首先要進(jìn)行其周圍八個(gè)點(diǎn)的激素權(quán)重和方向權(quán)重的計(jì)算，然后的到其所在3*3區(qū)域的可能矩陣，最終根據(jù)概率選擇方向。我們用win1來(lái)代表激素權(quán)重，用win2來(lái)表示方向權(quán)重。那么激素權(quán)重可以表示為：win1=（1+δ/1+δ*ζ）^β(3-1)其中，δ是該像素位置上現(xiàn)有的激素量，常數(shù)β表示控制著每一只螞蟻依據(jù)激素量進(jìn)行隨機(jī)選擇的程度。β值較低是，激素權(quán)重較小，較高是相反。1/δ描述了螞蟻感覺(jué)激素的變化能力。較小時(shí)，她對(duì)周圍環(huán)境的變化不敏感，較大時(shí)則相反。方向權(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ù)字對(duì)于該螞蟻來(lái)說(shuō)，是該位置的方向權(quán)重值。頭部的最大，依次減少為1/2、1/4、1/12、1/20。假設(shè)螞蟻當(dāng)前位置為ant(i,j)，那么欲選出螞蟻下一個(gè)前進(jìn)到的路徑,就要計(jì)算其周圍3*3的區(qū)域中每個(gè)被選中的概率。但是它計(jì)算的結(jié)果還是那一個(gè)點(diǎn)的激素權(quán)重和方向權(quán)重的積最大，就為下一個(gè)爬向的點(diǎn)，故其計(jì)算為：P(i,j)=win1*win2；(3-2)P(i,j)表示螞蟻從位置(i,j)為、位置到下一位置的概率。計(jì)算相鄰各點(diǎn)的選擇概率后，螞蟻再根據(jù)這個(gè)計(jì)算值選擇下一個(gè)到達(dá)的點(diǎn)。3.2激素的遺留3.2.1環(huán)境參數(shù)h如果不考慮螞蟻所要進(jìn)行的尋找邊緣的工作的話，那么每只螞蟻只要在其行走的每一個(gè)點(diǎn)上面留下固定量的激素，這與自然界螞蟻的習(xí)性是相同的。但自然界中的螞蟻前行的目標(biāo)是存在于某點(diǎn)的食物，通過(guò)激素信息傳播的結(jié)果是找到最短路徑，圖像處理中人工螞蟻的目的則是找到圖像的邊緣。為了達(dá)到這個(gè)目的，需要在螞蟻遺留的激素中加入其所在環(huán)境的邊緣性質(zhì)，這樣，激素的信息中就包含了環(huán)境的邊緣信息。螞蟻們?cè)谕ㄟ^(guò)激素間接交流的同時(shí)，就實(shí)現(xiàn)了對(duì)周圍區(qū)域圖像邊緣信息的交流。由于上述原因，引入激素環(huán)境參數(shù)h，其計(jì)算方法如下式(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)這個(gè)公式中，m表示灰度值，p表示標(biāo)準(zhǔn)方差。其中m1表示以螞蟻所在位置為中心的3*3的灰度區(qū)域的平均值，m2表示螞蟻選擇的下一位置為中心的3*3灰度平均值，max|m1-m2|表示當(dāng)螞蟻所在點(diǎn)周圍的8個(gè)點(diǎn)分別作為m2的中心點(diǎn)時(shí)，計(jì)算出來(lái)的最大差值，它的結(jié)果與下一位置和當(dāng)前位置之間存在邊緣的可能性的大小成正比。方差表示的與灰度基本類似。S表示兩窗口之間的灰度直方圖的不同，∑|f（1）-f（2）|計(jì)算。計(jì)算當(dāng)前窗口與下一個(gè)位置窗口對(duì)應(yīng)的灰度之差的和，表示從灰度直方圖角度看，認(rèn)為下一位置和當(dāng)前位置之間存在邊緣的可能性的大小。式子中的a，b，c為常數(shù)，a+b+c=1，用來(lái)調(diào)整以上三方面的各自的權(quán)重，具體的數(shù)值應(yīng)視圖像的灰度情況而定。 3.2.2激素遺留公式由于需要在螞蟻遺留的激素中加入圖像邊緣的信息，所以它們行走時(shí)遺留的激素不再時(shí)一個(gè)定值，而需要公式來(lái)計(jì)算，如(3-4)示。T=(T0+η+p*h)*k(3-4)其中p為常數(shù)，控制著環(huán)境信息在遺留的激素中的權(quán)重。η是螞蟻爬過(guò)一點(diǎn)時(shí)留下的激素的基本量。4測(cè)試與結(jié)論4.1螞蟻數(shù)量參數(shù)的選擇螞蟻數(shù)量的選擇也是對(duì)算法的時(shí)間影響很大的，當(dāng)然對(duì)處理的結(jié)果有舉足輕重的作用。我們經(jīng)過(guò)處理可知，最好的螞蟻數(shù)量在圖像像素的30%左右，當(dāng)螞蟻數(shù)量偏少的時(shí)候，處理的圖像上面是成點(diǎn)狀的。太多時(shí)處理的效果和30%時(shí)是差不多的。所以螞蟻數(shù)量可以在15%到30%最佳。圖4-1和圖4-2很容易得出我們的結(jié)論。4.2時(shí)間參數(shù)step的選擇時(shí)間參數(shù)step主要控制算法的步數(shù)，所以對(duì)算法的處理時(shí)間有很大的影響，對(duì)處理的結(jié)果的優(yōu)劣程度也有一定的影響。圖像處理初始化完成后。分析測(cè)試的結(jié)果可以得出結(jié)論：當(dāng)處理邊緣明顯的圖像時(shí)，在初試參數(shù)條件下，當(dāng)setp較小時(shí)圖像的處理效果與處理次數(shù)間的關(guān)系比較明顯。而當(dāng)step較大時(shí)如150左右處理后得到的圖像邊緣幾乎沒(méi)什么變化。但是，隨著step的增加，處理時(shí)間呈線形增加。所以，為獲得較快的處理速度，可以選擇setp在100到300作為處理次數(shù)參數(shù)。圖4-3和圖4-4的比較得出上述結(jié)論。4.3激素權(quán)重參數(shù)的選擇在激素權(quán)重的公式中，我們知道win1=（1+δ/1+δ*ζ）^β中對(duì)激素權(quán)重影響的有三個(gè)因素，其中β的影響為指數(shù)增減的，因此β選擇至關(guān)重要，一般在1.5到4間最佳。ζ視圖形中的灰度情況而定，如果圖像灰度差值較大時(shí)最好選擇大一些，較小時(shí)小些。一般得出的值在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)重完全取決與螞蟻的方向，在這里我們不在做過(guò)多的介紹，它的大小描述螞蟻對(duì)激素變化的能力。經(jīng)過(guò)實(shí)驗(yàn)的驗(yàn)證選時(shí)一般在0.5到2.5間最好。4.5激素遺留參數(shù)p選擇該參數(shù)決定了螞蟻根據(jù)環(huán)境所遺留的激素的量。P的值越大，螞蟻遺留的激素就越多，特別是處于圖像的邊緣的時(shí)候，但是p值過(guò)大時(shí)反而會(huì)使處理效果變的差一些。P值一般選在5.5到15左右，由于p與路徑的收斂有很大的關(guān)系因此p選大一些處理會(huì)好一些的。但不是越大越好。因?yàn)槁窂降倪x擇是基于兩個(gè)因素的，它們的關(guān)系時(shí)制約的激素權(quán)重大時(shí)，方向權(quán)重有影響，所以找到的不一定是最好的。4.6進(jìn)一步的研究本文對(duì)于螞蟻算法的研究已經(jīng)基本結(jié)束了，但是在未來(lái)還可以對(duì)這個(gè)算法進(jìn)行進(jìn)一步的研究。討論一些更深的問(wèn)題，比如對(duì)人工螞蟻賦予更多的機(jī)能和更好的處理能力。如螞蟻壽命，螞蟻出錯(cuò)的概率，隨機(jī)事件對(duì)螞蟻的影響，將螞蟻分為針對(duì)圖像的特點(diǎn)分為比率不同的蟻群來(lái)處理圖像等等。比如，對(duì)螞蟻參數(shù)設(shè)一個(gè)比較小的隨機(jī)系數(shù)在激素遺留公式里，來(lái)表示螞蟻的出錯(cuò)概率，有如在人工螞蟻的結(jié)構(gòu)方面，我們可以分兩類螞蟻，其中一類可以設(shè)計(jì)的讓它對(duì)連續(xù)的灰度值相近的像素更為容易選擇，而另一類則對(duì)處理的更為綜合一些?；谶@樣的思想，我們?nèi)ピO(shè)計(jì)螞蟻，能使螞蟻算法的性能更好。螞蟻算法用于圖像分割技術(shù)方面還不是很成熟，它拓展了人們關(guān)于圖像處理的思路，并且顯示出了很大程度的優(yōu)越性，所以進(jìn)行更深更廣泛的研究是必須的也是必要的。如果螞蟻算法的研究做的足夠深入，那么它將很廣泛的應(yīng)用在社會(huì)各個(gè)方面。本章總結(jié)本章將算法通過(guò)MATLAB實(shí)現(xiàn)在圖像的分割上面，并且對(duì)個(gè)主要參數(shù)進(jìn)行了討論。最后的得到處理圖像。說(shuō)明螞蟻算法在圖像分割中是可行的，本文對(duì)其它算子的討論都是基于以前他人的討論的，沒(méi)有做深刻的討論。最后對(duì)進(jìn)一步的研究只是自己的一些想法而已。5程序的實(shí)現(xiàn)流程5.1初始化數(shù)字圖像中，我們是圖像為像素組成的，那么圖像完全可以看成是一個(gè)由像素值組成的矩陣。這時(shí)的對(duì)圖像的操作就看成了對(duì)矩陣的操作。我們選擇用MATLAB來(lái)做。初始化的時(shí)候，一幅圖像空間存放圖像的信息，第二幅存放激素信息。申請(qǐng)相當(dāng)數(shù)量的螞蟻，將它們隨機(jī)的放置在圖上面，并隨機(jī)的放置方向，然后讀入方向參數(shù)，并將第一幅圖像的灰度轉(zhuǎn)化為激素權(quán)重.具體的看程序。5.2循環(huán)整個(gè)算法由兩重循環(huán)組成：處理時(shí)間的循環(huán)和處理螞蟻的循環(huán)。時(shí)間步和螞蟻數(shù)也是影響算法處理的關(guān)鍵因素，在初始時(shí)先循環(huán)步數(shù)，再循環(huán)螞蟻。在每一步里對(duì)每一只螞蟻進(jìn)行處理。螞蟻數(shù)量和循環(huán)步數(shù)在初始化時(shí)確定，在處理螞蟻時(shí)，先讀入其位置所在的3*3區(qū)域的激素值。最后以比率k對(duì)激素進(jìn)行揮發(fā)，并把揮發(fā)或的激素值轉(zhuǎn)化為灰度值寫回存放激素的圖像中。5.3偽算法和部分程序開始：初始化:ant←0（ant為螞蟻的數(shù)量）step←0(step為迭代步數(shù))將m個(gè)螞蟻隨機(jī)置于n個(gè)頂點(diǎn)上;循環(huán):fori←0ton-1dofork←1tomdo計(jì)算各螞蟻的目標(biāo)函數(shù)值；按概率選擇頂點(diǎn)j;移動(dòng)螞蟻k至頂點(diǎn)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%對(duì)每一步進(jìn)行循環(huán).%關(guān)于螞蟻的數(shù)組，第三、四列表示螞蟻下一個(gè)位置如圖所示%(-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%對(duì)每一只螞蟻進(jìn)行循環(huán)。win_fx=fx(ant,No);%提取方向權(quán)重。win_pher=pick(image2,ant(No,1),ant(No,2));%提取3*3的窗口的對(duì)應(yīng)的激素。[fangxiang,P]=Max_P(win_fx,win_pher,delta,beta);%計(jì)算下一個(gè)點(diǎn)。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算法的時(shí)間復(fù)雜度時(shí)間復(fù)雜度為O（m*n），其中m為螞蟻數(shù)，n為循環(huán)的步數(shù)。很容易的看出來(lái)程序的復(fù)雜度與步數(shù)和螞蟻的個(gè)數(shù)聯(lián)系最為緊密。5.5程序及其參數(shù)的說(shuō)明以上程序是在BATLAB中實(shí)現(xiàn)的，主程序中有七個(gè)子程序。它們是fx函數(shù)它用來(lái)調(diào)用方向權(quán)重；w_p用來(lái)調(diào)用激素權(quán)重；pick用來(lái)讀取像素信息；huanjing用來(lái)計(jì)算螞蟻對(duì)周圍環(huán)境的響應(yīng)參數(shù)h；Max_P求取螞蟻爬向的下一個(gè)點(diǎn)；T寫入激素值；rgb2gray讀圖像進(jìn)行灰度處理。在程序的運(yùn)行中由于軟件的原因，大約整幅圖像30%的像素，運(yùn)行200步大約需時(shí)12個(gè)小時(shí)（3%像素的螞蟻，運(yùn)行200步用時(shí)1小時(shí)10分鐘），所以參數(shù)選擇上多數(shù)基于已經(jīng)形成的結(jié)論。當(dāng)然簡(jiǎn)單的數(shù)據(jù)都是處理時(shí)的數(shù)據(jù)。結(jié)論本論文采用群體智能理論中的螞蟻算法來(lái)實(shí)現(xiàn)圖像分割的問(wèn)題。將人工螞蟻放置在數(shù)字圖像上，給螞蟻賦予一定的激素辨別和頭部朝向進(jìn)行下一步路徑選擇的能力，同時(shí)進(jìn)行一定量的激素釋放，使螞蟻經(jīng)過(guò)一段時(shí)間的爬行，最終將行走的路徑收斂到圖像的邊緣上面去，達(dá)到圖像分割的目的。本文的討論是螞蟻算法實(shí)現(xiàn)圖像分割的基層，無(wú)論對(duì)于圖像分割，還是螞蟻算法的討論都是淺薄的，螞蟻算法的研究空間還很大的，由于水平的限制只能做出這么多的努力。有機(jī)會(huì)再深入的討論。參考文獻(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ì)算機(jī)與信息技術(shù).2002,第100期5溫文波,杜維.蟻群算法概述.石油化工自動(dòng)化,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)用.模式識(shí)別與人工智能.2003年9月,第16卷第3期,328-33210張鈐.淺談螞蟻算法.計(jì)算機(jī)與信息技術(shù).2002,第100期致謝在此，我要衷心的感謝我的指導(dǎo)老師，從做設(shè)計(jì)的開始金雪松老師就給我很大的幫助和指導(dǎo)。從螞蟻算法的學(xué)習(xí)，到matlab的上機(jī)實(shí)踐都是在他的精心指導(dǎo)下進(jìn)行的。老師孜孜不倦的教誨使我收益匪淺。畢業(yè)設(shè)計(jì)的完成與父母對(duì)我在精神上的支持是分不開的。謹(jǐn)以此論文來(lái)表達(dá)對(duì)我讀書這么多年給予我?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