題-1_100_100.jpg)
基本信息
- 項目名稱：
- 求解最小費(fèi)用流問題的蟻群算法
- 小類：
- 數(shù)理
- 簡介：
- 本論文主要是提出了一種可行的模擬蟻群算法，并對此類問題進(jìn)行了實驗驗證。因受蟻群算法思想的啟發(fā)，故將路徑上的信息素采用路徑上的流量進(jìn)行局部更新，在建立的最小費(fèi)用流模型基礎(chǔ)上編程求解，得到了受最小費(fèi)用約束條件下的所有可行路徑及對應(yīng)的流量，然后將其分配得到了每條弧上可通過的最大流，并將所得結(jié)果與標(biāo)號算法、調(diào)整圈法進(jìn)行對比，其解比較理想，同時還對此模型進(jìn)行了一定的推廣。
- 詳細(xì)介紹：
- 本文為了能快速有效地解決最小費(fèi)用流問題，提出了一種可行的模擬蟻群算法.但因最小費(fèi)用流問題是基于有向圖上求解的，具有方向性，故針對此做了一些相應(yīng)轉(zhuǎn)化，并受蟻群算法思想的啟發(fā)將螞蟻在有向網(wǎng)絡(luò)圖中的信息素更新及選擇下一條路徑的概率公式做了相關(guān)改進(jìn).同時在最小費(fèi)用流模型的基礎(chǔ)上，利用從終點向始點反向?qū)ふ铱尚新窂降乃枷肭蠼?。并將仿真實驗的結(jié)果與標(biāo)號算法、調(diào)整圈法進(jìn)行對比，得到了較為理想、精確的解。
作品專業(yè)信息
撰寫目的和基本思路
- 寫作目的： 為了能快速有效地解決最小費(fèi)用流問題，提出了一種可行的模擬蟻群算法，并對此類問題進(jìn)行了實驗驗證，以便能解決實際生活中的眾多相關(guān)問題。 基本思路： 通過掌握蟻群算法的基本原理，結(jié)合有向網(wǎng)絡(luò)描述最小費(fèi)用流的數(shù)學(xué)模型，再運(yùn)用從終點向始點反向計算的思想求解在最大可行流的約束下的最小費(fèi)用，然后仿真實驗，最后調(diào)整圈法與標(biāo)號算法驗證。
科學(xué)性、先進(jìn)性及獨特之處
- 科學(xué)性、先進(jìn)性和獨特之處： 現(xiàn)階段，關(guān)于求解最小費(fèi)用流問題的傳統(tǒng)算法較多，而用現(xiàn)代優(yōu)化算法求解的研究較少，故在蟻群算法原理的啟發(fā)下，提出了一種可行的蟻群算法，該算法試圖將螞蟻選擇下一點的概率及路徑上信息素更新進(jìn)行了更改，在最小費(fèi)用流模型做相應(yīng)的轉(zhuǎn)化下運(yùn)用該算法求解。此蟻群算法在參數(shù)的選取合理恰當(dāng)下進(jìn)行仿真實驗，將所得結(jié)果與調(diào)整圈法、標(biāo)號算法進(jìn)行對比，并對此模型進(jìn)行了一定的推廣。
應(yīng)用價值和現(xiàn)實意義
- 實際應(yīng)用價值和現(xiàn)實指導(dǎo)意義在于，它能較好的解決規(guī)模較大、非整數(shù)情況下的最小費(fèi)用流問題，能應(yīng)用于現(xiàn)實生活中的多媒體網(wǎng)絡(luò)信息傳播、產(chǎn)品的運(yùn)輸與調(diào)度、指派問題等方面，并還能在許多工程領(lǐng)域和物理、化學(xué)、生物及應(yīng)用數(shù)學(xué)等科學(xué)領(lǐng)域有著廣泛的研究。
學(xué)術(shù)論文摘要
- 為了運(yùn)用蟻群算法解決最小費(fèi)用流問題，首先掌握了蟻群算法的基本原理，結(jié)合有向網(wǎng)絡(luò)描述了最小費(fèi)用流的數(shù)學(xué)模型，并運(yùn)用從終點向始點反向計算的思想求解在最大可行流約束下的最小費(fèi)用，然后給出了其具體過程。最后通過仿真實驗，調(diào)整圈法和標(biāo)號算法驗證表明：該算法是有效可行的。
獲獎情況
- 2010年6月內(nèi)江師范學(xué)院 發(fā)表在《內(nèi)江師范學(xué)院學(xué)報》（雙月刊） 中圖分類號：TP183 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-1785（2010）06-0030-03
鑒定結(jié)果
- 學(xué)報編輯部及導(dǎo)師評定結(jié)果： 本文具有較靈活的理論性和實務(wù)性，對解決最小費(fèi)用流類問題有一定的實際意義和應(yīng)用價值。
參考文獻(xiàn)
- [1]Dorigo M，Maniezzo V，Colorni A，The ant system：Optimization by a Colony of Cooperating Agents[J]．IEEE Transactions on Systems，Man，and Cybernetics-part B，1996，26(1):29?—41． [2]倪慶劍．蟻群算法及其應(yīng)用研究進(jìn)展[J]．計算機(jī)應(yīng)用與軟件，2008，25(8):12-18． [3]吳斌，史忠植．一種基于蟻群算法的TSP問題分段求解算法[J]．計算機(jī)學(xué)報，2001，24（12）：1328-1333． [4]謝民，高利新．蟻群算法在網(wǎng)絡(luò)最大流問題中的應(yīng)用[J]．計算機(jī)工程與應(yīng)用，2008,44(22):113-115． [5]張新敬，李剛，邱學(xué)紹．最小費(fèi)用最大流算法實現(xiàn)[J]．自然科學(xué)報，2005，20(3):132-134． [6]韓明亮．求解最小費(fèi)用最大流問題的一種方法[J]．中國民航學(xué)院學(xué)報，2000，18(1):49-53． [7]趙靜，但琦．?dāng)?shù)學(xué)建模與數(shù)學(xué)實驗(第三版) ．高等教育出版社[M]．2009，225—227．
同類課題研究水平概述
- 最小費(fèi)用流問題是一個經(jīng)典的組合優(yōu)化問題，已有40多年的研究歷史，人們已經(jīng)建立了最大流問題較為完善的理論，同時開發(fā)了大量的算法，如Ford和Fulkson增截軌算法、Dinic阻塞流算法、Goldberg推進(jìn)和重標(biāo)號算法以及Goldberg和Rao的二分長度阻塞流算法等，這些經(jīng)典算法及相關(guān)技術(shù)對網(wǎng)絡(luò)最大流方面的問題應(yīng)用與研究起到了非常重要的推動作用。盡管最大流問題在使用算法方面取得了許多突破性研究進(jìn)展，但到目前人們對最小費(fèi)用流問題的研究卻不夠成熟，值得探索。最小費(fèi)用流問題有著廣泛的實際應(yīng)用背景，如現(xiàn)實生活中的鐵路網(wǎng)、通信網(wǎng)、運(yùn)輸網(wǎng)等，所以研究如何解決最小費(fèi)用流問題有著十分重要的實用意義。 蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型、新型的模擬進(jìn)化算法．它由意大利學(xué)者M(jìn)arco Dorigo于1992年通過模擬自然界中螞蟻群體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化系統(tǒng)。在提出蟻群算法后，Dorigo等人應(yīng)用該算法求解了旅行商問題(traveling salesman problem，TSP)、二次分配問題、Job-Shop調(diào)度問題，在AS算法基礎(chǔ)上，ColorniA等人又提出了改進(jìn)的ACS(AColonySystem)模型，并在1999年將AS、ACS納入蟻群優(yōu)化的框架，稱為ACO(AntColonyOptimization)，在各個領(lǐng)域取得了較好的實驗結(jié)果。 蟻群算法是通過模擬真實蟻群的覓食機(jī)理求解優(yōu)化問題，引入信息素概念及相關(guān)的信息素更新機(jī)制。蟻群算法利用其基本原理適應(yīng)性地搜索問題的最優(yōu)解，在解決許多復(fù)雜優(yōu)化問題方面已經(jīng)展現(xiàn)出其優(yōu)異的性能和巨大的發(fā)展?jié)摿?，該算法具有較強(qiáng)的魯棒性、優(yōu)良的并行計算機(jī)制和易于與其他方法相結(jié)合等優(yōu)點，不論在搜索效率還是在時間的復(fù)雜度方面都有著令人滿意的效果。蟻群算法的思想已經(jīng)應(yīng)用到各個研究領(lǐng)域，取得了大量的研究成果。但其也存在一些不足，如搜索時間長、算法收斂最優(yōu)解速度遲緩、易于陷入局部最優(yōu)、易于停滯不能對空間進(jìn)行進(jìn)一步搜索。 當(dāng)然，本文的形成正是建立在蟻群算法領(lǐng)域?qū)＜仪拜厒兊难芯砍晒A(chǔ)上的，可以說如果沒有他們的研究成果是不會有本文的初步啟發(fā)和探索，故在此衷誠地對前輩專家們和導(dǎo)師表示感激之意！
