基于蟻群算法路由選擇可視化動態(tài)模擬——畢業(yè)論文

1、<p>　　J I A N G S U U N I V E R S I T Y</p><p>　　本 科 畢 業(yè) 論 文</p><p>　　基于蟻群算法路由選擇可視化動態(tài)模擬</p><p>　　Visul Simulation of Routing Selsect based on Ant Colony Algorithms

2、 </p><p>　　學(xué)院名稱： 計(jì)算機(jī)學(xué)院 </p><p>　　專業(yè)班級： </p><p>　　學(xué)生姓名： </p><p>　　指導(dǎo)教師姓名： <

3、;/p><p>　　指導(dǎo)教師職稱： </p><p><b>　　年 月</b></p><p><b>　　摘 要</b></p><p>　　路由選擇是一種基于網(wǎng)絡(luò)層的協(xié)議，而所有流行的網(wǎng)絡(luò)層路由選擇協(xié)議都是基于以下兩種典型的分布式算法之一：距離

4、向量路由算法和鏈路狀態(tài)路由算法。組合優(yōu)化問題是人們在工程技術(shù)、科學(xué)研究和經(jīng)濟(jì)管理等眾多領(lǐng)域經(jīng)常遇到的問題，其中許多問題如旅行商問題、0-1背包問題、圖著色問題、裝箱問題等，都被證明為NP-困難問題。用確定性的優(yōu)化算法求NP完全問題的最優(yōu)解，其計(jì)算時(shí)間使人難以忍受或因問題的高難度而使其計(jì)算時(shí)間隨問題規(guī)模的增加以指數(shù)速度延長。用近似算法如啟發(fā)式算法求解得到的近似解不能保證其可行性和最優(yōu)性，甚至無法知道所得解同最優(yōu)解的近似程度。因而在求解大規(guī)

5、模組合優(yōu)化問題時(shí)，傳統(tǒng)的優(yōu)化算法就顯得無能為力了。在過去的10多年，蟻群算法（ACO）的研究和應(yīng)用取得了很大的進(jìn)展，大量結(jié)果證明了算法的有效性和在某些領(lǐng)域的優(yōu)勢。蟻群算法是一種新型的模擬進(jìn)化算法, 研究表明該算法具有并行性, 魯棒性等優(yōu)良性質(zhì)。本文闡述了蟻群算法的原理,詳細(xì)的說明了螞蟻算法中各個(gè)功能模塊，并介紹了該算法在理論和實(shí)際問題中的應(yīng)用, 并對其前景進(jìn)行了展望。</p><p>　　關(guān)鍵詞: 蟻群算法 信

6、息素 仿真</p><p><b>　　Abstract</b></p><p>　　Whether it is one based on Internet agreement for route not to choose, and all Internet route that prevail choose agreement on the basis of

7、the following two typical distributed algorithm one of. Is it optimize problem people in engineering , scientific research , economic management numerous problem that field run into often to make up, among them a lot of

8、question if knapsack issue , issue of businessman in the travel industry and of TSP , pursue painted question , case issue ,etc., proved as</p><p>　　Keyword: Ant Colony Optimization algorithm Pheromone

9、Simulation</p><p><b>　　目 錄</b></p><p><b>　　前言1</b></p><p><b>　　第1章 緒論2</b></p><p>　　1.1 路由選擇的意義2</p><p>　　1.1.1 路由

10、選擇技術(shù)的組成2</p><p>　　1.1.2 路由算法設(shè)計(jì)目標(biāo)3</p><p>　　1.1.3 路由算法的分類4</p><p>　　1.1.4 路由算法衡量的標(biāo)準(zhǔn)4</p><p>　　1.2.目前常用的路由算法5</p><p>　　1.2.1 最短路徑算法5</p><p&

11、gt;　　第2章 蟻群算法的基本原理7</p><p>　　2.1螞蟻算法的產(chǎn)生7</p><p>　　2.2 螞蟻算法的算法思想7</p><p>　　2.3蟻群算法原理8</p><p>　　2.4 蟻群算法的應(yīng)用12</p><p>　　2.4.1螞蟻算法在電信網(wǎng)動態(tài)路由優(yōu)化中的應(yīng)用12</p

12、><p>　　2.4.2螞蟻算法在組合優(yōu)化中的應(yīng)用12</p><p>　　2.5 螞蟻算法的未來發(fā)展12</p><p>　　2.5.1 MMAS ( Max2Min ant system) 最大最小蟻群算法12</p><p>　　2.5.2 具有變異特征的蟻群算法12</p><p>　　2.5.3 自適應(yīng)

13、蟻群算法13</p><p>　　2.5.4大規(guī)模集成電路綜合布線13</p><p>　　2.5.5電信網(wǎng)絡(luò)路由13</p><p>　　第3章 開發(fā)工具14</p><p>　　3.1軟件環(huán)境14</p><p>　　3.2其他資料14</p><p>　　3.3 Java 的

14、簡單介紹14</p><p>　　3.3.1 網(wǎng)絡(luò)時(shí)代的需要14</p><p>　　3.3.2 Internet的普及14</p><p>　　3.3.3 跨平臺可移植性的要求14</p><p>　　3.4 Java 的主要特點(diǎn)15</p><p>　　3.4.1 簡單性15</p>&l

15、t;p>　　3.4.2 安全性15</p><p>　　3.4.3 面向?qū)ο笮?5</p><p>　　3.4.4 可靠性16</p><p>　　第4章 具體的功能結(jié)構(gòu)17</p><p>　　4.1 系統(tǒng)的結(jié)構(gòu)總框圖17</p><p>　　4.2 螞蟻算法的主要步驟18</p>&

16、lt;p>　　第5章 系統(tǒng)的實(shí)現(xiàn)25</p><p>　　5.1蟻群算法的實(shí)現(xiàn)結(jié)果25</p><p>　　第6章算法的不足和改進(jìn)29</p><p>　　6.1 算法的不足29</p><p>　　6.2 算法的改進(jìn)30</p><p>　　6.2.1信息素更新參數(shù)微調(diào)30</p>

17、<p>　　6.2.2 全局調(diào)整31</p><p>　　6.2.3 信息素值微調(diào)31</p><p>　　6.3一種先進(jìn)的螞蟻算法——智能螞蟻算法31</p><p>　　6.3.1 取消外激素31</p><p>　　6.3.2 自動調(diào)節(jié)選擇最優(yōu)路徑的比例32</p><p>　　5.6.3　

18、選擇目標(biāo)城市的依據(jù)32</p><p>　　6.3.4引入擾動32</p><p>　　6.4 螞蟻算法的展望33</p><p><b>　　結(jié)束語34</b></p><p><b>　　參考文獻(xiàn)35</b></p><p><b>　　前言</

19、b></p><p>　　蟻群算法是一種新生的算法，具有很強(qiáng)的通用性。從提出到現(xiàn)在，僅短短10余年的時(shí)間，但是在離散型組合優(yōu)化問題中。表現(xiàn)很突出，所以一起人們的關(guān)注。目前蟻群算法的研究者主要集中在比利時(shí)、意大利、德國等國家，美國和日本在近幾年也開始了對蟻群算法的研究。國內(nèi)的研究開始于1998年末。主要在上海、北京、東北少數(shù)幾個(gè)學(xué)校和研究所開展了此項(xiàng)工作，主要圍繞TSP及相關(guān)問題的實(shí)驗(yàn)仿真，少數(shù)涉及通信網(wǎng)絡(luò)的

20、路由選擇、負(fù)載平衡、電力系統(tǒng)的故障檢測以及蟻群算法在連續(xù)系統(tǒng)應(yīng)用，如函數(shù)逼近等方面應(yīng)用的嘗試。在國外，蟻群算法已經(jīng)在集成電路布線、網(wǎng)絡(luò)路由選擇、機(jī)器人線路規(guī)劃等方面得到了應(yīng)用。自1998年，第一屆螞蟻優(yōu)化國際研討會召開以來，已經(jīng)是第三屆了，大大推動了蟻群算法的發(fā)展。蟻群算法已經(jīng)引起越來越多的關(guān)注，盡管還缺乏完善的理論分析，對它的有效性也沒有出嚴(yán)格的數(shù)學(xué)解釋，但是回顧模糊控制的發(fā)展歷史，理論的不完善并不妨礙應(yīng)用，有時(shí)應(yīng)用是超前于理論的，并

21、推動理論的研究。我們相信蟻群算法必將得到廣泛的應(yīng)用。</p><p><b>　　第1章 緒論</b></p><p>　　1.1 路由選擇的意義 </p><p>　　路由(Route) 的概念出現(xiàn)于本世紀(jì)70 年代,當(dāng)時(shí)的網(wǎng)絡(luò)結(jié)構(gòu)較簡單,因此直至80 年代中期出現(xiàn)了大規(guī)模的網(wǎng)絡(luò)結(jié)構(gòu)后,路由技術(shù)才得到了廣泛的應(yīng)用。在ISO/ OSI 體

22、系結(jié)構(gòu)中,路由技術(shù)是第三層(網(wǎng)絡(luò)層) 的功能,路由選擇(Routing)是分組交換系統(tǒng)中的一個(gè)重要概念,是指在互聯(lián)網(wǎng)絡(luò)中選擇將信包(Package) 從信源機(jī)(Source Host) 傳往信宿機(jī)(Destination Host) 的傳輸路徑的過程。實(shí)際的網(wǎng)絡(luò)協(xié)議(如IP協(xié)議) ,其本身并不涉及具體的路由選擇細(xì)節(jié),它只說明路由選擇的一般原理和規(guī)則,具體的路由選擇是指路由表的建立與刷新機(jī)制,由一組獨(dú)立的路由選擇協(xié)議(RoutingPro

23、tocol) 描述。路由選擇的過程是由路由算法來完成的,路由算法可以運(yùn)行在網(wǎng)絡(luò)主機(jī)上,也可運(yùn)行在專用的路由設(shè)備上,如路由器是一種網(wǎng)絡(luò)互聯(lián)設(shè)備,其主要功能就是進(jìn)行路由選擇。</p><p>　　1.1.1 路由選擇技術(shù)的組成</p><p>　　路由選擇技術(shù)涉及兩方面內(nèi)容:最佳路徑的選擇及信包在網(wǎng)絡(luò)上的傳遞。信包的傳遞也可稱為交換(Switching) , 交換過程相對簡單,而路徑的選擇過程

24、比較復(fù)雜。</p><p><b>　　最佳路徑選擇</b></p><p>　　最佳路徑依賴于不同的衡量標(biāo)準(zhǔn),例如可使用路徑長度作為衡量標(biāo)準(zhǔn)。在確定最佳路徑的路由算法中,路由表(Routing Tables) 是一個(gè)重要的數(shù)據(jù)結(jié)構(gòu),其中包含了網(wǎng)絡(luò)的路由信息,算法通過建立和維護(hù)路由表進(jìn)行最佳路徑的確定。路由算法根據(jù)算法要求在路由表中填寫各種路由信息,其中最基本的是目標(biāo)

25、/ 驛站(Hop) 信息(見表1) 。這一組信息告訴路由器,在信包發(fā)往信宿機(jī)的過程中,最佳選擇是將信息轉(zhuǎn)發(fā)至下一驛站(Next Hop) 所代表的節(jié)點(diǎn)。當(dāng)路由器接收到一個(gè)輸入信息時(shí),首先檢查信包的目標(biāo)地址,然后嘗試找出與此目標(biāo)地址相匹配的下一驛站,若匹配成功則進(jìn)行信包轉(zhuǎn)發(fā),否則放棄該信包。除了目標(biāo)/ 驛站信息外,根據(jù)不同的路由算法,路由表中還包含有其它內(nèi)容,例如最佳路徑的衡量標(biāo)準(zhǔn)等信息。在路由器之間傳輸?shù)母鞣N信息中,有關(guān)路由選擇的信息稱

26、為路由刷新報(bào)文(Routing Update Message) 。路由刷新報(bào)文通常是全部或部分路由表內(nèi)容。通過對所有路由信息的分析,路由器可建立一個(gè)詳細(xì)的網(wǎng)絡(luò)拓?fù)鋱D。例如,用于鏈接-狀態(tài)路由算法的鏈接- 狀態(tài)廣播報(bào)文通知其它路由器有關(guān)自身的鏈接狀態(tài),通過這些信息,路由器可</p><p>　　1.1.2 路由算法設(shè)計(jì)目標(biāo)</p><p>　　路由算法往往具有下列一種或多種目標(biāo): 最佳性、簡

27、單性、穩(wěn)定性、快速收斂性及適應(yīng)性等目標(biāo)。</p><p><b>　　(1) 最佳性目標(biāo)</b></p><p>　　要求算法具有尋找最佳路徑的能力,最佳路徑依賴于算法所采用的衡量標(biāo)準(zhǔn)。通常路由選擇協(xié)議嚴(yán)格定義了計(jì)算時(shí)所采用的衡量標(biāo)準(zhǔn)。</p><p><b>　　(2) 簡單性目標(biāo)</b></p><

28、p>　　要求算法盡可能簡單,即用盡可能小的軟件開銷提供有效的功能。當(dāng)算法運(yùn)行在低檔設(shè)備上時(shí)效率尤為重要。</p><p><b>　　(3) 穩(wěn)定性目標(biāo)</b></p><p>　　算法必須是穩(wěn)定可靠的。在遇到特殊情況(如硬件故障、過載、誤操作等) 時(shí),算法能夠穩(wěn)定地運(yùn)行。由于路由器位于互聯(lián)網(wǎng)絡(luò)的連接點(diǎn)上, 有著相當(dāng)重要的地位, 若算法不穩(wěn)定將造成嚴(yán)重的后果。優(yōu)

29、秀的路由算法經(jīng)得起時(shí)間的檢驗(yàn)并且在任何情況下都能穩(wěn)定地工作。</p><p>　　(4) 快速收斂性目標(biāo)</p><p>　　路由算法要求能夠快速收斂。這里所指的收斂是指最佳路徑能迅速被網(wǎng)上所有路由器所接受。若發(fā)生網(wǎng)絡(luò)故障導(dǎo)致線路斷開或恢復(fù), 相應(yīng)路由器向網(wǎng)絡(luò)發(fā)出路由刷新報(bào)文,促使其它路由器重新計(jì)算最佳路徑,更新路由表,同時(shí)又向網(wǎng)絡(luò)發(fā)送刷新報(bào)文,直至所有路由器都相互認(rèn)可這些最佳路徑。收斂慢

30、的算法將導(dǎo)致路由環(huán)問題及網(wǎng)絡(luò)損耗。</p><p><b>　　(5) 適應(yīng)性目標(biāo)</b></p><p>　　路由算法必須具有較強(qiáng)的適應(yīng)能力,即能夠迅速準(zhǔn)確地適應(yīng)各種網(wǎng)絡(luò)環(huán)境的變化。例如,如果發(fā)現(xiàn)某一網(wǎng)段出現(xiàn)故障,能迅速為所有經(jīng)過該網(wǎng)段的路徑選擇另一條最佳路徑。另外,還必須能適應(yīng)網(wǎng)絡(luò)帶寬、路由器隊(duì)列大小、網(wǎng)絡(luò)延遲或其它變化。</p><p>

31、　　1.1.3 路由算法的分類</p><p>　　(1) 靜態(tài)或動態(tài)路由算法</p><p>　　靜態(tài)路由是由管理員在路由使用前建立的,只有管理員才能對路由表進(jìn)行修改。靜態(tài)路由算法的設(shè)計(jì)簡單,在可預(yù)知網(wǎng)絡(luò)的通信量且網(wǎng)絡(luò)結(jié)構(gòu)簡單的情況下使用靜態(tài)路由算法。靜態(tài)路由算法不能適應(yīng)網(wǎng)絡(luò)情況的變化,因此不適用于目前的大規(guī)模及變化頻繁的網(wǎng)絡(luò)結(jié)構(gòu), 90 年代占主導(dǎo)地位的路由算法是動態(tài)路由算法。動態(tài)路由

32、算法通過分析路由刷新報(bào)文,能夠進(jìn)行實(shí)時(shí)調(diào)整以適應(yīng)網(wǎng)絡(luò)的變化。當(dāng)網(wǎng)絡(luò)發(fā)生變化時(shí),根據(jù)路由刷新信息, 路由軟件重新計(jì)算最佳路徑并將變化信息向網(wǎng)絡(luò)上發(fā)送。這些信息在網(wǎng)絡(luò)上使得網(wǎng)絡(luò)上的其它路由器也相應(yīng)運(yùn)行路由算法刷新其路由表。</p><p>　　(2) 單重路徑或多重路徑算法</p><p>　　單重路徑算法對同一信宿機(jī)提供一條最佳路徑,多重路徑算法對同一信宿機(jī)提供多條路徑以供選擇,允許在復(fù)雜的

33、線路上進(jìn)行多重通信。多重路徑算法不僅提高了通信量而且提高了通信的可靠性。</p><p>　　(3) 單層或多層結(jié)構(gòu)算法</p><p>　　單層結(jié)構(gòu)中,網(wǎng)絡(luò)上所有的路由器是對等的,而在多層結(jié)構(gòu)中,存在主干路由器與分支路由器。信包從分支路由器轉(zhuǎn)發(fā)至主干路由器,再傳送至信宿機(jī)所在區(qū)域的主干路由器,再從這一位置通過一個(gè)或多個(gè)分支路由器最終到達(dá)信宿機(jī)。</p><p>　

34、　路由系統(tǒng)將一組邏輯節(jié)點(diǎn)稱為域或自治系統(tǒng)。在層次結(jié)構(gòu)中,有些路由器只能在自治系統(tǒng)內(nèi)相互通信,位于自治系統(tǒng)頂層的路由器可與其它自治系統(tǒng)的頂層路由器進(jìn)行通信。層次結(jié)構(gòu)的主要優(yōu)點(diǎn)在于模仿了公司的組織結(jié)構(gòu),因?yàn)榫W(wǎng)絡(luò)的大部分通信量存在于分公司內(nèi)部(自治系統(tǒng)) ,自治系統(tǒng)內(nèi)的路由器只需清楚系統(tǒng)內(nèi)其它路由器的情況。因此系統(tǒng)內(nèi)的路由算法可進(jìn)行簡化,相應(yīng)減少了路由刷新時(shí)產(chǎn)生的通信量。</p><p>　　(4) 向量- 距離算法或

35、鏈接- 狀態(tài)算法</p><p>　　這兩種算法是兩類基本的自動路徑廣播算法,在此基礎(chǔ)上相應(yīng)有多種協(xié)議,典型的有GGP 和SPF 協(xié)議。</p><p>　　1.1.4 路由算法衡量的標(biāo)準(zhǔn)</p><p>　　路由信息表中包含了交換所需的如何確定最佳路徑的要求, 即確定最佳路徑的標(biāo)準(zhǔn), 路由算法根據(jù)這些標(biāo)準(zhǔn)進(jìn)行計(jì)算。復(fù)雜的算法往往綜合多種標(biāo)準(zhǔn),常用的衡量標(biāo)準(zhǔn)有:&

36、lt;/p><p><b>　　(1) 路徑長度</b></p><p>　　路徑長度是使用最普遍的標(biāo)準(zhǔn),一些協(xié)議許可網(wǎng)絡(luò)管理員對網(wǎng)絡(luò)的線路賦予一定的代價(jià)值,在此類情況下,最佳路徑就是所經(jīng)過的每條線路的代價(jià)總和。有些協(xié)議定義驛站數(shù)量為標(biāo)準(zhǔn),即路徑上所經(jīng)過的網(wǎng)絡(luò)設(shè)備(如路由器) 的數(shù)量。</p><p><b>　　(2) 可靠性</

37、b></p><p>　　在路由算法中, 可靠性是指每個(gè)網(wǎng)絡(luò)連接的可靠性, 通常用每位的錯誤率表示。有些網(wǎng)絡(luò)連接可能經(jīng)常發(fā)生故障,而發(fā)生故障時(shí),有些網(wǎng)絡(luò)連接能很快或很容易恢復(fù)?？煽啃钥赏ㄟ^對網(wǎng)絡(luò)連接賦予相應(yīng)的數(shù)值來確定。</p><p><b>　　(3) 延遲</b></p><p>　　延遲是指將信包從信源機(jī)發(fā)送到信宿機(jī)所經(jīng)過的時(shí)間,

38、延遲受很多因素影響, 例如: 網(wǎng)絡(luò)帶寬、路由器端口隊(duì)列數(shù)量、網(wǎng)絡(luò)負(fù)荷以及實(shí)際傳輸?shù)木嚯x等。</p><p><b>　　(4) 帶寬</b></p><p>　　帶寬是指網(wǎng)絡(luò)連接的通信能力,雖然帶寬代表了網(wǎng)絡(luò)連接所能達(dá)到的最高的通信速率,但往往寬帶連接意味著網(wǎng)絡(luò)更繁忙, 傳送一個(gè)信包所需要實(shí)際時(shí)間可能更長, 因此寬帶連接并不一定能提供更好的路由能力。</p>

39、;<p><b>　　(5) 負(fù)載</b></p><p>　　負(fù)載是指網(wǎng)絡(luò)設(shè)備(如路由器) 的繁忙程度。負(fù)載有多種計(jì)算方式, 如CPU利用率、每秒處理的信包數(shù)量等, 對這些參數(shù)的監(jiān)控過程本身也是網(wǎng)絡(luò)的一種負(fù)載。</p><p>　　1.2.目前常用的路由算法</p><p>　　1.2.1 最短路徑算法</p>&

40、lt;p>　　尋找兩頂點(diǎn)間的最短路徑的算法很多目前公認(rèn)最好的算法是Dijkstra在1959 年提出的它不僅求出從始點(diǎn)到終點(diǎn)的最短路徑而且最后所得到的實(shí)際上是始點(diǎn)到各頂點(diǎn)的最短路徑對Dijkstra 算法進(jìn)行補(bǔ)充得出的步驟如下：</p><p>　　第一步：初始化V={1 2 N} S = {F} D [I ] = L[F I ] Y[ I ] = F 其中I=1，2 ，…N 。F 表示路徑的始點(diǎn)I 表示某

41、一頂點(diǎn)N 表示網(wǎng)絡(luò)中所有頂點(diǎn)的數(shù)目V 是所有頂點(diǎn)的集合L[F I]表示從F 點(diǎn)到I 點(diǎn)的距離S 是頂點(diǎn)的集合D 為N 個(gè)元素的數(shù)組用來存儲頂點(diǎn)F 到其它頂點(diǎn)的最短距離Y 為N 個(gè)元素的數(shù)組用來存儲最短路徑中在頂點(diǎn)I 之前經(jīng)過的最近頂點(diǎn)</p><p>　　第二步：從V S 集合中找一個(gè)頂點(diǎn)T 使得D[T] 是最小值并將T 加入到S 集合中如果V S 是空集合則結(jié)束運(yùn)算</p><p>　　

42、第三步：調(diào)整Y D 數(shù)組中的值在V S 集合中對于頂點(diǎn)T 的鄰接各頂點(diǎn)I 如果D[I ]> D[T]+L[I T] 那么令Y[I]=T D[I] = D[T]+L[I T]</p><p><b>　　繼續(xù)執(zhí)行第二步</b></p><p><b>　　最短路徑算法的不足</b></p><p>　　Dijkstra

43、 算法所采用的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)方法總體上說是比較復(fù)雜的其缺點(diǎn)也是明顯的難以應(yīng)付公交線路的網(wǎng)絡(luò)拓?fù)渲械膹?fù)雜性主要表現(xiàn)如下：</p><p>　　（1） 數(shù)據(jù)結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)在教學(xué)和計(jì)算領(lǐng)域被抽象為圖所以其基礎(chǔ)是圖的存儲表示一般而言無向圖可以用鄰接矩陣和十字鏈表表示公交線路網(wǎng)絡(luò)拓?fù)浜茈y用現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)加以完整的表示如果采用現(xiàn)有的最短路徑算法分析其建立的公交線路網(wǎng)絡(luò)圖的數(shù)據(jù)</p><p><

44、b>　　結(jié)構(gòu)模型將非常復(fù)雜</b></p><p>　?。?） 算法時(shí)間長以Dijkstra 算法來計(jì)算公交路線最短路徑在大數(shù)據(jù)量的情況下計(jì)算速度會慢得讓人難以忍受系統(tǒng)設(shè)計(jì)中要求公交轉(zhuǎn)車的查詢必須在較短的時(shí)間內(nèi)完成Dijkstra 算法難以實(shí)現(xiàn)</p><p>　?。?） Dijkstra 最短路徑算法對于網(wǎng)絡(luò)拓?fù)鋱D要求簡捷對于復(fù)雜的廣州公交網(wǎng)絡(luò)拓?fù)浔仨殞ζ溥M(jìn)行復(fù)雜的抽象

45、合并成簡捷的網(wǎng)絡(luò)拓?fù)鋱D這無疑增加了程序的復(fù)雜性</p><p>　　而蟻群算法是一種新型的模擬進(jìn)化算法，自從1991 年M. Dorigo 等人首先提出蟻群算法以來,有許多研究人員對該算法進(jìn)行研究,并成功地應(yīng)用于解決復(fù)雜組合優(yōu)化問題. 在研究該算法的過程中,研究人員提出一些改進(jìn)的算法,研究表明該算法具有很好的通用性和魯棒性,在離散的組合優(yōu)化問題中實(shí)驗(yàn),取得了良好的效果。下章節(jié)就著重介紹一下螞蟻算法。</p&

46、gt;<p>　　第2章 蟻群算法的基本原理</p><p>　　2.1螞蟻算法的產(chǎn)生</p><p>　　螞蟻是自然界中常見的一種生物，人們對螞蟻的關(guān)注大都是因?yàn)椤拔浵伆峒?，天要下雨”之類的民諺。然而隨著近代仿生學(xué)的發(fā)展，這種似乎微不足道的小東西越來越多地受到學(xué)者們的關(guān)注。1991年M·Dorigo等人首先提出了蟻群算法（Ant Colony Algorithm

47、s）。人們開始了對蟻群的研究：相對弱小，功能并不強(qiáng)大的個(gè)體是如何完成復(fù)雜的工作的（如尋找到食物的最佳路徑并返回等）。在此基礎(chǔ)上一種很好的優(yōu)化算法逐漸發(fā)展起來。</p><p>　　2.2 螞蟻算法的算法思想</p><p>　　蟻群算法是受到對真實(shí)的蟻群行為的研究的啟發(fā)而提出的.為了說明人工蟻群系統(tǒng)的原理,先從蟻群搜索食物的過程談起.象螞蟻、蜜蜂、飛蛾等群居昆蟲,雖然單個(gè)昆蟲的行為極其簡單

48、,但由單個(gè)簡單的個(gè)體所組成的群體卻表現(xiàn)出極其復(fù)雜的行為,原因是什么呢?仿生學(xué)家經(jīng)過大量細(xì)致觀察研究發(fā)現(xiàn),螞蟻個(gè)體之間是通過一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞的.螞蟻在運(yùn)動過程中,能夠在它所經(jīng)過的路徑上留下該種物質(zhì),而且螞蟻在運(yùn)動過程中能夠感知這種物質(zhì),并以此指導(dǎo)自己的運(yùn)動方向,因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象:某一路徑上走過的螞蟻越多,則后來者選擇該路徑的概率就越大.螞蟻個(gè)體之間就是通

49、過這種信息的交流達(dá)到搜索食物的目的。螞蟻個(gè)體之間的信息交換是一個(gè)正反饋過程。</p><p>　　說了這么多，螞蟻究竟是怎么找到食物的呢？    在沒有螞蟻找到食物的時(shí)候，環(huán)境沒有有用的信息素，那么螞蟻為什么會相對有效的找到食物呢？這要?dú)w功于螞蟻的移動規(guī)則，尤其是在沒有信息素時(shí)候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個(gè)前方是隨機(jī)固定的一個(gè)方向

50、），而不是原地?zé)o謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動下去，而是有一個(gè)隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時(shí)候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個(gè)方向正確，而其他方向則不對。這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。  

51、;  當(dāng)然，在有一只螞蟻找到了食物的時(shí)候，其他螞蟻會沿著信息素很快找到食物的。</p><p>　　螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說是計(jì)算機(jī)時(shí)鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞蟻多，這也無關(guān)緊要）。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會馬上返回來，

52、這樣，短的路螞蟻來回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實(shí)際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)

53、新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會被吸引過來。</p><p><b>　　2.3蟻群算法原理</b></p><p>　　蟻群算法是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法。它是從對蟻群行為的研究中產(chǎn)生的。正如M·Dorigo等人在關(guān)于蟻群算法的第1 篇文章中指出的：蟻群中的螞蟻以“外激素”（Stigmergy）為媒

54、介的間接的異步的聯(lián)系方式是蟻群算法的最大的特點(diǎn)。螞蟻在行動（尋找食物或者尋找回巢的路徑）中，會在它們經(jīng)過的地方留下一些化學(xué)物質(zhì)（我們稱之為“外激素”）。這些物質(zhì)能被同一蟻群中后來的螞蟻感受到，并作為一種信號影響后到者的行動（具體表現(xiàn)在后到的螞蟻選擇有這些物質(zhì)的路徑的可能性，比選擇沒有這些物質(zhì)的路徑的可能性大得多），而后到者留下的外激素會對原有的外激素進(jìn)行加強(qiáng)，并如此循環(huán)下去。這樣，經(jīng)過螞蟻越多的路徑，在后到螞蟻的選擇中被選中的可能性就越

55、大（因?yàn)闅埩舻耐饧に貪舛容^大的緣故）。由于在一定的時(shí)間內(nèi)，越短的路徑會被越多的螞蟻訪問，因而積累的外激素也就越多，在下一個(gè)時(shí)間內(nèi)被其他的螞蟻選中的可能性也就越大。這個(gè)過程會一直持續(xù)到所有的螞蟻都走最短的那一條路徑為止。（如圖）</p><p>　　圖1中有一條螞蟻經(jīng)過的路徑，我們假設(shè)a點(diǎn)是食物，而e點(diǎn)是螞蟻的巢穴，如圖1 a）所示。在某一個(gè)時(shí)刻忽然有一個(gè)障礙物出現(xiàn)在螞蟻經(jīng)過的路徑中，原有的路徑被切斷，從a點(diǎn)到e點(diǎn)

56、的螞蟻就必須在b點(diǎn)決定應(yīng)該往左還是往右走。而從a點(diǎn)到e點(diǎn)的螞蟻也必須在d點(diǎn)決定選擇哪條路徑。這種決定會受到各條路徑上以往螞蟻留下的外激素濃度（即殘留信息濃度）的影響。如果向右的路徑上的外激素濃度比較大，那么向右的路徑被螞蟻選中的可能性也就比較大一些。但是對障礙出現(xiàn)后第一個(gè)到達(dá)b點(diǎn)或d點(diǎn)的螞蟻而言，因?yàn)闆]有外激素的影響，所以它們選擇向左或者向右的可能性是一樣的，如圖1 b）所示。若以從a點(diǎn)到e點(diǎn)的螞蟻為例進(jìn)行說明，對于從e 點(diǎn)到a點(diǎn)的螞蟻

57、而言過程基本是一樣的。由于路徑bhd比路徑bed要短，因此選擇bhd路徑的第一只螞蟻要比選擇bed的第一只螞蟻早到達(dá)d點(diǎn)。此時(shí)，從d點(diǎn)向b點(diǎn)看，指向路徑dhb的外激素濃度要比指向路徑deb的外激素濃度大。因此從下一時(shí)刻開始,從e點(diǎn)經(jīng)d點(diǎn)達(dá)到a點(diǎn)的螞蟻選擇dhb路徑比選擇dcb路徑的可能性要大得多。從而使路徑bhd（或dhb）上外激素濃度與路徑bed（或deb）上外激素濃度的差變大。而外激素</p><p>　　設(shè)

58、想，如果我們要為螞蟻設(shè)計(jì)一個(gè)人工智能的程序，那么這個(gè)程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因?yàn)槌绦虻腻e誤也許會讓你前功盡棄。這是多么不可思議的程序，太復(fù)雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。

59、    然而，事實(shí)并沒有你想得那么復(fù)雜，上面這個(gè)程序每個(gè)螞蟻的核心程序編碼都不是很長。為什么這么簡單的程序會讓螞蟻干這樣復(fù)雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進(jìn)行決策，這樣，在蟻群這個(gè)集體里，復(fù)雜性的行為就會凸現(xiàn)出來。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律。那么，這些簡單規(guī)則是什么

60、呢？下面詳細(xì)說明：1、范圍：    螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑VR（一般是3），那么它能觀察到的范圍就是VR*VR</p><p>　　根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信

61、息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。</p><p>　　2.4 蟻群算法的應(yīng)用</p><p>　　2.4.1螞蟻算法在電信網(wǎng)動態(tài)路由優(yōu)化中的應(yīng)用</p><p>　　針對我國電信網(wǎng)的具體情況，提出借助螞蟻算法，用分散控制的方式實(shí)現(xiàn)電信網(wǎng)動態(tài)路由優(yōu)化的一種方案，目的是提高網(wǎng)絡(luò)資源的利用率、網(wǎng)絡(luò)運(yùn)行的效率和可靠

62、性。</p><p>　　2.4.2螞蟻算法在組合優(yōu)化中的應(yīng)用</p><p>　　螞蟻算法是近年來新出現(xiàn)的一種隨機(jī)型搜索尋優(yōu)算法 ,自從在 TSP等著名問題中得到富有成效的應(yīng)用之后 ,已引起越來越多的關(guān)注和重視 .本文進(jìn)一步將這種新型的生物優(yōu)化思想擴(kuò)展到其他一些組合優(yōu)化難題 ,包括目前尚缺乏有效求解手段的多目標(biāo)組合優(yōu)化問題 ,從實(shí)驗(yàn)上探索了螞蟻算法的優(yōu)化能力 ,獲得了滿意的效果。 <

63、;/p><p>　　2.5 螞蟻算法的未來發(fā)展</p><p>　　自從1991 年M. Dorigo 等人首先提出蟻群算法以來,有許多研究人員對該算法進(jìn)行研究,并成功地應(yīng)用于解決復(fù)雜組合優(yōu)化問題. 在研究該算法的過程中,研究人員提出一些改進(jìn)的算法。</p><p>　　2.5.1 MMAS ( Max2Min ant system) 最大最小蟻群算法</p&g

64、t;<p>　　其基本思想是:只讓最佳路徑的外激素增加,加快收斂速度;為了避免算法過早收斂于非全局最優(yōu)解,將各條路徑可能的外激素濃度限于[τmin ,τmax ] ,超出這個(gè)范圍的值被強(qiáng)制設(shè)為τmin 或τmax ,可以有效地避免某條路徑上的信息量遠(yuǎn)大于其余路徑,使螞蟻都集中到同一條路徑上,這樣使算法不再擴(kuò)散;將各條路徑上外激素的起始濃度設(shè)為τmax ,這樣便可以更加充分地進(jìn)行尋優(yōu)。</p><p>

65、;　　2.5.2 具有變異特征的蟻群算法</p><p>　　當(dāng)群體的規(guī)模較大時(shí),需要較長時(shí)間才能搜索到最佳路徑. 為了克服此缺點(diǎn),受遺傳算法中的變異算子的啟發(fā),提出具有變異特征的蟻群算法. 算法中使用逆轉(zhuǎn)變異方式, 即設(shè)某個(gè)體走的路徑是:i0i1i2 ?i (n- 1) , (i0 ,i1 , ?i (n- 1) ∈{0 ,1 ,2 , ?,n - 1})如果滿足其中s1 ,s2 ∈{0 ,1 , ?, (n

66、- 1) } , %表示整除. 將s1 + 1 和s2這一段顛倒過來. 此算法引入變異算子,經(jīng)較少的進(jìn)化代數(shù)就可以找到較好的解。</p><p>　　2.5.3 自適應(yīng)蟻群算法</p><p>　　在此算法中采用確定性選擇和隨機(jī)選擇相結(jié)合的選擇策略,并在搜索過程中動態(tài)調(diào)整確定性選擇的概率. 當(dāng)進(jìn)化到一定代數(shù)后,進(jìn)化方向已經(jīng)基本確定,對路徑上的信息量進(jìn)行動態(tài)調(diào)整,縮小最好和最差路徑上的信息量

67、的差距,并適當(dāng)加大隨機(jī)選擇的概率,以利于對空間的完全搜索,可有效地克服基本蟻群算法進(jìn)化速度慢及易陷入局部最優(yōu)解的缺陷。</p><p>　　2.5.4大規(guī)模集成電路綜合布線</p><p>　　大規(guī)模集成電路中的綜合布線可以采用蟻群算法的思想來進(jìn)行(在布線過程中，各個(gè)引腳對螞蟻的引力可根據(jù)引力函數(shù)來計(jì)算。各個(gè)線網(wǎng)Agent根據(jù)啟發(fā)策略，象蟻群一樣在開關(guān)盒網(wǎng)格上爬行，所經(jīng)之處便布上一條金屬線

68、，歷經(jīng)一個(gè)線網(wǎng)的所有引腳之后，線網(wǎng)便布通了。給定一個(gè)開關(guān)盒布線問題，問題的計(jì)算量是固定不變的。主要由算法的迭代次數(shù)決定，而迭代次數(shù)由Agent的智能和開關(guān)盒問題本身的性質(zhì)確定蟻群算法本身的并行法，使之比較適合于解決布線問題。</p><p>　　2.5.5電信網(wǎng)絡(luò)路由</p><p>　　電信網(wǎng)絡(luò)中的路由是通過路由表進(jìn)行的。在每個(gè)節(jié)點(diǎn)的路由表中!對每個(gè)目的節(jié)點(diǎn)都列出了與該節(jié)點(diǎn)相連的節(jié)點(diǎn)，當(dāng)

69、有數(shù)據(jù)包到達(dá)時(shí)，通過查詢路由表可知道下一個(gè)將要到達(dá)的節(jié)點(diǎn)，首先對路由表中的信息素強(qiáng)度進(jìn)行初始化。在節(jié)點(diǎn)Xi以節(jié)點(diǎn)i為目的地址，鄰節(jié)點(diǎn)為J處的信息素強(qiáng)度為從X經(jīng)節(jié)點(diǎn)J到節(jié)點(diǎn)i路徑的最小費(fèi)用值。然后周期性地釋放螞蟻來進(jìn)行路由。并修改相應(yīng)的信息素的值。無論呼叫是均勻分布還是集分布，利用蟻群算法所得呼叫拒絕率和平均路徑長度均小于最小負(fù)載法結(jié)果:在呼叫符合集中分布時(shí)，蟻群算法所得呼叫拒絕率低于最短路徑法。</p><p>

70、<b>　　第3章 開發(fā)工具</b></p><p><b>　　3.1軟件環(huán)境</b></p><p>　　裝有JDK的JAVA環(huán)境的計(jì)算機(jī)，由于螞蟻算法演示是用JAVA做的一個(gè)小程序，所以在裝有JAVA環(huán)境的機(jī)子上都能夠運(yùn)行。</p><p><b>　　3.2其他資料</b></p>

71、<p>　　JAVA工具書，軟件工程工具書。面向?qū)ο蠊ぞ邥?lt;/p><p>　　3.3 Java 的簡單介紹</p><p>　　3.3.1 網(wǎng)絡(luò)時(shí)代的需要</p><p>　　1995 年在美國舉辦的一年一度的COMDEX 展覽會上, IBM 公司總裁Gerstner作為第一個(gè)受邀請的發(fā)言人向全世界宣布人類已進(jìn)入計(jì)算機(jī)技術(shù)發(fā)展的新時(shí)代—— 網(wǎng)絡(luò)時(shí)

72、代。在信息極度膨脹、爆炸的網(wǎng)絡(luò)時(shí)代下, 網(wǎng)絡(luò)技術(shù)的發(fā)展為以網(wǎng)絡(luò)為中心的計(jì)算提供了現(xiàn)實(shí)的可能和基礎(chǔ)。這樣, 用戶便不必關(guān)心自己計(jì)算機(jī)的性能和操作系統(tǒng)及應(yīng)用軟件如何, 只要在網(wǎng)絡(luò)上掌握更高一級的計(jì)算能力即可。這樣, 就勢必要求有Java 或類似的網(wǎng)絡(luò)操作語言出現(xiàn)。</p><p>　　3.3.2 Internet的普及</p><p>　　網(wǎng)絡(luò)時(shí)代最突出的體現(xiàn)莫過于Internet (互連網(wǎng))

73、 的廣泛使用和迅速普及了。誕生十余年的Internet 如今依然是應(yīng)用開發(fā)的熱點(diǎn), 并有廣泛的市場和燦爛的前景。資料表明: 這種開放式的計(jì)算機(jī)網(wǎng)絡(luò)已覆蓋了160 多個(gè)國家和地區(qū),連接的網(wǎng)絡(luò)高達(dá)6 萬多個(gè), 終端用戶超過3300萬個(gè)。但是, 目前的Internet 依舊是個(gè)靜態(tài)的媒介,幾乎不比電話更具有交互性, 它僅僅對用戶的需求發(fā)送圖片和文本, 它所缺少的正是軟件。這樣便為Java 或類似語言創(chuàng)造了廣闊的市場。</p>&

74、lt;p>　　3.3.3 跨平臺可移植性的要求</p><p>　　目前的計(jì)算機(jī)行業(yè)的現(xiàn)狀使其工作難度變得越來越大。廣大軟件開發(fā)人員不僅需要在各種不兼容的軟件平臺、硬件平臺和操作系統(tǒng)下工作, 進(jìn)行開發(fā), 而且還需要在各種不同的軟件或硬件平臺上使用互不相容的圖形用戶界面(GUI) , 所以人們手頭現(xiàn)有的軟件開發(fā)工具已遠(yuǎn)遠(yuǎn)不能滿足網(wǎng)絡(luò)時(shí)代的要求, 開發(fā)一種網(wǎng)絡(luò)上暢通無阻的編程語言勢在必行, 于是Java 便應(yīng)運(yùn)

75、而生。事實(shí)上, Java 的前身Oak 是一個(gè)最初為消費(fèi)類電子產(chǎn)品開發(fā)的、險(xiǎn)些夭折的產(chǎn)品, 隨著WWW的盛行, Sun 公司發(fā)現(xiàn)其主要開發(fā)方向——平臺無關(guān)性、系統(tǒng)安全性與可靠性一旦與WWW 結(jié)構(gòu)相結(jié)合將有廣闊的市場。在經(jīng)過一番努力和改后, Java 才于1995 年5 月正式推出。</p><p>　　3.4 Java 的主要特點(diǎn)</p><p><b>　　3.4.1 簡單性&

76、lt;/b></p><p>　　簡單性是Java 語言設(shè)計(jì)的最基本的出發(fā)點(diǎn), 為了使程序員很容易進(jìn)行編程并便于廣大C+ + 編程人員掌握, Java 在設(shè)計(jì)上很大部分繼承了C+ + 的風(fēng)格, 并從以下幾個(gè)方面使其更為簡化:</p><p>　　(1) 摒棄了C+ + 的不足之處和一些極少用到的功能, 如操作符過載、多級繼承性和各種自動強(qiáng)制性等;</p><p&g

77、t;　　(2) 增加了自動垃圾搜集功能, 使程序員在開發(fā)過程中不必考慮存儲器管理方面的問題,有利于減少編程錯誤的發(fā)生率;</p><p>　　(3) 減小了程序規(guī)模, 使編程更為簡單, 用Java 編寫的應(yīng)用程序Applets(小蘋果) 能完成某項(xiàng)特定任務(wù), 但其規(guī)模卻不超過10kB。</p><p><b>　　3.4.2 安全性</b></p>&l

78、t;p>　　對于網(wǎng)絡(luò)操作而言, 最重要的莫不過是安全性了。針對此, Java 提供了一種分布式編程環(huán)境。在其運(yùn)行時(shí)間系統(tǒng)中, 內(nèi)置了防病毒和損害文件系統(tǒng)的保護(hù)機(jī)制, 對于用戶來說, 即使是從Internet 上卸載或者修改Java 的應(yīng)用程序, 也是非常安全的。并且, 在網(wǎng)絡(luò)環(huán)境中, 用戶終端機(jī)上的應(yīng)用程序是經(jīng)過Java 一級一級傳譯的,禁止其他未授權(quán)的代碼對其進(jìn)行干涉, 更加保證了程序的安全性。</p><p

79、>　　3.4.3 面向?qū)ο笮?lt;/p><p>　　Java 具有許多面向?qū)ο蟮墓δ芴匦? 如代碼重用、代碼擴(kuò)展及動態(tài)應(yīng)用等優(yōu)點(diǎn), 基本上與C+ + 相同。但它摒棄了C+ + 的復(fù)雜性, 擴(kuò)展了對象模型, 并對C+ + 作了功能擴(kuò)充, 以提供更多的動態(tài)解決方法。事實(shí)上, 在Java 語言中, 除了原始數(shù)據(jù)類型外, 其余的成分均屬Java 的對象。</p><p><b>　　

80、3.4.4 可靠性</b></p><p>　　Java 為了保證編寫的軟件的可靠性, 對可能存在的問題采取了早期(編程期) 和后期(運(yùn)行期) 兩級動態(tài)檢查的措施。此外, 為減少開發(fā)人員的出錯機(jī)會, Java 還摒棄了C 語言不易掌握、常常引起系統(tǒng)崩潰的指針操作功能, 并增加了自動內(nèi)存管理功能, 從而排除了導(dǎo)致Java 應(yīng)用程序運(yùn)行不穩(wěn)定的一個(gè)重要因素。</p><p><

81、;b>　　3.4.5 解釋性</b></p><p>　　Java 是一種解釋執(zhí)行語言, 其運(yùn)行環(huán)境是在Java 虛擬機(jī)上的, 而虛擬機(jī)又是獨(dú)立于各種硬件平臺上的, 所以Java 解釋程序可以在任何機(jī)器上直接執(zhí)行Java 字節(jié)代碼。而且Java 應(yīng)用程序在編譯期產(chǎn)生的各種信息作為字節(jié)碼流的一部分, 在運(yùn)行期間仍可使用, 因而Java 應(yīng)用軟件也更易于調(diào)試。除上述優(yōu)點(diǎn)以外, Java 還具有多線程

82、動態(tài)性、系統(tǒng)結(jié)構(gòu)中立性和可移植性等特點(diǎn)。正因如此, Java 的出現(xiàn)給Internet 帶來了新的希望和無限生機(jī)。迄今, 計(jì)算機(jī)行業(yè)內(nèi)除了DEC 以外的, 諸如Oracle、IBM、Microsoft、SGI 等所有的大公司都宣布支持Java。</p><p>　　第4章 具體的功能結(jié)構(gòu)</p><p>　　4.1 系統(tǒng)的結(jié)構(gòu)總框圖</p><p><b>

83、;　　、</b></p><p>　　4.2 螞蟻算法的主要步驟</p><p>　　第一步：判斷螞蟻是否已經(jīng)找到目標(biāo)點(diǎn)（在螞蟻沒有找到食物之前，目標(biāo)點(diǎn)是事物，找到食物后，目標(biāo)點(diǎn)則換成螞蟻的窩）；</p><p><b>　　實(shí)現(xiàn)代碼：</b></p><p>　　if(Judged==false){<

84、/p><p>　　if(JudgeEnd()){</p><p>　　//判斷目前螞蟻是否已經(jīng)到了目標(biāo)點(diǎn)，，如果找到了目標(biāo)點(diǎn)那么就退出該程序</p><p>　　Judged=true;</p><p><b>　　return;</b></p><p><b>　　}</b>&

85、lt;/p><p><b>　　}</b></p><p>　　第二步：計(jì)算螞蟻的主方向，也就是讓螞蟻的爬動有一個(gè)慣性，當(dāng)沒有信息素做指導(dǎo)的時(shí)候螞蟻就按照主方向運(yùn)動；</p><p><b>　　實(shí)現(xiàn)代碼：</b></p><p>　　private double SelectDirect(){<

86、/p><p>　　//選擇方向，最后選擇的方向?yàn)橹鞣较蚣右粋€(gè)隨機(jī)擾動</p><p>　　double direct,e=0;</p><p>　　if(Main_direct<0){</p><p>　　//如果目前還沒有主方向角，就隨機(jī)的選擇一個(gè)</p><p>　　e=2*Math.PI*Math.random

87、();</p><p>　　Main_direct=e;</p><p><b>　　}</b></p><p><b>　　//選擇主方向角</b></p><p>　　direct=Main_direct;</p><p>　　//做一個(gè)隨機(jī)模型，產(chǎn)生兩個(gè)隨機(jī)數(shù)，x,y都

88、是[0,1]內(nèi)的，這樣x^2-y^2就是一個(gè) [-1，1]的隨機(jī)數(shù)，并且在0點(diǎn)附近的概率大，兩邊小</p><p>　　double re=Math.random();</p><p>　　double re1=Math.random();</p><p>　　direct+=Math.PI*(re*re-re1*re1)/2;</p><p&g

89、t;　　if(re<0.02){</p><p>　　//以小一定的概率0.02改變主方向的值，主方向的選取為從螞蟻記住的點(diǎn)中隨機(jī)選一個(gè)點(diǎn)，計(jì)算當(dāng)前點(diǎn)和這個(gè)點(diǎn)之間的方向角。</p><p>　　int size=(int)(re1*memory)+1;</p><p>　　if(HistoryPoint.size()>size){</p>

90、<p>　　Point pt=(Point)(HistoryPoint.elementAt(HistoryPoint.size()-size));</p><p>　　if(pt.x!=nowPt.x||pt.y!=nowPt.y){</p><p>　　Main_direct=GetDirection(pt,nowPt);</p><p><b&g

91、t;　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return direct;</p><p>　　第三步：開始搜索自己周圍的空間信息，包括有多少信息素，是否有障礙物；</p><p><

92、b>　　實(shí)現(xiàn)代碼：</b></p><p>　　//開始搜索環(huán)境，搜索的空間是以當(dāng)前點(diǎn)為中心，VR為半徑的四方形內(nèi)，即VR/2*VR/2的正方形</p><p>　　for(int x=-VR;x<=VR;x++){</p><p>　　for(int y=-VR;y<=VR;y++)</p><p><b

93、>　　{ </b></p><p>　　if(x!=0||y!=0){ </p><p>　　if(maxphe<phe){</p><p>　　//如果當(dāng)前點(diǎn)的信息素是0，則表示螞蟻還在窩里，如果是1，就要根據(jù)隨機(jī)數(shù)</p><p>　　//以mistake來決定螞蟻犯錯誤的概率，即如果犯錯誤，它就不按信息素最大的方

94、向走</p><p>　　double ra=Math.random();</p><p>　　if(here==0||ra>mistake){</p><p>　　boolean found=false;</p><p>　　//查一下內(nèi)存最近走過的的點(diǎn)數(shù)，從而避免當(dāng)?shù)剞D(zhuǎn)圈</p><p>　　int size

95、=HistoryPoint.size();</p><p>　　int minsize=memory;</p><p>　　if(size<memory)minsize=size;</p><p>　　for(int i=size-1;i>=size-minsize;i--){</p><p>　　Point pt=(Point)

96、(HistoryPoint.elementAt(i));</p><p>　　if(pt.x==xx&&pt.y==yy){</p><p>　　found=true;</p><p><b>　　break;</b></p><p><b>　　}</b></p>&

97、lt;p><b>　　}</b></p><p>　　if(!found){</p><p>　　//如果沒有原地轉(zhuǎn)圈，那么記錄信息素。</p><p>　　maxphe=local_colony.Pheromone_grid[1-kind][xx][yy];</p><p><b>　　deltx=x;

98、</b></p><p><b>　　delty=y;</b></p><p><b>　　}</b></p><p>　　}//end here==0||ra>0.001</p><p>　　}//end maxphe<here</p><p>　　

99、}//end if x!=0</p><p>　　}//end for y</p><p>　　}//end for x</p><p><b>　　Point pt;</b></p><p>　　第四步：根據(jù)信息素的大小決定螞蟻的移動方向；</p><p><b>　　實(shí)現(xiàn)代碼：<

100、;/b></p><p>　　//根據(jù)獲得的信息的來的位移量deltx,delty，來具體的進(jìn)行移位</p><p>　　pt=Evade_obs(deltx,delty);</p><p>　　第五步：根據(jù)決策的目標(biāo)進(jìn)行移動，其中包括遇見障礙的躲避和灑下自己的信息素。</p><p><b>　　（1）躲避障礙物</b

101、></p><p>　　如果遇到障礙物，就根據(jù)主方向來確定位移，如果主方向也有障礙物了，那螞蟻就會隨機(jī)變換自己的主方向。</p><p><b>　　實(shí)現(xiàn)代碼：</b></p><p>　　if(pt.x==nowPt.x&&pt.y==nowPt.y){</p><p>　　pt=Evade_ob

102、s(deltx1,delty1);</p><p><b>　　}</b></p><p>　　（2）灑下自己的信息素</p><p>　　在本程序中，螞蟻灑下信息素的功能是通過一個(gè)子程序?qū)崿F(xiàn)的，</p><p><b>　　實(shí)現(xiàn)代碼： </b></p><p>　　if(P

103、heromone_count<=0)return;</p><p>　　//決定釋放信息素的種類</p><p>　　int kind=FoundTimes%2; </p><p>　　//獲得當(dāng)前點(diǎn)環(huán)境已有信息素的值</p><p>　　int Phec=local_colony.Pheromone_grid[kind][lastPt

104、.x][lastPt.y];</p><p>　　boolean ofound=false;</p><p>　　if(Phec!=0){</p><p>　　//如果當(dāng)前點(diǎn)已經(jīng)有信息素了在信息素向量中查找該點(diǎn)的信息</p><p>　　for(int i=0;i<local_colony.phe.size();i++){</p&

105、gt;<p>　　Pheromone ph=(Pheromone)(local_colony.phe.elementAt(i));</p><p>　　if(lastPt.x==ph.x&&lastPt.y==ph.y&&ph.kind==kind){</p><p>　　//找到了，則看看螞蟻所在的位置是否是剛剛走過的，如果不是才撒信息素&l

106、t;/p><p>　　int size=HistoryPoint.size();</p><p>　　//如果在表中找到信息素，則用ofound記錄。</p><p>　　ofound=true;</p><p>　　boolean found=false;</p><p>　　if(size>4){</p&g

107、t;<p>　　for(int j=size-4;j<size-1;j++){</p><p>　　Point pt=(Point)(HistoryPoint.elementAt(j));</p><p>　　if(pt.x==lastPt.x&&pt.y==lastPt.y){</p><p>　　//如果當(dāng)前點(diǎn)重復(fù)了以前走過的

108、路，就不釋放</p><p>　　found=true;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

109、;/p><p>　　if(!found){</p><p>　　//如果當(dāng)前點(diǎn)不重復(fù)，則開始撒</p><p>　　ph.Add(Phe);</p><p>　　local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;</p><p>　　//讓還剩下的信息素總

110、量減少</p><p>　　Pheromone_count-=Phe;</p><p><b>　　}</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b

111、></p><p><b>　　}</b></p><p>　　if(Phec==0||!ofound){</p><p>　　//如果當(dāng)前環(huán)境沒有信息素，或者當(dāng)前環(huán)境的信息素來自窩或者食物，則新建一個(gè)信息素元素放到列表中</p><p>　　Pheromone ph=new Pheromone(lastPt.x,

112、lastPt.y,local_colony.phe.size(),local_colony.Delimiter,id,local_colony,Phec,kind);</p><p>　　ph.Add(Phe);</p><p>　　local_colony.Pheromone_grid[kind][lastPt.x][lastPt.y]+=Phe;</p><p>

113、;　　local_colony.phe.addElement(ph);</p><p>　　//讓還剩下的信息素總量減少</p><p>　　Pheromone_count-=Phe;</p><p><b>　　}</b></p><p>　　//根據(jù)還剩下信息素的量調(diào)整釋放信息素的數(shù)值Phe， /

114、/把剩余信息量看成數(shù)組count(n)，count(n)以幾何級數(shù)的速度遞減，這樣，螞蟻剛走出的地方信息素遠(yuǎn)遠(yuǎn)高于后走的地方 </p><p>　　Phe=(int)(0.005*Pheromone_count);</p><p>　　//如果剩余信息素已經(jīng)太小了，則按照等差數(shù)列遞減</p><p>　　if(Phe<=10)Phe=10;</p>

115、<p><b>　　} </b></p><p>　　第5章 系統(tǒng)的實(shí)現(xiàn)</p><p>　　5.1蟻群算法的實(shí)現(xiàn)結(jié)果</p><p>　　程序執(zhí)行后的到的結(jié)果如圖：</p><p><b>　　程序運(yùn)行說明：</b></p><p>　　淺藍(lán)色的點(diǎn)表示食物，