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