基于蟻群算法的物流軟件的實(shí)現(xiàn)

1、基于蟻群算法的物流軟件的實(shí)現(xiàn)目 錄1引言- 1 -2算法部分- 1 -21簡(jiǎn)介- 1 -22 模型- 2 -23 算法的實(shí)現(xiàn)設(shè)計(jì)- 3 -24 螞蟻算法的優(yōu)點(diǎn)與不足- 4 -241 優(yōu)勢(shì)- 4 -242 不足- 4 -243 改進(jìn)的方法：優(yōu)選各種參數(shù)- 4 -244 優(yōu)選參數(shù)- 4 -3系統(tǒng)部分- 5 -31 軟件結(jié)構(gòu)：- 5 -32 軟件的實(shí)現(xiàn)- 6 -321 工具與原理- 6 -322 特點(diǎn)與實(shí)現(xiàn)原理- 6 -3221 核心算法使用了MatLab生成的動(dòng)態(tài)鏈接庫(kù)- 6 -3222 顯示坐標(biāo)系相對(duì)于用戶透明- 8 -3223 消除閃爍- 9 -3224 自定義代價(jià)表達(dá)式- 9 -3225 可

2、設(shè)定界面和默認(rèn)參數(shù)- 10 -3226 可保存地圖- 10 -4小結(jié)- 10 -參考文獻(xiàn)- 11 -附錄(主要代碼)- 12 -基于蟻群算法的物流軟件的實(shí)現(xiàn)【摘 要】隨著經(jīng)濟(jì)的發(fā)展，交流的加強(qiáng)，物流受到越來(lái)越多人的關(guān)注，物流技術(shù)也日新月異。如何使用一種物流技術(shù)來(lái)減小物流的代價(jià)，并且使這種技術(shù)能被大多數(shù)不熟悉計(jì)算機(jī)技術(shù)的物流工作者所使用成為人們關(guān)注的焦點(diǎn)。由于人們過(guò)多的關(guān)注蟻群算法的模型，基于蟻群算法的物流軟件市面上見到的并不多，在實(shí)際應(yīng)用中這類軟件不僅要解決好利用蟻群算法計(jì)算最小代價(jià)的問(wèn)題，還要解決好對(duì)于計(jì)算前后數(shù)據(jù)的可視化的處理，因?yàn)槲覀儾荒芷谕脩魧?duì)于一大堆浮點(diǎn)數(shù)有什么樣好的感覺。本文就從

3、算法和系統(tǒng)兩個(gè)方面介紹了以蟻群算法為核心的物流優(yōu)化軟件的開發(fā)過(guò)程。在計(jì)算模型的選擇上，由于物流配送最終要返回發(fā)貨的城市，從而在路徑上形成一個(gè)回環(huán)，故選用的是比較流行的蟻群算法解決TSP問(wèn)題的模型。用戶坐標(biāo)系選用的是用戶比較熟悉的經(jīng)緯度坐標(biāo)系。通過(guò)整個(gè)軟件系統(tǒng)的運(yùn)作，用戶可以很容易的得到他所期望代價(jià)的最優(yōu)路徑而不必關(guān)心繁雜的計(jì)算過(guò)程?！娟P(guān)鍵字】蟻群算法 物流配送 最優(yōu)路徑 可視化數(shù)據(jù)1引言開發(fā)一套優(yōu)秀的物流軟件，可以加快對(duì)客戶需求的響應(yīng)速度, 提高服務(wù)質(zhì)量, 增強(qiáng)客戶對(duì)物流系統(tǒng)的滿意度, 降低服務(wù)商的運(yùn)營(yíng)成本。近年來(lái)一些新的啟發(fā)式方法在求解此類問(wèn)題上可以獲得較快的收斂速度和較高質(zhì)量的全局解。蟻群

4、算法正是這樣的一種算法，它是由意大利學(xué)者M(jìn)arcoDorigo等提出的一種仿生尋優(yōu)算法，通過(guò)信息素的積累和更新來(lái)尋求最優(yōu)解。蟻群算法主要特點(diǎn)是: 正反饋、分布式計(jì)算、與某種啟發(fā)式算法相結(jié)合。正反饋過(guò)程使得該方法能很快發(fā)現(xiàn)較好解； 分布式計(jì)算使得該方法易于并行實(shí)現(xiàn)；與啟發(fā)式算法相結(jié)合, 使得該方法易于發(fā)現(xiàn)較好解。2算法部分21簡(jiǎn)介較為簡(jiǎn)單的主體的聚集相互作用, 必然會(huì)涌現(xiàn)出復(fù)雜的大尺度行為。遺傳算法之父霍蘭德稱這種現(xiàn)象為突現(xiàn)聚集特性。生物群體的復(fù)雜適應(yīng)性行為就是從組成群體的適應(yīng)性個(gè)體行為中涌現(xiàn)出來(lái)的一種全局性質(zhì)。螞蟻是一類行為簡(jiǎn)單的昆蟲, 只有十分有限的記憶能力。在個(gè)體水平上, 螞蟻的行為帶有隨

5、機(jī)性。但在群體水平上, 蟻群的集體行為卻高度有序。螞蟻依靠集體的智慧, 可完成相當(dāng)復(fù)雜的任務(wù)。螞蟻的覓食行為是動(dòng)物行為學(xué)家非常感興趣的現(xiàn)象。螞蟻搬運(yùn)食物回巢的路上, 分泌一種化學(xué)激素, 以吸引其他螞蟻到這條路上來(lái)。蟻群通過(guò)這種機(jī)制, 可以發(fā)現(xiàn)一條從蟻巢到食物源的最短路徑。假設(shè)在蟻巢和食物源之間, 存在兩條長(zhǎng)度不同的路徑A 和B, 其中路徑A 和B 的長(zhǎng)度不同, 且B 的長(zhǎng)度明顯地大于A的長(zhǎng)度, 那么螞蟻將會(huì)選擇較短的路徑A。一般認(rèn)為, 沿路徑A 找到食物, 然后又從路徑A 返回的螞蟻, 花費(fèi)時(shí)間較少, 將成為第一批攜帶食物回到蟻巢的螞蟻。這樣, 路徑A 首先被螞蟻兩次分泌的化學(xué)激素重復(fù)標(biāo)記。由

6、于這時(shí)路徑A 上化學(xué)激素比路徑B 上的多, 所以隨后出巢和返巢的螞蟻被吸引到A上來(lái)。隨著越來(lái)越多的螞蟻選擇路徑A , 路徑A 上化學(xué)激素的濃度也越來(lái)越大。最后, 幾乎所有螞蟻選擇了路徑A。這一現(xiàn)象首先被Deneubourg所發(fā)現(xiàn)。蟻群算法是根據(jù)以上現(xiàn)象提出的, 它的基本假設(shè)是群體的突現(xiàn)聚集特性。22 模型對(duì)一組給定的城市坐標(biāo),按照盡量少的消耗代價(jià)的原則,求其最佳的排列問(wèn)題。有一個(gè)物流公司要到送貨到n城市去,每個(gè)城市必須去一次且僅能去一次,遍歷所有城市之后回到出發(fā)城市,并且滿足代價(jià)最小的路徑。在最理想的情況下，假設(shè)有n個(gè)城市,每個(gè)城市都有到其他城市的一條加權(quán)邊,而且兩城市i, j間距離Dij =

7、 Dji ,要求出最優(yōu)解,即從( n -1) ! 條路徑搜索出一條,時(shí)間復(fù)雜度為O ( ( n - 1) ! ) ,當(dāng)問(wèn)題規(guī)模從n增加到( n + 1)時(shí),搜索空間會(huì)增加( n- 1)倍,所以當(dāng)問(wèn)題空間較大時(shí),在有限時(shí)間內(nèi),無(wú)法得出最優(yōu)解。在實(shí)際應(yīng)用中,找出接近最優(yōu)解的較優(yōu)解往往能夠滿足實(shí)際需要,如何在減小搜索空間的情況下找出高質(zhì)量的較優(yōu)解,成了研究的方向。利用了蟻群搜索食物的過(guò)程與物流配送問(wèn)題的相似性,通過(guò)人工模擬螞蟻搜索食物的過(guò)程來(lái)求解貨物配送的問(wèn)題。實(shí)際應(yīng)用中,每一個(gè)節(jié)點(diǎn)會(huì)面臨很多的分支選擇,問(wèn)題的求解空間將會(huì)變得很大,以至于窮舉尋找真正的最優(yōu)解變得不可能,這時(shí)用螞蟻算法求出的解往往并不

8、是最優(yōu)解,而是接近最優(yōu)解的較優(yōu)解。設(shè)m 表示蟻群中螞蟻的數(shù)量, n表示城市的數(shù)量, Cij = Cji ( i, j = 1, 2, , n) ,表示城市i和城市j之間的代價(jià),Eij表示城市i和j間的邊，i j ( t) 表示t時(shí)刻在Eij上殘余的信息素的量，ij=1/Cij ,是自定義可調(diào)整的參數(shù),用于調(diào)節(jié)ij和ij的關(guān)系,Pkij表示第k只螞蟻選擇邊Eij的概率, Jk 表示第k只螞蟻還未訪問(wèn)過(guò)的城市,各條路徑上信息量都為0。每只螞蟻將按照（1）式計(jì)算所得的概率,從(1)式可以看出,螞蟻選擇路徑的概率隨著ij增大而增加,隨著Cij的增大而減小。并根據(jù)程序產(chǎn)生的隨機(jī)數(shù),決定下一步的方向,直到

9、完成周游路徑。每當(dāng)所有螞蟻完成一次循環(huán)后,按照(2)式(3) 式對(duì)路徑信息量進(jìn)行更新,式中的kij表示第k只螞蟻在本次循環(huán)中在Eij上留下的信息量,表示信息素蒸發(fā)系數(shù)，其中 (4) 式公式中Q是一常數(shù),表示每只螞蟻周游一遍留下的信息素總量。當(dāng)每只螞蟻都完成一次上述操作時(shí),就稱該算法進(jìn)行了一次周游。循環(huán)以上步驟,直到周游次數(shù)達(dá)到指定次數(shù)或在一定時(shí)間內(nèi)沒有新的更優(yōu)解出現(xiàn)。23 算法的實(shí)現(xiàn)設(shè)計(jì)搜索最優(yōu)解的算法的流程如下：1輸入城市數(shù)據(jù)。2初始化等參數(shù), m , n, Q。3每只螞蟻隨機(jī)分配到各個(gè)城市并開始周游城市。4若一次周游沒完成,選擇下一個(gè)城市。5對(duì)每只螞蟻經(jīng)過(guò)的路徑執(zhí)行局部更新規(guī)則,得到新的最

10、優(yōu)解,并對(duì)最優(yōu)解進(jìn)行更新。6若尚未達(dá)到指定周游次數(shù),轉(zhuǎn)到3。7輸出最優(yōu)解。算法中的核心部分是螞蟻如何選取下一個(gè)城市,詳細(xì)說(shuō)明如下：螞蟻k對(duì)城市i選擇下一步的依據(jù)：根據(jù)(1)式計(jì)算螞蟻選擇不同城市的概率,其中J 表示本次周游尚未訪問(wèn)的城市集合,然后由計(jì)算機(jī)產(chǎn)生隨機(jī)數(shù)rand ( ) ,根據(jù)下面規(guī)則進(jìn)行城市選擇,令p =rand ( ) ，sigma ( pki ) = pkij , (其中j =min ( J ) ) ,然后按照(5)式對(duì)城市進(jìn)行選擇：(5)式24 螞蟻算法的優(yōu)點(diǎn)與不足241 優(yōu)勢(shì)根據(jù)上述蟻群算法的求解流程,可知用螞蟻算法能夠極大的縮小求解搜索范圍,算法復(fù)雜度從O ( ( n -

11、 1) ! )降低到O (NC*m *n2 ) ,由于大規(guī)模的并行計(jì)算,使蟻群算法能夠在較大的空間中搜索理想的解;由于采用正反饋機(jī)制,收斂速度加快;使用構(gòu)造性的貪婪算法,能在搜索的早期階段找到較好的可接受的解。242 不足蟻群算法本質(zhì)上和模擬退火算法、遺傳算法等隨機(jī)搜索算法一樣,容易陷入局部極小點(diǎn),存在擴(kuò)大搜索空間與尋找最優(yōu)解之間的矛盾,仿真實(shí)驗(yàn)表明,當(dāng)搜索空間較小時(shí),難以搜索到滿意解,而若要增大搜索空間以提高搜索到最優(yōu)解的概率,機(jī)器運(yùn)算次數(shù)將迅速增多。243 改進(jìn)的方法：優(yōu)選各種參數(shù)通過(guò)大量仿真實(shí)驗(yàn),發(fā)現(xiàn)諸如信息素的消散速度,在城市數(shù)量一定的情況下,螞蟻的數(shù)量對(duì)于算法的影響都至關(guān)重要。244

12、 優(yōu)選參數(shù)參數(shù)m研究發(fā)現(xiàn),在其他參數(shù)不變的情況下,當(dāng)螞蟻數(shù)量太少,向最優(yōu)解收斂很慢,在重復(fù)同樣代數(shù)情況下,由于螞蟻數(shù)量少,在能導(dǎo)致最優(yōu)路徑的那些邊(優(yōu)選邊)走過(guò)的次數(shù)較少,難以留下較多的信息素,不利于算法迅速向最優(yōu)解收斂,而且當(dāng)優(yōu)選邊在數(shù)代之內(nèi)不能被再次選擇時(shí),其信息素將揮發(fā)殆盡,從而造成之前數(shù)代螞蟻的優(yōu)選結(jié)果浪費(fèi),造成最優(yōu)路徑值的劇烈震蕩。當(dāng)m 值太大,首先,會(huì)增加運(yùn)算量;其次,因?yàn)樵谧畛醯膸状驗(yàn)檫x擇路徑的隨機(jī)性比較大,最初的最優(yōu)值因?yàn)槲浵伓嘁灾劣诘玫綇?qiáng)化的速度太快,容易造成局部最優(yōu)解。參數(shù)當(dāng)太小時(shí), 后代蟻會(huì)受到前輩螞蟻的路線嚴(yán)重影響,早期收斂減慢,后期容易陷入局部最優(yōu), 當(dāng)過(guò)大,初期收

13、斂雖然很快,但早期的優(yōu)選邊會(huì)因?yàn)閾]發(fā)太快而失去,從而影響最優(yōu)解的搜索速度。3系統(tǒng)部分31 軟件結(jié)構(gòu)：我們知道一個(gè)好的軟件必然有一個(gè)好的設(shè)計(jì)，在軟件開始的設(shè)計(jì)過(guò)程中，引入了一個(gè)分層的概念，整個(gè)軟件被從邏輯上分為4個(gè)層次，如圖2-1：（圖3-1）UI 層：負(fù)責(zé)與用戶的交流，它包括地圖的顯示，參數(shù)的輸入等?？梢暬瘮?shù)據(jù)處理層：負(fù)責(zé)把從文件處理層和計(jì)算子層取得的數(shù)據(jù)與供UI層顯示的可視數(shù)據(jù)進(jìn)行相互轉(zhuǎn)化，它包括了一個(gè)計(jì)算子層，用于利用蟻群算法計(jì)算最優(yōu)的路徑，在計(jì)算子層之上有一個(gè)數(shù)據(jù)接口，它負(fù)責(zé)MatLab中使用的數(shù)據(jù)和VC中使用的數(shù)據(jù)間的相互轉(zhuǎn)化。文 件 處 理 層：負(fù)責(zé)把文件中的數(shù)據(jù)載入內(nèi)存中。通 用

14、層：它維護(hù)整個(gè)系統(tǒng)運(yùn)行過(guò)程中的各種數(shù)據(jù)結(jié)構(gòu)，并提供一些通用的方法。在圖2-1中我們可以看到，UI層，可視化數(shù)據(jù)處理層，文件處理層之間是用虛線連接的，這是因?yàn)檫@三個(gè)層次間并沒有實(shí)際的數(shù)據(jù)流，它們之間的數(shù)據(jù)交換都是通過(guò)共享通用層維護(hù)的數(shù)據(jù)來(lái)實(shí)現(xiàn)的，這樣做的目的是為了減小系統(tǒng)的開銷，因?yàn)檫@三個(gè)層次之間傳遞的數(shù)據(jù)流是相當(dāng)龐大的。32 軟件的實(shí)現(xiàn)321 工具與原理該系統(tǒng)使用了Microsoft公司的Visual C+6.0和MathWorks公司的MatLab6.5來(lái)實(shí)現(xiàn)。它的原理是由MatLab生成實(shí)現(xiàn)蟻群算法的DLL（動(dòng)態(tài)鏈接庫(kù)）,VC+則實(shí)現(xiàn)整個(gè)程序的界面，并通過(guò)調(diào)用MatLab生成的DLL實(shí)現(xiàn)利

15、用蟻群算法計(jì)算最優(yōu)路徑的功能。圖2-2為系統(tǒng)的主界面。(圖3-2)322 特點(diǎn)與實(shí)現(xiàn)原理3221 核心算法使用了MatLab生成的動(dòng)態(tài)鏈接庫(kù)Matlab作為當(dāng)今世界上應(yīng)用最為廣泛的數(shù)學(xué)軟件，具有非常強(qiáng)大的數(shù)值計(jì)算、數(shù)據(jù)分析處理、系統(tǒng)分析、圖形顯示甚至符號(hào)運(yùn)算的功能。它是一個(gè)完整的數(shù)學(xué)平臺(tái)，在這個(gè)平臺(tái)上，用戶只需寥寥數(shù)語(yǔ)就可以完成十分復(fù)雜的功能，大大提高了工程分析計(jì)算、圖像處理的效率。但是Matlab強(qiáng)大的功能只能在它所提供的平臺(tái)上才能使用。這樣當(dāng)我們需要將在Matlab下已開發(fā)完畢的蟻群算法應(yīng)用到開發(fā)這個(gè)系統(tǒng)所使用的Visual C+的環(huán)境下時(shí)就帶來(lái)了問(wèn)題，幸好的是MatLab的Compile

16、r可以將*.m文件編譯成*.dll文件嵌入到VC+的程序中，我們按照以下步驟生成DLL：1建立MatLab的編譯環(huán)境，在MatLab命令行下輸入以下命令并按提示完成：Mbuild -setup2使用MatLab的Mcc命令生成DLL：Mcc B csglsharedlib:ACATSPLib ACATSP其中ACATSP是在MatLab下已經(jīng)完成了的實(shí)現(xiàn)蟻群算法的函數(shù)，ACATSPLib是生成的DLL文件(包括引入庫(kù)LIB文件)的文件名，運(yùn)行結(jié)束后生成了很多的文件，其中ACATSPLib.dll，ACATSPLib.lib，ACATSPLib.h是我們所需要的。接下來(lái)，我們按照以下的步驟在VC

17、中使用剛才生成的DLL文件：1配制VC的環(huán)境(1)設(shè)置Include和Library目錄在VC+IDE中選擇Tools->Options->Directories。在Showdirectorisfor：中選擇Includefiles，添加如下兩個(gè)目錄：<Matlab>externinclude<Matlab>externincludecpp在Showdirectorisfor:中選擇Libraryfiles，添加如下兩個(gè)目錄：<Matlab>externlibwin32<Matlab>externlibwin32microsofmsv

18、c6這里假設(shè)<Matlab>為你的Matlab的安裝目錄。這些操作只需要一次，VC+IDE就會(huì)自動(dòng)記錄。自動(dòng)應(yīng)用到每一個(gè)工程（Project）。(2)工程(project)本身的一些設(shè)置在VC+IDE中選擇Project->Setting->C/C+；在Category中選擇CodeGeneration，在Userun-timelibrary中選擇Multithreaded DLL；在Category中選擇Preprocessor，在preprocessordefinitions中添加MSVC,MSWIND,IBMPC；在VC+IDE中選擇Project->Set

19、tings->Lin，在Categories中選擇Input，在Ignorelibraries:中填入：msvcrt.lib；2將剛才MatLab生成的ACATSPLib.dll,ACATSPLib.lib,ACATSPLib.h導(dǎo)入VC工程，并在使用的地方包含頭文件"#include "ACATSPLib.h""3在使用之前還需要對(duì)ACATSPLib.dll進(jìn)注冊(cè)，使用完畢之后需要對(duì)其進(jìn)行釋放。注冊(cè)使用函數(shù)ACATSPLibInitiallize(),釋放使用函數(shù)ACATSPLibTerminate()。4由于MatLab和VC他們對(duì)于矩陣的存儲(chǔ)

20、方式是不同的(MatLab中是先列后行，而VC是先行后列)，而且在生成的ACATSPLib.dll中的函數(shù)所接受和返回的參數(shù)是mxArray 型數(shù)據(jù),因此我們?cè)谑褂脮r(shí)必須把VC和MatLab中的數(shù)據(jù)進(jìn)行相互的轉(zhuǎn)換，具體的轉(zhuǎn)換過(guò)程請(qǐng)參看程序VisualData.cpp中的CalcOptimal()函數(shù)。由于核心的算法是封裝在動(dòng)態(tài)鏈接庫(kù)中的，這使得核心算法獨(dú)立于主程序，換句話說(shuō)，如果要改進(jìn)核心的算法，只需要替換掉主程序調(diào)用的DLL文件即可，使得主程序的修改代價(jià)為零，這便于以后的升級(jí)。3222 顯示坐標(biāo)系相對(duì)于用戶透明經(jīng)緯度坐標(biāo)系是用戶在實(shí)際使用中最熟悉的坐標(biāo)系，而在VC中是不能直接使用這種坐標(biāo)系的

21、，因而在程序中使用了坐標(biāo)的映射機(jī)制，將經(jīng)緯度坐標(biāo)系轉(zhuǎn)化為可以用于顯示的坐標(biāo)系，并且使顯示坐標(biāo)系的縮放和平移相對(duì)與經(jīng)緯度坐標(biāo)系無(wú)關(guān)，從而使得顯示坐標(biāo)系相對(duì)于用戶透明，用戶可以隨意的使用經(jīng)緯度坐標(biāo)系并且對(duì)地圖進(jìn)行縮放和平移。我們首先看一下VC默認(rèn)的坐標(biāo)系，如圖2-3：(圖3-3)下面是我們需要映射的可縮放平移的坐標(biāo)系，如圖2-4：(圖3-4)其中dSize是表征縮放程度的變量；dXVal是表征X向平移程度的變量；dYVal是表征Y向平移程度的變量；rc.Width表示可視區(qū)的寬度；rc.Height表示可視區(qū)的高度。我們使用以下步驟實(shí)現(xiàn)映射：1改變VC默認(rèn)的映射模式，使用以下語(yǔ)句使其X向?yàn)閺淖笙蛴?/p>

22、增加，Y向?yàn)閺南孪蛏显黾?，并且保證可視區(qū)位于坐標(biāo)系的中央：SetMapMode(MM_ANISOTROPIC);SetViewportOrg(rc.left+dSize,rc.bottom-dSize);SetWindowExt(1,-1);2根據(jù)地圖繪制區(qū)大小計(jì)算各城市的顯示坐標(biāo)。3根據(jù)平移程度在地圖繪制區(qū)繪制出各個(gè)城市點(diǎn)。4當(dāng)需要對(duì)地圖進(jìn)行縮放或平移時(shí)只需改變dSize，dXVal，dYVal值即可。3223 消除閃爍在完成使用地圖縮放拖動(dòng)的功能的時(shí)候，發(fā)現(xiàn)在縮放拖動(dòng)的過(guò)程中地圖閃爍現(xiàn)象非常嚴(yán)重，仔細(xì)分析后發(fā)現(xiàn)造成閃爍的主要是這兩個(gè)方面的原因：1在Windows中，當(dāng)窗口由于任何原因需要重

23、繪時(shí)，系統(tǒng)總是先用背景色（在這里是白色）將顯示區(qū)清除，然后才調(diào)用OnPaint進(jìn)行繪圖，而背景色往往與繪圖內(nèi)容反差很大，這樣在短時(shí)間內(nèi)背景色與顯示圖形的交替出現(xiàn)，使得顯示窗口看起來(lái)在閃。2由于要繪制的對(duì)象比較復(fù)雜，系統(tǒng)不能夠在很短的時(shí)間內(nèi)全部繪出，造成了比較大的反差，致使畫面閃爍。那么為了消除閃爍，采用了以下兩個(gè)方法：1重載OnEraseBkgnd(CDC* pDC)。這個(gè)函數(shù)就是用來(lái)處理刷新背景的消息，將所有的繪圖全部繪在背景上，而在OnPaint中不做任何事情，這樣在重繪時(shí)系統(tǒng)就會(huì)使用已經(jīng)繪上地圖的CDC刷新背景，因而沒有反差也就不會(huì)造成閃爍。2使用雙緩沖技術(shù)。首先我在內(nèi)存環(huán)境中建立一個(gè)繪

24、圖區(qū)域，然后在這個(gè)繪圖區(qū)域上繪制復(fù)雜的圖形，等圖形全部繪制完畢的時(shí)候，再一次性的把內(nèi)存中繪制好的圖形復(fù)制到屏幕上，由于這種復(fù)制是非常規(guī)的內(nèi)存對(duì)拷，速度很快，從而消除了閃爍。3224 自定義代價(jià)表達(dá)式要允許用戶自定義表達(dá)式就必須解決好程序?qū)τ谟脩糨斎氲谋磉_(dá)式的處理，在這里，我選用的是以波蘭表達(dá)式的形式計(jì)算表達(dá)式的值，并且在表達(dá)式中支持兩個(gè)變量distance和cost，表達(dá)式的計(jì)算按照以下的步驟進(jìn)行：1對(duì)于表達(dá)式字符串的檢查：檢查輸入的表達(dá)式是否正確，包括括號(hào)是否配對(duì)、庫(kù)函數(shù)是否正確。2將算術(shù)表達(dá)式字符串轉(zhuǎn)化成波蘭表達(dá)式。3求波蘭式的值。4返回計(jì)算得到的表達(dá)式值。具體的計(jì)算步驟參見程序MathS

25、tring.cpp中的注釋。由于允許用戶自定義代價(jià)表達(dá)式，這極大的提高了系統(tǒng)的靈活性，例如：例1：如果用戶不希望從城市A直接到達(dá)城市B，那么他可以設(shè)代價(jià)表達(dá)式為“distance+cost”并且將A到B間的代價(jià)系數(shù)設(shè)為一個(gè)很大的數(shù)（比如999999），這樣運(yùn)行出的結(jié)果就不會(huì)出現(xiàn)從A 到B的直接通路。例2：如果用戶希望以最短的時(shí)間完成整個(gè)陪送的過(guò)程，那么他可以設(shè)置代價(jià)表達(dá)式為“distance/cost”，再將每個(gè)城市間的代價(jià)系數(shù)設(shè)為兩個(gè)城市間的平均速度，這時(shí)的運(yùn)行結(jié)果就會(huì)體現(xiàn)出最短的時(shí)間。以上的例子只是起到拋磚引玉的作用，只要用戶善于開發(fā)利用，就可以實(shí)現(xiàn)很多很復(fù)雜的功能。3225 可設(shè)定界面和

26、默認(rèn)參數(shù)用戶可以根據(jù)自己的喜好設(shè)定界面和默認(rèn)參數(shù)，比如說(shuō)標(biāo)識(shí)城市標(biāo)志的大小和顏色，路徑的顏色等。3226 可保存地圖用戶可以在任何時(shí)候保存已顯示出的地圖，這樣當(dāng)再次察看最優(yōu)路徑的時(shí)候只需要打開保存下來(lái)的地圖圖片即可，不需要用戶重新計(jì)算。4小結(jié)經(jīng)過(guò)一段時(shí)間的設(shè)計(jì)、編碼和測(cè)試，系統(tǒng)能夠按照功能需求正常運(yùn)行，如圖（3-5）為系統(tǒng)運(yùn)行的結(jié)果。（圖3-5）從圖中我們可以看出系統(tǒng)選擇的是一個(gè)依附在所選城市邊緣的環(huán)狀路徑，由于所選用的代價(jià)只是兩個(gè)城市間的距離，根據(jù)經(jīng)驗(yàn)我們知道這類環(huán)狀路徑一般來(lái)說(shuō)是較優(yōu)的。由于起初沒有找到一家真正的物流公司收集需求，該系統(tǒng)不能真正的應(yīng)用于實(shí)際，不過(guò)它的底層功能（包括核心算法的

27、代碼以及數(shù)據(jù)接口等）比較完善，在將來(lái)有需求的時(shí)候可以很容易的進(jìn)行二次開發(fā)而使其商業(yè)化。參考文獻(xiàn) 1 Dorigo M , Caro G D. The ant colony optimization Meta-heuristic. New ldeas in Optimization,1999:1- 27. 2 Dorigo M , Gambardella L M. Ant colonies for the traveling salesman problem. BioSystems,1997,43: 73- 81. 3 Jayaraman V K, KulkarniB D, Karale S,

28、et al. Ant colony framework for optimal design and scheduling of batch plants. Computers and Chemical Engineering, 2000,7 (24) : 1901- 1912. 4 Dorigo M , Bonabeau E, Theraulaz G. Ant algorithms and stigmergy. Future Generation Computer Systems, 2000,6(16): 851- 871. 5 張紀(jì)會(huì), 高齊圣, 徐心和. 自適應(yīng)蟻群算法. 控制理論與應(yīng)用

29、, 2000,5: 181- 182. 6 陳駿堅(jiān), 李臘元. 用新型螞蟻算法求解QoSR 問(wèn)題.武漢理工大學(xué)學(xué)報(bào): 交通科學(xué)與工程版, 2005,29(3) : 342-345.The Realization of logistics Software Based on ACO（WangChao, Anhui Agricultural University, 230036）【Abstract】Along with the economical development, exchange strengthening, logistics receive attention from more

30、and more people, logistics technology also changes everyday. How to use one kind of technology to reduce the cost of logistics? How to make it acceptable for the people who are not familiar with computer employed in logistics? The mentioned questions become the focus of people's attention. Becau

31、se too many people concerned about the ACO model, logistics software based on ACO on the market is not a lot, the practical application of such software is not only resolve calculation for the minimum price by ACO, also solve for the visual data before and after calculation, we can not expect the us

32、er who face to a lot of float have a good feeling. This paper from the algorithms and systems two aspects introduces the development process of logistics software based on ACO. In the calculation model selection, logistics and distribution eventually to return to the consignor city, which formed in

33、the road on a loop, therefore, we select the model which is more popular and used to solve the TSP by ACO. User Coordinate System uses the longitude and latitude coordinates which the users are more familiar with. Through the entire software system, users can easily get the price he expects the opti

34、mal path and does not have to care about complicated calculation process.【Key Words】ACO Logistics Cost Optimal Path Visual Data附錄(主要代碼)蟻群算法（ACATSP.m）%=% Shortest_Route 最優(yōu)路徑% C n個(gè)城市代價(jià)表，n×n的矩陣% NC_max 最大迭代次數(shù)% m 螞蟻個(gè)數(shù)% Alpha 表征信息素重要程度的參數(shù)% Beta 表征啟發(fā)式因子重要程度的參數(shù)% Rho 信息素蒸發(fā)系數(shù)% Q 信息素增加強(qiáng)度系數(shù)%=function Shor

35、test_Route=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%初始化等參數(shù), m , n, Qn=size(C,1);%n表示問(wèn)題的規(guī)模（城市個(gè)數(shù)）D=C;for i=1 : n D(i,i)=eps;endEta=1./D;%Eta為啟發(fā)因子，這里設(shè)為代價(jià)的倒數(shù)Tau=ones(n,n);%Tau為信息素矩陣Tabu=zeros(m,n);%存儲(chǔ)并記錄路徑的生成NC=1;%迭代計(jì)數(shù)器R_best=zeros(NC_max,n);%各代最佳路線L_best=inf.*ones(NC_max,1);%各代最佳路線的長(zhǎng)度L_ave=zeros(NC_max,1);%

36、各代路線的平均長(zhǎng)度while NC<=NC_max%停止條件%每只螞蟻隨機(jī)分配到各個(gè)城市Randpos=;for i=1:(ceil(m/n)Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m)'%開始周游城市for j=2:nfor i=1:mvisited=Tabu(i,1:(j-1);%已訪問(wèn)的城市J=zeros(1,(n-j+1);%待訪問(wèn)的城市P=J;%待訪問(wèn)城市的選擇概率分布Jc=1;for k=1:nif length(find(visited=k)=0J(Jc)=k;Jc=Jc+1;endend%下面計(jì)算

37、待選城市的概率分布for k=1:length(J)P(k)=(Tau(visited(end),J(k)Alpha)*(Eta(visited(end),J(k)Beta);endP=P/(sum(P);%按概率原則選取下一個(gè)城市Pcum=cumsum(P);Select=find(Pcum>=rand);to_visit=J(Select(1);Tabu(i,j)=to_visit;endendif NC>=2Tabu(1,:)=R_best(NC-1,:);end%對(duì)每只螞蟻經(jīng)過(guò)的路徑執(zhí)行局部更新規(guī)則,得到新的最優(yōu)解L=zeros(m,1);for i=1:mR=Tabu(i

38、,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);endL(i)=L(i)+D(R(1),R(n);endL_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);NC=NC+1%對(duì)最優(yōu)解進(jìn)行更新Delta_Tau=zeros(n,n);for i=1:mfor j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);endDelta_Tau(T

39、abu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);endTau=(1-Rho).*Tau+Delta_Tau;%路徑表清空Tabu=zeros(m,n);end%返回結(jié)果Shortest_Route=R_best(Pos(1),:)坐標(biāo)映射(DistributionManageView.cpp)/1建立顯示坐標(biāo)系/2在內(nèi)存中根據(jù)顯示坐標(biāo)和縮放平移程度繪出個(gè)坐標(biāo)點(diǎn)/3將在第2步中繪出的圖形拷貝到屏幕上BOOL CDistributionManageView:OnEraseBkgnd(CDC* pDC) CDC MemDC; MemDC

40、.CreateCompatibleDC(NULL);/建立相兼容的內(nèi)存緩沖CString colorStr;COLORREF color;/城市的顏色GetPrivateProfileString("SYSTEM","CityClr","FFFFFF",colorStr.GetBuffer(10),10,CCommon:iniFilePath);sscanf(colorStr.GetBuffer(colorStr.GetLength(),"%x",&color);CBrush CityColor(color

41、);/已選城市的顏色GetPrivateProfileString("SYSTEM","SelClr","00000FF",colorStr.GetBuffer(10),10,CCommon:iniFilePath);sscanf(colorStr.GetBuffer(colorStr.GetLength(),"%x",&color);CBrush SelectedCityColor(color);GetPrivateProfileString("SYSTEM","PathCl

42、r","00000FF",colorStr.GetBuffer(10),10,CCommon:iniFilePath);sscanf(colorStr.GetBuffer(colorStr.GetLength(),"%x",&color);CPen PathPen(PS_SOLID,1,color);/最優(yōu)路徑的顏色CRect rc;this->GetClientRect(&rc);CBitmap MemBitmap;MemBitmap.CreateCompatibleBitmap(pDC,rc.Width(),rc.He

43、ight();/建立相兼容的位圖CBitmap *pOldBit=MemDC.SelectObject(&MemBitmap);/選擇位圖/以下根據(jù)縮放程度建立顯示坐標(biāo)系（建立的坐標(biāo)系會(huì)保證可視區(qū)位于繪圖區(qū)中央）/*MemDC.SetMapMode(MM_ANISOTROPIC); int length=rc.Width()<rc.Height()?rc.Width():rc.Height();if(CPanelView:dSize>length/2)/縮小程度約束CPanelView:dSize=length/2;MemDC.SetViewportOrg(rc.left+

44、CPanelView:dSize,rc.bottom -CPanelView:dSize);/設(shè)置原點(diǎn)位置MemDC.SetWindowExt(1,-1);/設(shè)置坐標(biāo)系（以一個(gè)象素為增量單位，x向右增大，y向上增大）/*MemDC.FillSolidRect(-CPanelView:dSize,-CPanelView:dSize,rc.Width(),rc.Height(),RGB(255,255,255);/向可視區(qū)填充背景色CVisualData:CalcDispCoor(CRect(rc.left+CPanelView:dSize,rc.top+CPanelView:dSize,rc.r

45、ight-CPanelView:dSize,rc.bottom-CPanelView:dSize);/計(jì)算顯示各城市顯示坐標(biāo)int CitySize=:GetPrivateProfileInt("SYSTEM","CityLogSize",5,CCommon:iniFilePath);/得到城市標(biāo)志的半徑CBrush *pOldBrush;for(int i=0;i<CCommon:CityNum;i+)/根據(jù)平移程度繪出各城市CRect CityRect;CityRect.left=(int)(CCommon:DispCoor.GetData(i,0)-CitySize)+CPanelView:dXVal;CityRect.right=(int)(CCommon:DispCoor.GetData(i,0)+CitySize)+CPanelView:dXVal;CityRect.top=(int)(CCommon:DispCoor.GetData(i,1)+CitySize)+CPanelView:dYVal;CityRect.bottom=(int)(CCom