第五章電腦鼠控制策略與算法研究

1、第五章 蟻群算法在迷宮電腦鼠中的應(yīng)用5.1 引言許多智能問題，如下棋游戲、戰(zhàn)略決策、機(jī)器人路徑規(guī)劃等都可以轉(zhuǎn)化為尋找迷宮最優(yōu)路徑問題。傳統(tǒng)解決迷宮最優(yōu)路徑問題的算法通常會隨著迷宮規(guī)模的增大、復(fù)雜性的增加，算法的空間和時間復(fù)雜性呈指數(shù)增加，從而很難用于求解大規(guī)模的問題實例。從蟻群覓食過程中能夠發(fā)現(xiàn)蟻巢與食物源之間的最短路徑受到啟發(fā)，并利用該過程與著名的旅行商問題(TravelingSalesman Problem, TSP)之間的相似性，意大利學(xué)者M(jìn). Dorigo等人提出了一種新型的模擬進(jìn)化算法-蟻群算法1,2。對TSP問題的求解結(jié)果顯示，蟻群算法具有極強的魯棒性和發(fā)現(xiàn)較好解的能力，但同時也存

2、在一些缺陷，如收斂速度慢、易出現(xiàn)停滯現(xiàn)象等2。目前，蟻群算法已在組合優(yōu)化、計算機(jī)網(wǎng)絡(luò)路由、連續(xù)函數(shù)優(yōu)化、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘、電網(wǎng)優(yōu)化等領(lǐng)域取得了突出的成就2-5，實踐證明該算法是一種解決優(yōu)化問題特別是組合優(yōu)化問題的有力工具。5.2 迷迷宮的基基本信息息及常用用迷宮搜搜尋策略略5.2.11 迷宮宮的基本本信息從比賽規(guī)則則中得知知，迷宮宮是由一一個個118cmm18ccm大小小的方格格組成的的，迷宮宮大小為為1616，即即行列各各有166個方格格。若將將三維迷迷宮轉(zhuǎn)化化成二維維圖形,迷宮可可用圖55.1表表示.圖 5.11 迷迷宮行列列與坐標(biāo)標(biāo)對應(yīng)關(guān)關(guān)系5.2.22 常用用搜尋法法則和策策略

3、5.2.22.1迷宮宮搜尋法法則設(shè)定搜尋法法則和策策略是為為了電腦腦鼠可以以以最快快的方式式找到終終點，到到達(dá)目標(biāo)標(biāo)后隨即即從所走過過的路徑徑中找出出一條可行路徑徑返回起起點，然然后再做做沖刺，直直達(dá)目的的；法則則的設(shè)定定很重要要，它可可以使電電腦鼠不不多走冤冤枉路，可可節(jié)省很很多時間間而制勝勝。每一只電腦腦鼠到達(dá)達(dá)一方格格時它最最多有三三個方向向可前進(jìn)進(jìn)，最少少則因為為三面都都有墻，沒沒有可以以前進(jìn)的的方向；當(dāng)遇到到二個以以上的可可選擇方方向時，由由于不同同場合需需要而有有不同優(yōu)優(yōu)先搜尋尋的方向向順序，常常見的法法則有以以下幾種種：右手法則則：遇叉叉路時，以以右邊為為優(yōu)先前前進(jìn)方向向，然后后

4、直線方方向，左左邊方向向；左手法則則：遇叉叉路時，以以左邊為為優(yōu)先前前進(jìn)方向向，然后后直線方方向，右右邊方向向；中左法則則：與右右手法則則相似，不不過方向向選擇順順序改為為直線優(yōu)優(yōu)先，然然后左邊邊，右邊邊；中右法則則：遇叉叉路時，以以直線為為優(yōu)先前前進(jìn)方向向，然后后右邊方方向，左左邊方向向；求心法則則：遇叉叉路時，以以距中心心最短的的那個方方向優(yōu)先先，然后后依次選選擇。亂數(shù)法則則：以電電腦鼠的隨機(jī)值作為為下一前前進(jìn)方向向。5.2.22.2迷宮宮搜尋策策略迷宮搜尋模模式有全全迷宮搜搜尋策略略和部分分迷宮搜搜尋策略略兩種：全迷宮搜搜尋策略略：電腦腦鼠以任任一搜尋尋法則前前進(jìn)到達(dá)達(dá)終點后后，電腦腦鼠

5、會反反身繼續(xù)續(xù)前進(jìn)，然然后以原原設(shè)定的的搜尋法法則，時時時檢查查未走過過的路，直直到每一一方格都都搜尋過過后，才才回起點點。部分迷宮宮搜尋策策略：電電腦鼠以以任一搜搜尋法則則前進(jìn)到到達(dá)終點點后，電電腦鼠將將沿原路路線返回回起點，不不再進(jìn)行行其它搜搜尋。如果比賽規(guī)規(guī)則不計計算搜尋尋時間，可可采用全全迷宮搜搜尋策略略，待地地毯式的的搜尋過過所有方方格后，再再計算最最佳路徑徑，作最最后的沖沖刺，沖沖刺成績績一定相相當(dāng)不錯錯。由于于新制國國際比賽賽規(guī)則加加入搜尋尋時間的的成績計計量，因因此我們們必須考考慮部分分迷宮搜搜尋策略略，甚至至還可能能須考慮慮加入求求心法則則，截路路徑功能能等更智智慧的法法則來

6、協(xié)協(xié)助；此此時找到到的路徑徑可能不不是最佳佳路徑，但但保證花花的時間間最短。5.2.33迷宮問問題經(jīng)典典算法求解迷宮問問題，經(jīng)經(jīng)典算法法有深度度優(yōu)先搜搜索和廣廣度優(yōu)先先搜索兩兩種。深度優(yōu)先先搜索(DFSS)：從從入口出出發(fā)，順順著某一一方向向向前探索索，若能能走通，則則繼續(xù)往往前走；否則沿沿原路退退回(回溯)，換一一個方向向再繼續(xù)續(xù)探索直至所所有可能能的通路路都探索索到為止止。如果果恰好某某一步探探索到出出口，則則就找到到了從入入口到出出口的路路徑。為為了保證證在任何何位置上上都能沿沿原路退退回，防防止死循循環(huán)，需需要使用用堆棧來來保存大大量記錄錄。而要要求解迷迷宮最短短路徑，則則必須用用深度

7、優(yōu)優(yōu)先搜索索出所有有到達(dá)出出口的路路徑，通通過比較較得到最最短距離離的路徑徑這樣樣也必然然要求增增加數(shù)據(jù)據(jù)空間來來保存搜搜索過程程中當(dāng)前前最短路路徑增增加了空空間復(fù)雜雜度。廣度優(yōu)先先搜索(BFSS)：從從入口出出發(fā)，離離開入口口后依次次訪問與與當(dāng)前位位置鄰接接的單元元格(上下左左右方向向)，然后后分別從從這些相相鄰單元元格出發(fā)發(fā)依次訪訪問它們們的鄰接接格，并并使“先被訪訪問的單單元格的的鄰接格格先于后被訪訪問的單單元格的的鄰接格格”被訪問問，直至至訪問到到迷宮出出口，則則找到了了迷宮問問題的最最優(yōu)解，即即迷宮最最短路徑徑。該算算法的顯顯著特點點是“層層推推進(jìn)”，探索索點會隨隨著探索索的深入入急

8、劇增增加，相相應(yīng)地，需需要大量量的空間間用來保保存探索索過程的的記錄空間復(fù)復(fù)雜度大大。與此同時，上上述兩種種算法都都比較抽抽象復(fù)雜雜，編程程實現(xiàn)容容易出現(xiàn)現(xiàn)問題調(diào)試比比較困難難，因此此在本篇篇論文中中提出了了一種新新的容易易理解和和調(diào)試的的算法，該該算法復(fù)復(fù)雜度較較低，求求解較大大規(guī)模的的迷宮問問題也有有不俗的的表現(xiàn)。5.3蟻群群算法在在迷宮電電腦鼠中中的應(yīng)用用5.3.11 蟻群群算法的的基本知知識5.3.11.1 螞蟻的的基本習(xí)習(xí)性 螞螞蟻是最最古老的的社會昆昆蟲之一一，它的的個體結(jié)結(jié)構(gòu)和行行為雖簡簡單，但但是由這這些簡單單個體構(gòu)構(gòu)成的螞螞蟻群體體，卻表表現(xiàn)出高高度結(jié)構(gòu)構(gòu)化的社社會組織織.螞

9、蟻蟻王國儼儼然是一一個小小小“社會”。這里，有有專司產(chǎn)產(chǎn)卵的后后蟻;有有為數(shù)眾眾多的從從事覓食食打獵、興興建屋穴穴、撫育育后代的的工蟻;有負(fù)責(zé)責(zé)守衛(wèi)門門戶、對對敵作戰(zhàn)戰(zhàn)的兵蟻蟻;還有有專備后后蟻招婿婿納贅的雄蟻蟻等等.螞蟻是社會會性昆蟲蟲，組成成社會的的三要素素之一就就是社會會成員除除有組織織、有分分工之外外，還有有相互的的通訊和和信息傳傳遞。研究究表明，蟻蟻群有著著奇妙的的信息系系統(tǒng)，其中包包括視覺覺信號、聲聲音通訊訊和更為為獨特的的無聲語語育，即即包括化化學(xué)物質(zhì)質(zhì)不同的的組合、觸觸角信號號和身體體動作在在內(nèi)的多多個征集集系統(tǒng)，來來策動其其他個體體.螞蟻蟻特有的的控制自自身環(huán)境境的能力力，是

10、在在高級形形式的社社會性行行為及不不斷進(jìn)化化過程中中獲得的的。5.3.11.2螞螞蟻的覓覓食策略略覓食行為是是蟻群一一個重要要而有趣趣的行為為.據(jù)昆昆蟲學(xué)家家的觀察察和研究究，發(fā)現(xiàn)現(xiàn)螞蟻有有能力在在沒有任任何可見見提示下下找出從從蟻穴到到食物源源的最短短路徑，并并且能隨隨環(huán)境變變化適應(yīng)應(yīng)性地搜搜索新的的路徑，產(chǎn)產(chǎn)生新的的選擇.雖然單單個螞蟻蟻的行為為極其簡簡單，但但由大量量的螞蟻蟻個體組組成螞蟻蟻群體卻卻表現(xiàn)出出極其復(fù)復(fù)雜的行行為，能能夠完成成復(fù)雜的的任務(wù)。1生物學(xué)家和和仿生學(xué)學(xué)家經(jīng)過過大量的的細(xì)致觀觀察研究究發(fā)現(xiàn)，螞螞蟻在覓覓食走過過的路徑徑上釋放放一種媽媽蟻特有有的分泌泌物-信息激激素(P

11、Pherromoone).螞蟻蟻個體之之間正是是通過這這種信息息激素進(jìn)進(jìn)行信息息傳遞，從從而能相相互協(xié)作作，完成成復(fù)雜任任務(wù).在在一定范范圍內(nèi)螞螞蟻能夠夠察覺到到這種信信息激素素并指導(dǎo)導(dǎo)它的行行為，當(dāng)當(dāng)一些路路徑通過過的螞蟻蟻越多，則則留下的的信息激激素軌跡跡(trraill )也也就越多多，招致致后來更更多的螞螞蟻選擇擇該路徑徑的概率率也越高高，于是是越發(fā)增增加了該該路徑的的信息素素強度.這種選選擇過程程稱之為為螞蟻的的自催化化過程，形形成一種種正反饋饋機(jī)制，可可理解為為增強型型學(xué)習(xí)系系統(tǒng).螞螞蟻最終終可以發(fā)發(fā)現(xiàn)最短短路徑.自然界中蟻蟻群的自自組織行行為引起起了昆蟲蟲學(xué)家的的注意.Deuuu

12、u-bouurg等等通過“雙橋?qū)崒嶒灐睂ο伻喝旱囊捠呈承袨檫M(jìn)進(jìn)行了研研究如圖圖5.22所示，對對稱雙橋橋(兩座座橋的長長度相同同)A、B將蟻巢與食物源分開，螞蟻從蟻巢自由地向食物源移動.實驗結(jié)果顯示，在初始階段出現(xiàn)一段時間的震蕩(由于某些隨機(jī)因素，使通過某座橋上的螞蟻數(shù)急劇增多或減少)后，螞蟻趨向于走同一條路徑.在該實驗中，絕大部分螞蟻選擇A橋. 在實驗初期期，A, B兩兩座橋上上都沒有有外激素素存在，螞螞蟻將以以相同的的概率選選擇A、BB兩座橋橋，故此此時螞蟻蟻在兩座座橋上留留下的外外激素量量相等.經(jīng)過一一段時間間后，由由于隨機(jī)波波動致使使大部分分螞蟻選選擇A橋橋(也有有可能為為B橋)，因此

13、此更多的的外激素素將會留留在A橋橋上，致致使A橋橋?qū)髞韥淼奈浵佅佊懈蟠蟮奈?隨隨著時問問的推移移，A橋橋上的螞螞蟻數(shù)將將越來越越多,而而B橋上上正好相相反.SG.ooaaLLsy等等人給出出了上述實驗驗的概率模型型.首先先，假定定橋上殘殘留的外外激素量量與過去去一段時時間經(jīng)過過該橋的的螞蟻數(shù)數(shù)成正比比(這意意味著不不考慮外外激素蒸蒸發(fā)的情情況);其次，某某一時刻刻螞蟻按按橋上外外激素量量的多少少來選擇擇某座橋橋，即螞螞蟻選擇擇某座橋橋的概率率與經(jīng)過過該橋的的螞蟻數(shù)數(shù)成正比比.當(dāng)所所有m只螞蟻蟻都經(jīng)過過兩座橋橋以后，設(shè)設(shè)Am, Ann分別為為經(jīng)過AA橋和BB橋的螞螞蟻數(shù)(Am+ Ann

14、=m),則第m+ 1只螞蟻蟻選擇AA橋的概概率為:式(5.00)而選擇B橋橋的概率率為:其中參數(shù)hh和k用來匹匹配真實實實驗數(shù)數(shù)據(jù).第第(m+1)只螞蟻蟻首先按按式(55.0)計算選選擇概率率PA(m)，然然后生成成一個在在區(qū)間0,11上一一致分布布的隨機(jī)機(jī)數(shù)a，如果果aPA(m)，則則選擇AA橋，否否則選擇擇B橋. 圖5.2雙雙橋?qū)嶒烌灣軌蛘业降较伋埠秃褪澄镌丛粗g的的最短路路徑外，蟻蟻群還有有極強的的適應(yīng)環(huán)環(huán)境的能能力，如如圖5.3所示示，在蟻蟻群經(jīng)過過的路線線上突然然出現(xiàn)障障礙物時時，蟻群群能夠很很快重新新找到新新的最優(yōu)優(yōu)路徑。圖5.3 蟻群的的自適應(yīng)應(yīng)行為(a.)蟻蟻群在蟻蟻巢和食食

15、物源之之間的路路徑上移移動(b)路徑徑上出現(xiàn)現(xiàn)障礙物物(c)較短短路徑上上的外激激素以更更快的速速度增加加(d)所有有的螞蟻蟻都選擇擇較短的的路徑5.1.11.3 人工螞螞蟻與真真實螞蟻蟻的異同同比較相同點比比較蟻群算法是是從自然然中真實實螞蟻覓覓食的群群體行為為得到啟啟發(fā)而提提出的，其其很多觀觀點都來來源于真真實蟻群群，因此此算法中中所定義義的人工工螞蟻與與真實螞螞蟻存在在如下共共同點。都存在一一個群體體中個體體相互交交流通信信的機(jī)制制。人工工螞蟻與與真實螞螞蟻都存存在一種種改變當(dāng)當(dāng)前所處處環(huán)境的的機(jī)制：真實螞螞蟻在經(jīng)經(jīng)過的路路徑上留留下信息息素，人人工螞蟻蟻改變在在其所經(jīng)經(jīng)過路徑徑上存儲儲

16、的數(shù)字字信息，該該信息就就是算法法中所定定義的信信息量，它它記錄了了螞蟻當(dāng)當(dāng)前解和和歷史解解的性能能狀態(tài)，而而且可被被其他后后繼人工工螞蟻讀讀寫。都要完成成一個相相同的任任務(wù)。人人工螞蟻蟻與真實實螞蟻都都要完成成一個相相同的任任務(wù)，即即尋找一一條從源源節(jié)點（巢巢穴）到到目的節(jié)節(jié)點（食食物）的的最短路路徑。利用當(dāng)前前信息進(jìn)進(jìn)行路徑徑選擇的的隨機(jī)選選擇策略略。人工工螞蟻與與真實螞螞蟻從某某一個節(jié)節(jié)點到下下一個節(jié)節(jié)點的移移動是利利用概率率選擇策策略實現(xiàn)現(xiàn)的，概概率選擇擇策略只只利用當(dāng)當(dāng)前的信信息去預(yù)預(yù)測未來來的情況況，而不不能利用用未來的的信息，故故選擇策策略在時時間和空空間都是是局部的的。不同點比

17、比較在從真實蟻蟻群行為為獲得啟啟發(fā)而構(gòu)構(gòu)造蟻群群算法的的過程中中，人工工螞蟻還還具備了了真實螞螞蟻所不不具有的的一些特特性。人工螞蟻蟻存在于于一個離離散的空空間中，他他們的移移動式從從一個狀狀態(tài)到另另外一個個狀態(tài)的的轉(zhuǎn)換。人工螞蟻蟻具有記記憶起本本身過去去行為的的內(nèi)在狀狀態(tài)。人工螞蟻蟻存在于于一個與與時間無無關(guān)聯(lián)的的環(huán)境之之中。人工不是是完全盲盲目的，它它還受到到問題空空間特征征的啟發(fā)發(fā)。例如如有的問問題中人人工螞蟻蟻在產(chǎn)生生一個解解后改變變信息量量，而有有的問題題中人工工螞蟻每每作出一一步選擇擇就更改改信息量量，但無無論哪種種方法，信信息量的的更新并并不是隨隨機(jī)都可可以進(jìn)行行的。為了改善善算

18、法的的優(yōu)化效效率，人人工螞蟻蟻可增加加一些性性能，如如預(yù)測未未來、局局部優(yōu)化化、回退退等，這這些行為為在真實實螞蟻行行為中是是不存在在的。在在很多具具體的應(yīng)應(yīng)用中，人人工螞蟻蟻可在局局部優(yōu)化化過程中中相互交交換信息息，還有有一些蟻蟻群算法法中的人人工螞蟻蟻可實現(xiàn)現(xiàn)簡單的的預(yù)測。5.3.11.4 蟻群群算法的的基本特特點蟻群優(yōu)化算算法是從從自然界界中螞蟻蟻的覓食食行為受受到啟發(fā)發(fā)而提出出的一種種模擬進(jìn)進(jìn)化算法法。ACCO算法法可以看看成是一一種基于于解空間間參數(shù)化化概率分分布模型型的搜索索算法框框架，其其中解空空間參數(shù)化化概率模模型的參參數(shù)就是是信息素素，因而而這種模模型就是是信息素素模型.在基

19、于于模型的的搜索算算法框架架中，可可行解通通過在一一個解空空間參數(shù)數(shù)化概率率分布模模型上的的搜索產(chǎn)產(chǎn)生，此此模型的的參數(shù)用用以前產(chǎn)產(chǎn)生的解解來進(jìn)行行更新，使使得在新新模型上上的搜索索能集中中在高質(zhì)質(zhì)量的解解搜索空空間內(nèi).這種方方法的有有效性建建立在高高質(zhì)量的的解總是是包含好好的解構(gòu)構(gòu)成元素素的假設(shè)設(shè)前提下下.通過過學(xué)習(xí)這這些解構(gòu)構(gòu)成元素素對解的的質(zhì)量的的影響有有助于找找到一種種機(jī)制，并并通過解解構(gòu)成元元素的最最佳組合合來構(gòu)造造出高質(zhì)質(zhì)量的解。蟻群優(yōu)優(yōu)化算法法的主要要特點概概括如下下:采用分布布式控制制，不存存在中心心控制;每個個體體只能感感知局部部的信息息，不能能直接使使用全局局信息;個體可改

20、改變環(huán)境境，并通通過環(huán)境境來進(jìn)行行間接通通訊機(jī)制制;具有自組組織性，即即群體的的復(fù)雜行行為是通通過個體體的交互互過程中中突現(xiàn)出出來的智智能;是一類概概率型的的全局搜搜索方法法，這種種非確定定性使算算法能夠夠有更多多的機(jī)會會求得全全局最優(yōu)優(yōu)解;其優(yōu)化過過程不依依賴于優(yōu)優(yōu)化問題題本身的的嚴(yán)格數(shù)數(shù)學(xué)性質(zhì)質(zhì)，諸如如連續(xù)性性、可導(dǎo)導(dǎo)性及目目標(biāo)函數(shù)數(shù)和約束束函數(shù)的的精確數(shù)數(shù)學(xué)描述述;是一類基基于多主主體的智智能算法法，各主主體間通通過相互互協(xié)作來來更好地地適應(yīng)環(huán)環(huán)境;具有潛在在的并行行性，其其搜索過過程不是是從一點點出發(fā)，而而是同時時從多個個點同時時進(jìn)行.這種分分布式多多智能體體的協(xié)作作過程是是異步并并發(fā)

21、進(jìn)行行的，分分布并行行模式將將大大提提高整個個算法的的運行效效率和快快速反應(yīng)應(yīng)能力。5.3.22 基本本蟻群算算法的原原理及算算法實現(xiàn)現(xiàn)5.3.22.1 基本蟻蟻群算法法的機(jī)制制原理模擬螞蟻蟻群體覓覓食行為為的蟻群群算是作作為一種種新的計計算智能能模式引引入的,該算法法基于如如下基本本假設(shè)：螞蟻之間間通過信信息素和和環(huán)境進(jìn)進(jìn)行通信信.每只只螞蟻僅僅更具其其周圍的的局部環(huán)環(huán)境做出出反應(yīng),也只對對其周圍圍的局部部環(huán)境產(chǎn)產(chǎn)生影響響。螞蟻對環(huán)環(huán)境的反反應(yīng)由其其內(nèi)部模模式?jīng)Q定定.因為為螞蟻是是基因生生物,螞螞蟻的行行為實際際上是其其基因的的適應(yīng)性性表現(xiàn),即螞蟻蟻是反應(yīng)應(yīng)型適應(yīng)應(yīng)性主體。在個體水水平上,每

22、只螞螞蟻僅根根據(jù)環(huán)境境做出獨獨立選擇擇;在群群體水平平上,單單質(zhì)螞蟻蟻的行為為是隨機(jī)機(jī)的,但但蟻群可可通過自自組織過過程形成成高度有有序的群群體行為為。由上述假設(shè)設(shè)和分析析可見,基本蟻蟻群算法法的尋優(yōu)優(yōu)機(jī)制包包括兩個個基本段段:適應(yīng)應(yīng)階段和和協(xié)作階階段.在在適應(yīng)階階段,各各候選解解根據(jù)積積累的信信息不斷斷調(diào)整自自身結(jié)構(gòu)構(gòu),路徑徑上經(jīng)過過的螞蟻蟻越多,信息量量越大,則該路路徑越容容易被選選擇;時時間越長長,信息息量會越越小;在在協(xié)作階階段,候候選解之之間通過過信息交交流,以以期望產(chǎn)產(chǎn)生性能能更好的的解,類類似于學(xué)學(xué)習(xí)自動動機(jī)的學(xué)學(xué)習(xí)機(jī)制制。蟻群算法實實際上是是一類智智能多主主體系統(tǒng)統(tǒng),其自自組織

23、機(jī)機(jī)制使得得蟻群算算法不需需要對所所求問題題的每一一個方面面都有詳詳盡的認(rèn)認(rèn)識.自自組織本本質(zhì)上是是蟻群算算法機(jī)制制在沒有有外界作作用下使使系統(tǒng)熵熵增加的的動態(tài)過過程,體體現(xiàn)了從從無序到到有序的的動態(tài)演演化,其其邏輯結(jié)結(jié)構(gòu)如圖圖5.44所示。信息素更新管理組合優(yōu)化問題信息素更新管理組合優(yōu)化問題信息素,決策點問題表達(dá)個體B信息素個體A信息素蟻群活動規(guī)劃圖5.4 基本蟻蟻群算法法的邏輯輯結(jié)構(gòu)由圖5.44可見,先將具具體的組組合優(yōu)化化問題表表述成規(guī)規(guī)范的格格式,然然后利用用蟻群算算法在“探索(expplorratiion)”和“利用(expploiitattionn)”之間根根據(jù)信息息素這一一反饋載

24、載體確定定決策點點,同時時按照相相應(yīng)的信信息素根根新規(guī)則則對每只只螞蟻個個體的信信息素進(jìn)進(jìn)行增量量構(gòu)建,隨后從從整體角角度規(guī)劃劃出蟻群群活動的的行為方方向,周周而復(fù)始始,即可可求出組組合優(yōu)化化問題的的最優(yōu)解解。5.3.22.2基本蟻蟻群算法法的數(shù)學(xué)學(xué)模型設(shè)bi(tt)表示示t時刻刻位于元元素i的的螞蟻數(shù)數(shù)目,為為t時刻刻路徑上上的信息息量,nn表示TTSP規(guī)規(guī)模,mm為蟻群群螞蟻的的總數(shù)目目,則mm=;=是t時時刻各條條路徑上上信息量量相等,并設(shè)=connst,基本蟻蟻群算法法的尋優(yōu)優(yōu)是通過過有向圖圖g=(C,LL,)實現(xiàn)現(xiàn)的. 螞蟻在在運動過過程中,根據(jù)各各條路徑徑上的信信息量決決定其轉(zhuǎn)轉(zhuǎn)移

25、方向向.這里里用禁忌忌表來記記錄螞蟻蟻k當(dāng)前前所走過過的城市市,集合合隨著進(jìn)進(jìn)化過程程做動態(tài)態(tài)調(diào)整.在搜索索過程中中,螞蟻蟻根據(jù)各各路徑上上的信息息量及路路徑的啟啟發(fā)信息息來計算算狀態(tài)轉(zhuǎn)轉(zhuǎn)移概率率.表示示t時刻刻螞蟻由由元素(城市)i轉(zhuǎn)移到到元素(城市)j的狀態(tài)態(tài)轉(zhuǎn)移概概率 式(5.11)式中,表示示螞蟻下下一步允允許選擇擇的城市市;為信信息啟發(fā)發(fā)式因子子,表示示軌跡的的相對重重要性,反映了了螞蟻在在運動過過程中所所積累的的信息在在螞蟻運運動時所所起的作作用,其其值越大大,則改改螞蟻越越傾向于于選擇其其他螞蟻蟻經(jīng)過的的路徑,螞蟻之之間協(xié)作作性越強強;為期期望啟發(fā)發(fā)式因子子,表示示能見度度的相對

26、對重要性性,反映映了螞蟻蟻在運動動過程中中啟發(fā)信信息在螞螞蟻選擇擇路徑中中的受重重視的成成度,其其值越大大,則該該狀態(tài)轉(zhuǎn)轉(zhuǎn)移概率率越接近近于貪心心規(guī)則;為啟發(fā)發(fā)函數(shù),其表達(dá)達(dá)式如下下式(5.22)式中,表示示相鄰兩兩個城市市之間的的距離.對螞蟻蟻而言,越小,則越大大,也越越大.顯顯然,該該啟發(fā)函函數(shù)表示示螞蟻從從元素(城市)i轉(zhuǎn)移移到元素素(城市市)j的的期望程程度.為了避免免殘留信信息素過過多引起起殘留信信息淹沒沒啟發(fā)信信息,在在每只螞螞蟻走完完了一步步或者完完成對所所有n個個城市的的遍歷(也即一一個循環(huán)環(huán)結(jié)束)后,要要對殘留留信息進(jìn)進(jìn)行更新新處理.這種更更新策略略模仿了了人類大大腦記憶憶的

27、特點點,在新新信息不不斷存如如大腦的的同時,存儲在在大腦中中的舊信信息隨著著時間的的推移逐逐漸淡化化,甚至至忘記.由此,t+nn時刻路路徑上的的信息量量可按如如下規(guī)則則進(jìn)行調(diào)調(diào)整 式(55.3)式(5.44)式中,表示示信息素素?fù)]發(fā)系系數(shù),則則表示信信息素殘殘留因子子,為了了防止信信息的無無限積累累,的取取值范圍圍為:;表示本本次循環(huán)環(huán)中路徑徑(i, j)上的信信息素增增量,初初始時刻刻,)表示示第只螞螞蟻在本本次循環(huán)環(huán)中留在在路徑(i, j)上上的信息息量.根據(jù)信息息素更新新策略的的不同，Dorrigoo M提提出了三三種不同同的基本本蟻群算算法模型型,分別別稱之為為Antt-Cyyclee

28、模型、Antt-Quuanttityy模型及及Antt-Deensiity模模型,其其差別在在于求發(fā)發(fā)不同.在Antt-Cyyclee模型中中式(5.55)式中,Q表表示信息息素強度度,它在在一定程程度上影影響了算算法的收收斂速度度;表示示第只螞螞蟻在本本次循環(huán)環(huán)中所走走路徑的的總長度度.在Antt-Quuanttityy模型中中式(5.66)在Ant-Dennsitty模型型中式(5.77)區(qū)別:式(5.66)和式式(5.7)中中利用的的是局部部信息,即螞蟻蟻走完一一步后更更新路徑徑上的信信息素;而式(5.55)中利利用的是是整體信信息,即即螞蟻完完成了一一個循環(huán)環(huán)后更新新所有路路徑上的的信

29、息素素,在求求解TSSP時性性能較好好,因此此通常采采用式(5.55)作為為蟻群算算法的基基本模型型.此外外，在DDoriigo MM等人的的論文中中還對蟻蟻群算法法提出了了一些討討論，其其中包括括不同的的蟻群初初始分布布對求解解的影響響等，還還提出了了所謂的的精英策策略(eelittistt sttrattegyy)，以以強化精精英螞蟻蟻(發(fā)現(xiàn)現(xiàn)迄今最最好路徑徑的螞蟻蟻)的影影響.結(jié)結(jié)果發(fā)現(xiàn)現(xiàn)，對精精英螞蟻蟻數(shù)而言言有一個個最優(yōu)的的范圍:低于此范圍圍，增加加精英螞螞蟻數(shù)可可較早地地發(fā)現(xiàn)更更好的路路徑，高高于此范圍圍，精英英螞蟻會會在搜索索早期迫迫使尋優(yōu)過程程始終在在次優(yōu)解解附近，導(dǎo)導(dǎo)致性能能

30、變差。5.3.22.2 基基本蟻群群算法的的實現(xiàn)步步驟及程程序結(jié)構(gòu)構(gòu)流程以TSP為為例,基基本蟻群群算法的的具體實實現(xiàn)步驟驟如下:參數(shù)初始始化.令令時間tt=0和和循環(huán)次次數(shù)=00,設(shè)置置最大循循環(huán)次數(shù)數(shù),將m只只螞蟻置置于個元元素(城城市)上上,令有有向圖每每條邊的的初始化化信息量量,其中中表示常常數(shù),且且初始化化時刻。循環(huán)次數(shù)數(shù)=+1.螞蟻的禁禁忌表索索引號=1螞蟻數(shù)目目=+1.螞蟻個體體根據(jù)狀狀態(tài)轉(zhuǎn)換換概率公公式計算算的概率率選擇元元素(城城市)jj并前進(jìn)進(jìn),.修改禁忌忌表指針針,即選選擇好之之后將螞螞蟻移動動到新的的元素(城市),并把把該元素素(城市市)移動動到該螞螞蟻個體體的禁忌忌表

31、中.若集合CC中的元元素(城城市)未未遍歷完完,即=0) aand(i+ddiii=00) annd(jj+djji 00。迷宮可行行解的構(gòu)構(gòu)造在利用蟻群群算法求求解迷宮宮最短路路徑問題題時，為為了使每每只螞蟻蟻能以盡盡可能高高的概率率生成可可行解，本本文采用用兩組數(shù)數(shù)量相等等的蟻群群分別從從迷宮的的起點和和終點同同時出發(fā)發(fā)，每只只螞蟻按按公式(2)確確定的概概率在迷迷宮中漫漫游。為為盡量避避免生成成無效路路徑，為為螞蟻分分配一張張禁忌表表。該表表記錄螞螞蟻當(dāng)前前走過的的點集，以以避免選選擇已經(jīng)經(jīng)走過的的點。則則對任意意一只螞螞蟻，在在移動過過程中可可以定義義如下的的生命周周期:螞蟻走走進(jìn)死角角，除非非沿原路路返回一一步或多多步，不