本科生畢業(yè)論文(設(shè)計(jì)) 文獻(xiàn)綜述和開題報(bào)告

本科生畢業(yè)論文〔設(shè)計(jì)〕文獻(xiàn)綜述和開題報(bào)告畢業(yè)論文〔設(shè)計(jì)〕開題報(bào)告一．論文題目?jī)?yōu)化方法研究和應(yīng)用二．選題的背景意義網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題是網(wǎng)絡(luò)最優(yōu)化的一個(gè)重要方面，它的理論和方法已廣泛地滲透到控制論、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域，并在工程技術(shù)、通信網(wǎng)絡(luò)和物流分配等方面有著極為重要的應(yīng)用。由于現(xiàn)階段的網(wǎng)絡(luò)最優(yōu)化問(wèn)題往往都具有大規(guī)模性，因此對(duì)網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的各種有效算法的研究一直頗受學(xué)者們的青睞和重視。另一方面，近年來(lái)隨著啟發(fā)式智能化方法的崛起，諸如遺傳算法、蟻群算法等的新興類算法逐漸引起學(xué)者們的關(guān)注和興趣。這些模仿自然界進(jìn)化的“仿生〞類算法，因?yàn)槟軌蚪鉀Q很多傳統(tǒng)算法不能解決的問(wèn)題，因此受到科學(xué)家們的高度重視。而它們所應(yīng)用的領(lǐng)域也隨著科學(xué)的開展而變得越來(lái)越廣。綜上，本次選題希望能夠使用蟻群算法這個(gè)“仿生類〞算法去解決網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題，另外由于目前蟻群算法的參數(shù)設(shè)定問(wèn)題還沒(méi)有成熟理論，因此本文還希望能夠通過(guò)對(duì)不同參數(shù)的設(shè)定，觀察和分析其對(duì)算法求解正確率的影響。這些工作將是對(duì)優(yōu)化方法的一個(gè)很好的研究和應(yīng)用。三．此題的有關(guān)研究現(xiàn)狀網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的研究現(xiàn)狀：最小費(fèi)用流是一個(gè)根本的網(wǎng)絡(luò)流模型，對(duì)于該模型的研究已有不少成果。人們對(duì)最小費(fèi)用流問(wèn)題的研究最先是從圖論和規(guī)劃的思想出發(fā)。Ford最先于1956年提出了求最短路問(wèn)題的算法，隨后他參加規(guī)劃理論中的原始-對(duì)偶思想，將其改良成可用于求解最小費(fèi)用流問(wèn)題的算法。后來(lái)Jewell等人通過(guò)對(duì)路徑的增廣和最小平均費(fèi)用路的概念提出了最小費(fèi)用路算法。1967年，Klein根據(jù)環(huán)流負(fù)和的思想，提出了負(fù)回路算法，又稱消圈算法。求解網(wǎng)絡(luò)最小費(fèi)用流的第一個(gè)多項(xiàng)式時(shí)間算法是由Edmonds和Karp于1972年提出的，此后不斷有多項(xiàng)式時(shí)間算法被提出。Tardos提出了第一個(gè)求解最小費(fèi)用流問(wèn)題的強(qiáng)多項(xiàng)式時(shí)間算法，很快又有不少?gòu)?qiáng)多項(xiàng)式時(shí)間算法被提出。1997年，Orlin給出了第一個(gè)多項(xiàng)式時(shí)間的原始網(wǎng)絡(luò)單純形算法。另外，在二十世紀(jì)80年代中期，許多學(xué)者開始嘗試用內(nèi)點(diǎn)法來(lái)求解某些網(wǎng)絡(luò)流問(wèn)題，其中就包括網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題。對(duì)于廣義的最小費(fèi)用流問(wèn)題，目前也已經(jīng)有不少多項(xiàng)式時(shí)間算法，但當(dāng)前還暫時(shí)沒(méi)有求解此類問(wèn)題的強(qiáng)多項(xiàng)式時(shí)間算法。對(duì)于帶有嵌入式網(wǎng)絡(luò)(embeddednetwork)的網(wǎng)絡(luò)流問(wèn)題，因?yàn)槠浔旧砭褪翘厥獾木€性規(guī)劃問(wèn)題，所以可以用求解一般線性規(guī)劃的方法得以解決。然而，當(dāng)額外約束的數(shù)量不多時(shí)，問(wèn)題仍保存有一定的網(wǎng)絡(luò)結(jié)構(gòu)。假設(shè)算法能夠充分利用問(wèn)題的網(wǎng)絡(luò)結(jié)構(gòu)，那么求解問(wèn)題的效率會(huì)顯著提高，目前己有很多這方面的研究。另外，對(duì)于一些特殊問(wèn)題，還可以用拉格朗日松弛法去求解，但是收斂速度卻比擬慢。Cohen和Megiddo對(duì)幾類帶額外約束的網(wǎng)絡(luò)流問(wèn)題的算法及其復(fù)雜度進(jìn)行了分析，其研究結(jié)果說(shuō)明，此類問(wèn)題中的任何一個(gè)實(shí)例假設(shè)存在強(qiáng)多項(xiàng)式時(shí)間算法，那么意味著一般的線性規(guī)劃問(wèn)題均存在強(qiáng)多項(xiàng)式時(shí)間算法，并證明了當(dāng)額外約束的數(shù)量為一常數(shù)時(shí)，問(wèn)題存在強(qiáng)多項(xiàng)式時(shí)間算法。L.R.Ford和D．R．Fulkerson提出了求解最小費(fèi)用流問(wèn)題的Ford_Fulkerson迭代算法，其根本思路是將各條弧上單位流量的費(fèi)用看作是某種長(zhǎng)度，用求解最短路問(wèn)題的算法確定一條從出發(fā)點(diǎn)到接收點(diǎn)的最短路；并將這條最短路作為增廣路，用求解最大流問(wèn)題的算法將其上的流量增加至指定的流值；當(dāng)此最短路上的流量增加后，其上的各條弧的單位流量的費(fèi)用需重新確定。如此迭代屢次，最終得到指定流值的最小費(fèi)用流。JianzhongZhang提出了一個(gè)解決一般LP問(wèn)題的方法，此方法主要基于LP問(wèn)題的最優(yōu)性條件，同時(shí)將最小費(fèi)用流問(wèn)題的反問(wèn)題作為此方法的一個(gè)特例，通過(guò)一系列線性規(guī)劃的轉(zhuǎn)化，將最小費(fèi)用流問(wèn)題的反問(wèn)題轉(zhuǎn)化成最小費(fèi)用循環(huán)流(minimumcostcirculation)問(wèn)題，得出了強(qiáng)多項(xiàng)式算法。X．Cai提出了隨時(shí)間而變化的一般最大流問(wèn)題，并用擬多項(xiàng)式算法對(duì)其進(jìn)行求解。Ahuja和Orlin研究得比擬系統(tǒng)，也得出了比擬好的結(jié)果。研究顯示，模下的最小費(fèi)用流反問(wèn)題，假設(shè)是在單位權(quán)重下，可以轉(zhuǎn)化成單位容量的最小費(fèi)用流問(wèn)題進(jìn)行求解；假設(shè)是在非單位權(quán)重下，那么可以轉(zhuǎn)化成一般的最小費(fèi)用流問(wèn)題進(jìn)行求解。對(duì)于模下的最小費(fèi)用流反問(wèn)題，假設(shè)是在單位權(quán)重下，可以轉(zhuǎn)化成最小平均回路問(wèn)題進(jìn)行求解；假設(shè)是在非單位權(quán)重下，那么可以轉(zhuǎn)化成最小費(fèi)用與時(shí)間比例回路問(wèn)題進(jìn)行求解。國(guó)內(nèi)學(xué)者謝政等首次提出了帶模糊約束的最小費(fèi)用流問(wèn)題，建立了相應(yīng)的數(shù)學(xué)模型并且給出了求解這一模型的相關(guān)算法。甘應(yīng)愛等對(duì)最小費(fèi)用流的反問(wèn)題進(jìn)行了討論：如何在一定的費(fèi)用條件下，盡可能地?cái)U(kuò)充容量參數(shù)，以到達(dá)一個(gè)預(yù)定的流值。建立了最小費(fèi)用流反問(wèn)題的數(shù)學(xué)模型，并給出了最優(yōu)參數(shù)配置的算法。另外，在可擴(kuò)充弧的容量上限不變的情況下，以取最大上限時(shí)的單位費(fèi)用流作為擴(kuò)充弧的單位費(fèi)用，提供了一個(gè)算法。謝政等系統(tǒng)歸納了求解普通網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的幾個(gè)經(jīng)典算法，并對(duì)雙容量網(wǎng)絡(luò)作了一些討論。蟻群算法的研究現(xiàn)狀：蟻群算法是受自然界中真實(shí)蟻群行為啟發(fā)而模擬產(chǎn)生的一種人工進(jìn)化算法，是由意大利學(xué)者Dorigo等人在20世紀(jì)90年代最先提出的。其中螞蟻系統(tǒng)模型〔AS模型〕是最經(jīng)典的蟻群算法模型，最先被應(yīng)用于旅行商問(wèn)題〔TSP〕。后來(lái)蟻群算法得到了各種各樣的改良，主要的改良方向有信息素設(shè)置、搜索策略改善、多算法結(jié)合等；另外，將螞蟻智能化的思想也在近年來(lái)逐步成熟，成為一個(gè)蟻群算法改良的新方向。ThomasStuztle等于1997年提出了最值螞蟻模型〔Max-MinAntSystem〕，也稱作MMAS模型。和傳統(tǒng)的AS模型相比，MMAS模型能夠克服蟻群算法收斂慢、容易出現(xiàn)停滯以及運(yùn)算時(shí)間較長(zhǎng)等缺陷。主要的改良是對(duì)信息素濃度加以一定限制，并且在初始狀態(tài)時(shí)信息素濃度取最大值。此外，ThomasStuztle還提出了MMAS的一種改良措施，稱作信息素平滑，主要思想是當(dāng)各邊信息素濃度相差很大時(shí)，將各邊的信息素濃度與其中的最大值進(jìn)行加權(quán)平均，以便更有利于搜索新的路線。LeeSG等于2001年提出了將信息素更新分成局部更新和全局更新兩局部：當(dāng)局部更新時(shí)，揮發(fā)程度動(dòng)態(tài)改變；當(dāng)全局更新時(shí)，最優(yōu)路線得到信息素加強(qiáng)，其余路線那么隨時(shí)間減弱。郝晉等于2002年提出一種具有隨機(jī)擾動(dòng)的蟻群算法，核心思想是采用倒指數(shù)曲線來(lái)描述擾動(dòng)因子以及設(shè)計(jì)了相應(yīng)的隨機(jī)選擇策略。徐婕、詹士昌等于2003年提出了動(dòng)態(tài)調(diào)節(jié)信息素的蟻群算法，根本機(jī)理是隨著迭代次數(shù)的增加，動(dòng)態(tài)地調(diào)整路徑上的信息素濃度和各種參數(shù)，使搜索能夠更順利進(jìn)行。Vlachogiannis等于2005年提出了引進(jìn)信息素矩陣的思想，通過(guò)信息素矩陣來(lái)協(xié)調(diào)螞蟻之間的選擇行為，從而實(shí)現(xiàn)對(duì)解空間進(jìn)行更好的搜索。許殿等于2005年提出一種回歸蟻群算法，主要思想是通過(guò)外部力量使螞蟻按照城市的整體分布規(guī)律尋優(yōu)，從而增加了算法的全局收斂性。Fabio等和丁建立等將蟻群算法和遺傳算法相結(jié)合，從而有效彌補(bǔ)了蟻群算法中參數(shù)設(shè)置憑經(jīng)驗(yàn)的缺陷，成功地將兩個(gè)算法的優(yōu)點(diǎn)糅合起來(lái)。蟻群算法最開始被應(yīng)用在經(jīng)典的組合優(yōu)化問(wèn)題上，但隨著研究的深入，其應(yīng)用范圍逐漸擴(kuò)展到其它更多的組合優(yōu)化問(wèn)題中，包括靜態(tài)的和動(dòng)態(tài)的組合優(yōu)化問(wèn)題。另外，目前也有了用蟻群算法求解連續(xù)性優(yōu)化問(wèn)題的相關(guān)研究。在水資源規(guī)劃設(shè)計(jì)方面，蟻群算法得到了不錯(cuò)的應(yīng)用。事實(shí)上，水利科學(xué)中的供水系統(tǒng)、灌溉系統(tǒng)等的設(shè)計(jì)工程，本質(zhì)上都是組合優(yōu)化問(wèn)題，因此蟻群算法在水利工程優(yōu)化領(lǐng)域中有廣泛的應(yīng)用前景。Zecchin等就將蟻群算法應(yīng)用在對(duì)供水系統(tǒng)設(shè)計(jì)的優(yōu)化上，取得了一定成果。蟻群算法在電力系統(tǒng)領(lǐng)域的應(yīng)用也有很高的實(shí)際價(jià)值。Foong等將蟻群算法應(yīng)用于發(fā)電廠檢測(cè)維修方案的優(yōu)化上，有效的為電力企業(yè)節(jié)省了大量資源。在物流領(lǐng)域的應(yīng)用上，研究較多的是物流分配領(lǐng)域的車輛路徑問(wèn)題。Gambardella等首先提出了將蟻群算法應(yīng)用在車輛路徑問(wèn)題上。通信領(lǐng)域?qū)儆趧?dòng)態(tài)組合優(yōu)化的范疇，通信網(wǎng)絡(luò)的一些特征，如分布式的信息存儲(chǔ)結(jié)構(gòu)、網(wǎng)絡(luò)動(dòng)態(tài)特性等均與蟻群算法的本質(zhì)特征非常相像，所以蟻群算法在通信領(lǐng)域也有很廣泛的應(yīng)用前景。Schoonderwoerd等首先提出把蟻群算法應(yīng)用于通信網(wǎng)絡(luò)的路由問(wèn)題上，并提出了基于蟻群算法的路由算法。Ho等通過(guò)改良信息素更新策略提出了求解連續(xù)優(yōu)化問(wèn)題的蟻群算法，該算法被運(yùn)用在電磁裝置的優(yōu)化設(shè)計(jì)中，并取得了不錯(cuò)的效果。啟發(fā)式智能算法求解網(wǎng)絡(luò)流問(wèn)題的研究現(xiàn)狀：由于最小費(fèi)用流問(wèn)題已存在多項(xiàng)式，因此有關(guān)用蟻群算法等的“仿生類〞算法去求解網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的研究并不多。謝民等將蟻群算法應(yīng)用在求解網(wǎng)絡(luò)最大流問(wèn)題上；董振寧等提出了用遺傳算法求解帶容量限制的最小費(fèi)用流問(wèn)題。四．研究的根本內(nèi)容和擬解決的主要問(wèn)題研究的根本內(nèi)容：1、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的模型、根本特征及現(xiàn)有求解算法2、蟻群算法的模型、根本特點(diǎn)和應(yīng)用情況3、啟發(fā)式智能算法求解網(wǎng)絡(luò)流問(wèn)題的應(yīng)用實(shí)例擬解決的主要問(wèn)題：1、設(shè)計(jì)出能夠求解網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的蟻群算法2、測(cè)試算法的求解正確率并對(duì)其進(jìn)行有效提高3、不同的參數(shù)設(shè)置對(duì)算法求解正確率的影響五．研究方法及措施研究方法：本人準(zhǔn)備通過(guò)查閱文獻(xiàn)資料的方法先對(duì)目前該類型問(wèn)題的研究現(xiàn)狀作個(gè)明確了解，以便能確定研究方向和角度。接著，本人以自行思考為主、與導(dǎo)師定期討論為輔的方式對(duì)本問(wèn)題進(jìn)行進(jìn)一步研究。具體措施：1、到圖書館查閱相關(guān)方面的書籍；2、從因特網(wǎng)及各個(gè)電子數(shù)據(jù)庫(kù)中查閱相關(guān)文獻(xiàn)；3、每周與導(dǎo)師就本研究問(wèn)題討論一次，獲取及時(shí)的指導(dǎo)；4、在電腦中編寫程序，通過(guò)數(shù)據(jù)模擬等方式進(jìn)行實(shí)驗(yàn)。六．論文根本架構(gòu)本論文主要由四個(gè)局部組成，分別是對(duì)網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的概述、對(duì)蟻群算法的概述、提出基于蟻群算法思想的求解最小費(fèi)用流問(wèn)題的算法以及實(shí)證檢驗(yàn)。前兩局部分別闡述網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題和蟻群算法的模型和研究進(jìn)展，為本文的算法提出打下根底；第三局部提出一個(gè)求解最小費(fèi)用流問(wèn)題的蟻群算法，通過(guò)根本思路、問(wèn)題轉(zhuǎn)化和算法設(shè)計(jì)三個(gè)步驟將算法表達(dá)出來(lái)，并對(duì)算法進(jìn)行正確性分析；第四局部那么通過(guò)幾個(gè)實(shí)例來(lái)驗(yàn)證算法的求解正確性，并分析不同參數(shù)變化對(duì)算法正確率的影響。本論文的根本架構(gòu)如下：一．引言二．網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題概述〔一〕網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題簡(jiǎn)介及研究現(xiàn)狀1、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題簡(jiǎn)介2、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的研究現(xiàn)狀〔二〕網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題模型及兩個(gè)經(jīng)典算法1、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題模型2、網(wǎng)絡(luò)最小費(fèi)用流問(wèn)題的兩種經(jīng)典算法三．蟻群算法概述〔一〕蟻群算法根本原理1、螞蟻覓食機(jī)理2、螞蟻系統(tǒng)〔AntSystem〕模型〔二〕蟻群算法的改良及應(yīng)用1、蟻群算法的改良模型2、蟻群算法的應(yīng)用現(xiàn)狀四．最小費(fèi)用流問(wèn)題的蟻群算法設(shè)計(jì)〔一〕根本思路〔二〕問(wèn)題轉(zhuǎn)化〔三〕算法設(shè)計(jì)〔四〕正確性分析五．實(shí)證檢驗(yàn)六．總結(jié)〔一〕本文總結(jié)〔二〕研究展望七．研究工作的步驟與進(jìn)展第一階段：2021年11月25日—12月19日查閱相關(guān)文獻(xiàn)和學(xué)習(xí)工具書，選題；第二階段：2021年12月20日—12月22日確定選題；第三階段：2021年12月23日—12月31日完成開題報(bào)告；第四階段：2021年1月1日—1月12日完成文獻(xiàn)綜述、譯文；第五階段：2021年1月13日—2月23日完成正文初稿，實(shí)現(xiàn)算法進(jìn)行檢驗(yàn)評(píng)估第六階段：2021年2月24日—3月15日屢次修改初稿，向?qū)熣髟円庖?，最后定稿；第七階段：2021年3月20日論文辯論八．主要參考文獻(xiàn)[1]FordLR.Networkflowtheory.RandCorporationReport，1956，923[2]FordLR，F(xiàn)ulkersonDR.AsimplealgorithmforfindingmaximalNetworkFlowsandanapplicationtotheHitchcockproblem[J].Canada.J.Math.，1957，9：210—218[3]KleinM.Aprimalmethodforminimumcostflows.Mgt.Sci.，1967，14：205—220[4]BusackerRG，GowenPJ.AProcedureforDeterminingaFamilyofMinimalCostNetworkFlowPatterns.O.R.O.TechnicalReport15，JohnsHopkinsUniversity，1961[5]E.Cohen，N.Megiddo．Algorithmsandcomplexityanalysisforsomeflowproblems．Algorithmica，1994，11：320—340[6]王勤波，最小費(fèi)用流問(wèn)題及其擴(kuò)展，2021[7]ZhangJianzhong，LiuZhenghong．Calculatingsomeinverselinearprogrammingproblems．1995[8]X．Cai，D．Sha，C．K．Wong．Time-varyinguniversalmaximumflowproblems.EuropeanJournalofOperationalResearch，1997，407—430[9]R.K.Ahuja，J.B.Orlin．Inverseoptimization．OperationsResearch.2001，49(5)：771—783[10]謝政，湯澤瀅，帶模糊約束的最小費(fèi)用流問(wèn)題，模糊系統(tǒng)與數(shù)學(xué)，1999，13(2)[11]甘應(yīng)愛，田豐，李維錚，等．運(yùn)籌學(xué)．北京：清華大學(xué)出版社，1996．1—80[12]謝政，網(wǎng)絡(luò)算法與復(fù)雜性理論，長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2003[13]ColorniA，DorigoM，ManiezzoV，Distributedoptimizationbyantcolonies[C].ProceedingsoftheFirstEuropeanConferenceonArtificialLife，Paris，F(xiàn)rance，1991[14]ThomasStuztle，HolgerHoos.ImprovementsontheAntSystem：introducingMAX-MINAntSystem[M].inGDSmith，NCSteele，RA，editor.ArtificialNeuralNetworksandGeneticAlgorithms，1998[15]LeeSG，JungTU，ChungTC.Aneffectivedynamicweightedruleforantcolonysystemoptimization[C].In：Proc.ofthe2001CongressonEvolutionaryComputation，2001[16]郝晉，石立寶，周家啟，求解復(fù)雜TSP問(wèn)題的隨機(jī)擾動(dòng)蟻群算法[J]，系統(tǒng)工程理論與實(shí)踐，2002，9：88—92[17]徐婕，詹士昌，動(dòng)態(tài)調(diào)整信息素的蟻群算法[J]，漢中師范學(xué)院學(xué)報(bào)，2003，21(2)：31—35[18]VlachogiannisJG，HatziargyriouND，LeeKY.Antcolonysystem-basedalgorithmforconstrainedloadflowproblem[J].PowerSystems，IEEETransactionson.2005，20(3)：1241—1249[19]許殿，史小衛(wèi)，程睿，回歸蟻群算法[J]，西安電子科技大學(xué)學(xué)報(bào)，2005，32(6)：944—947[20]吳斌，趙燕偉，蟻群算法的研究現(xiàn)狀[J]，自動(dòng)化儀表，2004，25(1)：1—4[21]丁建立，陳增強(qiáng)，袁著祉，遺傳算法與螞蟻算法的融合[J]，計(jì)算機(jī)研究與開展，2003，40(9)：1351—1355[22]胡祥培，丁秋雷，李永先，蟻群算法研究評(píng)述，管理工程學(xué)報(bào)，2006,22(2):74—78[23]ZecchinAC，SimpsonAR，HRMaier，Parametricstudyforanantalgorithmappliedtowaterdistributionsystemoptimization.IEEETransactiononEvolutionaryComputation，2005，9(2)：175—191[24]WaiKuanF，HolgerRM，AngusRS，Antcolonyoptimizationforpowerplantm