蟻群算法在車輛路徑優(yōu)化中的應(yīng)用畢業(yè)設(shè)計(jì)論文

1、<p>　　畢 業(yè) 設(shè) 計(jì)（論 文）</p><p>　　題目：蟻群算法在車輛路徑優(yōu)化中的應(yīng)用</p><p>　　姓 名 夏彬彬 </p><p>　　學(xué) 號(hào) 0910312134 </p><p>　　所在學(xué)院 湖北工業(yè)大學(xué) </p&g

2、t;<p>　　專業(yè)班級(jí) 09計(jì)職1班 </p><p>　　指導(dǎo)教師 宗欣露 </p><p>　　日 期 2013 年 5 月 8 日 </p><p><b>　　摘 要</b></p><p>　　許多實(shí)際工程問(wèn)題可以抽象

3、為相應(yīng)的組合優(yōu)化問(wèn)題，TSP問(wèn)題是作為所有組合優(yōu)化問(wèn)題的范例而存在的，它已成為并將繼續(xù)成為測(cè)試組合優(yōu)化新算法的標(biāo)準(zhǔn)問(wèn)題。從理論上講，使用窮舉法可以求解出TSP問(wèn)題的最優(yōu)解；但是對(duì)現(xiàn)有的計(jì)算機(jī)來(lái)說(shuō)，讓它在如此龐大的搜索空間中尋求最優(yōu)解，幾乎是不可能的。所以，各種求TSP問(wèn)題近似解的算法應(yīng)運(yùn)而生了，本文所描述的蟻群算法（AC）也在其中。</p><p>　　目前已出現(xiàn)了很多的啟發(fā)式算法，而蟻群算法作為一種新型的啟發(fā)式

4、算法，已成功地應(yīng)用于求解TSP問(wèn)題。螞蟻通過(guò)分泌信息素來(lái)加強(qiáng)較好路徑上信息素的濃度，同時(shí)按照路徑上的信息素濃度來(lái)選擇下一步的路徑：好的路徑將會(huì)被越來(lái)越多的螞蟻選擇，因此更多的信息素將會(huì)覆蓋較好的路徑；最終所有的螞蟻都集中到了好的路徑上。螞蟻的這種基于信息素的正反饋原理正是整個(gè)算法的關(guān)鍵所在。</p><p>　　本文介紹了基本蟻群算法概念、原理及蟻群算法的特點(diǎn)，再根據(jù)蟻群算法的缺點(diǎn)做出了優(yōu)化。采用輪盤賭選擇代替了

5、基本框架中通過(guò)啟發(fā)式函數(shù)和信息素選擇路徑，改進(jìn)蟻群算法的信息素傳遞參數(shù)，讓整個(gè)算法更快速的找到最優(yōu)解。其次，采用最大最小優(yōu)化系統(tǒng)限制最大值和最小值，讓整個(gè)系統(tǒng)更快收斂，得到最優(yōu)解。</p><p>　　關(guān)鍵字：蟻群算法，TSP問(wèn)題，啟發(fā)式函數(shù)，輪盤算法，最大最小優(yōu)化</p><p><b>　　ABSTRACT</b></p><p>　　Ma

6、ny practical engineering problems can be abstracted as corresponding combinatorial optimization problem, TSP problem is an example of all as a combinatorial optimization problem, it has become and will continue to be a n

7、ew combinatorial optimization algorithm of standard test problems. In theory, using the exhaustion method can solve the TSP problem optimal solution; But for the existing computer, let it in such a large search space to

8、seek the optimal solution, it is almost impossible. So, al</p><p>　　Has appeared a lot of heuristic algorithm and ant colony algorithm as a kind of new heuristic algorithm, has been successfully used in solv

9、ing TSP problems. Ant secretion by pheromones to strengthen the good path pheromone concentration, at the same time according to the path to choose the next path pheromone concentration: good paths will be more and more

10、ants to choose, so that more information will cover good path; Eventually all the ants on a good path. This positive feedback based on the ph</p><p>　　This paper introduces the basic concept of ant colony al

11、gorithm, principle and characteristics of ant colony algorithm, according to the disadvantages of ant colony algorithm optimization. Adopting roulette selection instead of the basic framework by heuristic function and ch

12、oose path pheromone, pheromone passing parameters of improved ant colony algorithm, make the whole algorithm find the optimal solution more quickly. Second, limiting the maximum and the minimum maximum minimum optimizati

13、on s</p><p>　　Keywords: ant colony algorithm, the TSP problem, a heuristic function, roulette algorithm, maximum_minimum optimization</p><p><b>　　目錄</b></p><p><b>

14、　　摘 要2</b></p><p>　　ABSTRACT3</p><p><b>　　第1章 緒論6</b></p><p>　　1.1 研究目的和意義6</p><p>　　1.2 國(guó)內(nèi)外研究現(xiàn)狀7</p><p>　　1.2.1 國(guó)外研究現(xiàn)狀7<

15、/p><p>　　1.2.2 國(guó)內(nèi)研究現(xiàn)狀8</p><p>　　1.3 本文研究?jī)?nèi)容9</p><p>　?。?） 基本蟻群算法9</p><p>　　（2） 蟻群算法的優(yōu)化9</p><p>　?。?） 蟻群算法在TSP問(wèn)題中的應(yīng)用9</p><p>　　1.4 開發(fā)環(huán)境與工具

16、9</p><p>　　1.5 論文的組織結(jié)構(gòu)10</p><p>　　第2章蟻群算法10</p><p>　　2.1 蟻群算法簡(jiǎn)介10</p><p>　　2.2 蟻群算法的原理11</p><p>　　2.2.1 螞蟻覓食規(guī)則12</p><p>　　2.2.2 螞蟻移

17、動(dòng)規(guī)則12</p><p>　　2.2.3 螞蟻避障規(guī)則12</p><p>　　2.2.4 螞蟻撒信息素規(guī)則12</p><p>　　2.3 蟻群算法的特點(diǎn)及優(yōu)缺點(diǎn)13</p><p>　　2.3.1 蟻群算法的特點(diǎn)13</p><p>　　2.3.2 蟻群算法的優(yōu)點(diǎn)14</p>

18、<p>　　2.3.3 蟻群算法的缺點(diǎn)14</p><p>　　2.5 蟻群算法的核心函數(shù)15</p><p><b>　?。?）初始化15</b></p><p>　?。?）選擇下一個(gè)城市，返回城市編號(hào)15</p><p>　?。?）更新環(huán)境信息素17</p><p>

19、;　?。?）檢查終止條件18</p><p>　?。?）輸出最優(yōu)值18</p><p>　　2.6 蟻群算法的參數(shù)分析19</p><p>　　2.6.1 螞蟻數(shù)量N_ANT_COUNT19</p><p>　　2.6.2 啟發(fā)因子19</p><p>　　2.6.3 期望啟發(fā)因子20</p>

20、<p>　　2.6.4 信息素?fù)]發(fā)度20</p><p>　　2.6.5 總信息量（DBQ）21</p><p>　　第3章改進(jìn)的蟻群算法21</p><p>　　3.1 輪盤賭選擇22</p><p>　　3.1.1 輪盤賭選擇基本思想22</p><p>　　3.1.2 輪盤賭選擇工

21、作過(guò)程22</p><p>　　3.2 MAX_MIN ACO24</p><p>　　3.2.1 MAX_MIN算法的框架結(jié)構(gòu)24</p><p>　　3.2.2 MAX_MIN 算法流程圖26</p><p>　　第4章蟻群算法在車輛路徑問(wèn)題中的應(yīng)用28</p><p>　　4.1 車輛路徑問(wèn)

22、題簡(jiǎn)介28</p><p>　　4.1.1 車輛路徑問(wèn)題定義28</p><p>　　4.1.2 車輛路徑問(wèn)題分類29</p><p>　　4.2 車輛路徑問(wèn)題的求解算法29</p><p>　　4.2.1 精確算法29</p><p>　　4.2.2 啟發(fā)式算法30</p><

23、;p>　　4.3 蟻群算法解決車輛路徑問(wèn)題31</p><p>　　4.4 數(shù)值實(shí)驗(yàn)結(jié)果及分析33</p><p>　　4.4.1 輪盤賭選擇優(yōu)化前后數(shù)據(jù)對(duì)比33</p><p>　　4.4.2 MAX_MIN算法改進(jìn)前后數(shù)據(jù)對(duì)比34</p><p>　　第5章總結(jié)與展望36</p><p>

24、;<b>　　參考文獻(xiàn)36</b></p><p><b>　　第1章 緒論</b></p><p>　　TSP問(wèn)題是一種特殊的車輛路徑問(wèn)題，是作為所有組合優(yōu)化問(wèn)題的范例而存在的，它已成為并將繼續(xù)成為測(cè)試組合優(yōu)化新算法的標(biāo)準(zhǔn)問(wèn)題。傳統(tǒng)解法對(duì)小搜索空間的TSP問(wèn)題適用，而且有的算法獲得精確解的性質(zhì)也正是人們所期望的。</p>&l

25、t;p>　　于是，許多求TSP問(wèn)題近似解的新算法應(yīng)運(yùn)而生，啟發(fā)式算法便是其中之一。而蟻群算法（AC）是由意大利學(xué)者M(jìn)acro Dorigo等人在20世紀(jì)90年代提出來(lái)的[1]，它是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法等之后的一種新型的啟發(fā)式算法，已成功地應(yīng)用于求解TSP問(wèn)題。</p><p>　　蟻群算法在解決TSP問(wèn)題時(shí)具有許多優(yōu)良性質(zhì)，但也存在著兩個(gè)主要的缺陷：收斂速度較慢，并且容易

26、出現(xiàn)停滯。為此，不少研究者提出了一些優(yōu)化策略及改進(jìn)，如：蟻群系統(tǒng)算法ACS（也稱蟻群優(yōu)化算法ACO）、最大最小蟻群系統(tǒng)算法MMAS等；這些改進(jìn)在一定程度上提高了算法的有效性，但效果并不明顯。如何進(jìn)一步地對(duì)算法進(jìn)行優(yōu)化，即優(yōu)化策略的研究，也正是當(dāng)前蟻群算法研究的最大的熱點(diǎn)。</p><p>　　另外，人們也注意到：改進(jìn)后的蟻群算法在解決大型的TSP問(wèn)題時(shí)，關(guān)鍵參數(shù)的設(shè)置和信息素的更新將花費(fèi)很長(zhǎng)的時(shí)間。而由于蟻群算法

27、中螞蟻的個(gè)體行為具有內(nèi)在的并行性，因此可以考慮將算法進(jìn)行分布式并行處理來(lái)縮短算法的運(yùn)行時(shí)間。如何進(jìn)行并行處理，亦即并行策略的研究，是目前蟻群算法研究的又一個(gè)熱點(diǎn)。</p><p>　　1.1 研究目的和意義</p><p>　　物流是供應(yīng)鏈中最重要的組成部分，是商品從生產(chǎn)者經(jīng)過(guò)各流通環(huán)節(jié)最終到達(dá)消費(fèi)者手中的過(guò)程。物流業(yè)這是專門從事物流活動(dòng)的行業(yè)，從企業(yè)銷售成本和商品價(jià)格組成角度考察，物流

28、業(yè)蘊(yùn)藏著巨大的商機(jī)。物流業(yè)被譽(yù)為經(jīng)濟(jì)發(fā)展動(dòng)脈的“加速器”和商業(yè)結(jié)果演變的“潤(rùn)滑劑”，現(xiàn)代企業(yè)的“第三利潤(rùn)源泉”。</p><p>　　通過(guò)提高物流管理水平和效率，降低物流成本，可以為企業(yè)及社會(huì)帶來(lái)可觀的經(jīng)濟(jì)效益，改善國(guó)民經(jīng)濟(jì)運(yùn)行效率，提高國(guó)際競(jìng)爭(zhēng)力。因此，國(guó)家和各地政府紛紛定制了各種有利于物流發(fā)展的政策和計(jì)劃。在國(guó)家“十一五規(guī)劃”中講“大力發(fā)展現(xiàn)代物流”作為今后重點(diǎn)發(fā)展的領(lǐng)域，明確提出“十一五”結(jié)束即2010年，

29、全社會(huì)物流成本要比2004年的計(jì)策上下降2—3個(gè)百分點(diǎn)。</p><p>　　合理使用優(yōu)化運(yùn)輸路線，降低企業(yè)物流成本，是物流管理的很重要內(nèi)容。針對(duì)物流管理中對(duì)運(yùn)輸車輛路徑優(yōu)化調(diào)配的要求，1959年由Dantzig和Ramser首先提出了車輛路徑問(wèn)題的數(shù)學(xué)模型。車輛路徑問(wèn)題已經(jīng)是近幾十年來(lái)運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、網(wǎng)絡(luò)分析、計(jì)算機(jī)應(yīng)用及交通運(yùn)輸?shù)葘W(xué)科研究一個(gè)熱點(diǎn)問(wèn)題，并且在通訊、身長(zhǎng)、國(guó)防、生物計(jì)算機(jī)應(yīng)用等領(lǐng)域得到了廣泛的

30、應(yīng)用。</p><p>　　1.2 國(guó)內(nèi)外研究現(xiàn)狀</p><p>　　車輛路徑問(wèn)題的研究有著現(xiàn)實(shí)的經(jīng)濟(jì)意義和學(xué)術(shù)意義。自從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)域的前沿問(wèn)題和研究熱點(diǎn)。許多學(xué)者對(duì)該問(wèn)題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，目前己經(jīng)產(chǎn)

31、生出多種成熟的算法，取得了令人矚目的成果，為后人的繼續(xù)研究提供了極高的參考價(jià)值。</p><p>　　1.2.1 國(guó)外研究現(xiàn)狀</p><p>　　1962年，Balinski等人首先提出VRP的集分割，直接考慮可行解集合，在此基礎(chǔ)上進(jìn)行優(yōu)化，建立了最簡(jiǎn)單的VRP模型。</p><p>　　1971年，Eilon提出將動(dòng)態(tài)規(guī)劃法用于固定車輛數(shù)的VRP，通過(guò)遞歸方法

32、求解。</p><p>　　1974年，Wren Gillett等人提出掃描算法，將該算法應(yīng)用于車輛調(diào)度問(wèn)題，并和當(dāng)時(shí)其它算法進(jìn)行了比較，證明該算法所求得的解較優(yōu)于其它方法。</p><p>　　1981年，Christofides等人提出了k度中心樹和相關(guān)算法，對(duì)固定車輛數(shù)m的m-TSP進(jìn)行了進(jìn)行k度中心樹松弛。后來(lái)，M.L.Fishe對(duì)這種方法做了進(jìn)一步改進(jìn)，可求解有134個(gè)客戶的VR

33、P。</p><p>　　1991年，Gendreau等人將禁忌搜索方法應(yīng)用于VRP，它是比較好的啟發(fā)式算法，可以成功地應(yīng)用于許多經(jīng)典的VRP。</p><p>　　1996年，J.Lawrence將遺傳算法用于VRP的研究，有效的求解出帶時(shí)間窗限制的VRP。</p><p>　　1.2.2 國(guó)內(nèi)研究現(xiàn)狀</p><p>　　在我國(guó)，有關(guān)車

34、輛路徑問(wèn)題的研究是在20世紀(jì)90年代以后才逐漸興起的，比國(guó)外相對(duì)落后。隨著顧客需求的變化，運(yùn)輸車輛的調(diào)度顯得日益重要。近年來(lái)，我國(guó)理論界逐漸開始關(guān)注車輛路徑問(wèn)題的研究，并已取得初步成果。蟻群算法、啟發(fā)式算法以及一些混合算法被學(xué)者們廣泛的利用，代表了較近的研究思想。啟發(fā)式算法作為一種逐次逼近的算法，雖然不一定得到最優(yōu)解，但是可以高效率地得到具有較高精度的解，而且也易于考慮各種實(shí)際問(wèn)題，因此，現(xiàn)已成為解決VRP問(wèn)題的重要方法。與傳統(tǒng)的啟發(fā)式

35、算法相比，近年來(lái)所采用的一些新的啟發(fā)式算法，通過(guò)對(duì)啟發(fā)式規(guī)則和搜索方式的改進(jìn)，在求解多節(jié)點(diǎn)、多約束的VRP問(wèn)題上可以獲得較快的收斂速度和較高質(zhì)量的全局解。浙江大學(xué)蔡延光等人運(yùn)用模擬退火算法和遺傳算法求解多重車輛調(diào)度問(wèn)題，并將其集成為智能算法庫(kù)，作為設(shè)計(jì)智能運(yùn)輸調(diào)度系統(tǒng)的依據(jù)。鞍山鋼鐵學(xué)院李大衛(wèi)和東北大學(xué)姜大力等分別針對(duì)有時(shí)間窗和無(wú)時(shí)間窗約束下的車輛路徑問(wèn)題用基因編碼遺傳算法求解，結(jié)果在較快速度下得到了近優(yōu)解。崔雪麗、馬良和范炳全等人基于

36、近年來(lái)出現(xiàn)的新型智能優(yōu)化思想：人工螞蟻系統(tǒng)給出了一種可快速求解VRP的螞蟻搜索算法。通過(guò)定義基本的人工螞蟻</p><p>　　1.3 本文研究?jī)?nèi)容</p><p>　　本文的研究?jī)?nèi)容可以概括為三部分：蟻群算法的基礎(chǔ)性理論、蟻群算法的優(yōu)化以及蟻群算法在TSP問(wèn)題中的應(yīng)用：</p><p>　　（1） 基本蟻群算法</p><p>　　了解基

37、本蟻群算法的概念、原理以及代碼如何實(shí)現(xiàn)。</p><p>　　（2） 蟻群算法的優(yōu)化</p><p>　　根據(jù)蟻群算法的基本原理做出優(yōu)化，避免蟻群算法的缺點(diǎn)，在迭代次數(shù)盡量少，迭代結(jié)果盡量趨近最優(yōu)解的情況下做出優(yōu)化。本文主要講解輪盤算法和max_min算法在蟻群算法中的優(yōu)化。</p><p>　　（3） 蟻群算法在TSP問(wèn)題中的應(yīng)用</p><p

38、>　　利用蟻群算法的特點(diǎn)以及蟻群算法的優(yōu)化應(yīng)用到TSP問(wèn)題中。</p><p>　　1.4 開發(fā)環(huán)境與工具</p><p>　　計(jì)算機(jī)：HP ProBook 4416S</p><p>　　系統(tǒng)：Microft Windows XP</p><p>　　Professinal</p><p><b>

39、　　版本2002</b></p><p>　　Service Pack3</p><p><b>　　內(nèi)存：2G</b></p><p><b>　　開發(fā)語(yǔ)言：C++</b></p><p>　　運(yùn)行環(huán)境：Microsoft Visual C++ 6.0</p><p

40、>　　1.5 論文的組織結(jié)構(gòu)</p><p>　　第一章 緒論 主要是講解本課題研究?jī)?nèi)容、目的和意義，國(guó)內(nèi)外對(duì)蟻群算法的研究現(xiàn)狀以及本系統(tǒng)開發(fā)環(huán)境的介紹；</p><p>　　第二章 蟻群算法 主要是介紹什么是蟻群算法，蟻群算法的原理和思想以及蟻群算法的優(yōu)缺點(diǎn)；</p><p>　　第三章 改進(jìn)的蟻群算法 主要是講解在基本蟻群算法的基礎(chǔ)上對(duì)蟻群算

41、法做出優(yōu)化（本文采用了輪盤選擇和MAX-MIN兩種優(yōu)化方式）</p><p>　　第四章 蟻群算法在車輛路徑問(wèn)題中的應(yīng)用</p><p>　　第五章 總結(jié)與展望</p><p><b>　　第2章蟻群算法</b></p><p>　　2.1 蟻群算法簡(jiǎn)介</p><p>　　蟻群算法(an

42、t colony optimization, ACO)，又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對(duì)PID控制器參數(shù)優(yōu)化設(shè)計(jì)問(wèn)題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和

43、應(yīng)用價(jià)值。</p><p>　　蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無(wú)智能或有輕微智能的個(gè)體（Agent）通過(guò)相互協(xié)作而表現(xiàn)出智能行為，從而為求解復(fù)雜問(wèn)題提供了一個(gè)新的可能性。</p><p>　　蟻群算法是一種仿生學(xué)算法，是由自然界中螞蟻覓食的行為而啟發(fā)的。在自然界中，螞蟻覓食過(guò)程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優(yōu)路

44、徑。圖（1）顯示了這樣一個(gè)覓食的過(guò)程。</p><p><b>　　圖（1）螞蟻覓食</b></p><p>　　在圖1（a）中，有一群螞蟻，假如A是蟻巢，E是食物源（反之亦然）。這群螞蟻將沿著蟻巢和食物源之間的直線路徑行駛。假如在A和E之間突然出現(xiàn)了一個(gè)障 礙物（圖1（b）），那么，在B點(diǎn)（或D點(diǎn)）的螞蟻將要做出決策，到底是向左行駛還是向右行駛？由于一開始路上沒(méi)有前

45、面螞蟻留下的信息素 （pheromone），螞蟻朝著兩個(gè)方向行進(jìn)的概率是相等的。但是當(dāng)有螞蟻?zhàn)哌^(guò)時(shí)，它將會(huì)在它行進(jìn)的路上釋放出信息素，并且這種信息素會(huì)議一定的速率散 發(fā)掉。信息素是螞蟻之間交流的工具之一。它后面的螞蟻通過(guò)路上信息素的濃度，做出決策，往左還是往右。很明顯，沿著短邊的的路徑上信息素將會(huì)越來(lái)越濃（圖 1（c）），從而吸引了越來(lái)越多的螞蟻沿著這條路徑行駛。</p><p>　　2.2 蟻群算法的原理&l

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

47、 太復(fù)雜了，恐怕沒(méi)人能夠完成這樣繁瑣冗余的程序。</p><p>　　然而，事實(shí)并沒(méi)有你想得那么復(fù)雜，上面這個(gè)程序每個(gè)螞蟻的核心程序編碼不過(guò)100多行！為什么這么簡(jiǎn)單的程序會(huì)讓螞 蟻干這樣復(fù)雜的事情？答案是：簡(jiǎn)單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前信息，而且根 據(jù)這些局部信息利用幾條簡(jiǎn)單的規(guī)則進(jìn)行決策，這樣，在蟻群這個(gè)集體里，復(fù)雜性的行為就會(huì)凸現(xiàn)出來(lái)

48、。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡(jiǎn)單規(guī)則是什么呢？</p><p>　　2.2.1 螞蟻覓食規(guī)則</p><p>　　在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地 方走，并且每只螞蟻都會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過(guò)它對(duì)

49、窩的信息素做出反應(yīng)，而對(duì)食物信息素沒(méi)反應(yīng)。</p><p>　　2.2.2 螞蟻移動(dòng)規(guī)則</p><p>　　每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒(méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住剛才走過(guò)了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在之前走過(guò)了，它就會(huì)盡量避開。</p>&

50、lt;p>　　2.2.3 螞蟻避障規(guī)則</p><p>　　如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。</p><p>　　2.2.4 螞蟻撒信息素規(guī)則</p><p>　　每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少。</p>&l

51、t;p>　　根據(jù)這幾條規(guī)則，螞蟻之間并沒(méi)有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過(guò)信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來(lái)了。比如，當(dāng)一只螞蟻找到了食物，它并沒(méi)有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過(guò)它附近的時(shí)候，就會(huì)感覺(jué)到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。</p><p>　　2.3 蟻群算法的特點(diǎn)及優(yōu)缺點(diǎn)</p><p>　　

52、2.3.1 蟻群算法的特點(diǎn)</p><p>　?。?）蟻群算法是一種自組織的算法</p><p>　　在系統(tǒng)論中，自組織和它組織是組織的兩個(gè)基本分類，其區(qū)別在于組織力或組織指令是來(lái)自于系統(tǒng)的內(nèi)部還是來(lái)自于系統(tǒng)的外部，來(lái)自于系統(tǒng)內(nèi)部的是自組織，來(lái)自于系統(tǒng)外部的是他組織。如果系統(tǒng)在獲得空間的、時(shí)間的或者功能結(jié)構(gòu)的過(guò)程中，沒(méi)有外界的特定干預(yù)，我們便說(shuō)系統(tǒng)是自組織的。在抽象意義上講，自組織就是在

53、沒(méi)有外界作用下使得系統(tǒng)熵增加的過(guò)程(即是系統(tǒng)從無(wú)序到有序的變化過(guò)程)。蟻群算法充分體現(xiàn)了這個(gè)過(guò)程，以螞蟻群體優(yōu)化為例子說(shuō)明。當(dāng)算法開始的初期，單個(gè)的人工螞蟻無(wú)序的尋找解，算法經(jīng)過(guò)一段時(shí)間的演化，人工螞蟻間通過(guò)信息激素的作 用，自發(fā)的越來(lái)越趨向于尋找到接近最優(yōu)解的一些解，這就是一個(gè)無(wú)序到有序的過(guò)程。</p><p>　?。?）蟻群算法是一種本質(zhì)上并行的算法</p><p>　　每只螞蟻搜索的

54、過(guò)程彼此獨(dú)立，僅通過(guò)信息激素進(jìn)行通信。所以蟻群算法則可以看作是一個(gè)分布式的多agent系統(tǒng)，它在問(wèn)題空間的多點(diǎn)同時(shí)開始進(jìn)行獨(dú)立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強(qiáng)的全局搜索能力。</p><p>　?。?）蟻群算法是一種正反饋的算法</p><p>　　從真實(shí)螞蟻的覓食過(guò)程中我們不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短 路徑上信息激素的堆積，而信息激素的堆積卻是一

55、個(gè)正反饋的過(guò)程。對(duì)蟻群算法來(lái)說(shuō)，初始時(shí)刻在環(huán)境中存在完全相同的信息激素，給予系統(tǒng)一個(gè)微小擾動(dòng)，使得各 個(gè)邊上的軌跡濃度不相同，螞蟻構(gòu)造的解就存在了優(yōu)劣，算法采用的反饋方式是在較優(yōu)的解經(jīng)過(guò)的路徑留下更多的信息激素，而更多的信息激素又吸引了更多的螞 蟻，這個(gè)正反饋的過(guò)程使得初始的不同得到不斷的擴(kuò)大，同時(shí)又引導(dǎo)整個(gè)系統(tǒng)向最優(yōu)解的方向進(jìn)化。因此，正反饋是螞蟻算法的重要特征，它使得算法演化過(guò)程得以進(jìn)行。</p><p>　

56、?。?）蟻群算法具有較強(qiáng)的魯棒性</p><p>　　相對(duì)于其它算法，蟻群算法對(duì)初始路線要求不高，即蟻群算法的求解結(jié)果不依賴子初始路線的選擇，而且在搜索過(guò)程中不需要進(jìn)行人工的調(diào)整。其次，蟻群算法的參數(shù)數(shù)目少，設(shè)置簡(jiǎn)單，易于蟻群算法應(yīng)用到其它組合優(yōu)化問(wèn)題的求解。</p><p>　　2.3.2 蟻群算法的優(yōu)點(diǎn)</p><p>　　蟻群算法的成果運(yùn)用激起了人們的極大

57、興趣，并吸引了一批研究人員從事蟻群算法的研究。研究表明，蟻群算法是一種有效的隨機(jī)搜素算法，具有如下優(yōu)點(diǎn)：</p><p>　?。?）較強(qiáng)的魯棒性：無(wú)中心控制，不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的求解；</p><p>　?。?）本質(zhì)并行性：蟻群在問(wèn)題空間的多點(diǎn)不同時(shí)開始進(jìn)行獨(dú)立的解搜素，增強(qiáng)了算法的全局搜素能力；</p><p>　?。?）正反饋性：蟻

58、群算法能夠最終找到最短路徑，直接依賴于最短路徑上的信息素的堆積，而信息素的堆積就是一個(gè)正反饋的過(guò)程；</p><p>　?。?）易于與其他方法結(jié)合：蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法的性能。</p><p>　?。?）自組織性：算法初期，單個(gè)的人工螞蟻無(wú)序地尋找解，經(jīng)過(guò)一段時(shí)間的煙花，螞蟻間通過(guò)信息素的作用，自發(fā)地越來(lái)越趨向于尋找到接近最優(yōu)解的一些解，是個(gè)從無(wú)序到有序的過(guò)程；&

59、lt;/p><p>　　2.3.3 蟻群算法的缺點(diǎn)</p><p>　　雖然蟻群算法有許多優(yōu)點(diǎn)，但同時(shí)也存在一些缺陷，如：</p><p>　　（1）與其他方法相比，該算法一般需要較長(zhǎng)的搜索時(shí)間，計(jì)算量較大，蟻群算法的復(fù)雜度可以反映這一點(diǎn)；</p><p>　　（2）該方法容易出現(xiàn)停滯現(xiàn)象（stagnation behaviour），即搜索進(jìn)

60、行到一定程度后，所有個(gè)體所發(fā)現(xiàn)的解完全一致，不能對(duì)解空間進(jìn)一步進(jìn)行搜索，不利于發(fā)現(xiàn)更好的解。</p><p>　　2.5 蟻群算法的核心函數(shù)</p><p><b>　?。?）初始化</b></p><p>　　將所有城市設(shè)置為沒(méi)有去過(guò)，清空螞蟻?zhàn)哌^(guò)的路徑編號(hào)（置0），螞蟻?zhàn)哌^(guò)長(zhǎng)度設(shè)置0，并隨機(jī)選取一個(gè)出發(fā)點(diǎn)，以及標(biāo)識(shí)改點(diǎn)走過(guò)。</p&

61、gt;<p>　　void CAnt::Init()</p><p><b>　　{</b></p><p>　　for (int i=0;i<N_CITY_COUNT;i++)</p><p><b>　　{</b></p><p>　　m_nAllowedCity[i]=1;

62、 //設(shè)置全部城市為沒(méi)有去過(guò)</p><p>　　m_nPath[i]=0; //螞蟻?zhàn)叩穆窂饺吭O(shè)置為0</p><p><b>　　}</b></p><p>　　//螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度設(shè)置為0</p><p>　　m_dbPathLength=0.0; </p><p>　　//隨機(jī)選擇一個(gè)

63、出發(fā)城市</p><p>　　m_nCurCityNo=rnd(0,N_CITY_COUNT);</p><p><b>　　//設(shè)置出發(fā)城市</b></p><p>　　m_nPath[0]=m_nCurCityNo;</p><p>　　//標(biāo)識(shí)出發(fā)城市為已經(jīng)去過(guò)了</p><p>　　m_n

64、AllowedCity[m_nCurCityNo]=0; </p><p>　　//已經(jīng)去過(guò)的城市數(shù)量設(shè)置為1</p><p>　　m_nMovedCityCount=1; </p><p><b>　　}</b></p><p>　?。?）選擇下一個(gè)城市，返回城市編號(hào)</p><p>　　int

65、 CAnt::ChooseNextCity()</p><p><b>　　{</b></p><p>　　int nSelectedCity=-1; //返回結(jié)果，先暫時(shí)把其設(shè)置為-1</p><p>　　//計(jì)算當(dāng)前城市和沒(méi)去過(guò)的城市之間的信息素總和</p><p>　　double dbTotal=0.0;<

66、;/p><p>　　double prob[N_CITY_COUNT]; // 保存城市被選中的概率</p><p>　　for (int i=0;i<N_CITY_COUNT;i++)</p><p><b>　　{</b></p><p>　　if (m_nAllowedCity[i] == 1) //城市沒(méi)去過(guò)&

67、lt;/p><p><b>　　{</b></p><p>　　prob[i]=pow(g_Trial[m_nCurCityNo][i],ALPHA)*pow(1.0/g_Distance[m_nCurCityNo][i],BETA); //該城市和當(dāng)前城市間的信息素</p><p>　　dbTotal=dbTotal+prob[i]; //累加信

68、息素，得到總和</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　prob[i]=0.0;</p><p><b>　　}</b><

69、;/p><p><b>　　}</b></p><p>　　//直接選擇概率最大的點(diǎn)</p><p>　　double temp_max=-1;</p><p>　　for(int ii=0;ii<N_CITY_COUNT;ii++){</p><p>　　if(temp_max<prob

70、[ii]){</p><p>　　temp_max=prob[ii];</p><p>　　nSelectedCity=ii;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if (nSelectedCity == -1

71、)</p><p><b>　　{</b></p><p>　　for (int i=0;i<N_CITY_COUNT;i++)</p><p><b>　　{</b></p><p>　　if (m_nAllowedCity[i] == 1) //城市沒(méi)去過(guò)</p><p

72、><b>　　{</b></p><p>　　nSelectedCity=i;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>

73、<b>　　}</b></p><p><b>　　//返回結(jié)果</b></p><p>　　return nSelectedCity;</p><p><b>　　}</b></p><p>　?。?）更新環(huán)境信息素</p><p>　　//更新環(huán)境信

74、息素,基本算法</p><p><b>　　//*</b></p><p>　　void CTsp::UpdateTrial()</p><p><b>　　{</b></p><p><b>　　//臨時(shí)保存信息素</b></p><p>　　doub

75、le dbTempAry[N_CITY_COUNT][N_CITY_COUNT];</p><p>　　memset(dbTempAry,0,sizeof(dbTempAry)); //先全部設(shè)置為0</p><p>　　//計(jì)算新增加的信息素,保存到臨時(shí)數(shù)組里</p><p><b>　　int m=0;</b></p><

76、;p><b>　　int n=0;</b></p><p>　　for (int i=0;i<N_ANT_COUNT;i++) //計(jì)算每只螞蟻留下的信息素</p><p><b>　　{</b></p><p>　　for (int j=1;j<N_CITY_COUNT;j++)</p>

77、<p><b>　　{</b></p><p>　　m=m_cAntAry[i].m_nPath[j];</p><p>　　n=m_cAntAry[i].m_nPath[j-1];</p><p>　　dbTempAry[n][m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;&l

78、t;/p><p>　　dbTempAry[m][n]=dbTempAry[n][m];</p><p><b>　　}</b></p><p>　　//最后城市和開始城市之間的信息素</p><p>　　n=m_cAntAry[i].m_nPath[0];</p><p>　　dbTempAry[n]

79、[m]=dbTempAry[n][m]+DBQ/m_cAntAry[i].m_dbPathLength;</p><p>　　dbTempAry[m][n]=dbTempAry[n][m];</p><p><b>　　}</b></p><p><b>　　//更新環(huán)境信息素</b></p><p&g

80、t;　　for (i=0;i<N_CITY_COUNT;i++)</p><p><b>　　{</b></p><p>　　for (int j=0;j<N_CITY_COUNT;j++)</p><p><b>　　{</b></p><p>　　g_Trial[i][j]=g_Tr

81、ial[i][j]*ROU+dbTempAry[i][j]; //最新的環(huán)境信息素 = 留存的信息素 + 新留下的信息素</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

82、　　（4）檢查終止條件</b></p><p>　　如果達(dá)到最大迭代次數(shù)，算法終止，輸出最終最優(yōu)解；否則，執(zhí)行（5），輸出當(dāng)前迭代最優(yōu)解，重新初始化所有的螞蟻的路徑矩陣所有元素初始化為0，禁忌表表清空，允許表表中加入所有的城市節(jié)點(diǎn)。隨機(jī)選擇它們的起始位置（也可以人工指定）。在路徑矩陣中加入起始節(jié)點(diǎn)，允許表中去掉該起始節(jié)點(diǎn)，重復(fù)執(zhí)行（2），（3）,(4)步。</p><p>&l

83、t;b>　?。?）輸出最優(yōu)值</b></p><p>　　每次迭代結(jié)束，輸出當(dāng)前迭代編號(hào)以及本次迭代中最優(yōu)解螞蟻的路徑長(zhǎng)度。</p><p>　　2.6 蟻群算法的參數(shù)分析</p><p>　　從蟻群算法的模型中可以看出，蟻群算法的參數(shù)空間龐大，合適的參數(shù)組合能夠過(guò)有全局收喲能力和較快的瘦臉術(shù)的，不合適的參數(shù)組合則會(huì)使得算法收斂較慢或者達(dá)到局部最

84、優(yōu)解。然而，目前對(duì)各參數(shù)該如何選擇也沒(méi)有嚴(yán)格的理論依據(jù)，只是根據(jù)經(jīng)驗(yàn)和實(shí)驗(yàn)來(lái)選取合適的參數(shù)值?；诖耍瑖?guó)內(nèi)外許多研究人員在蟻群算法的參數(shù)分析和優(yōu)化組合方面做了大量的工作。對(duì)、、、N_ANT_COUNT（N_ANT_COUNT，螞蟻數(shù)量）等參數(shù)的選擇進(jìn)行了初步研究；</p><p>　　2.6.1 螞蟻數(shù)量N_ANT_COUNT</p><p>　　螞蟻算法是通過(guò)多個(gè)候選解組成的群體進(jìn)化過(guò)程

85、來(lái)搜索最優(yōu)解，所以螞蟻的數(shù)目N_ANT_COUNT對(duì)一群算法有一定的影響。N_ANT_COUNT大，會(huì)提高蟻群算法的全局搜索能力和穩(wěn)定性，但數(shù)量過(guò)大會(huì)導(dǎo)致大量曾被搜索過(guò)的路徑上的信息素變化趨于平均，信息正反饋?zhàn)饔脺p弱，隨機(jī)性增強(qiáng)，收斂速度減慢。反之，N_ANT_COUNT小，會(huì)使從來(lái)未被搜索到的解上的信息素減小到接近于0，全局搜索的隨機(jī)性減弱，雖然收斂速度加快，但是會(huì)使算法的全局性能降低，穩(wěn)定性變差，出現(xiàn)過(guò)早停滯現(xiàn)象。經(jīng)大量的仿真試驗(yàn)獲

86、得：</p><p>　　當(dāng)N_ANT_COUNT屬于【0.6*N_CITY_COUNT,09*N_CITY_COUNT】時(shí)（N_CITY_COUNT為城市數(shù)量），蟻群算法的全局收斂性和收斂速度都比較好。</p><p>　　2.6.2 啟發(fā)因子</p><p>　　啟發(fā)銀子 是表示螞蟻在運(yùn)動(dòng)過(guò)程中所積累的信息素在知道蟻群搜索中的相對(duì)重要程度，其大小反映了螞蟻在路徑

87、搜索中隨機(jī)因素作用強(qiáng)弱。</p><p>　　越大，螞蟻選擇以前走過(guò)的路徑可能性就越大，實(shí)現(xiàn)自催化過(guò)程，但搜索的隨機(jī)性減弱；</p><p>　　越小，易使蟻群算法過(guò)早陷入局部最優(yōu)。</p><p>　　而已有研究證明：對(duì)于小規(guī)模的TSP問(wèn)題，在蟻群算法的三種模型中=1時(shí)，解的質(zhì)量和穩(wěn)定性都是最好的。</p><p>　　2.6.3 期望啟發(fā)

88、因子 </p><p>　　期望啟發(fā)因子是表示能見(jiàn)度相對(duì)重要程度的參數(shù)。的大小反映了螞蟻在路徑搜索過(guò)程中確定性因素作用的強(qiáng)弱。</p><p>　　而已有研究表明：過(guò)小，講導(dǎo)致螞蟻群體陷入純粹的隨機(jī)搜索，在此情況下很難找到最優(yōu)解；過(guò)大，螞蟻在局部點(diǎn)上選擇局部最短路徑的可能性越大，雖然加快了收斂速度，但減弱了隨機(jī)性，易陷入局部最優(yōu)。</p><p>　　對(duì)于TSP問(wèn)題

89、，不同城市規(guī)模，的具體取值各有不同。一般 【2,5,8】時(shí)，算法的綜合性比較好。</p><p>　　2.6.4 信息素?fù)]發(fā)度 </p><p>　　在蟻群算法中，人工螞蟻是具有人類記憶功能的，隨著時(shí)間的推移，以前留下的信息將要逐漸消失。如前所述，在算法模型中，參數(shù)表示信息素?fù)]發(fā)度，其大小直接關(guān)系到蟻群算法的全局搜索能力及其收斂速度；1-信息素殘留印子，反映了螞蟻個(gè)體之間相互影響的強(qiáng)弱

90、。研究表明：</p><p>　　在其它參數(shù)相同的情況下，信息素?fù)]發(fā)度的大小對(duì)一群算法的收斂性影響非常大，與循環(huán)次數(shù)近似成反比關(guān)系。當(dāng)極小時(shí)，路徑上殘留信息占主導(dǎo)地位，信息正反饋?zhàn)饔孟鄬?duì)較弱，手術(shù)的隨機(jī)性增強(qiáng)，因而蟻群算法的收斂速度很慢。若較大時(shí)，正反饋?zhàn)饔谜贾鲗?dǎo)地位，搜素的隨機(jī)性減弱，導(dǎo)致收斂速度快，但易陷入局部最優(yōu)狀態(tài)。對(duì)于TSP問(wèn)題，不同的問(wèn)題規(guī)模，的曲子也不盡相同。一般來(lái)說(shuō)， 【0.1,0.5】時(shí)，性能的

91、算法較好。</p><p>　　2.6.5 總信息量（DBQ）</p><p>　　總信息量DBQ為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)路徑上的信息素總量，在基本一群算法中他是一個(gè)產(chǎn)量。一般的理解是：總信息量DBQ越大，則在螞蟻已經(jīng)走過(guò)的路徑上信息素的累積越快，可以加強(qiáng)蟻群搜素時(shí)的正反饋性能，有助于算法的快速收斂。DBQ過(guò)小，則信息素濃度增長(zhǎng)太慢，正反饋信息太少，使算法難以收斂。研究表明：</p

92、><p>　　在蟻周模型中，由于TSP的規(guī)模不同，路徑長(zhǎng)度各不相同，如果讀不通的TSP使用相同的DBQ值，則信息素總量更新尺度是不同的，最終修改信息素的程度存在很大不穩(wěn)定性。DBQ的取值應(yīng)與說(shuō)處理的TSP的規(guī)模相對(duì)應(yīng)，確保信息素總量更新在可控制范圍內(nèi)。在小規(guī)模TSP問(wèn)題中，DBQ=100是大多數(shù)研究學(xué)者認(rèn)為所公認(rèn)的較好值。</p><p>　　第3章改進(jìn)的蟻群算法</p>&l

93、t;p>　?。?）采用輪盤賭選擇代替了基本框架中通過(guò)啟發(fā)式函數(shù)和信息素選擇路徑，改進(jìn)蟻群算法的信息素傳遞參數(shù)，讓整個(gè)算法更快速的找到最優(yōu)解。</p><p>　?。?）最大最小優(yōu)化主要作了如下改進(jìn)：</p><p>　　A：每次迭代結(jié)束后，只有最優(yōu)解所屬路徑上的信息被更新，從而更好地利用了歷史信息；</p><p>　　B：為了避免算法過(guò)早收斂于并非全局最優(yōu)的

94、解，將各條路徑可能的外激素濃度限制于【T_min,T_max】,超出這個(gè)范圍的值被強(qiáng)制設(shè)為T_min或者是T_max，可以有效的避免某條路徑上的信息量遠(yuǎn)大于其余路徑，使得所有螞蟻都集中到同一條路徑上，從而使算法不再擴(kuò)散；</p><p>　　C：初始時(shí)刻，各條路徑上外激素的其實(shí)濃度設(shè)為T_max，在算法的初始時(shí)刻，P（0<p<1，信息素政法系數(shù)）取較小值時(shí)，算法有更好的發(fā)現(xiàn)較好解的能力。所有螞蟻完成一

95、次迭代后，按下式對(duì)路徑上的信息作全局更新：</p><p>　　(t+1)=(1-) (t)+ (t), (0,1)</p><p><b>　　= </b></p><p>　　允許更新的路徑可以全局最優(yōu)解，或本次迭代的最優(yōu)解。實(shí)踐證明，逐漸增加全局最優(yōu)解的使用頻率，會(huì)使該算法獲得較好的性能。</p><p

96、>　　3.1 輪盤賭選擇</p><p>　　3.1.1 輪盤賭選擇基本思想</p><p>　　個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中遺傳到下一代群體的概率為：</p><p><b>　　= / </b></p><p>　　3.1.2 輪盤賭選擇工作

97、過(guò)程</p><p>　　設(shè)想群體全部個(gè)體的適當(dāng)性分?jǐn)?shù)由一張餅圖來(lái)代表 (見(jiàn)圖)。</p><p>　　群體中每一染色體指定餅圖中一個(gè)小塊。塊的大小與染色體的適應(yīng)性分?jǐn)?shù)成比例，適應(yīng)性分?jǐn)?shù)愈高，它在餅圖中對(duì)應(yīng)的小塊所占面積也愈大。為了選取一個(gè)染色體，要做的就是旋轉(zhuǎn)這個(gè)輪子，直到輪盤停止時(shí)，看指針停止在哪一塊上，就選中與它對(duì)應(yīng)的那個(gè)染色體。</p><p><b&

98、gt;　　舉例：</b></p><p>　　輪盤賭選擇法的選擇概率計(jì)算表</p><p>　　若產(chǎn)生隨機(jī)數(shù)為0.81，則6號(hào)個(gè)體被選中。</p><p><b>　　實(shí)現(xiàn)代碼：</b></p><p>　　//*//輪盤選擇，選擇第一個(gè)大于隨機(jī)數(shù)的點(diǎn)</p><p>　　double

99、 dbTemp=0.0;</p><p>　　if (dbTotal > 0.0) //總的信息素值大于0</p><p><b>　　{</b></p><p>　　dbTemp=rnd(0.0,dbTotal); //取一個(gè)隨機(jī)數(shù)</p><p>　　for (int i=0;i<N_CITY_COUNT

100、;i++)</p><p><b>　　{</b></p><p>　　if (m_nAllowedCity[i] == 1) //城市沒(méi)去過(guò)</p><p><b>　　{</b></p><p>　　dbTemp=dbTemp-prob[i]; //這個(gè)操作相當(dāng)于轉(zhuǎn)動(dòng)輪盤</p>

101、<p>　　if (dbTemp < 0.0) //輪盤停止轉(zhuǎn)動(dòng)，記下城市編號(hào)，直接跳出循環(huán)</p><p><b>　　{</b></p><p>　　nSelectedCity=i;</p><p><b>　　break;</b></p><p><b>　　}<

102、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　3.2 MAX_MIN ACO</p><p>　　3.2.1 MAX_MIN算法的框架結(jié)

103、構(gòu)</p><p>　　Max-Min算法非常類似于Min-Min算法。同樣要計(jì)算每一任務(wù)在任一可用機(jī)器上的最早完成時(shí)間，不同的是Max-Min算法改進(jìn)了信息素更新策略，增加了限制條件：</p><p><b>　?。?）信息素更新</b></p><p>　　在蟻群算法中，對(duì)所有螞蟻?zhàn)哌^(guò)的路徑都進(jìn)行信息素更新；而在MAX_MIN螞蟻算法中，只

104、對(duì)在當(dāng)前循環(huán)中找到最優(yōu)解或是自實(shí)驗(yàn)以來(lái)找到的最優(yōu)解的螞蟻進(jìn)行信息素更新，更新公式為：</p><p>　　= （a）</p><p>　　= (b)</p><p>　　在公式(a)(b)中， 表示迭代最優(yōu)解或全局最優(yōu)解。在本文的所講解的內(nèi)容，所采用的是每次迭代的全局最優(yōu)解。</p><p>　?。?）信息素

105、大小的限制</p><p>　　在每個(gè)解元素上的信息被限定在一個(gè)區(qū)間（ , ）內(nèi)，在更新信息素的時(shí)候，信息素的量如果超過(guò)了這個(gè)范圍，就要做相應(yīng)的限制：</p><p>　　如果 >= ,，則設(shè)置 = ；</p><p>　　如果 <= ，則設(shè)置 = ；</p><p>　　和 的值可以分別由以下公式得到：</p>

106、<p><b>　　= </b></p><p>　　其中： 是得到的最優(yōu)解路徑長(zhǎng)度。</p><p>　　螞蟻完成一次搜索，即為一次迭代。設(shè)迭代次數(shù)為n<=2時(shí)，取 ＝ /20；當(dāng)?shù)螖?shù)n>2時(shí)，則由以下公式來(lái)計(jì)算：</p><p><b>　　= </b></p><p&

107、gt;　　式中 =n/2， =0.5</p><p>　?。?）信息素初始值設(shè)為 </p><p>　　3.2.2 MAX_MIN 算法流程圖</p><p>　　MAX_MIN改進(jìn)算法與基本的蟻群算法的其他地方一致，僅僅是更新信息素的策略不同，以下是MAX_MIN更新信息素的函數(shù)流程圖：</p><p><b>　　是<

108、/b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p>　　第4章蟻群算法在車輛路徑問(wèn)題中的應(yīng)用</p><p>　　4.1 車輛路徑問(wèn)題簡(jiǎn)介</p&g

109、t;<p>　　4.1.1 車輛路徑問(wèn)題定義</p><p>　　車輛路徑問(wèn)題（VRP）是Dantzig和Ramser于1959年提出的，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。</p><p>　　車

110、輛路線問(wèn)題自1959年提出以來(lái)，一直是網(wǎng)絡(luò)優(yōu)化問(wèn)題中最基本的問(wèn)題之一，由于其應(yīng)用的廣泛性和經(jīng)濟(jì)上的重大價(jià)值，一直受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注。車輛路線問(wèn)題可以描述如下（如圖）： </p><p><b>　　VRP示意圖</b></p><p>　　設(shè)有一場(chǎng)站（depot），共有M 輛貨車，車輛容量為Q，有N位顧客（customer），每位顧客有其需求量D。車輛從場(chǎng)站出發(fā)

111、對(duì)客戶進(jìn)行配送服務(wù)最后返回場(chǎng)站，要求所有顧客都被配送，每位顧客一次配送完成，且不能違反車輛容量的限制，目的是所有車輛路線的總距離最小。車輛路線的實(shí)際問(wèn)題包括配送中心配送、公共汽車路線制定、信件和報(bào)紙投遞、航空和鐵路時(shí)間表安排、工業(yè)廢品收集等。</p><p>　　4.1.2 車輛路徑問(wèn)題分類</p><p>　　根據(jù)研究的重點(diǎn)不同，VRP存在多種分類方式：</p><p

112、>　　（a）按一直信息的特征，可分為確定性VRP和不確定性VRP，其中不確定性VRP可進(jìn)一步分為隨機(jī)車輛路徑問(wèn)題（SVRP）和模糊車輛路徑（PVRP）；</p><p>　　（b）按約束條件，可以分為帶有容量限制的車輛路徑問(wèn)題（CVRP），帶有時(shí)間距離約束的車輛路徑問(wèn)題（DVRP）以及帶有時(shí)間窗的車輛路徑問(wèn)題（VRPTW）；</p><p>　?。╟）按需求是否可以分割，可以分為可分

113、割的車輛路徑問(wèn)題和不可分割的車輛路徑問(wèn)題；</p><p>　?。╠）按每個(gè)顧客需求量是否超過(guò)車的容量來(lái)分，可以分為滿載車輛路徑和非滿載車輛路徑問(wèn)題；</p><p>　?。╡）按配送中心的多少來(lái)分可以分為但車場(chǎng)車輛路徑問(wèn)題（SVRP）。即一般車輛路徑問(wèn)題（VRP），以及多車場(chǎng)車輛路徑問(wèn)題（MVRP），其中MVRP又可以根據(jù)是否每輛車都有固定的重點(diǎn)車場(chǎng)分為重點(diǎn)車場(chǎng)固定的車輛路徑問(wèn)題和重點(diǎn)車

114、場(chǎng)不固定的開放式車輛路徑問(wèn)題（OVRP）；按優(yōu)化目標(biāo)分，又可以分為單目標(biāo)問(wèn)題和多目標(biāo)問(wèn)題；按路由過(guò)程中相關(guān)信息是否改變，又可以分為動(dòng)態(tài)VRP和靜態(tài)VRP。</p><p>　　4.2 車輛路徑問(wèn)題的求解算法</p><p>　　由于情況不同，VRP數(shù)學(xué)模型夠早及求解算法也有較大的差別。目前有關(guān)VRP模型的研究已經(jīng)取得了較大的成果。綜合過(guò)去的相關(guān)研究，VRP模型基本可以分為圖模型、數(shù)學(xué)模型

115、和仿真模型。VRP的求解算法非常豐富，基本可以分為緊缺算法和iq法師算法兩大類。求解VRP的啟發(fā)式算法有不同的分類方法。</p><p>　　4.2.1 精確算法</p><p>　　精確算法指可求出最優(yōu)解的算法。到目前為止，已提出的精確算法種類較多，有分支定界法、割平面法、整數(shù)規(guī)劃算法和動(dòng)態(tài)規(guī)劃算法等。</p><p>　　另外，還有的認(rèn)為精確算法指股東認(rèn)購(gòu)配

116、股，可認(rèn)購(gòu)數(shù)量不足1股的部分按照精確算法原則處理。即先按照配售比例和每個(gè)賬戶股數(shù)計(jì)算出可認(rèn)購(gòu)數(shù)量 的整數(shù)部分；對(duì)于計(jì)算出不足1股的部分（尾數(shù)保留三位小數(shù)），將所有賬戶按照尾數(shù)從大到小的順序進(jìn)位（尾數(shù)相同則隨機(jī)排序），直至每個(gè)賬戶獲得的可配股數(shù) 量加總與可配售總量一致。</p><p>　　另外關(guān)于精確算法原則取整，其實(shí)舉個(gè)例子就明白了： </p><p>　　假設(shè)有共有100手債券發(fā)行，四

117、個(gè)人認(rèn)購(gòu) ：</p><p>　　第1人認(rèn)購(gòu)25.8手，第2人認(rèn)購(gòu)25.6手，第3人認(rèn)購(gòu)25.4手，第4人認(rèn)購(gòu)25.2手 ，結(jié)果是每人25手。 </p><p>　　再假設(shè)有共有101手債券發(fā)行，四個(gè)人認(rèn)購(gòu) ：</p><p>　　第1人認(rèn)購(gòu)25.8手，第2人認(rèn)購(gòu)25.6手，第3人認(rèn)購(gòu)25.4手，第4人認(rèn)購(gòu)25.2手，結(jié)果是第1人26手，其他人25手。 </p