論基于MPI的并行蟻群算法的應(yīng)用研究

蔣瀚洋

摘要：基于MPI的并行蟻群算法是一種新型、便捷的元啟發(fā)式算法。并行蟻群算法具有天然的并行性，對(duì)于大量的優(yōu)化數(shù)據(jù)的問(wèn)題，并行蟻群算法能夠最大程度的節(jié)省時(shí)間，也可以為蟻群算法的應(yīng)用打好堅(jiān)實(shí)的基礎(chǔ)，該文從蟻群算法的相關(guān)定義及原理、基于MPI的并行蟻群算法的相關(guān)內(nèi)容、蟻群算法并行化的可行性和必要性以及并行蟻群算法在日常生活中的應(yīng)用。通過(guò)對(duì)這些問(wèn)題的研究讓人們對(duì)并行蟻群算法能夠有更加細(xì)致全面的了解，將蟻群算法更好的發(fā)展，以便更好的運(yùn)用到我們的實(shí)際操作中來(lái)。

關(guān)鍵詞：基于MPI；并行蟻群算法；研究

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2012）32-7720-02

隨著并行蟻群算法在人們?nèi)粘Ｉ钪械倪\(yùn)用，人們對(duì)并行蟻群算法的研究也越來(lái)越多，蟻群算法的優(yōu)化具有相當(dāng)優(yōu)良的分布式計(jì)算機(jī)制以及和其它的計(jì)算方法相結(jié)合的特點(diǎn)。所以在很大程度上提高了我們對(duì)于算術(shù)的運(yùn)用，蟻群算法對(duì)于其它算法的發(fā)展也有很大的幫助，自它出現(xiàn)，激發(fā)了其它算法的不斷發(fā)展，豐富了我們?nèi)粘５倪\(yùn)用。同時(shí)，蟻群算法的的應(yīng)用領(lǐng)域非常的廣泛，已經(jīng)擴(kuò)展到我們的工程優(yōu)化、經(jīng)濟(jì)管理、軍事運(yùn)籌等。并行蟻群算法以其自身的優(yōu)勢(shì)已經(jīng)滲透到我們生活的方方面面，通過(guò)準(zhǔn)確的研究可以讓蟻群算法更好的得到運(yùn)用和發(fā)展。

1蟻群算法的相關(guān)定義及原理

1）蟻群算法是一種概率算法，這種形式的算法是將數(shù)據(jù)通過(guò)迭代的方式從而獲得最優(yōu)解，在不停的迭代過(guò)程中，當(dāng)次數(shù)達(dá)到一定程度的時(shí)候，算法就會(huì)收斂，直到算法中的最優(yōu)解的值保持穩(wěn)定。MPI，指的是一個(gè)工業(yè)化的標(biāo)準(zhǔn)，寬泛的意義上來(lái)講只是某種規(guī)范的代表。并不是具體的物體的實(shí)現(xiàn)，是專(zhuān)門(mén)為了大規(guī)模的信息傳遞而制定的。

2）基本蟻群算法原理為螞蟻在運(yùn)動(dòng)的前進(jìn)過(guò)程當(dāng)中，憑借著在路徑上的信息素濃度進(jìn)行的路徑選擇。于此同時(shí)，螞蟻也會(huì)在所經(jīng)過(guò)的路徑上釋放出大量的信息素，對(duì)應(yīng)的在路徑上經(jīng)過(guò)的螞蟻越多，釋放的信息素濃度越高被螞蟻選擇的概率就越大，因此可知，由多數(shù)螞蟻組成的集體行為便可以表現(xiàn)出一種信息正反饋現(xiàn)象。螞蟻群就是通過(guò)這種行為從而找到到達(dá)目的地的最佳方位。蟻群算法求解TSP問(wèn)題的最優(yōu)路徑其實(shí)也就是求解一個(gè)完全加權(quán)的有向圖中的最優(yōu)路徑問(wèn)題。

2基于MPI的并行蟻群算法的相關(guān)內(nèi)容

1）并行蟻群算法的可行性和重要性。蟻群算法其實(shí)從本質(zhì)上來(lái)講就是一個(gè)并行系統(tǒng)。螞蟻算法沿襲的是螞蟻在搜集食物中的并行行為，在這種行為中慢慢的形成了螞蟻尋找食物的最佳和最短的路線，蟻群算法就是運(yùn)用了螞蟻在運(yùn)動(dòng)過(guò)程中的這種并行機(jī)制。蟻群算法在現(xiàn)在可以說(shuō)是一種智能化的優(yōu)化算法，為我們的算術(shù)上帶來(lái)了很多的便利，成功解決了多種復(fù)雜的問(wèn)題。螞蟻算法擁有的這種天然的并行性，讓這種算法的每一次的迭代都是在獨(dú)立的進(jìn)行解的構(gòu)建，也為螞蟻算法的其它機(jī)能打下了良好的基礎(chǔ)但是并行螞蟻算法現(xiàn)在的現(xiàn)實(shí)情況很大限度僅僅只能解決小規(guī)模的問(wèn)題，然而對(duì)于大規(guī)模問(wèn)題的蟻群優(yōu)化算法的研究和應(yīng)用卻不太多。然而在很多地方，螞蟻算法的實(shí)際應(yīng)用問(wèn)題卻是針對(duì)大規(guī)模問(wèn)題有的時(shí)候甚至是超大規(guī)模問(wèn)題，可見(jiàn)，并行螞蟻算法的發(fā)展是勢(shì)在必行，這有利于我們簡(jiǎn)易我們的算法和對(duì)問(wèn)題的理解，方便我們的日常生活。

2）并行螞蟻算法的策略抉擇。并行螞蟻算法的策略是多種多樣，而策略的選擇也直接關(guān)系著最后的結(jié)果。所以說(shuō)，并行策略的選擇對(duì)于蟻群算法的并行實(shí)現(xiàn)至關(guān)重要。就目前所擁有的集中策略來(lái)說(shuō)，可以說(shuō)是各有千秋，例如：并行獨(dú)立蟻群，這種方法的有點(diǎn)就在于各個(gè)處理器之間都不需要互聯(lián)，方法簡(jiǎn)單，直觀。每一個(gè)的蟻群的主參數(shù)的數(shù)值都有差別，其中任何一個(gè)參數(shù)都可以通過(guò)處理器進(jìn)而加以更改。并行交互蟻群，這種方法和其它方法的最大不同之處就在于在特定的迭代中，蟻群可以通過(guò)相互之間的信息的交換將其中最好最準(zhǔn)確的信息傳遞發(fā)哦其它的蟻群，然而由于不同的蟻群方法有不同的衡量標(biāo)準(zhǔn)，所以對(duì)于究竟哪個(gè)蟻群表現(xiàn)的最好沒(méi)有具體的判定。還有呢就是并行螞蟻，在這種方法里，每個(gè)螞蟻都擁有一個(gè)自己的處理器來(lái)構(gòu)建相應(yīng)的解決方式，并行螞蟻這種方法的通信量相對(duì)適中，如若遇到大量的通信量數(shù)據(jù)，就會(huì)相應(yīng)的增加螞蟻的個(gè)數(shù)。算法的每個(gè)步驟完成之后，其中的每一個(gè)螞蟻都需要更新它的最新值。從而滿足相應(yīng)信息素的更新規(guī)則。

3）基于并行蟻群算法的火力分配優(yōu)化。基于MPI并行蟻群的火力分配優(yōu)化是最新研究發(fā)現(xiàn)的一種算法，主要問(wèn)題是針對(duì)高端軍事化的一個(gè)解決范疇，旨在解決的是在面對(duì)各式各類(lèi)的外界威脅時(shí)可以及時(shí)的想出解決的方法，及時(shí)應(yīng)對(duì)?；鹆Ψ峙鋬?yōu)化的結(jié)果可以在有限的時(shí)間內(nèi)處理大量的問(wèn)題。所以說(shuō)，對(duì)火力開(kāi)發(fā)的細(xì)致研究是至關(guān)重要的，相對(duì)于傳統(tǒng)的蟻群解決方法，通常很難在短時(shí)間里面得到結(jié)果，而且對(duì)于性對(duì)復(fù)雜的問(wèn)題也很難在快的時(shí)間里解決，而且，蟻群優(yōu)化算法正是應(yīng)對(duì)這種問(wèn)題而存在的，它兼具了并行計(jì)算，信息的正面反饋和啟發(fā)式搜索的特點(diǎn)，但是在它的實(shí)際研發(fā)上還是存在著大量的困難的，相信在以后的道路上以后一定會(huì)越來(lái)越好。

3基于MPI的并行蟻群算法的應(yīng)用

1）基于MPI的并行蟻群算法在交通系統(tǒng)中的應(yīng)用，隨著社會(huì)的快速發(fā)展，一系列的社會(huì)問(wèn)題也隨之浮出水面，城市擁擠、交通擁堵情況日益嚴(yán)重。如何解決交通道路的擁擠問(wèn)題關(guān)系到人、物、信息各個(gè)方面。嚴(yán)重影響到我們的日常生活。VRP也就是車(chē)輛路徑問(wèn)題是現(xiàn)在出現(xiàn)最多的問(wèn)題，通過(guò)螞蟻算法與VRP的具體應(yīng)用，將螞蟻算法的特性，在覓食過(guò)程中會(huì)選擇從蟻穴出發(fā)到達(dá)食物源最短的路徑。在此之中，也要考慮到多方面的因素，諸如多條道路的交通問(wèn)題。通過(guò)使用并行蟻群算法我們可以將道路的選擇看作是如火熱選擇最快的道路。這也就要求我們?cè)谶\(yùn)用的過(guò)程中藥充分的利用道路的利用率，合理的分配交通的流量。這也就能在最大程度的緩解交通的壓力，便民便利。

2）基于MPI的并行蟻群算法在數(shù)據(jù)挖掘中的應(yīng)用，利用螞蟻算法的特性可以解決數(shù)據(jù)挖掘中的各式各樣的問(wèn)題，例如聚類(lèi)問(wèn)題、分類(lèi)問(wèn)題以及關(guān)聯(lián)規(guī)則方面的問(wèn)題等等，通過(guò)將螞蟻算法里的螞蟻當(dāng)作是搬運(yùn)工，將一系列的數(shù)據(jù)搬運(yùn)到合適的地點(diǎn)從而形成聚類(lèi)，通過(guò)這一類(lèi)的方法，將數(shù)據(jù)排列的有自組織、自適應(yīng)、高效率等等特點(diǎn)。而對(duì)于分類(lèi)問(wèn)題，則是將當(dāng)前所面臨的不同問(wèn)題進(jìn)行了不同的分析，利用螞蟻算法的并行化策略，對(duì)信息數(shù)據(jù)進(jìn)行深入的挖掘，得到數(shù)據(jù)也更加的準(zhǔn)確。在針對(duì)聚類(lèi)問(wèn)題的信息挖掘上，數(shù)據(jù)對(duì)象在空間的分布狀態(tài)對(duì)聚類(lèi)的結(jié)果會(huì)產(chǎn)生一定的影響，假設(shè)網(wǎng)格中的兩個(gè)對(duì)象A和B之間的距離為D，則可以用歐式距離進(jìn)行計(jì)算，假若A和B是同一類(lèi)型的對(duì)象，那么他們的距離D就是0，如果對(duì)象不一樣，距離D則是1，這樣我們就可以得到二進(jìn)制的相異度的矩陣。這種方法可以通過(guò)螞蟻之間對(duì)象的空間分布狀態(tài)從而達(dá)到信息相互作用的目的。

4總結(jié)

基于MPI的并行蟻群算法的發(fā)展在不斷的提升，對(duì)我們的生活品質(zhì)和生活結(jié)構(gòu)有著巨大的改變。隨著社會(huì)的告訴發(fā)展，無(wú)論是科技還是學(xué)術(shù)都在不斷的發(fā)展，不斷的向前，我們對(duì)于螞蟻算法也要有一個(gè)細(xì)致的了解，才能更好的掌握這門(mén)技術(shù)為自己找取更大的便利。通過(guò)這篇文章我們整體的概括了并行螞蟻算法的理論知識(shí)，相應(yīng)的內(nèi)容以及它的廣泛應(yīng)用。讓我們從整體上對(duì)螞蟻算法進(jìn)行了解，再逐步的進(jìn)行深入的了解，將知識(shí)運(yùn)用到實(shí)際的生活當(dāng)中，給我們的生活增添色彩。

參考文獻(xiàn)：

[1]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)出版社，2005.

[2]張靜樂(lè).具有新型遺傳特征的蟻群算法[J].微計(jì)算機(jī)信息，2006，2（2）：261-263.

[3]章春芳.自適應(yīng)的并行蟻群算法及其應(yīng)用[D].揚(yáng)州：揚(yáng)州大學(xué)，2006.

[4]段海濱，王道波，朱家強(qiáng)，等.蟻群算法理論及應(yīng)用研究的進(jìn)展[J].控制與決策，2004（12）.

[5]陳云飛，劉玉樹(shù)，范杰，等.火力優(yōu)化分配問(wèn)題的小生境遺傳螞蟻算法[J].計(jì)算機(jī)運(yùn)用，2005（1）.