蟻群算法用于TSP的并行策略及模型_圖文

1、 蟻群算法用于TSP的并行策略及模型作者:劉乃文, 劉方愛(ài), LIU Nai-wen, LIU Fang-ai作者單位:山東師范大學(xué),信息科學(xué)與工程學(xué)院,濟(jì)南,250014刊名: 計(jì)算機(jī)應(yīng)用研究英文刊名:APPLICATION RESEARCH OF COMPUTERS年,卷(期:2007,24(12被引用次數(shù):1次參考文獻(xiàn)(15條1.COLORNI A.DORIGO M.MANIEZZO V Distributed optimization by ant colonies 19912.DOGIGO M Optimization,learning and natural algorithms

2、19923.DORIGO M.MANIEZZO V.COLORNI A Ant system:optimization by a colony of cooperating agents 1996(014.GUTJAHR W J A generalized convergence result for the graph based ant system 2003(045.GUTJAHR W J A graph-based ant system and its convergence 2000(086.BLUM C.ROLI A Metaheuristics in combinatorial

3、optimization:overview and conceptual comparison 2003(038.CARO G D Swarm intelligence 20059.BULLNHEIMER B.KOTSIS G.STRAU C Parallelization strategies for the ant systemTR DOM 9-97 199710.DORIGO M.STUTZLE T Ant colony optimization 200311.段海濱蟻群算法及其在高性能電動(dòng)仿真轉(zhuǎn)臺(tái)參數(shù)優(yōu)化中的應(yīng)用研究 200512.秦玲蟻群算法的改進(jìn)與應(yīng)用學(xué)位論文 200413.CHU

4、 S C.RODDICK J F.PAN J S Parallel ant colony systems 200314.段海濱蟻群算法原理及其應(yīng)用 200515.GENDRON B Parallel computing in combinatorial optimization 2005相似文獻(xiàn)(10條1.學(xué)位論文肇勇改進(jìn)蟻群算法的理論及方法研究2004本文總結(jié)了國(guó)內(nèi)外蟻群算法的研究成果,并提出了新的改進(jìn)蟻群算法.蟻群算法在組合優(yōu)化問(wèn)題的成功應(yīng)用,使得人們開始將焦點(diǎn)又集中在其在連續(xù)優(yōu)化問(wèn)題上的應(yīng)用.目前國(guó)內(nèi)外對(duì)于蟻群算法在連續(xù)優(yōu)化問(wèn)題的應(yīng)用研究成果還很少,但初步研究已顯示出蟻群算法較好的性能.

5、多極值全局優(yōu)化問(wèn)題是本文研究的重點(diǎn),通過(guò)使用一種新的蟻群算法基于網(wǎng)格法的蟻群算法進(jìn)行多個(gè)算例的測(cè)試,證明了該算法的性能較好.可以預(yù)見隨著蟻群算法理論的不斷完善,蟻群算法將越來(lái)越成功地用于連續(xù)優(yōu)化問(wèn)題.本文的主要研究?jī)?nèi)容及成果如下:(1對(duì)全局優(yōu)化方法的基本框架和研究進(jìn)展進(jìn)行了系統(tǒng)的綜述,分別從全局優(yōu)化問(wèn)題的特點(diǎn),全局優(yōu)化方法的構(gòu)造原理和分類,以及現(xiàn)有全局優(yōu)化方法的不足等幾個(gè)方面進(jìn)行了系統(tǒng)的闡述.(2針對(duì)近幾年來(lái)發(fā)展較快的啟發(fā)式搜索算法的理論和方法進(jìn)行了系統(tǒng)的研究.詳細(xì)研究了啟發(fā)式搜索算法的產(chǎn)生、構(gòu)造方法、基本類型等幾個(gè)方面.并概述了幾種元啟發(fā)式算法:蟻群算法、模擬退火法、遺傳算法、禁忌搜索法、混

6、沌優(yōu)化算法等.(3詳細(xì)系統(tǒng)的研究了蟻群算法的發(fā)展現(xiàn)狀,對(duì)于各種改進(jìn)蟻群算法的特點(diǎn)進(jìn)行了分析和對(duì)比,在此基礎(chǔ)之上提出了新的改進(jìn)蟻群算法,并經(jīng)過(guò)程序調(diào)試,其結(jié)果顯示新的改進(jìn)蟻群算法的有較好的性能.在研究用于組合優(yōu)化問(wèn)題的蟻群算法的基礎(chǔ)上,詳細(xì)地闡述了一種用于連續(xù)優(yōu)化問(wèn)題的蟻群算法基于網(wǎng)格的改進(jìn)蟻群算法,通過(guò)測(cè)試多個(gè)算例發(fā)現(xiàn)該方法能夠較好地解決一些多極值函數(shù)的優(yōu)化問(wèn)題.(4對(duì)廣義鄰域搜索算法及其統(tǒng)一結(jié)構(gòu)進(jìn)行了詳細(xì)的闡述和分析,并提出了一種新的混合優(yōu)化算法-ACOSA,即基于蟻群算法和模擬退火法的混合算法.對(duì)于ACOSA混合算法的結(jié)構(gòu)和性能進(jìn)行了分析,經(jīng)過(guò)測(cè)試證明ACOSA混合算法優(yōu)于單純蟻群算法和模

7、擬退火法等元啟發(fā)式算法.2.學(xué)位論文于沛欣一種混合蟻群算法在JSP問(wèn)題中的應(yīng)用研究2008隨著市場(chǎng)競(jìng)爭(zhēng)的日趨激烈,每個(gè)企業(yè)都在尋求更好的生產(chǎn)與運(yùn)作管理方案,以提高企業(yè)的生產(chǎn)、經(jīng)營(yíng)和管理效率,從而提高企業(yè)的核心競(jìng)爭(zhēng)優(yōu)勢(shì)。生產(chǎn)與運(yùn)作管理的核心是車間調(diào)度問(wèn)題能否高效地獲得優(yōu)化解,研究車間調(diào)度問(wèn)題具有很大的理論意義和現(xiàn)實(shí)價(jià)值。車間調(diào)度問(wèn)題是解決如何按時(shí)間的先后分配資源來(lái)完成不同的生產(chǎn)任務(wù),使預(yù)定目標(biāo)最優(yōu)化的問(wèn)題。作業(yè)車間調(diào)度-(JSP問(wèn)題是許多實(shí)際車間調(diào)度問(wèn)題的簡(jiǎn)化模型,是一個(gè)典型的NP一難問(wèn)題。該問(wèn)題具有約束性、非線性、不確定性、大規(guī)模性等復(fù)雜性,已被證明在多項(xiàng)式時(shí)間內(nèi)得不到最優(yōu)值。近年來(lái),對(duì)于Jo

8、b-shop調(diào)度問(wèn)題求解方式主要有啟發(fā)式算法和元啟發(fā)式算法,但各有其不足之處:元啟發(fā)式方法的運(yùn)行時(shí)間長(zhǎng),可獲得較好的解,但其解不穩(wěn)定;啟發(fā)式方法可在較短的時(shí)間內(nèi)得到魯棒性較強(qiáng)的解,但是極少獲得較優(yōu)的解。為了更好地解決作業(yè)車間調(diào)度問(wèn)題,將一些解決此類問(wèn)題較好的算法組合起來(lái)。蟻群算法是通過(guò)信息素的累積和更新收斂于最優(yōu)路徑上,具有分布式并行全局搜索能力,但初期信息素匾乏,求解速度慢。禁忌搜索法(TabuSearch是一種通過(guò)鄰域搜索以獲取最優(yōu)解的方法,能有效地加快解的收斂速度。本文根據(jù)蟻群算法的特點(diǎn),對(duì)蟻群算法進(jìn)行改進(jìn),并將禁忌搜索算法熔入到蟻群算法中,以改善蟻群算法的收斂速度。算法動(dòng)態(tài)融合的思想是

9、首先應(yīng)用改進(jìn)的蟻群算法找到JSP問(wèn)題的可行解,然后應(yīng)用禁忌搜索在可行解的鄰域找到更優(yōu)的解。最后,本文對(duì)JSP問(wèn)題應(yīng)用實(shí)驗(yàn)仿真計(jì)算。結(jié)果表明,改進(jìn)的蟻群算法與禁忌搜索結(jié)合后的混合蟻群算法的收斂速度更高,具有更好的全局收斂性能,能在更少的迭代次數(shù)達(dá)到全局最優(yōu)解,具有更高的收斂速度。3.學(xué)位論文 王珊珊 基于混合蟻群算法的車輛可重復(fù)利用VRPTW問(wèn)題的研究 2006 車輛路徑問(wèn)題(VRP是近年來(lái)交通運(yùn)輸、管理科學(xué)、運(yùn)籌學(xué)、圖論、網(wǎng)絡(luò)分析等學(xué)科研究的熱點(diǎn)問(wèn)題之一，在現(xiàn)實(shí)中有著廣泛的應(yīng)用，例如公交線路 、物流配送、網(wǎng)絡(luò)路由等等。研究此類問(wèn)題具有很強(qiáng)的現(xiàn)實(shí)意義。本文著重研究帶時(shí)間窗的車輛路徑問(wèn)題(VRPT

10、W。VRPTW是在基本VRP上添加時(shí)間窗約束 條件后的一種變化形式，是更為復(fù)雜和特殊的問(wèn)題。VRPTW已被證明是NP-hard組合優(yōu)化問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)，很難得到問(wèn)題的精確解。如何設(shè)計(jì)有 效的算法，從而在較短的計(jì)算時(shí)間快速獲得較好的解，成為現(xiàn)階段研究的重點(diǎn)。 蟻群算法是受自然界中螞蟻覓食行為的啟發(fā)而發(fā)展起來(lái)的一種元啟發(fā)式優(yōu)化算法，是一種本質(zhì)并行的算法，全局搜索能力強(qiáng)。螞蟻之間通過(guò)信息交 流加速了進(jìn)化過(guò)程，利用了正反饋原理和學(xué)習(xí)機(jī)制，具有較強(qiáng)的搜索較優(yōu)解的能力。在基本蟻群算法的基礎(chǔ)上，又逐漸發(fā)展出來(lái)許多新的改進(jìn)算法，并 在二次分配(QAP、網(wǎng)絡(luò)路由、車間調(diào)度(JSP、車輛路徑(VRP等組合優(yōu)

11、化問(wèn)題的求解中取得了很好的效果。 本文基于蟻群算法對(duì)VRPTW問(wèn)題進(jìn)行系統(tǒng)研究。主要工作如下： 首先，介紹VRP問(wèn)題的各種約束條件和分類標(biāo)準(zhǔn)。分析VRPTW問(wèn)題的特性以及構(gòu)造VRPTW問(wèn)題的模型時(shí)須考慮的各種因素如目標(biāo)函數(shù)、約束條件、變量 等等，給出VRPTW問(wèn)題的數(shù)學(xué)模型。對(duì)求解VRPTW問(wèn)題的精確算法、傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法進(jìn)行介紹。接下來(lái)介紹蟻群算法的基本原理、發(fā)展變 化以及在VRP領(lǐng)域的應(yīng)用。 然后，基于對(duì)VRPTW問(wèn)題的研究，結(jié)合物流配送中的實(shí)際情況，提出車輛可重復(fù)利用的VRPTW問(wèn)題(VRPTWRV，建立相應(yīng)的多目標(biāo)數(shù)學(xué)規(guī)劃模型。并在 蟻群系統(tǒng)(Ant ColonySyste

12、m的基礎(chǔ)上，按照優(yōu)先訪問(wèn)服務(wù)開始時(shí)間較早、服務(wù)所需時(shí)間較短以及關(guān)窗時(shí)間較早的客戶的原則，設(shè)計(jì)相應(yīng)的啟發(fā)式因子 和螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則；結(jié)合最大最小螞蟻系統(tǒng)(MMAS、基于排序的螞蟻系統(tǒng)(ASRank的優(yōu)點(diǎn)，并引入自適應(yīng)機(jī)制，動(dòng)態(tài)調(diào)整信息素的揮發(fā)系數(shù)，設(shè)計(jì) 相應(yīng)的信息素更新策略，既加強(qiáng)對(duì)每次迭代最優(yōu)解的利用，又避免過(guò)早陷入局優(yōu)，從而兼顧算法的收斂速度和全局性。根據(jù)客戶服務(wù)結(jié)束時(shí)間較早優(yōu)先 的原則構(gòu)造較好的初始解。使用候選表來(lái)加快搜索速度。在算法中加入局部搜索階段，在所有螞蟻都構(gòu)造完解之后信息素全局更新之前，使用在求解 VRPTW問(wèn)題上非常有效的幾種局部搜索方法如2-opt*、or-opt、CROS

13、S-exchange等，并在or-opt中結(jié)合GENI-exchange算子的思想，來(lái)對(duì)螞蟻構(gòu)造的解進(jìn) 行改進(jìn)，將元啟發(fā)式算法和局部搜索方法的優(yōu)點(diǎn)結(jié)合起來(lái)，設(shè)計(jì)出求解VRPTWRV問(wèn)題的混合蟻群算法(HACO-VRPTWRV。最后，進(jìn)行大量的數(shù)據(jù)仿真實(shí)驗(yàn)。 研究在不同的參數(shù)組合下HACO-VRPTWRV算法性能的變化，確定較好的參數(shù)組合和取值范圍。比較不同的初始解生成策略對(duì)算法性能的影響。研究解的多 樣性。對(duì)比加入局部搜索過(guò)程前后算法的收斂速度和求得的解的質(zhì)量，以及車輛可重復(fù)利用和不可重復(fù)利用下使用的車輛數(shù)和總運(yùn)行時(shí)間、等待時(shí)間、 行駛時(shí)間等等。實(shí)驗(yàn)結(jié)果表明，本文所設(shè)計(jì)的算法是有效的，具有較快

14、的收斂速度，解的全局性也較好。 4.學(xué)位論文 羅旭輝 應(yīng)用于TSP問(wèn)題的蟻群優(yōu)化算法參數(shù)研究 2007 基于自然的元啟發(fā)式算法一直是人工智能領(lǐng)域中一個(gè)非常重要的研究課題，在以往的研究工作中，學(xué)者們提出了神經(jīng)網(wǎng)絡(luò)，模擬退火，遺傳算法等 許多優(yōu)秀的元啟發(fā)式算法，并在解決各類問(wèn)題時(shí)取得了良好的效果。而作為一種較新穎的啟發(fā)式算法，蟻群算法自上個(gè)世紀(jì)九十年代初誕生以來(lái)，一直 受到研究人員的關(guān)注。蟻群算法在優(yōu)化求解許多問(wèn)題時(shí)都能夠取得很好的效果，特別是在對(duì)一些離散問(wèn)題求解時(shí)的表現(xiàn)尤其突出。 然而，時(shí)至今日蟻群算法還是存在一些內(nèi)在的問(wèn)題有待解決。和許多其他的啟發(fā)式算法一樣，蟻群算法的一個(gè)缺點(diǎn)在于，算法的優(yōu)化

15、性能往往取決 于對(duì)于算法控制參數(shù)的取值，這些取值在以往的工作中往往是非常機(jī)械的，各個(gè)參數(shù)的取值也是獨(dú)立的，如果取值不當(dāng)，蟻群算法將容易陷入局部最優(yōu) ，并且優(yōu)化性能也不理想。 本文對(duì)以TSP問(wèn)題為優(yōu)化對(duì)象的蟻群優(yōu)化算法ACS進(jìn)行參數(shù)研究，分析各個(gè)控制參數(shù)在優(yōu)化過(guò)程中對(duì)算法的影響，以及某些參數(shù)之間的關(guān)系。從而制 定一種有效的參數(shù)預(yù)設(shè)規(guī)則，在保持算法優(yōu)化性能的前提下，降低算法參數(shù)設(shè)置的復(fù)雜度。本文的工作主要可以分為四個(gè)部分，第一部分，回顧了一些 的經(jīng)典的蟻群算法的優(yōu)化性能及其應(yīng)用領(lǐng)域，同時(shí)研究了它們參數(shù)設(shè)置的規(guī)則。第二部分，描述ACS算法，研究收斂狀態(tài)變化對(duì)優(yōu)化性能的影響。第三部 分，通過(guò)分析算法優(yōu)

16、化原理，研究算法各個(gè)參數(shù)在迭代過(guò)程中對(duì)路徑構(gòu)建的作用，選取具體的預(yù)設(shè)參數(shù)。第四部分，進(jìn)行ACS算法的仿真試驗(yàn)，研究參數(shù) 對(duì)優(yōu)化過(guò)程的影響，以及參數(shù)之間的關(guān)系，制定一種有效的參數(shù)預(yù)設(shè)規(guī)則。本文的研究工作表明，參數(shù)預(yù)設(shè)規(guī)則應(yīng)用于不同的TSP問(wèn)題實(shí)例時(shí)都能取得較 好的效果，并且對(duì)蟻群算法的參數(shù)研究具有很高的發(fā)展價(jià)值。 5.學(xué)位論文 孫海鷹 蟻群算法的理論與性能研究 2009 蟻群優(yōu)化算法是一種新型的求解復(fù)雜優(yōu)化問(wèn)題的元啟發(fā)式算法，它是由意大利學(xué)者M(jìn).Dorigo等人受到自然界中真實(shí)蟻群集體行為的靈感而首先提出 來(lái)的，并用來(lái)解決離散優(yōu)化問(wèn)題。由于蟻群算法具有穩(wěn)健性、全局性、普遍性、分布式計(jì)算等優(yōu)點(diǎn)，其

17、理論研究不斷深入，應(yīng)用領(lǐng)域不斷擴(kuò)大。大量實(shí) 驗(yàn)結(jié)果表明，它在解決許多組合優(yōu)化問(wèn)題時(shí)都能表現(xiàn)出較好的求解能力，經(jīng)過(guò)了眾多國(guó)內(nèi)外學(xué)者不斷地對(duì)其進(jìn)行擴(kuò)展和改進(jìn)，蟻群算法正經(jīng)歷著一個(gè)不 斷發(fā)展和完善的過(guò)程。 雖然通過(guò)對(duì)大量應(yīng)用問(wèn)題的求解，已經(jīng)顯示出蟻群優(yōu)化算法的高效性，但它的成功主要在實(shí)驗(yàn)層次上，很少有理論來(lái)解釋利用蟻群算法為什么能夠 成功地解決這些問(wèn)題。它能否保證所得到的解一定是全局最優(yōu)解，還有什么問(wèn)題利用蟻群算法不能解決，對(duì)于能夠解決的問(wèn)題，它的時(shí)間復(fù)雜性到底有 多大。因此有必要研究蟻群優(yōu)化算法的欺騙性問(wèn)題。由于蟻群算法具有本質(zhì)上的并行特性，我們需要研究如何高效率地對(duì)它進(jìn)行并行化，如何平衡通信 開

18、銷與加速比之間的關(guān)系。蟻群算法的一個(gè)主要缺點(diǎn)是不能直接解決連續(xù)優(yōu)化問(wèn)題。以往解決此類問(wèn)題的方案，大部分改變了蟻群優(yōu)化算法的基本結(jié)構(gòu) ，不能充分發(fā)揮蟻群優(yōu)化算法的正反饋機(jī)制的優(yōu)勢(shì)。因此有必要研究在解決連續(xù)優(yōu)化問(wèn)題時(shí)該如何保持本質(zhì)模型的不變，如何充分利用信息素和啟發(fā)式 信息，保證解的精確性的同時(shí)能加速收斂速度。 本文針對(duì)蟻群算法的上述問(wèn)題，作了下面的研究。 (1研究蟻群算法求解欺騙性問(wèn)題時(shí)的收斂性和時(shí)間復(fù)雜度。以n-bit陷阱問(wèn)題為例，證明了蟻群算法一階欺騙性問(wèn)題在一定的信息素初始值條件下 ，不滿足解的收斂性，但滿足值的收斂性。我們證明了，使用信息素帶限的蟻群算法MMAS求解n-bit陷阱問(wèn)題達(dá)到

19、最優(yōu)解的時(shí)間復(fù)雜度為 O(n2m.logn，這里n為問(wèn)題的規(guī)模，m為螞蟻的個(gè)數(shù)。同時(shí)，我們的實(shí)驗(yàn)結(jié)果也驗(yàn)證了上述結(jié)論的正確性。 (2提出了一種MPP上的自適應(yīng)的并行蟻群算法PACO。該算法在兩個(gè)方面進(jìn)行了重要改進(jìn)來(lái)加強(qiáng)算法的性能。一方面，我們提出一種處理機(jī)之間的信 息交流策略，使得每個(gè)處理機(jī)可自適應(yīng)地選擇另外一個(gè)處理機(jī)來(lái)交流信息并更新信息素。另一方面，我們還提出一種根據(jù)解的多樣性來(lái)自適應(yīng)地調(diào)節(jié)信 息交流周期的方法，以在加強(qiáng)優(yōu)化能力的同時(shí)避免早熟收斂，以增加解的多樣性。我們對(duì)并行蟻群算法PACO值的收斂性進(jìn)行了分析與證明。我們用標(biāo)準(zhǔn) 的旅行商問(wèn)題在大規(guī)模并行機(jī)上做了測(cè)試，實(shí)驗(yàn)結(jié)果表明，我們算法在

20、收斂速度，加速比，穩(wěn)定性和準(zhǔn)確性各方面都要優(yōu)于別的并行蟻群算法。 (3提出了一種用蟻群算法求解連續(xù)空間優(yōu)化問(wèn)題的方法。該方法保持了基本蟻群算法的基本框架，將傳統(tǒng)蟻群算法中螞蟻由解分量的信息素和啟發(fā) 式的乘積值按比例來(lái)決定取值概率的方式，改為根據(jù)連續(xù)的概率分布函數(shù)來(lái)取值。我們還將函數(shù)在各個(gè)維上的極值點(diǎn)方向作為螞蟻搜索的啟發(fā)式信息。 在標(biāo)準(zhǔn)測(cè)試函數(shù)上的試驗(yàn)結(jié)果顯示，我們的算法與其他類似的算法相比，不但具有較快的收斂速度，而且能夠有效地提高解的精確性，增強(qiáng)了算法的穩(wěn) 定性。 6.學(xué)位論文 陳佑健 蟻群算法的研究及在網(wǎng)絡(luò)路由優(yōu)化上的應(yīng)用 2005 蟻群算法是一種新型的用于求解組合優(yōu)化或函數(shù)優(yōu)化問(wèn)題的元

21、啟發(fā)式算法,其基本思想是借用生物界的螞蟻群體覓食機(jī)理,將每個(gè)螞蟻看作一個(gè)智能 體,作為智能群體的蟻群,其覓食過(guò)程顯現(xiàn)出高度的并行性、正反饋性和魯棒性,以此為基礎(chǔ)的蟻群算法也具有這樣一些特點(diǎn).因此,蟻群算法的研究無(wú)論從 理論上還是實(shí)用上,都具有較高的價(jià)值.本文首先分析了蟻群算法的原理與模型,介紹了算法的特點(diǎn)和研究現(xiàn)狀,通過(guò)實(shí)驗(yàn)分析了算法中幾個(gè)關(guān)鍵參數(shù)的選 擇.針對(duì)基本蟻群算法的主要缺陷,如收斂速度慢和易于陷入局部最優(yōu)等問(wèn)題,將用于求解組合優(yōu)化問(wèn)題的基本蟻群算法進(jìn)行了改進(jìn).首先,在概率選擇上采 用了確定性與隨機(jī)性相結(jié)合的選擇原則;其次,由于基本蟻群算法初期時(shí)各條路徑上的信息素?cái)?shù)量相同,導(dǎo)致算法的初

22、期求解速度緩慢,因此提出了分區(qū)搜 索的思想,使各條路徑上的信息素在初期有所差別,加速算法的收斂;第三,結(jié)合局部與全局信息素調(diào)整策略對(duì)路徑上的信息素進(jìn)行動(dòng)態(tài)更新;第四,對(duì)與信 息素相關(guān)的一些參數(shù)進(jìn)行了自適應(yīng)改變;最后,引入遺傳算法中的變異思想,以擴(kuò)大解的搜索空間.針對(duì)蟻群算法在求解連續(xù)優(yōu)化問(wèn)題上相對(duì)較弱的特點(diǎn),提 出了基于網(wǎng)格劃分的蟻群算法,將傳統(tǒng)的用于求解離散空間優(yōu)化問(wèn)題的蟻群算法進(jìn)行了擴(kuò)展.在應(yīng)用研究上,分析了網(wǎng)絡(luò)路由優(yōu)化問(wèn)題,研究了基于蟻群算 法的IP網(wǎng)絡(luò)QoS單播路由;討論了基于蟻群算法的一些其它應(yīng)用.通過(guò)算例對(duì)所提出的改進(jìn)的蟻群算法進(jìn)行了仿真驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,本文提出的改進(jìn)算法 是有

23、效和可行的;在連續(xù)函數(shù)優(yōu)化上和基于蟻群算法的網(wǎng)絡(luò)路由優(yōu)化等應(yīng)用上也進(jìn)行了實(shí)驗(yàn)仿真.本課題旨在為推進(jìn)蟻群算法的理論研究和應(yīng)用研究起到 一定的作用. 7.學(xué)位論文 高磊 基于蟻群算法的帶能力約束的車輛路徑問(wèn)題研究 2007 車輛路徑問(wèn)題(Vehicle Routing Problem，VRP是近年來(lái)交通運(yùn)輸、管理科學(xué)、運(yùn)籌學(xué)、圖論、網(wǎng)絡(luò)分析等學(xué)科研究的熱點(diǎn)問(wèn)題之一，在現(xiàn)實(shí)中有 著廣泛的應(yīng)用，例如公交線路、物流配送、網(wǎng)絡(luò)路由等等。研究此類問(wèn)題具有很強(qiáng)的現(xiàn)實(shí)意義。本文著重研究帶能力約束的車輛路徑問(wèn)題 (Capabilityconstrained Vehicle Routing Problem，CVRP

24、，CVRP是在基本VRP上添加能力約束條件后的一種變化形式，是更為復(fù)雜和特殊的問(wèn)題。 VRP已被證明是NPhard組合優(yōu)化問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)，很難得到問(wèn)題的精確解。如何設(shè)計(jì)有效的算法，從而在較短的計(jì)算時(shí)間快速獲得較好的解 ，成為現(xiàn)階段研究的重點(diǎn)。 蟻群算法是受自然界中螞蟻覓食行為的啟發(fā)而發(fā)展起來(lái)的一種元啟發(fā)式優(yōu)化算法，是一種本質(zhì)并行的算法，全局搜索能力強(qiáng)。螞蟻之間通過(guò)信息交 流加速了進(jìn)化過(guò)程，利用了正反饋原理和學(xué)習(xí)機(jī)制，具有較強(qiáng)的搜索能力，近年來(lái)改進(jìn)蟻群算法在在二次分配(QAP、網(wǎng)絡(luò)路由、車間調(diào)度(JSP、車輛 路徑(VRP等組合優(yōu)化問(wèn)題得到廣泛應(yīng)用。 本文基于蟻群算法對(duì)車輛路徑問(wèn)題進(jìn)行系

25、統(tǒng)研究，主要工作如下： 首先，介紹VRP問(wèn)題國(guó)內(nèi)外研究現(xiàn)狀，在對(duì)VRP問(wèn)題從構(gòu)成要素、分類和界定幾個(gè)方面做概述的基礎(chǔ)上，深入探討了VRP問(wèn)題的理論框架：包括從 TSP問(wèn)題到VRP問(wèn)題的描述及模型建立，并對(duì)求解VRP問(wèn)題的精確算法、傳統(tǒng)啟發(fā)式算法和元啟發(fā)式算法進(jìn)行分析和總結(jié)。 然后，介紹蟻群算法的基本原理，分析歸納蟻群算法的主要特點(diǎn)，并對(duì)蟻群算法近年來(lái)的發(fā)展變化做簡(jiǎn)要總結(jié)，最后對(duì)蟻群算法在組合優(yōu)化領(lǐng)域的 應(yīng)用情況，尤其在VRP問(wèn)題上的應(yīng)用情況進(jìn)行概述。 最后，基于對(duì)VRP問(wèn)題的研究，結(jié)合物流配送中的實(shí)際情況，建立帶能力約束車輛路徑問(wèn)題(CVRP數(shù)學(xué)規(guī)劃模型。并在基本蟻群算法(Ant Algori

26、thm的基礎(chǔ)上，設(shè)計(jì)出求解CVRP問(wèn)題的簡(jiǎn)易蟻群算法(BA和三個(gè)逐步改進(jìn)的蟻群算法(AA1，AA2，AA3，經(jīng)過(guò)編程調(diào)試和反復(fù)實(shí)驗(yàn)仿真，上述算法 在求解中小規(guī)模CVRP問(wèn)題上效果令人滿意，在較大規(guī)模的CVRP問(wèn)題的快速求解上獲得成功，實(shí)驗(yàn)結(jié)果表明，本文所設(shè)計(jì)的算法是有效的，具有較快的收 斂速度，解的全局性也較好。 8.學(xué)位論文 吳圣寧 嵌入式處理器編譯器關(guān)鍵技術(shù)研究 2007 嵌入式系統(tǒng)通常對(duì)性能、實(shí)時(shí)性、功耗等有著嚴(yán)格的要求，需要非常高效的機(jī)器代碼。因此，嵌入式軟件開發(fā)常采用匯編語(yǔ)言。但匯編語(yǔ)言編程費(fèi) 時(shí)、調(diào)試?yán)щy，而且代碼難以移植。嵌入式系統(tǒng)的廣泛應(yīng)用和嵌入式軟件規(guī)模的不斷擴(kuò)大，決定了用高

27、級(jí)語(yǔ)言代替匯編語(yǔ)言進(jìn)行嵌入式軟件開發(fā)是必然 趨勢(shì)。但使用高級(jí)語(yǔ)言編譯器生成代碼的質(zhì)量和手工編寫的匯編代碼相比還有很大差距，不能滿足嵌入式系統(tǒng)的要求。因此，嵌入式處理器編譯技術(shù)研 究有著非常重要的現(xiàn)實(shí)意義。 傳統(tǒng)編譯技術(shù)通常不能直接適用于嵌入式領(lǐng)域，需要進(jìn)行擴(kuò)展或者設(shè)計(jì)全新的算法。傳統(tǒng)的編譯技術(shù)一般基于規(guī)則的機(jī)器模型，并采用簡(jiǎn)單啟發(fā)式 方法以達(dá)到較快的編譯速度。嵌入式處理器一般具有不規(guī)則的體系結(jié)構(gòu)特征，且在嵌入式環(huán)境中，編譯器生成高質(zhì)量代碼的重要性高于編譯時(shí)間。 本文主要研究了嵌入式處理器編譯技術(shù)的三個(gè)問(wèn)題：嵌入式處理器寄存器分配、多媒體擴(kuò)展指令集的代碼生成、雙指令集處理器多目標(biāo)代碼選擇。 在傳

28、統(tǒng)圖著色寄存器分配方法中，假設(shè)機(jī)器模型具有簡(jiǎn)單的寄存器文件。這些算法采用“degreek”測(cè)試沖突圖結(jié)點(diǎn)是否局部可著色，并通過(guò)特殊 的技巧對(duì)此擴(kuò)展，以適用于不規(guī)則的寄存器文件特征。經(jīng)過(guò)多年研究，此問(wèn)題取得了很大進(jìn)展。但是，傳統(tǒng)圖著色寄存器分配算法在進(jìn)行沖突圖結(jié)點(diǎn)局 部可著色測(cè)試時(shí)，無(wú)法知道鄰居結(jié)點(diǎn)所分配的顏色，只能采取保守的估算，因而降低了編譯生成的代碼質(zhì)量。這是它們難以克服的困難。 傳統(tǒng)樹模式匹配和動(dòng)態(tài)規(guī)劃技術(shù)不能有效利用多媒體處理器的指令集并行，基于傳統(tǒng)并行編譯技術(shù)的擴(kuò)展一般局限于循環(huán)級(jí)并行，且沒(méi)有全局優(yōu)化 標(biāo)量指令和SIMD指令的使用。 傳統(tǒng)編譯技術(shù)一般僅優(yōu)化單一的目標(biāo)，例如性能、功耗。

29、嵌入式系統(tǒng)常需同時(shí)優(yōu)化多個(gè)目標(biāo)。單一目標(biāo)的優(yōu)化對(duì)其它目標(biāo)有何影響，如何在多個(gè)目 標(biāo)間權(quán)衡，需要進(jìn)一步研究。 嵌入式系統(tǒng)的復(fù)雜性決定了需要采用新的方法學(xué)來(lái)研究嵌入式編譯技術(shù)。從元啟發(fā)式算法以及編譯器前后端有機(jī)結(jié)合這兩個(gè)角度來(lái)研究嵌入式編譯 技術(shù)是本文工作的重要思想。 近二十年來(lái)，元啟發(fā)式(Meta-heuristics算法得到廣泛研究。這些算法來(lái)自于人們從自然界得到的啟發(fā)，通過(guò)模擬物理過(guò)程、生物進(jìn)化等自然現(xiàn)象 ，能夠克服經(jīng)典優(yōu)化算法的局限性，系統(tǒng)地搜索問(wèn)題的解空間，較好地解決多種優(yōu)化問(wèn)題。編譯技術(shù)中同樣存在各種優(yōu)化問(wèn)題，尤其在嵌入式環(huán)境中 ，這些問(wèn)題更加復(fù)雜，常使得傳統(tǒng)編譯技術(shù)不能簡(jiǎn)單地適用。元

30、啟發(fā)式算法為求解復(fù)雜的編譯優(yōu)化問(wèn)題提供了廣闊空間。 程序分析是編譯優(yōu)化的基礎(chǔ)。可以把編譯器前端程序分析的優(yōu)勢(shì)和編譯器后端的機(jī)器相關(guān)信息結(jié)合起來(lái)，以適應(yīng)復(fù)雜的嵌入式環(huán)境下編譯技術(shù)研究 的需要。 本文主要研究成果和創(chuàng)新包括以下幾個(gè)方面： 1.針對(duì)嵌入式處理器不規(guī)則寄存器文件體系結(jié)構(gòu)特征，本文提出了一種新的圖著色寄存器分配混合演化算法HMAGRA，突破了傳統(tǒng)圖著色寄存器分 配算法在寄存器沖突圖結(jié)點(diǎn)局部可著色測(cè)試問(wèn)題上難以克服的障礙，為實(shí)現(xiàn)嵌入式處理器寄存器分配器提供了新途徑。本文的HMA-GRA算法主要由遺傳算 法和禁忌搜索算法構(gòu)成，利用Chaitin算法作為前端對(duì)沖突圖進(jìn)行預(yù)處理，對(duì)剩余沖突圖中各

31、結(jié)點(diǎn)按照其類型隨機(jī)分配顏色，計(jì)算結(jié)點(diǎn)間的沖突數(shù)量，通 過(guò)演化過(guò)程逐漸減少圖的總體沖突，最終實(shí)現(xiàn)圖成功著色。此算法不僅可以精確計(jì)算沖突圖結(jié)點(diǎn)是否局部可著色，而且能夠用規(guī)范的寄存器分配模型代 替?zhèn)鹘y(tǒng)算法中的特殊技巧，以適應(yīng)嵌入式處理器寄存器文件不規(guī)則特征帶來(lái)的復(fù)雜性。 2.面向多媒體指令集，本文提出了一種新的SIMD代碼生成算法ICGME。ICG-ME算法擴(kuò)展了傳統(tǒng)的樹模式匹配和動(dòng)態(tài)規(guī)劃技術(shù)，通過(guò)修改代碼生成器 的產(chǎn)生器iburg工具為數(shù)據(jù)流樹結(jié)點(diǎn)的每個(gè)目標(biāo)非終結(jié)符保留多個(gè)匹配規(guī)則，以識(shí)別構(gòu)造SIMD指令的并行操作；在編譯器前端對(duì)存儲(chǔ)操作相對(duì)于向量寄存 器的對(duì)齊狀況進(jìn)行數(shù)據(jù)流分析，并把分析結(jié)果傳遞

32、給編譯器后端，以輔助構(gòu)造SIMD和數(shù)據(jù)重組指令；最終生成多媒體向量指令和非多媒體標(biāo)量指令混合 的匯編代碼。通過(guò)結(jié)合編譯器前端程序分析的優(yōu)勢(shì)和編譯器后端的機(jī)器信息，ICGME算法不僅簡(jiǎn)化了SIMD代碼的生成，而且能夠同時(shí)利用SIMD指令和非 SIMD指令，以生成高質(zhì)量的機(jī)器代碼。 3.以ARMThumb雙指令集處理器為例，本文提出了用元啟發(fā)式算法求解編譯技術(shù)中多目標(biāo)優(yōu)化問(wèn)題的方法學(xué)。本文把雙指令集處理器代碼選擇問(wèn)題 表示為權(quán)衡程序代碼大小和運(yùn)行時(shí)間的多目標(biāo)優(yōu)化問(wèn)題，利用程序profiling技術(shù)為其建立數(shù)學(xué)模型，通過(guò)一種多目標(biāo)蟻群算法結(jié)合子集選擇的方法求解 此問(wèn)題。 4.基于SuIFMachineSUIF編譯器研究框架，我們進(jìn)一步完善了代碼選擇、寄存器分