【正文】 ohn Holland教授于1975年首先提出的一類仿生型優(yōu)化算法，具有大范圍快速全局搜索能力。與自然界相似，遺傳算法對求解問題的本身一無所知。遺傳算法是從代表問題可能潛在解集的種群開始的，而種群則由經(jīng)過基因編碼的一定數(shù)目的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)(即基因型)是某種基因組合，它決定了個體形狀的外部表現(xiàn)。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解。在每一代進化過程中，根據(jù)問題域中個體適應(yīng)度大小來挑選(selection)個體，借助于自然遺傳學(xué)的遺傳算子進行組合交叉(erossover)和變異(mutation)，產(chǎn)生出代表新解集的種群。這個過程將導(dǎo)致種群像自然進化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼(decoding)，可以作為問題近似最優(yōu)解，這就是遺傳算法基本思想。遺傳算法應(yīng)用于Zigbee路由問題需要確定以下要素：(1) 編碼規(guī)則：需要針對具體的物理模型提出合適的編碼方法；(2) 創(chuàng)建初始群體：即確定路徑解集；(3) 確定遺傳算子：即確定選擇、交叉、變異的方法；(4) 確定適應(yīng)度函數(shù)：即確定Zigbee路由是根據(jù)那些參數(shù)的優(yōu)化并確定參數(shù)。將傳統(tǒng)遺傳算法直接應(yīng)用于Zigbee路由選擇存在以下問題：(1) 傳統(tǒng)的編碼不能很好的反應(yīng)實際物理模型；(2) 簡單的初始種群形成方法和交叉、變異操作容易產(chǎn)生非法路徑；(3) 通用的遺傳算法在解決Qos問題時具有單一約束上的困難。對于以上幾點現(xiàn)有的文獻已有很好的解決。但在已有的遺傳算法應(yīng)用于Zigbee路由的文獻中，選擇，交叉，變異的過程都是采用按概率隨機選擇的方法，這種方法具有多樣性好和全局性好的優(yōu)點，但針對具體的Zigbee路由問題具有以下缺點：(1) 每次迭代前需要遍歷所有父代個體，并計算每條染色體的概率，增加了算法復(fù)雜度；(2) 按概率隨機性選擇會存在統(tǒng)計誤差，導(dǎo)致一些本來優(yōu)秀的染色體丟失。由于本算法僅需要保存最優(yōu)的幾條路徑，對多樣性要求不高，針對Zigbee路由問題，解集多樣化固然重要，但減小Zigbee路由開銷和縮短Zigbee路由尋找時間才是最重要的，基于以上原因，本文擬對基本遺傳算法進行改進，提出一種確定性按比例遺傳算法，即按比例確定參與遺傳算子操作的個體。確定性選擇既保留了傳統(tǒng)遺傳算法可產(chǎn)生多樣化解集的優(yōu)點，又能保證算法可以以最快速度收斂到最優(yōu)，同時減小了算法的復(fù)雜度，具有易實施的優(yōu)點。 課題的可行性評估蟻群算法憑借其簡單的算法結(jié)構(gòu)和突出的問題求解能力, 以及靈活、穩(wěn)定、分布式控制和自組織能力等特點，吸引了很多研究者, 并取得了令人注目的成果。該理論很適合于工程問題中日益復(fù)雜的信息處理需求，尤其是動態(tài)特性突出的問題。然而, 由于其理論依據(jù)來源于對生物群落社會性的模擬, 因此其相關(guān)數(shù)學(xué)分析還比較薄弱, 這就導(dǎo)致了現(xiàn)有研究還存在以下幾個主要問題：(1) 蟻群算法的數(shù)學(xué)理論基礎(chǔ)薄弱, 缺乏普遍意義的理論性分析。算法中涉及的參數(shù)設(shè)置沒有確切的理論依據(jù), 一般按照經(jīng)驗確定, 對具體問題的依賴性大；(2) 比較性研究不足, 與各種成熟的優(yōu)化算法之間的基本特性及性能特點的對比研究還不是十分充分。將來的研究工作應(yīng)加強算法特性的分析, 進一步明確與算法原理相關(guān)的重要意義。如：單個個體的復(fù)雜性、學(xué)習(xí)能力和推理能力等。還應(yīng)擴展蟻群算法與其神經(jīng)網(wǎng)絡(luò)、禁忌搜索和支持向量機等先進技術(shù)的融合, 以改善其自身的性能。作為一種新型的模擬進化算法, 蟻群算法研究時間較短, 不像其他啟發(fā)式算法那樣具有系統(tǒng)的分析方法和堅實的數(shù)學(xué)理論。揮發(fā)因子等參數(shù)的選擇基本是依靠實驗和經(jīng)驗, 目前尚無通用及確定的理論方法來確定, 因此理論和實踐方面尚有許多問題需要更深入的研究與探討。 但是該算法的并行特性和強魯棒性等優(yōu)點吸引著許多學(xué)者不斷對其進行深入研究。 隨著理論研究和實踐經(jīng)驗的積累, 蟻群算法必將成為求解復(fù)雜組合優(yōu)化問題的高效算法。Ad hoc網(wǎng)絡(luò)在未來幾年有著極其誘人的前景和潛在的巨大市場。國內(nèi)外均有大量相關(guān)資料可供查閱，這些研究為迄今為止的Ad Hoc的Zigbee路由技術(shù)開發(fā)和系統(tǒng)設(shè)計提供了必要的參考依據(jù)和理論指導(dǎo)，也為本研究提供了豐富的基礎(chǔ)數(shù)據(jù)。現(xiàn)在，螞蟻算法和遺傳算法受到廣泛關(guān)注，作為一種新興的仿生學(xué)算法由于其良好的并行性對解決完全問題起到了良好的效果。并在車間作業(yè)調(diào)度問題，聚類分析、車輛路徑問題等方面取得了一系列成果。尤其螞蟻算法在網(wǎng)絡(luò)Zigbee路由問題方面的研究與本課題學(xué)科領(lǐng)域相近，可為本課題在方法論和技術(shù)路線上提供指導(dǎo)。迄今為止，課題研究人一直從事螞蟻算法，遺傳算法以及Ad Hoc網(wǎng)絡(luò)Zigbee路由的學(xué)習(xí)研究，對螞蟻算法，遺傳算法和Ad Hoc網(wǎng)絡(luò)有較為全面的掌握，知識上有較為充分的儲備。此外，本課題著重研究的內(nèi)容已取得階段性的成果，為課題的完成打下了基礎(chǔ)。綜上所述，本課題已具備了比較充分的理論基礎(chǔ)和仿真驗證，已打下較為扎實的基礎(chǔ)，預(yù)計可以成功實現(xiàn)。 本章小結(jié)本章對解決全文的最優(yōu)路徑規(guī)劃問題有重要的作用，先洗個長度和通行時間的線性組合為目標(biāo)函數(shù)，不僅解決了時間最短問題，還考慮到了螞蟻走過路徑的期望程度。實驗證明使勁路徑規(guī)劃中要考慮很多問題，克服zigbee網(wǎng)絡(luò)的缺點，滿足無線網(wǎng)絡(luò)不同需要，在一定程度上說明了蟻群算法的可靠性，實用性，解決了路徑小路徑選擇是值考慮道路的距離，重要程度和寬敞通常程度等因素。假設(shè)某一段時間的道路交通情況是不變的，而實際情況確是實時動態(tài)變化的。如果想要更完美、更貼切的實際情況，我們還可以研究實時動態(tài)變化，更大規(guī)模的仿真實例。本文將改進的遺傳算法應(yīng)用到簡單相關(guān)多路徑中，在目的節(jié)點搜索到路徑解集后，利用遺傳算法進行優(yōu)化，通過選擇、交叉、變異的過程實現(xiàn)在不需要增加任何尋路開銷的前提下對路徑優(yōu)化的目的。結(jié) 論無線傳感器網(wǎng)絡(luò)（WSN）是由大量體積小、成本低，具有計算和通信能力的微小傳感器節(jié)點密集布設(shè)在無人值守的監(jiān)控區(qū)域而構(gòu)成的能夠根據(jù)環(huán)境自主完成指定任務(wù)的“智能”測控網(wǎng)絡(luò)系統(tǒng)。WSN具有十分廣闊的應(yīng)用前景，能夠廣泛地應(yīng)用于軍事領(lǐng)域、環(huán)境監(jiān)測、醫(yī)療健康、智能家居、城市交通、空間探索和商業(yè)應(yīng)用等方面。由于WSN巨大的科研價值和實用價值，已經(jīng)引起了世界上許多國家的軍事界、學(xué)術(shù)界和工業(yè)界的高度重視，并成為近年來研究的熱點。由于無線傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境以及傳感器節(jié)點的能量有限，使得設(shè)計高效的WSN路由協(xié)議受到了巨大挑戰(zhàn)，能耗問題成了制約傳感器網(wǎng)絡(luò)發(fā)展的重要因素。因此，如何設(shè)計能夠有效節(jié)約并且均衡網(wǎng)絡(luò)能量消耗的WSN路由算法成為無線傳感器網(wǎng)絡(luò)研究方面的關(guān)鍵網(wǎng)絡(luò)問題之一。 由于一般網(wǎng)絡(luò)結(jié)點電池更換成本較高，因此要求每個結(jié)點都要最小化自身的能量消耗。理想的WSN路由算法應(yīng)充分考慮結(jié)點能量有限的特點，使路由算法具有較高的節(jié)能性和全局尋優(yōu)能力。但有時缺少對路徑全局尋優(yōu)方面的考慮，降低了WSN的整體吞吐量。由于WSN受到能量約束、處理能力有限和無線通信帶寬的限制，傳感器結(jié)點難以獲得整個網(wǎng)絡(luò)的拓?fù)湫畔?，因此必須要在不維護全局信息的前提下，構(gòu)建能源有效的全局最優(yōu)路由。WSN的路由算法必須在節(jié)能的前提下，采用全局尋優(yōu)方式進行路徑優(yōu)化，從而提高網(wǎng)絡(luò)的吞吞吐量。由于無線傳感器網(wǎng)絡(luò)具有結(jié)點計算能力弱、結(jié)點電能(電池提供的)有限等特點，在設(shè)計無線傳感器網(wǎng)絡(luò)路由算法時，必須考慮算法的節(jié)能性和簡單性。蟻群優(yōu)化作為一個啟發(fā)式搜索算法，具有分布性好、全局尋優(yōu)能力強、算法簡單易實現(xiàn)等優(yōu)點。對于蟻群優(yōu)化問題，經(jīng)過老師指導(dǎo)，我們還可以研究，是否不同種蟻群在路徑上釋放的信息素不同呢？作為以后的研究方向，我們可以繼續(xù)探索。致 謝在論文完成之際，我非常感謝自己的恩師于鄭燦香老師，在論文的完成過程中一直以來對我的悉心指導(dǎo)和多方面的入微關(guān)懷與幫助。同時也要感謝我的朋友，在論文遇到困難時給予我的鼓勵，為我做試驗提供了良好的試驗環(huán)境，讓我在畢業(yè)設(shè)計實踐過程中會走很多彎路，同時也感謝學(xué)院為我提供良好的做畢業(yè)設(shè)計的環(huán)境。在此特別表示感謝，使我的畢業(yè)設(shè)計有了個圓滿的結(jié)束。在校四年的學(xué)習(xí)生涯中，恩師的一絲不茍，科學(xué)嚴(yán)謹(jǐn)?shù)墓ぷ鲬B(tài)度深深地影響了我，恩師針對我們的各自興趣愛好，引導(dǎo)我們對于科研的道路的探索，并授予了我們治學(xué)的方法，在此對恩師致以崇高的敬意。在此我還要非常感謝我的父母，是他們含辛茹苦地養(yǎng)育了我，他們的樸實和奉獻將永存我的心里，衷心地祝福父母永遠健康和快樂。參考文獻[1] Vittorio Manizzo, An tonella carbonaro. Ant colony optimization: an over view[J]. Knowledge and Data Engineering, 1999．[2] Dorigo M, G ambardella L M, Midderd or fM，eta . Guesteditoria Special section on ant colony optimization [J].IEEE T rans. On Evolutionary putation, 2002．[3] 李聞等．傳感網(wǎng)絡(luò)中一 種基于螞蟻算法的分布式數(shù)據(jù)匯集路由算法[J]．小型微型計算機系統(tǒng)，2005年5月．[4] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo. Distributed Optimization by Ant Colonies[J]．Dipartimento di Elettronica, Politeicodi Milano，2003．[5] Chang J H，Tassiulas L．Maximum lifetime routing in wireless sensor networks[J]. IEEE AcM Transactions on Networking，2004．[6] 吳春明，陳治，[J].電子學(xué)報，2006年8月.[7] 謝民，[J]．計算機工程與應(yīng)用，2008年8月. [8] Laura R，Matteo B，Cgianluea．On Ant Routing Algorithms in Ad Hoc Networks with Critical Connectivity[J].Ad Hoc Network Journal，2008.[9] 王結(jié)太，許家棟，[J].系統(tǒng)仿真學(xué)報，2008年9月.[10] 馬良. 來自昆蟲世界的尋優(yōu)策略——蟻群算法[J].自然雜志, 1999年6月.[11] 張紀(jì)會, 高齊圣, 徐心和. 自適應(yīng)蟻群算法[J]．控制理論與應(yīng)用. 2000年7月.[12] 張航， 羅熊. 蟻群優(yōu)化算法的研究現(xiàn)狀及研究展望[J]．信息與控制,2004年3月.[13] 張凱，馮介一. ZigBee技術(shù)在無線傳感器網(wǎng)絡(luò)中的應(yīng)用[J].湛江師范學(xué)院學(xué)報，2010年6月.[14] [J].計算機專業(yè)，2008年6月.[15] 梁華為，陳萬明，李帥，梅濤，孟慶虎. 基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)能量均衡路由算法[J].模式認(rèn)識與人工智能，2007年4月.[16] 班艷麗．基于能量有效的ZigBee網(wǎng)絡(luò)路由算法研究[J]．山東大學(xué)碩士學(xué)位論文,2009年4月.[17] 王青正，閔林，郭拯危. 基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)能耗均衡路由算法[J].計算機應(yīng)用技術(shù)研究，2009年12月.[18] 肖偉，全惠云，劉楓. 基于蟻群算法的多路徑多約束QoS路由研究[J]．計算機工程與應(yīng)用，2008年4月.附 錄 AA WSN routing task which consists of stable or limited mobile nodes and a base station is considered as the problem. To achieve an efficient and robust routing operation, major features of typical WSNs are taken into consideration. First, failures in munication nodes are more probable in WSNs than classical networks, as nodes are often located in unattended places and they use a limited power supply. Therefore the network should not be affected by a node’s failure and should be in an adaptive structure to maintain the routing operation. This is performed by sustaining different paths alive in a routing task. A node transferring data to the base sends it in divided parts (as data packages) using different paths. When a failure occurs in a path, the associated data package cannot arrive at the base. To achieve guaranteed delivery, acknowledgement signals are used. In the case of an absent acknowledgement for a data package, the source node resends that package to a different path. By performing acknowledgementassociated data transfers and sus