【正文】 織的。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。 螞蟻撒信息素規(guī)則每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。為了防止螞蟻原地轉(zhuǎn)圈，它會記住剛才走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在之前走過了，它就會盡量避開。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？ 螞蟻覓食規(guī)則在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。然而，事實(shí)并沒有你想得那么復(fù)雜，上面這個(gè)程序每個(gè)螞蟻的核心程序編碼不過100多行！為什么這么簡單的程序會讓螞 蟻干這樣復(fù)雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。 蟻群算法的原理設(shè)想，如果我們要為螞蟻設(shè)計(jì)一個(gè)人工智能的程序，那么這個(gè)程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開障礙物，就必 須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路 徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因?yàn)槌绦虻腻e(cuò)誤也許會讓你前功盡棄。它后面的螞蟻通過路上信息素的濃度，做出決策，往左還是往右。但是當(dāng)有螞蟻?zhàn)哌^時(shí)，它將會在它行進(jìn)的路上釋放出信息素，并且這種信息素會議一定的速率散 發(fā)掉。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。圖（1）顯示了這樣一個(gè)覓食的過程。蟻群算法是一種仿生學(xué)算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。針對PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價(jià)值。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。（3） 蟻群算法在TSP問題中的應(yīng)用利用蟻群算法的特點(diǎn)以及蟻群算法的優(yōu)化應(yīng)用到TSP問題中。（2） 蟻群算法的優(yōu)化根據(jù)蟻群算法的基本原理做出優(yōu)化，避免蟻群算法的缺點(diǎn)，在迭代次數(shù)盡量少，迭代結(jié)果盡量趨近最優(yōu)解的情況下做出優(yōu)化。尹小峰等針對了蟻群算法存在的過早收斂問題引入節(jié)省量以及車輛載重利用率兩種啟發(fā)式信息對蟻群算法加以改進(jìn)，計(jì)算機(jī)仿真結(jié)果表明，這種混合蟻群算法對求解車輛路徑問題有較好的改進(jìn)效果。楊善林人等提出一種基于蟻群優(yōu)化的混合算法來解決VRP。通過定義基本的人工螞蟻狀態(tài)轉(zhuǎn)移概，并結(jié)合局部搜索策略，用迭代次數(shù)控制算法的運(yùn)行時(shí)間，從而使該方法具有使用意義和可操作性。鞍山鋼鐵學(xué)院李大衛(wèi)和東北大學(xué)姜大力等分別針對有時(shí)間窗和無時(shí)間窗約束下的車輛路徑問題用基因編碼遺傳算法求解，結(jié)果在較快速度下得到了近優(yōu)解。與傳統(tǒng)的啟發(fā)式算法相比，近年來所采用的一些新的啟發(fā)式算法，通過對啟發(fā)式規(guī)則和搜索方式的改進(jìn)，在求解多節(jié)點(diǎn)、多約束的VRP問題上可以獲得較快的收斂速度和較高質(zhì)量的全局解。蟻群算法、啟發(fā)式算法以及一些混合算法被學(xué)者們廣泛的利用，代表了較近的研究思想。隨著顧客需求的變化，運(yùn)輸車輛的調(diào)度顯得日益重要。1996年，有效的求解出帶時(shí)間窗限制的VRP。后來，可求解有134個(gè)客戶的VRP。1974年，Wren Gillett等人提出掃描算法，將該算法應(yīng)用于車輛調(diào)度問題，并和當(dāng)時(shí)其它算法進(jìn)行了比較，證明該算法所求得的解較優(yōu)于其它方法。 國外研究現(xiàn)狀1962年，Balinski等人首先提出VRP的集分割，直接考慮可行解集合，在此基礎(chǔ)上進(jìn)行優(yōu)化，建立了最簡單的VRP模型。自從VRP被Dantzig和Ramser于1959年提出之后，很快就引起了運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、物流科學(xué)、計(jì)算機(jī)科學(xué)等各個(gè)學(xué)科專家學(xué)者與運(yùn)輸計(jì)劃制定者和管理者的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的前沿問題和研究熱點(diǎn)。車輛路徑問題已經(jīng)是近幾十年來運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、網(wǎng)絡(luò)分析、計(jì)算機(jī)應(yīng)用及交通運(yùn)輸?shù)葘W(xué)科研究一個(gè)熱點(diǎn)問題，并且在通訊、身長、國防、生物計(jì)算機(jī)應(yīng)用等領(lǐng)域得到了廣泛的應(yīng)用。合理使用優(yōu)化運(yùn)輸路線，降低企業(yè)物流成本，是物流管理的很重要內(nèi)容。因此，國家和各地政府紛紛定制了各種有利于物流發(fā)展的政策和計(jì)劃。物流業(yè)被譽(yù)為經(jīng)濟(jì)發(fā)展動脈的“加速器”和商業(yè)結(jié)果演變的“潤滑劑”，現(xiàn)代企業(yè)的“第三利潤源泉”。 研究目的和意義物流是供應(yīng)鏈中最重要的組成部分，是商品從生產(chǎn)者經(jīng)過各流通環(huán)節(jié)最終到達(dá)消費(fèi)者手中的過程。而由于蟻群算法中螞蟻的個(gè)體行為具有內(nèi)在的并行性，因此可以考慮將算法進(jìn)行分布式并行處理來縮短算法的運(yùn)行時(shí)間。如何進(jìn)一步地對算法進(jìn)行優(yōu)化，即優(yōu)化策略的研究，也正是當(dāng)前蟻群算法研究的最大的熱點(diǎn)。蟻群算法在解決TSP問題時(shí)具有許多優(yōu)良性質(zhì)，但也存在著兩個(gè)主要的缺陷：收斂速度較慢，并且容易出現(xiàn)停滯。于是，許多求TSP問題近似解的新算法應(yīng)運(yùn)而生，啟發(fā)式算法便是其中之一。本科畢業(yè)生設(shè)計(jì)（論文）蟻群算法在車輛路徑優(yōu)化中的應(yīng)用畢業(yè)論文目錄摘 要 2ABSTRACT 3第1章 緒論 6 研究目的和意義 6 國內(nèi)外研究現(xiàn)狀 7 國外研究現(xiàn)狀 7 國內(nèi)研究現(xiàn)狀 8 本文研究內(nèi)容 9（1） 基本蟻群算法 9（2） 蟻群算法的優(yōu)化 9（3） 蟻群算法在TSP問題中的應(yīng)用 9 開發(fā)環(huán)境與工具 9 論文的組織結(jié)構(gòu) 10第2章 蟻群算法 10 蟻群算法簡介 10 蟻群算法的原理 11 螞蟻覓食規(guī)則 12 螞蟻移動規(guī)則 12 螞蟻避障規(guī)則 12 螞蟻撒信息素規(guī)則 12 蟻群算法的特點(diǎn)及優(yōu)缺點(diǎn) 13 蟻群算法的特點(diǎn) 13 蟻群算法的優(yōu)點(diǎn) 14 蟻群算法的缺點(diǎn) 14 蟻群算法的核心函數(shù) 15（1）初始化 15（2）選擇下一個(gè)城市，返回城市編號 15（3）更新環(huán)境信息素 17（4）檢查終止條件 18（5）輸出最優(yōu)值 18 蟻群算法的參數(shù)分析 19 螞蟻數(shù)量N_ANT_COUNT 19 啟發(fā)因子 19 期望啟發(fā)因子 20 信息素?fù)]發(fā)度 20 總信息量（DBQ） 21第3章 改進(jìn)的蟻群算法 21 輪盤賭選擇 22 輪盤賭選擇基本思想 22 輪盤賭選擇工作過程 22 MAX_MIN ACO 24 MAX_MIN算法的框架結(jié)構(gòu) 24 MAX_MIN 算法流程圖 26第4章 蟻群算法在車輛路徑問題中的應(yīng)用 28 車輛路徑問題簡介 28 車輛路徑問題定義 28 車輛路徑問題分類 29 車輛路徑問題的求解算法 29 精確算法 29 啟發(fā)式算法 30 蟻群算法解決車輛路徑問題 31 數(shù)值實(shí)驗(yàn)結(jié)果及分析 33 輪盤賭選擇優(yōu)化前后數(shù)據(jù)對比 33 MAX_MIN算法改進(jìn)前后數(shù)據(jù)對比 34第5章 總結(jié)與展望 36參考文獻(xiàn) 36第1章 緒論 TSP問題是一種特殊的車輛路徑問題，是作為所有組合優(yōu)化問題的范例而存在的，它已成為并將繼續(xù)成為測試組合優(yōu)化新算法的標(biāo)準(zhǔn)問題。傳統(tǒng)解法對小搜索空間的TSP問題適用，而且有的算法獲得精確解的性質(zhì)也正是人們所期望的。而蟻群算法（AC）是由意大利學(xué)者M(jìn)acro Dorigo等人在20世紀(jì)90年代提出來的[1]，它是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法等之后的一種新型的啟發(fā)式算法，已成功地應(yīng)用于求解TSP問題。為此，不少研究者提出了一些優(yōu)化策略及改進(jìn)，如：蟻群系統(tǒng)算法ACS（也稱蟻群優(yōu)化算法ACO）、最大最小蟻群系統(tǒng)算法MMAS等；這些改進(jìn)在一定程度上提高了算法的有效性，但效果并不明顯。另外，人們也注意到：改進(jìn)后的蟻群算法在解決大型的TSP問題時(shí)，關(guān)鍵參數(shù)的設(shè)置和信息素的更新將花費(fèi)很長的時(shí)間。如何進(jìn)行并行處理，亦即并行策略的研究，是目前蟻群算法研究的又一個(gè)熱點(diǎn)。物流業(yè)這是專門從事物流活動的行業(yè)，從企業(yè)銷售成本和商品價(jià)格組成角度考察，物流業(yè)蘊(yùn)藏著巨大的商機(jī)。通過提高物流管理水平和效率，降低物流成本，可以為企業(yè)及社會帶來可觀的經(jīng)濟(jì)效益，改善國民經(jīng)濟(jì)運(yùn)行效率，提高國際競爭力。在國家“十一五規(guī)劃”中講“大力發(fā)展現(xiàn)代物流”作為今后重點(diǎn)發(fā)展的領(lǐng)域，明確提出“十一五”結(jié)束即2010年，全社會物流成本要比2004年的計(jì)策上下降2—3個(gè)百分點(diǎn)。針對物流管理中對運(yùn)輸車輛路徑優(yōu)化調(diào)配的要求，1959年由Dantzig和Ramser首先提出了車輛路徑問題的數(shù)學(xué)模型。 國內(nèi)外研究現(xiàn)狀車輛路徑問題的研究有著現(xiàn)實(shí)的經(jīng)濟(jì)意義和學(xué)術(shù)意義。許多學(xué)者對該問題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，目前己經(jīng)產(chǎn)生出多種成熟的算法，取得了令人矚目的成果，為后人的繼續(xù)研究提供了極高的參考價(jià)值。1971年，Eilon提出將動態(tài)規(guī)劃法用于固定車輛數(shù)的VRP，通過遞歸方法求解。1981年，Christofides等人提出了k度中心樹和相關(guān)算法，對固定車輛數(shù)m的mTSP進(jìn)行了進(jìn)行k度中心樹松弛。1991年，Gendreau等人將禁忌搜索方法應(yīng)用于VRP，它是比較好的啟發(fā)式算法，可以成功地應(yīng)用于許多經(jīng)典的VRP。 國內(nèi)研究現(xiàn)狀在我國，有關(guān)車輛路徑問題的研究是在20世紀(jì)90年代以后才逐漸興起的，比國外相對落后。近年來，我國理論界逐漸開始關(guān)注車輛路徑問題的研究，并已取得初步成果。啟發(fā)式算法作為一種逐次逼近的算法，雖然不一定得到最優(yōu)解，但是可以高效率地得到具有較高精度的解，而且也易于考慮各種實(shí)