基于.粒子群算法的TSP問題設(shè)計(jì)研究

..WORD格式可編輯專業(yè)知識(shí)分享畢業(yè)設(shè)計(jì)<論文>題目：基于粒子群算法的TSP問題研究院〔系理學(xué)院專業(yè)信息與計(jì)算科學(xué)班級(jí)姓名xxx學(xué)號(hào)xxx導(dǎo)師xxx20XX6月畢業(yè)設(shè)計(jì)<論文>題目：基于粒子群算法的TSP問題研究院〔系理學(xué)院專業(yè)信息與計(jì)算科學(xué)班級(jí)101001姓名xxx學(xué)號(hào)101001106導(dǎo)師xxx20XX6月WORD格式可編輯專業(yè)知識(shí)分享XX工業(yè)大學(xué)畢業(yè)設(shè)計(jì)〔論文任務(wù)書院〔系理學(xué)院專業(yè)信息與計(jì)算科學(xué)班101001姓名xxx學(xué)號(hào)1010011061.畢業(yè)設(shè)計(jì)〔論文題目：基于粒子群算法的TSP問題研究2.題目背景和意義：粒子群算法,也稱粒子群優(yōu)化算法〔ParticleSwarmOptimization,縮寫為PSO,是近年來發(fā)展起來的一種新的進(jìn)化算法〔EvolutionaryAlgorithm-EA。1995年由Eberhart博士和kennedy博士提出。PSO算法屬于進(jìn)化算法的一種,和遺傳算法相似,它也是從隨機(jī)解出發(fā),通過迭代尋找最優(yōu)解。但它比遺傳算法規(guī)則更為簡單,它沒有遺傳算法的"交叉"<Crossover>和"變異"<Mutation>操作,它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。旅行商問題,即TSP問題〔TravelingSalesmanProblem是數(shù)學(xué)領(lǐng)域中著名的優(yōu)化問題之一,很多現(xiàn)實(shí)問題可歸結(jié)為TSP問題。粒子群優(yōu)化算法原理簡單,從算法提出的伊始,就被廣泛應(yīng)用于求解各類優(yōu)化問題。因此用粒子群算法求解典型的優(yōu)化問題—TSP問題,具有很高的理論與現(xiàn)實(shí)意義。3.設(shè)計(jì)<論文>的主要內(nèi)容〔理工科含技術(shù)指標(biāo)：1了解粒子群算法的由來,熟練掌握粒子群算法的原理；2了解TSP問題的本質(zhì),知道現(xiàn)實(shí)中都有哪些問題可以轉(zhuǎn)化為TSP問題,知道此問題在現(xiàn)實(shí)生活中的廣泛存在性；3用粒子群算法求解TSP問題,要求程序?qū)崿F(xiàn)〔可以用數(shù)學(xué)軟件如matlab之類的來實(shí)現(xiàn),并作出理論分析。4.設(shè)計(jì)的基本要求及進(jìn)度安排〔含起始時(shí)間、設(shè)計(jì)地點(diǎn)：第1周-第2周對(duì)相關(guān)資料進(jìn)行整理并提交開題報(bào)告第2周-第8周深入了解相關(guān)內(nèi)容和理論第9周-第10周完成中期報(bào)告和外文翻譯第11周-第16周對(duì)相關(guān)內(nèi)容進(jìn)行整理,完成畢業(yè)設(shè)計(jì)論文初稿第17周-第18周修改論文,準(zhǔn)備答辯5.畢業(yè)設(shè)計(jì)〔論文的工作量要求①實(shí)驗(yàn)〔時(shí)數(shù)*或?qū)嵙?xí)〔天數(shù)：②圖紙〔幅面和張數(shù)*：③其他要求：指導(dǎo)教師簽名：年月日學(xué)生簽名：年月日系〔教研室主任審批：年月日..專業(yè)知識(shí)分享基于粒子群算法的TSP問題研究..摘要1995年,肯尼迪〔Kennedy與埃伯哈特〔Eberhart兩位學(xué)者提出了粒子群算法。粒子群算法具有易理解、易實(shí)現(xiàn)和全局搜索能力強(qiáng)等特點(diǎn),因此該算法問世以后迅速得到科學(xué)與工程領(lǐng)域的廣泛關(guān)注,已經(jīng)成為發(fā)展最快的智能優(yōu)化算法之一。文章介紹了基本粒子群算法的概念和原理,并介紹了旅行商問題的概念及數(shù)學(xué)定義。基本粒子群優(yōu)化算法已經(jīng)成功地應(yīng)用于求解連續(xù)域問題,但是,對(duì)于離散域問題求解研究還很少。很不幸旅行商問題恰恰就屬于離散問題,因此接下來文章介紹了幾種可以解決旅行商問題的改進(jìn)粒子群算法,并詳細(xì)介紹了其中的兩種：引入模糊矩陣的改進(jìn)粒子群算法和引入交換序和交換算子的改進(jìn)粒子群算法。這兩種改進(jìn)的粒子群算法實(shí)現(xiàn)了對(duì)旅行商問題的求解。實(shí)驗(yàn)結(jié)果表明這兩種改進(jìn)粒子群算法的有效性。關(guān)鍵詞：粒子群算法；全局搜索；旅行商問題；連續(xù)；離散..Particleswarmoptimization<PSO>-basedalgorithmForthetravelingsalesmanproblem<TSP>AbstractTheParticleswarmoptimization<PSO>algorithmoriginallydevelopedbyKennedyandEberhartin1995.The

algorithm

has

the

characteristics

thateasytounderstand,easytoimplementand

global

searching

ability.Ithadgot

extensive

attention

in

the

field

of

scienceand

engineeringassoonasthealgorithmwasproposed.Bynow,PSOhas

became

one

ofthe

mostpopularoptimizationalgorithms.

WeintroducedtheconceptsandsomeprinciplesofPSOandthemathematicaldefinitionofTSP.WeknowPSOhassucceededinmanycontinuousproblems,butthereislessresearchaboutdiscreteproblems.Unfortunately,TSPjustbelongtosuchaproblem.Accordingtothis,someimprovedPSOalgorithmstosolveTSPwasintroduced,andtwoofthemwasdescribedindetail.Onealgorithmisimprovedbyintroducethefuzzymatrixandtheotherisimprovedbyintroducethepermutationconcept.WeappliedthetwoimprovedPSOalgorithmsontheproblemofTSPsuccessfully.Theresultsshowsbothofthemareavailable.Keywords:TheParticleswarmoptimization;GlobalSearch;Travelingsalesmanproblem;Continuous;Discrete..WORD格式可編輯專業(yè)知識(shí)分享目錄摘TOC\o"1-3"\h\u648要I30476AbstractII51431緒論1242851.1背景和意義191631.2國內(nèi)外研究的進(jìn)展情況111421.3主要內(nèi)容2139551.4結(jié)構(gòu)安排2155842基本的粒子群算法3189892.1思想起源380162.2算法的原理4200232.3算法的流程和流程圖516022.4算法的優(yōu)缺點(diǎn)分析8247863旅行商問題956923.1TSP問題介紹9325403.2TSP問題定義9245304改進(jìn)的粒子群算法求解TSP問題1119494.1改進(jìn)的粒子群算法簡介1178454.2引入模糊矩陣的粒子群算法求解TSP問題12106944.2.1旅行商問題的解用模糊矩陣表示12259634.2.2引入模糊矩陣的粒子群算法重新定義13292654.2.3引入模糊矩陣的粒子群算法求解旅行商問題的具體操作15182554.3引入交換算子和交換序的粒子群算法求解TSP問題18255214.3.1引入交換算子和交換序的粒子群算法定義和流程18207714.3.2實(shí)驗(yàn)結(jié)果與參數(shù)設(shè)置20171425結(jié)論2731027致謝2917611畢業(yè)設(shè)計(jì)〔論文知識(shí)產(chǎn)權(quán)聲明308902畢業(yè)設(shè)計(jì)〔論文獨(dú)創(chuàng)性聲明3125471參考文獻(xiàn)3231371附錄1程序3411827附錄2外文翻譯原文45..WORD格式可編輯專業(yè)知識(shí)分享1緒論1.1背景和意義粒子群算法〔ParticleSwarmOptimization,縮寫為PSO。1995年由肯尼迪〔Kennedy與埃伯哈特〔Eberhart兩位學(xué)者所提出,他們發(fā)明PSO靈感來源于對(duì)鳥群捕食行為的研究。粒子群算法的理論基礎(chǔ)是把每一只鳥看作為一個(gè)粒子,并賦予該粒子〔個(gè)體擁有記憶性,并能通過與粒子群體中的其他粒子之間的通信而尋求到最適解。目前,粒子群算法在函數(shù)優(yōu)化,神經(jīng)網(wǎng)絡(luò)訓(xùn)練,模糊系統(tǒng)控制,組合優(yōu)化入侵檢測,以及決策調(diào)度等多個(gè)領(lǐng)域得到廣泛的應(yīng)用。粒子群算法有較強(qiáng)的全局搜索能力,但也容易陷入局部極值導(dǎo)致早熟。旅行商問題〔TravellingSalesmanProblem,英文縮寫為TSP,是數(shù)學(xué)領(lǐng)域中著名問題之一,也是一個(gè)典型的NP完全問題。問題描述為：假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市,他必須選擇所要走的路徑,路徑的限制是每個(gè)城市只能拜訪一次,而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。目前解決旅行商問題的主要算法有：蟻群算法,免疫算法,遺傳算法等等。粒子群算法中每個(gè)粒子由一個(gè)多維向量表示,其下一代粒子的飛行方向和速度由個(gè)體最優(yōu)解和群體最優(yōu)解向量來修正,基本粒子群算法已成功應(yīng)用于求解連續(xù)域問題,但解決離散問題還是存在很大困難的。為了解決諸多實(shí)際工程中的離散問題,通過引入交換序和交換因子重構(gòu)了粒子群算法并成功應(yīng)用于小規(guī)模TSP問題求解。也可以通過引入模糊矩陣重構(gòu)粒子群算法同樣成功應(yīng)用于旅行商問題求解。本文會(huì)詳細(xì)介紹引入模糊矩陣的粒子群算法和引入交換序和交換因子的粒子群算法并總結(jié)各自的優(yōu)缺點(diǎn)。由于旅行商問題的特殊性,因此任何能使該問題的求解得以簡化的方法,都將受到高度的評(píng)價(jià)和關(guān)注。因此,用粒子群算法去解決旅行商問題具有很高研究價(jià)值。1.2國內(nèi)外研究的進(jìn)展情況1995年由肯尼迪〔Kennedy與埃伯哈特〔Eberhart兩位學(xué)者在IEEE國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議發(fā)表了題為"ParticleSwarmOptimization"的論文,標(biāo)志著PSO算法誕生。1999年美國的ClercM.發(fā)表的文章《自適應(yīng)粒子群優(yōu)化算法》對(duì)PSO算法的收斂性進(jìn)行了研究,證明采用收斂因子能夠確保算法的收斂。1999年SuganthanPN.在發(fā)表的文章《優(yōu)化與鄰域》第一次提到帶鄰域操作的SO模型,克服了PSO模型在優(yōu)化搜索后期隨迭代次數(shù)增加和搜索結(jié)果無明顯改進(jìn)的缺點(diǎn)。20XX來自普度大學(xué)工程與技術(shù)院的ParsopoulosKE.提出將拉伸技術(shù)用于PSO最小化問題的求解,力圖避免PSO算法易陷于局部最小值的缺點(diǎn)。20XX由來自中國XX科技大學(xué)電子信息學(xué)院的高尚,韓斌,吳小俊,楊靜宇等學(xué)者,他們結(jié)合了遺傳算法、蟻群算法和模擬退火算法的思想,對(duì)粒子群算法進(jìn)行了優(yōu)化并提出了混合粒子群算法,通過這種優(yōu)化的粒子群算法使得組合優(yōu)化問題很容易解決。1.3主要內(nèi)容清楚基本的粒子群算法的原理并知道如何應(yīng)用；了解旅行商問題的本質(zhì)及生活中哪些問題都可以轉(zhuǎn)化為旅行商問題；了解有哪些改進(jìn)的方法可以求解旅行商問題,并選擇幾種改進(jìn)的粒子群算法詳細(xì)介紹。使用Matlab實(shí)現(xiàn)引入交換序和交換算子的改進(jìn)粒子群算法并解決旅行商問題。并對(duì)粒子群算法的參數(shù)進(jìn)行研究,選出粒子群算法解決旅行商問題效率比較高的參數(shù)。最后,總結(jié)各種改進(jìn)粒子群算法解決旅行商問題的優(yōu)點(diǎn)和缺點(diǎn)。1.4結(jié)構(gòu)安排第一章緒論中分別介紹了基本粒子群算法和旅行商問題,以及國內(nèi)外研究現(xiàn)狀和論文所研究的主要內(nèi)容。第二章詳細(xì)介紹了基本粒子群算法思想起源和算法具體流程。第三章詳細(xì)介紹了旅行商問題概念,數(shù)學(xué)定義和應(yīng)用領(lǐng)域。第四章中,首先,介紹了幾種可以求解旅行商問題的改進(jìn)粒子群算法,并詳細(xì)介紹了其中的兩種。然后,使用Matlab實(shí)現(xiàn)了一種求解旅行商問題的改進(jìn)粒子群算法。在附錄中給出了具體實(shí)現(xiàn)代碼。..WORD格式可編輯2基本的粒子群算法2.1思想起源1995年IEEE國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議發(fā)表了題為"ParticleSwarmOptimization"的論文,標(biāo)志著粒子群優(yōu)化<ParticleSwarmOptimization,PSO>算法[1]誕生。粒子群算法是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化一組隨機(jī)解,粒子在解空間通過個(gè)體間的協(xié)作與競爭,實(shí)現(xiàn)復(fù)雜空間最優(yōu)解的搜索。同時(shí),粒子群算法又不像其他進(jìn)化算法那樣對(duì)個(gè)體進(jìn)行交叉、變異、選擇等進(jìn)化算子操作,而是把個(gè)體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子,每個(gè)粒子被隨機(jī)初始化位置和初速度,粒子通過參考全局最佳位置和局部最佳位置,進(jìn)行進(jìn)化也就是改變他的位置和速度。通過這樣不斷的迭代來求解問題。粒子群算法具有很好的生物社會(huì)背景[2]而且易理解、參數(shù)少、易實(shí)現(xiàn)。目前在科學(xué)研究與工程實(shí)踐中得到了廣泛關(guān)注[3-10]。人工生命的主要研究領(lǐng)域之一是探索自然界生物的群體行為,從而在計(jì)算機(jī)上構(gòu)建其群體模型。生物仿真學(xué)給人類的生活帶來了巨大的改變,因此科學(xué)家對(duì)研究此課題有很大的興趣,生物學(xué)家CraigReynolds在1987年提出了一個(gè)非常有影響的鳥群聚集模型[7],在他的仿真中,每一個(gè)個(gè)體遵循：<1>避免與鄰域個(gè)體相沖撞；<2>匹配鄰域個(gè)體的速度；<3>飛向鳥群中心,且整個(gè)群體飛向目標(biāo)。仿真中僅利用上面三條簡單的規(guī)則,就可以非常接近的模擬出鳥群飛行的現(xiàn)象。1990年,生物學(xué)家FrankHeppner也提出了鳥類模型[8],它的不同之處在于：鳥類被吸引飛到棲息地。在仿真中,一開始每一只鳥都沒有特定的飛行目標(biāo),只是使用簡單的規(guī)則確定自己的飛行方向和飛行速度〔每一只鳥都試圖留在鳥群中而又不相互碰撞,當(dāng)有一只鳥飛到棲息地時(shí),它周圍的鳥也會(huì)跟著飛向棲息地,這樣,整個(gè)鳥群都會(huì)落在棲息地。1995年,美國社會(huì)心理學(xué)家JamesKennedy和電氣工程師RussellEberhart[1]共同提出了粒子群算法,其基本思想是受對(duì)鳥類群體行為進(jìn)行建模與仿真的研究結(jié)果的啟發(fā)。他們的模型和仿真算法主要對(duì)FrankHeppner的模型進(jìn)行了修正,以使粒子飛向解空間并在最好解處降落。Kennedy在他的書中描述了粒子群算法思想的起源。自20世紀(jì)30年代以來,社會(huì)心理學(xué)的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。在人們的不斷交互過程中,由于相互的影響和模仿,他們總會(huì)變得更相似,結(jié)果就形成了規(guī)范和文明。人類的自然行為和魚群及鳥群并不類似,而人類在高維認(rèn)知空間中的思維軌跡卻與之非常類似。思維背后的社會(huì)現(xiàn)象遠(yuǎn)比魚群和鳥群聚集過程中的優(yōu)美動(dòng)作復(fù)雜的多：首先,思維發(fā)生在信念空間,其維數(shù)遠(yuǎn)遠(yuǎn)高于3；其次,當(dāng)兩種思想在認(rèn)知空間匯聚于同一點(diǎn)時(shí),稱其一致,而不是發(fā)生沖突。但思維背后的社會(huì)現(xiàn)象還不能完全理解鳥類的社會(huì)行為。顯然,我們的模仿協(xié)調(diào)性遠(yuǎn)不及鳥類自身行為的協(xié)調(diào)性。綜上,從開始的簡單鳥類的社會(huì)行為模仿到復(fù)雜的鳥類社會(huì)行為模仿,最后模仿越來越接近真實(shí)的鳥類社會(huì)行為,這就是粒子群算思想誕生的過程。2.2算法的原理粒子群優(yōu)化算法首先初始化一群隨機(jī)粒子,這些初始化的粒子都是空間搜索的潛在解,并且每個(gè)粒子都有一個(gè)被優(yōu)化函數(shù)決定的適應(yīng)值〔fittness,每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索[1]。粒子通過跟蹤兩個(gè)極值來更新自己；第一個(gè)就是粒子本身所找到的最優(yōu)解,這個(gè)解稱為個(gè)體極值〔pbest；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解,這個(gè)極值是全局極值〔gbest。假設(shè)在一個(gè)維的目標(biāo)搜索空間中,有個(gè)粒子組成一個(gè)群落,其中第個(gè)粒子表示為一個(gè)維的向量,。第個(gè)粒子的"飛行"速度也是一個(gè)維的向量,為,。第個(gè)粒子目前為止搜索到的最優(yōu)位置稱為個(gè)體極值,為,。整個(gè)粒子群目前為止搜索到的最優(yōu)位置為全局極值,為在找到這兩個(gè)最優(yōu)值時(shí),粒子根據(jù)如下的公式<1>和<2>來更新自己的速度和位置[12]：<2.2.1><> 其中為慣性權(quán)重,為學(xué)習(xí)因子,為0到1之間均勻分布的隨機(jī)數(shù)。 粒子群算法的性能很大程度上取決于算法參數(shù)的選擇,選取較好的參數(shù),不僅能縮短算法執(zhí)行的時(shí)間,而且可以提高解決問題的準(zhǔn)確性。這其中決定算法性能的參數(shù)有：粒子數(shù)、慣性權(quán)重、學(xué)習(xí)因子、等,各個(gè)參數(shù)的選擇一般情況下可以參考如下：粒子數(shù)：粒子數(shù)的多少選擇一般是根據(jù)問題的復(fù)雜性決定的。對(duì)于一般優(yōu)化問題取20到40個(gè)粒子完全可以得到很好的結(jié)果。粒子的維度：這是由優(yōu)化問題決定,就是問題解的維度。學(xué)習(xí)因子：學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個(gè)體的學(xué)習(xí)能力,一般取值范圍為0到4。慣性權(quán)重：決定了粒子對(duì)當(dāng)前速度繼承多少,合適的選擇可以使粒子具有均衡的探索能力和開發(fā)能力。慣性權(quán)重越大粒子的全局搜索能力越強(qiáng),反之慣性權(quán)重越小粒子的局部搜索能力越強(qiáng)。2.3算法的流程和流程圖算法的流程如下：步驟1：初始化粒子群,包括群體規(guī)模,每個(gè)粒子的位置和速度；步驟2：計(jì)算每個(gè)粒子的適應(yīng)度值,并將當(dāng)前微粒的位置和適應(yīng)值存儲(chǔ)在pbest中,將所有粒子的pbest中適應(yīng)值最好的個(gè)體存儲(chǔ)在gbest中；步驟3：根據(jù)公式<2.2.1>,<2.2.2>更新粒子的速度和位置；步驟4：每個(gè)粒子,用它的適應(yīng)度值和個(gè)體極值比較出較優(yōu)為新；步驟5：所有粒子的新的pbest選出最優(yōu)的,為新的gbest；步驟6：如果滿足結(jié)束條件<通常為預(yù)設(shè)的計(jì)算精度或到達(dá)最大循環(huán)次數(shù)>退出,否則返回步驟3。算法的流程圖如下：開始開始求出整個(gè)群體的全局最優(yōu)值求出每個(gè)粒子的個(gè)體最優(yōu)計(jì)算每個(gè)粒子的適應(yīng)值初始化每個(gè)粒子的速度和位置求出整個(gè)群體的全局最優(yōu)值求出每個(gè)粒子的個(gè)體最優(yōu)計(jì)算每個(gè)粒子的適應(yīng)值初始化每個(gè)粒子的速度和位置根據(jù)方程<2.2.1>對(duì)粒子的速度進(jìn)行進(jìn)化根據(jù)方程<2.2.1>對(duì)粒子的速度進(jìn)行進(jìn)化根據(jù)方程<2.2.2>對(duì)粒子的位置進(jìn)行進(jìn)化根據(jù)方程<2.2.2>對(duì)粒子的位置進(jìn)行進(jìn)化是否滿足條件否是否滿足條件是輸出結(jié)果總結(jié)：對(duì)于這種連續(xù)性的問題,用粒子群算法求解,只要隨著粒子數(shù)和迭代步數(shù)的增加,求解的結(jié)果會(huì)不斷趨近最優(yōu)解。2.4算法的優(yōu)缺點(diǎn)分析粒子群算法的優(yōu)點(diǎn)：粒子群優(yōu)化算法<PSO>是模擬鳥群覓食過程中的行為提出的一種基于群體智能的演化計(jì)算方法。該算法易于描述,在求解過程中只有非常少的參數(shù)需要調(diào)整并且無集中控制約束,不會(huì)因個(gè)體的故障影響整個(gè)問題的求解,確保了系統(tǒng)具備很強(qiáng)的魯棒性,相比其它演化算法,只需要較少的函數(shù)計(jì)算次數(shù)就可達(dá)到收斂,因此能以較大概率找到問題的全局最優(yōu)解。最后該算法最大的優(yōu)勢也在于編程簡單,易實(shí)現(xiàn)。粒子群算法的缺點(diǎn)：在求解全局最優(yōu)解的過程中對(duì)于有多個(gè)局部極值點(diǎn)的函數(shù),容易陷入到局部極值點(diǎn)中,得不到正確的結(jié)果。此外,由于粒子群算法問世時(shí)間不長在搜索糾結(jié)過程中缺乏精密搜索方法的配合,導(dǎo)致使用粒子群算法這種方法往往不能得到精確的結(jié)果。再則,PSO方法提供了全局搜索的可能,但并不能嚴(yán)格證明它在全局最優(yōu)點(diǎn)上的收斂性。因此,PSO一般適用于存在多個(gè)局部極值點(diǎn)而并不需要得到很高精度的優(yōu)化問題。對(duì)于本文而言,基本粒子群算法有一個(gè)致命的的缺點(diǎn),它速度更新和位置更新都是由特定的連續(xù)函數(shù)決定的,所以它只能解決連續(xù)性優(yōu)化問題,對(duì)于求解離散問題存在困難。..WORD格式可編輯3旅行商問題3.1TSP問題介紹旅行商問題<TravelingSalesmanProblem,簡稱TSP>是一個(gè)典型的NP問題也是一個(gè)典型的組合優(yōu)化問題。旅行商問題描述如下：給定n個(gè)城市及兩兩城市之間的距離,求一條經(jīng)過各城市一次且僅一次的最短路線。對(duì)于n個(gè)城市的TSP問題,存在著〔n-1!/2條可能的路徑,隨著城市數(shù)目n的增長,可能路徑的數(shù)目以n的指數(shù)倍增加。如果使用窮舉法搜索,需要考慮所有可能的情況,并兩兩比較,找出最優(yōu)解,那么可搜索的路徑及距離之和的計(jì)算量將正比于n!/2,算法的復(fù)雜度呈指數(shù)增長,要求出旅行商問題的最優(yōu)化解是很困難的,這也是該問題被認(rèn)為是NP問題的原因。同樣不幸的是,旅行商問題為離散問題,使得可以解決該問題的方法更少。因此,任何可以求解旅行商問題的方法都應(yīng)被高度關(guān)注。在生產(chǎn)生活中許多問題都可以轉(zhuǎn)化為旅行商這類問題的模型,因此旅行商問題具有很高的實(shí)際應(yīng)用價(jià)值,例如：城市管道鋪設(shè)優(yōu)化、物流行業(yè)中的車輛調(diào)度優(yōu)化、制造業(yè)中的切割路徑優(yōu)化以及電力系統(tǒng)配電網(wǎng)絡(luò)重構(gòu)等現(xiàn)實(shí)生活中的很多優(yōu)化問題都可以歸結(jié)為旅行商模型來求解,目前旅行商問題應(yīng)用的一個(gè)非常重要方面就是無人飛機(jī)的航路設(shè)計(jì)問題,即事先針對(duì)敵方防御區(qū)內(nèi)的威脅部署和目標(biāo)的分布情況,對(duì)無人作戰(zhàn)飛機(jī)的飛行航路進(jìn)行整體規(guī)劃設(shè)計(jì),可以綜合減小被敵方發(fā)現(xiàn)和反擊的可能性降低耗油量,從而顯著提高UCAV〔無人戰(zhàn)斗機(jī)執(zhí)行對(duì)地攻擊〔或偵察任務(wù)的成功率。3.2TSP問題定義設(shè)n為城市數(shù)目為n*n階距離矩陣,代表從城市i到城市j的距離,,。問題是要找出訪問每個(gè)城市且每個(gè)城市恰好只訪問一次的一條Hamilton回路,且其路徑的總長度是最短的。這條Hamilton回路可以表示為<1,2,...,n>的所有循環(huán)排列的集合,即為<1,2,...,n>的排列,表示訪問第i個(gè)城市后訪問第j個(gè)城市。目標(biāo)函數(shù)〔在粒子群算法中也可以叫做適應(yīng)值函數(shù)：城市Hamilton回路總長度為：<3.2.1>引入決策變量：<3.2.2>旅行商問題定義雖然非常簡單,使用窮舉法可以讓旅行商得到確定的最優(yōu)解,但隨著需要訪問城市數(shù)目的增加,會(huì)出現(xiàn)所謂的組合爆炸現(xiàn)象。所以,城市數(shù)目比較多的時(shí)候使用窮舉搜索策略幾乎是不可能做到的。..WORD格式可編輯4改進(jìn)的粒子群算法求解TSP問題4.1改進(jìn)的粒子群算法簡介由第二章的基本粒子群算法介紹,我們可以看出基本的粒子群算法對(duì)適應(yīng)度函數(shù)是有連續(xù)的要求。因此,基本粒子群算法在很多連續(xù)優(yōu)化問題中得到成功應(yīng)用,但粒子群算法不能直接應(yīng)用到離散問題中,那么,如果非要用它解決離散問題,就必須對(duì)算法進(jìn)行改進(jìn)。我們需要對(duì)方程<2.2.1>和方程<2.2.2>進(jìn)行改寫并且重新定義方程中加法和乘法的含義。下面我將介紹幾種改進(jìn)的粒子群算法,這些算法可以比較好的解決旅行商這種離散型問題。王翠茹,張江維,王等[13][14]對(duì)粒子群優(yōu)化算法進(jìn)行了改進(jìn)后,粒子不僅根據(jù)自身和同伴中最好的個(gè)體調(diào)整自己的飛行速度,而且按照一定的概率向其他個(gè)體學(xué)習(xí),這種強(qiáng)化后的學(xué)習(xí)行為更符合自然界生物的學(xué)習(xí)規(guī)律,更有利于粒子發(fā)現(xiàn)問題的全局最優(yōu)解。同時(shí)借鑒單點(diǎn)調(diào)整算法思想,提出了調(diào)整因子和調(diào)整序概念用以重構(gòu)粒子群算法。傅剛[15]認(rèn)為,用粒子群算法解決旅行商問題時(shí),調(diào)整因子的先后順序決定下一代種子的優(yōu)劣,以及能否很快地收斂到最優(yōu)值,如何恰當(dāng)?shù)亟鉀Q慣性權(quán)重個(gè)體間的協(xié)作和個(gè)體歷史最優(yōu)以及群體最優(yōu)對(duì)個(gè)體的影響是快速高效解決這一問題的關(guān)鍵。旁巍,王康平,周春光等[16]通過引入模糊矩陣提出了一種改進(jìn)的粒子群優(yōu)化算法,采用模糊矩陣來表示粒子的位置和速度,并重新定義速度和位置更新公式中的各種運(yùn)算符號(hào),這種改進(jìn)的粒子群算法給求解旅行商問題提供了一種新思路。基于這種思路下文將會(huì)介紹詳細(xì)的實(shí)現(xiàn)過程。郭文忠等[17]在介紹目前已經(jīng)有多種針對(duì)慣性權(quán)值的研究的基礎(chǔ)上,提出引入模糊技術(shù),并提出了佳粒子距的概念,并給出了一種慣性權(quán)值的模糊自適應(yīng)調(diào)整模型及其相應(yīng)的粒子群優(yōu)化算法,使用不同的慣性權(quán)值更新同一代種群,用于TSP問題的求解。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法不僅在求解組合優(yōu)化問題中的有效性,而且同時(shí)提高了算法的性能,加快了收斂速度。20XX中國學(xué)者易云飛,陳國鴻[18]提出了基于k-means的改進(jìn)粒子群算法求解旅行商問題。也是一種基本粒子群算法進(jìn)行了改進(jìn),每一步都借鑒貪心算法的思想取局部最優(yōu),這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問題的解,可以節(jié)省搜索時(shí)間,提高算法收斂速度。針對(duì)粒子群算法易陷入局部最優(yōu)的缺陷,采取了適合于求解旅行商問題的基于k-means的改進(jìn)策略,對(duì)粒子群進(jìn)行聚類分析,實(shí)現(xiàn)了粒子之間的信息交換,擴(kuò)大了粒子的搜索空間。兩個(gè)種群同時(shí)尋優(yōu),種群內(nèi)部獨(dú)立進(jìn)行粒子群算法進(jìn)化,種群個(gè)體最優(yōu)之間以一定概率進(jìn)行交叉,兩個(gè)種群同時(shí)尋優(yōu)可以減小算法陷入局部最優(yōu)的概率,種群間個(gè)體最優(yōu)的交叉能夠增強(qiáng)兩種群間以及粒子間的信息共享,及時(shí)傳遞最優(yōu)值信息,提高粒子向更好解進(jìn)化的速度。實(shí)驗(yàn)結(jié)果表明這種改進(jìn)粒子群算法是有效的。西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院的教授王文峰,劉光遠(yuǎn),溫萬惠[19]共同進(jìn)行了求解旅行商問題的自逃逸混合離散粒子群算法研究。這種算法是結(jié)合自然界中種群密度過大時(shí),個(gè)體自動(dòng)尋找棲息地的習(xí)性,提出了一種自逃逸思想：從候選邊集合中吸收新邊,給陷入局部區(qū)域的粒子一個(gè)變異,使其跳出局部區(qū)域。自逃逸思想提高了粒子群算法的全局搜索能力,成功地克服了早熟的缺陷。實(shí)驗(yàn)結(jié)果表明,自逃逸的粒子群算法比混合蟻群算法具有更好的效率和收斂速度,尤其在較大規(guī)模的實(shí)例上更具優(yōu)勢。4.2引入模糊矩陣的粒子群算法求解TSP問題4.2.1旅行商問題的解用模糊矩陣表示在用模糊矩陣[16]表示旅行問題的解前,我們首先引入以下幾個(gè)定義：定義1：一個(gè)城市為n的旅行商問題,設(shè)集合s為旅行商問題的一個(gè)解序列,s可以表示為,其中表示旅行商問題的解即Hamilton回路中第i個(gè)結(jié)點(diǎn)。定義2：一個(gè)城市為n的旅行商問題,設(shè)集合M是旅行商問題的結(jié)點(diǎn)集合,M可以表示為：,那么表示旅行商問題中編號(hào)為i的具體結(jié)點(diǎn)。對(duì)上述的定義1和定義2,進(jìn)行解釋：集合S中的每個(gè)元素,表示旅行商問題可行解中按照訪問的先后次序的第i個(gè)結(jié)點(diǎn),即已訪問了i-1個(gè)結(jié)點(diǎn),即將訪問第i個(gè)結(jié)點(diǎn),還有n-i個(gè)結(jié)點(diǎn)需要訪問；對(duì)于集合M中的元素表示的是旅行商問題中編號(hào)為i的結(jié)點(diǎn)<這個(gè)結(jié)點(diǎn)的順序不發(fā)生改變>。則整個(gè)狀態(tài)空間可以表示為S和M的笛卡爾積：S與M的模糊關(guān)系R有如下意義：<4.2.1>是隸屬度函數(shù),表示在一個(gè)可行解中第i個(gè)要訪問的點(diǎn)選擇編號(hào)為j的結(jié)點(diǎn)的隸屬度。顯然,如果我們有了這個(gè)隸屬度函數(shù),那么我就可以確定一個(gè)模糊矩陣。下面介紹旅行商問題的解是怎樣用模糊矩陣表示的。在上文定義中已經(jīng)分別提到了集合和集合它們的模糊關(guān)系可以用模糊矩陣來表示,因此,從S到M的模糊關(guān)系可以寫成：<4.2.2>其中,它表示集合S中第i個(gè)元素與集合M中第j個(gè)元素對(duì)于關(guān)系R的隸屬程度。4.2.2引入模糊矩陣的粒子群算法重新定義基于上面提出的用模糊矩陣表示旅行商問題的解,進(jìn)而提出了一種改進(jìn)的粒子群算法。首先重新定義速度和位置的更新公式<2.2.1>、<2.2.2>中的符號(hào)與操作符。粒子的位置是要用來表示旅行商問題的解,因此定義為公式〔這種形式：〔4.2.3粒子的速度重新定義為：〔4.2.4操作符"乘法"的重新定義:我們使用符號(hào)""表示新的乘法,設(shè)a是一個(gè)實(shí)數(shù),則：〔4.2.5操作符"減法"的重新定義:我們使用符號(hào)""表示新的減法,則：〔4.2.6操作符"加法"的重新定義:我們使用符號(hào)""表示新的加法,加法可以是速度之間的加法也可以是位置和速度之間的加法則分別表示為：〔4.2.7〔4.2.8根據(jù)以上對(duì)粒子群算法的重新定義,可以把公式〔2.2.1、〔2.2.2分別改寫。速度更新公式為：〔4.2.9其中為慣性權(quán)重,為學(xué)習(xí)因子,為0到1之間均勻分布的隨機(jī)數(shù),表示第i個(gè)粒子第t次迭代后的速度,表示第i個(gè)粒子第t次迭代后的位置,表示第i個(gè)粒子第t次迭代后的局部最好位置,表示第i個(gè)粒子第t次迭代后的全局最好位置。位置更新公式為：〔.3引入模糊矩陣的粒子群算法求解旅行商問題的具體操作基本粒子群算法通過引入模糊矩陣把公式〔2.2.1、〔2.2.2分別改寫為公式〔4.2.9、〔4.2.10,為了確保改寫后粒子群算法公式能夠適用這種矩陣的變化,因此,在初始化時(shí)需要有許多特定的條件。下面先介紹這種改進(jìn)的粒子群算法是如何初始化的。初始化位置：〔4.2.11矩陣中的元素是按照如下條件隨機(jī)生成：〔4.2.12〔4.2.13速度初始化：〔4.2.14隨機(jī)產(chǎn)生速度中元素必須也滿足下面條件：〔4.2.15下面引入幾個(gè)引理,能很好的說明為何會(huì)有如此的條件限制初始位置和初始速度。引理1：設(shè)a是一個(gè)實(shí)數(shù),如果速度V滿足條件,則也滿足條件。引理2：如果位置X滿足,并且位置V滿足,則也滿足。引理3：如果位置和滿足,則滿足條件。引理4：如果速度和速度滿足,則也滿足。根據(jù)上述引理可以得到如下結(jié)論,在需要公式<4.2.9>和<4.2.10>進(jìn)行更新的矩陣,若矩陣滿足等式<4.2.13>和<4.2.15>,則在以后的更新迭代中,更新后的速度將總是滿足條件<4.2.15>,并且更新后的位置也將總是滿足條件<4.2.13>。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法進(jìn)行證明,由于證明過程比較簡單,所以在此我就不詳細(xì)說明。有了以上結(jié)論我們可以成功的把粒子群算法思想應(yīng)用于離散的旅行商問題中。但這不能說粒子群算法已經(jīng)可以解決旅行商問題了,這其中還存在有些問題需要解決。這其中最主要的問題是:在每次迭代后,位置矩陣中的元素可能產(chǎn)生負(fù)值,這與條件〔4.2.13是不相符的。因此,在每次迭代后都應(yīng)該對(duì)元素中是否出現(xiàn)負(fù)數(shù)進(jìn)行檢測。對(duì)于不符合條件的元素可以采用如下規(guī)范化進(jìn)行操作：首先將矩陣中所有為負(fù)數(shù)的元素清零,然后將位置矩陣<4.2.3>在不違反<4.2.12>的情況下進(jìn)行如下的變化：〔4.2.16算法流程描述：在介紹算法流程前,首先介紹一個(gè)概念：非模糊化〔也就是模糊化的一個(gè)逆過程。非模糊化采用的方法為："最大數(shù)法",是非模糊化的常用方法,在這種方法中,用一個(gè)標(biāo)志數(shù)組記錄是否選擇了矩陣中的列,并用一個(gè)路徑數(shù)組來存儲(chǔ)路徑解。首先所有的列都標(biāo)記為"未選擇",然后對(duì)于矩陣中的每一行,選擇未被其他行選擇過的并且具有最大值的那個(gè)元素,然后將這個(gè)元素所在的列標(biāo)記為"選擇",并且該列的列號(hào)被記錄在路徑數(shù)組中,表示在本行中選擇序號(hào)為該列號(hào)的節(jié)點(diǎn)。當(dāng)所有的行都被處理完成后,就可以從路徑數(shù)組中得到解路徑以及解路徑的費(fèi)用值。采用這種方法,能夠保證最終得到旅行商問題的可行解[16]。步驟1：初始化步驟1-1：設(shè)置粒子群算法中粒子的個(gè)數(shù),和最大迭代次數(shù),對(duì)于解決旅行商問題的粒子算法中的迭代次數(shù)設(shè)置非常關(guān)鍵,因?yàn)榈螖?shù)一般為算法終止條件,因此選擇合適的迭代次數(shù)對(duì)算法的性能影響非常大。步驟1-2：應(yīng)用上述初始化過程,對(duì)粒子群算法中的每個(gè)粒子進(jìn)行初始化得到一個(gè)隨機(jī)的位置,并且隨機(jī)初始化得到一個(gè)隨機(jī)速度。最后讓這些初始化的粒子位置為粒子的局部最優(yōu)解,并在這些初始化后粒子群中選出全局最優(yōu)解。步驟2：計(jì)算粒子群算法中每個(gè)粒子的速度和位置。步驟2-1：用公式〔4.2.9更新每個(gè)粒子的速度。步驟2-2:用公式〔4.2.10更新每個(gè)粒子的位置。步驟2-3：對(duì)新位置矩陣進(jìn)行非模糊化,計(jì)算新位置的費(fèi)用。如果新位置的費(fèi)用比當(dāng)前局部最好解的費(fèi)用還要小,則用新的位置更新當(dāng)前的局部最好解。步驟3：如果粒子群算法中粒子的局部最優(yōu)解中存在優(yōu)于當(dāng)前的全局最優(yōu)解時(shí),則用此局部最優(yōu)解來更新當(dāng)前的全局最優(yōu)解。步驟4：判斷當(dāng)前的迭代次數(shù)是否達(dá)到預(yù)先設(shè)定的最大值,如果大于轉(zhuǎn)步驟5,否則轉(zhuǎn)步驟2.步驟5：輸出最好路徑和費(fèi)用?？偨Y(jié)：這種改進(jìn)的粒子群優(yōu)化算法,其算法的流程和基本的粒子群算法的流程相似,只是在一些計(jì)算方面有些區(qū)別。該算法在解決旅行商這類離散型問題表現(xiàn)的不是那么高效,但它也是粒子群算法解決離散型問題的新嘗試。值得注意的是,該算法不僅僅能夠解決旅行商問題,經(jīng)過修改后也能夠解決一般路由問題。由于旅行商問題的特殊性,模糊矩陣的規(guī)模是n2,在一些簡單的路由問題中,可以縮減矩陣的規(guī)模。另外,能否尋找更好的非模糊化的方法,也是今后的工作需要解決的問題[16]。4.3引入交換算子和交換序的粒子群算法求解TSP問題4.3.1引入交換算子和交換序的粒子群算法定義和流程黃嵐等,王康平等[11]通過引入交換子和交換序的概念,并對(duì)基本公式中的符號(hào)賦予新的含義,構(gòu)造了一種特殊的粒子群優(yōu)化算法,這種改進(jìn)的粒子群算法使得用粒子群算法思想解決離散問題成為可能。后來Clerc,M[12]重新定義了運(yùn)算符號(hào)和規(guī)則,并用于求解離散問題,重新定義后的粒子群算法相比以前的算法有了很明顯的改觀。下文將會(huì)把這種改進(jìn)的粒子群算法應(yīng)用到解決旅行商問題中。引入交換算子和交換序是另種一種改進(jìn)的粒子群算法去解決旅行商這種離散型問題的方法。這種方法也是粒子群算法應(yīng)用到離散型問題的第一次嘗試的方法。此方法的問世,使得粒子群算法的應(yīng)用領(lǐng)域反生巨大的改變。下面先介紹交換算子和交換序的概念。交換算子：是用來交換一個(gè)有序序列中元素的位置,一個(gè)交換算子可以使這個(gè)有序序列中兩個(gè)元素位置發(fā)生調(diào)換。具體到改變旅行商問題中,表示旅行商的可行解序列發(fā)生改變,改變后的結(jié)果仍是旅行商問題的可行解。用SO〔i,j表示一個(gè)交換子,i,j就表示序列中第i個(gè)元素和序列中第j個(gè)元素的位置發(fā)生調(diào)換。例：序列S=〔1,2,3,4,交換算子SO〔1,2,用表示交換算子作用于序列S,即SSO變化后得到=〔2,1,3,4這里的被賦予特定含義。交換序：一個(gè)或多個(gè)交換子的有序隊(duì)列就是交換序。如交換算子SO,SOO,SOOO,SOOOO...組成交換序SS,那么SS=〔SO,SOO,SOOO,SOOOO。當(dāng)SS作用一個(gè)序列就等于這個(gè)交換序中每個(gè)交換算子作用于這個(gè)序列。例：序列S=〔1,2,3,4交換序SS<SO,SOO>,SO<1,2>,SOO<3,4>,那么SSS=SSOSOO=〔2,1,4,3。在上邊兩個(gè)概念基礎(chǔ)上再定義幾個(gè)概念：交換序的等價(jià)集：不同的交換序作用于同一解上可能產(chǎn)生相同的新解,所有有相同效果的交換序的集合稱為交換序的等價(jià)集?；窘粨Q序：在交換序等價(jià)集中,擁有最少交換子的交換序稱為該等價(jià)集的基本交換序。例：設(shè)給定兩個(gè)解路徑A=〔1,2,3,4,5和B=〔4,3,2,1,5,需要構(gòu)造一個(gè)基本交換序SS,使得BSS=A可以看出A〔1=B〔4,A〔2=B〔3,A〔3=B〔2,A〔4=B〔1,A〔5=B〔5可以看出第一個(gè)交換算子為SO〔1,4,第二個(gè)交換算子為SO〔2,3,第三個(gè)交換算子為SO〔3,2,第四個(gè)交換算子為SO〔4,1,第五個(gè)交換算子為SO〔5,5那么SS=〔〔1,4,〔2,3,〔3,2,〔4,1,〔5,5,即SS=BA,這里的和被賦予新的含義。在引入交換序和交換序列后基本的粒子群算法的公式〔2.2.1需要改寫,計(jì)算符號(hào)的含義也需要改變。粒子速度更新公式改寫為：〔4.3.1這個(gè)公式的和的含義于上文概念介紹提到的含義相同；和為0到1之間的隨機(jī)數(shù),表示第i個(gè)粒子第t次迭代后的速度,表示第i個(gè)粒子第t次迭代后的位置,表示第i個(gè)粒子第t次迭代后的局部最好位置,表示第i個(gè)粒子第t次迭代后的全局最好位置；表示基本交換序中的所有交換子以概率保留；同理表示基本交換序中的所有交換子以概率保留；可以看出和的值越大保留的交換子就越多。粒子群算法思想的向局部最好解和全局最好解學(xué)習(xí),改變移動(dòng)方向在這個(gè)速度更新公式中也得到體現(xiàn)。粒子的位置更新公式保持原來的基本粒子群算法的公式〔2.2.2,只是加法的含義發(fā)生改變,因此新位置更新公式可以改寫為：〔4.3.2算法的步驟：〔1初始化粒子群,即給群體中的每個(gè)粒子賦一個(gè)隨機(jī)的初始解和一個(gè)隨機(jī)的交換序；<2>如果滿足結(jié)束條件一般為最大迭代次數(shù),轉(zhuǎn)步驟<5>;<3>根據(jù)粒子當(dāng)前位置,計(jì)算其下一個(gè)位置,即旅行商問題新的可行解；具體到一下步驟：1>計(jì)算和之間的差A(yù),A=其中A是一個(gè)基本交換序,表示A作用于得到；2>同理,計(jì)算B=,其中B也是一基本交換序；3>根據(jù)〔4.3.1式計(jì)算速度,并將交換序轉(zhuǎn)換為一個(gè)基本交換序;4>計(jì)算搜索到的新解〔4.3.2；5>計(jì)算解的適應(yīng)度,如果找到一個(gè)更好的解,則更新；<4>比較每個(gè)粒子的最好適應(yīng)度值,如果整個(gè)群體找到一個(gè)更好的解,更新,轉(zhuǎn)步驟<2>；<5>顯示求出的結(jié)果值〔本文中對(duì)該問題實(shí)現(xiàn)使用圖像輸出結(jié)果,充分利用Matlab的強(qiáng)大繪圖能力。4.3.2實(shí)驗(yàn)結(jié)果與參數(shù)設(shè)置設(shè)10個(gè)城市的二維坐標(biāo)分布為：city10=[0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634];這十個(gè)城市的最短Hamilton回路為2.691當(dāng)粒子數(shù)為30,迭代次數(shù)取100,和都取0.25時(shí)運(yùn)行結(jié)果如下：注：第二個(gè)圖像中上邊線表示平均距離,下邊線表示最短距離,以下所有這種圖像都是本規(guī)則。當(dāng)粒子數(shù)為30,迭代次數(shù)取100,和都取0.5時(shí)運(yùn)行結(jié)果如下：經(jīng)過反復(fù)測試,得出當(dāng)旅行商問題的規(guī)模比較小時(shí),和的取值小更有利于求到最優(yōu)解。當(dāng)粒子數(shù)為30,迭代次數(shù)取200,和都取0.25時(shí)運(yùn)行結(jié)果如下：經(jīng)過反復(fù)測試,顯然當(dāng)粒子數(shù)和、一定時(shí),迭代次數(shù)越多該方法求到最優(yōu)解的概率就越大。當(dāng)粒子數(shù)為40,迭代次數(shù)取200,和都取0.25時(shí)運(yùn)行結(jié)果如下：經(jīng)過反復(fù)測試,顯然粒子群數(shù)越多對(duì)于求解旅行商更有利。當(dāng)粒子數(shù)為40,迭代次數(shù)取400,和都取0.25時(shí)測試得到了最優(yōu)解運(yùn)行結(jié)果如下：這個(gè)結(jié)果就為該旅行商問題的最優(yōu)解?？偨Y(jié)：十個(gè)城市的旅行商問題由于問題的規(guī)模比較小,可以盡可能讓和都取較小的值,粒子數(shù)盡可能的多,迭代次數(shù)也比較大時(shí),求出最優(yōu)解的可能性就越大。設(shè)30個(gè)城市二維坐標(biāo)分布為：city30=[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450];目前測試的最短路程為423.471.當(dāng)粒子數(shù)為30,迭代次數(shù)取200,和都取0.25時(shí)運(yùn)行結(jié)果如下：當(dāng)粒子數(shù)為30,迭代次數(shù)取200,和都取0.85時(shí)運(yùn)行結(jié)果如下：可以看出對(duì)于問題規(guī)模稍大的旅行商問題,粒子群算法的效率開始惡化。經(jīng)過反復(fù)測試,還是可以得出,在其它參數(shù)不變的情況下,和的取值大,有利于對(duì)交換算子的保留,從而提高得到最優(yōu)解的概率。當(dāng)粒子數(shù)為30,迭代次數(shù)取400,和都取0.85時(shí)運(yùn)行結(jié)果如下：當(dāng)粒子數(shù)為40,迭代次數(shù)取400,和都取0.85時(shí)運(yùn)行結(jié)果如下:可以看出當(dāng)旅行商問題的規(guī)模比較大時(shí),增加粒子群算法中的粒子數(shù)和迭代次數(shù),該算法效率提高的不明顯,因此該算法對(duì)于解決規(guī)模比較大的旅行商問題存在局限性。給出50個(gè)城市的二維坐標(biāo)分布為：city50=[3132;3239;4030;3769;2768;3752;3846;3162;3048;2147;2555;1657;1763;4241;1733;2532;564;852;1242;738;525;1077;4535;4257;3222;2723;5637;5241;4949;5848;5758;3910;4610;5915;5121;4828;5233;5827;6133;6263;2026;56;1313;2110;3015;3616;6242;6369;5264;4367];到目前為止經(jīng)過大量測試最短距離為427.855當(dāng)粒子數(shù)為30,迭代次數(shù)取200,和都取0.85時(shí)運(yùn)行結(jié)果如下：給出75個(gè)城市的二維坐標(biāo)分布為：city75=[4821;5226;5550;5050;4146;5142;5545;3833;3334;4535;4037;5030;5534;5438;2613;155;2148;2939;3344;1519;1619;1217;5040;2253;2136;2030;2629;4020;3626;6248;6741;6235;6527;6224;5520;3551;3050;4542;2145;366;625;1128;2659;3060;2222;2724;3020;3516;5410;5015;4413;3560;4060;4066;3176;4766;5070;5772;5565;238;743;956;1556;1070;1764;5557;6257;7064;644;595;504;6015;6614;668;4326];該旅行商問題目前測試的最短距離為549.18。當(dāng)粒子數(shù)為30,迭代次數(shù)取200,和都取0.85時(shí)運(yùn)行結(jié)果如下：可以看出不管是50個(gè)城市的旅行商問題還是75個(gè)城市的旅行商問題,用這種粒子群算法的效率已經(jīng)非常低了?？偨Y(jié)：引入交換算子和交換序的改進(jìn)粒子群算法,對(duì)于問題規(guī)模比較小的旅行商問題,其算法可以表現(xiàn)出很高的效率,但是隨著問題規(guī)模的增加該算法在解決旅行商問題的效率急劇惡化。..WORD格式可編輯5結(jié)論粒子群優(yōu)化<PSO>是一種新興的基于群體智能的啟發(fā)式全局隨機(jī)搜索算法,具有易理解、易實(shí)現(xiàn)、全局搜索能力強(qiáng)等特點(diǎn),為各個(gè)領(lǐng)域的研究人員提供了一種有效的全局優(yōu)化技術(shù)。本文對(duì)粒子群算法的原理和思想做了詳細(xì)的介紹,目前粒子群優(yōu)化算法從所解決的問題上分類可以分為解決連續(xù)問題的粒子群算法和解決離散問題的粒子群算法。解決連續(xù)問題的粒子群算法對(duì)所解決問題連續(xù)性有要求,并且在連續(xù)問題上具有很高的效率。在解決連續(xù)的問題時(shí),隨著粒子群算法中的參數(shù)〔粒子數(shù)和參數(shù)迭代次數(shù)增加,所求問題的結(jié)果是可以不斷趨近最優(yōu)解。后來也有許多學(xué)者基于基本粒子群算法的思想提出許多改進(jìn)的粒子群算法,比如,帶壓縮因子的粒子群算法,權(quán)重改進(jìn)的粒子群算法,變學(xué)習(xí)因子的粒子群算法,混合粒子群算法等。這些改進(jìn)的粒子群算法的提出,使得求解連續(xù)問題的效率更高。作者認(rèn)為,這些改進(jìn)的解決連續(xù)問題的粒子群算法對(duì)解決離散問題的粒子群算法有很高的參考價(jià)值。解決離散問題的粒子群算法也是基于基本粒子群算法的思想改進(jìn)而來的,原始的粒子群算法是不能解決離散問題的,更不要說旅行商這類NP問題,但后來隨著學(xué)者的不斷研究,通過引入一些概念并對(duì)符號(hào)的含義做了重新定義,使得粒子群算法的思想在離散問題上應(yīng)用成為可能。本文主要介紹了兩種改進(jìn)的粒子群算法在離散問題上的應(yīng)用,第一種就是引入模糊矩陣的粒子群算法,采用模糊矩陣來表示粒子的位置和速度,并對(duì)速度更新公式和位置更新公式中的各種運(yùn)算符號(hào)〔加法,減法和乘法重新定義,該算法是求解旅行商問題的新嘗試。值得注意的是,該算法不僅僅能夠解決旅行商問題,經(jīng)過修改后也能夠解決一般的路由問題。由于旅行商問題的特殊性,模糊矩陣的規(guī)模是n2,在一些簡單的路由問題中,可以縮減矩陣的規(guī)模。另外,能否尋找更好的非模糊化的方法,也是今后的工作需要解決的問題。另一種就是引入交換算子和交換序的粒子群算法,這種方法是實(shí)現(xiàn)了粒子群算法在離散問題上應(yīng)用的第一次嘗試。該方法在旅行商問題規(guī)模比較小時(shí)表現(xiàn)出很高的效率,但是隨問題規(guī)模的增大算法的性能急劇下降。加上旅行商問題特殊性,決定了該算法很難求出較大規(guī)模旅行商問題的最優(yōu)解。作者認(rèn)為改進(jìn)的粒子群算法求解旅行商問題的過程不像求解連續(xù)問題,會(huì)不斷的接近最優(yōu)解,而是,存在一定的概率向最優(yōu)解的靠近。當(dāng)對(duì)于規(guī)模比較小旅行商問題選取較大的迭代數(shù)和粒子群規(guī)模,粒子群算法表現(xiàn)出很高的效率。但問題規(guī)模比較大時(shí),有可能很快就求出了較優(yōu)的解,也有可能很久都求不出較優(yōu)解。因此要使粒子群算法在規(guī)模較大旅行商問題表現(xiàn)出很高的優(yōu)越性,還有待于研究粒子間新的配合方案。..WORD格式可編輯專業(yè)知識(shí)分享致謝歷時(shí)將近三個(gè)月的時(shí)間終于將這篇論文寫完,在論文的寫作過程中遇到了無數(shù)的困難和障礙,都在同學(xué)和老師的幫助下度過了。感謝所有幫助過我的人,尤其要強(qiáng)烈感謝我的論文指導(dǎo)老師—xxx老師,她對(duì)我進(jìn)行了無私的指導(dǎo)和幫助,不厭其煩的幫助進(jìn)行論文的改進(jìn)。其中開題報(bào)告給我改了九遍,外文翻譯給我改了六遍,老師對(duì)我寫的每篇文章都仔細(xì)檢查,甚至連標(biāo)點(diǎn)符號(hào)都給我指出來,老師對(duì)學(xué)術(shù)的精益求精,深深的影響著我,我想這是我跟著xxx老師學(xué)到最有價(jià)值的東西。另外,在校圖書館查找資料的時(shí)候,圖書館的老師也給我提供了很多方面的支持與幫助。在此向他們表示最衷心的感謝！也感謝學(xué)校給我們開放的機(jī)房方便我們下載資料。感謝這篇論文所涉及到的各位學(xué)者。本文引用了數(shù)位學(xué)者的研究文獻(xiàn),如果沒有各位學(xué)者的研究成果的幫助和啟發(fā),我將很難完成本篇論文。光陰似箭,白駒過隙。轉(zhuǎn)眼間四年大學(xué)本科生活即將結(jié)束,我在這里必須感謝我的學(xué)?！猉X工業(yè)大學(xué)和這四年給我們孜孜不倦上課的老師們,是你們教會(huì)了我知識(shí),是你們教會(huì)了我該怎樣做學(xué)問和怎樣做人。我還必須感謝所有101001班的所有同學(xué)們,謝謝你們給我?guī)椭?陪我成長,尤其要感謝陪我度過無數(shù)日日夜夜的舍友們,謝謝！最后,由于作者的學(xué)術(shù)水平有限,所寫論文難免有不足之處,懇請各位老師和學(xué)友批評(píng)和指正！..WORD格式可編輯專業(yè)知識(shí)分享畢業(yè)設(shè)計(jì)〔論文知識(shí)產(chǎn)權(quán)聲明本人完全了解XX工業(yè)大學(xué)有關(guān)保護(hù)知識(shí)產(chǎn)權(quán)的規(guī)定,即：本科學(xué)生在校攻讀學(xué)士學(xué)位期間畢業(yè)設(shè)計(jì)〔論文工作的知識(shí)產(chǎn)權(quán)屬于XX工業(yè)大學(xué)。本人保證畢業(yè)離校后,使用畢業(yè)設(shè)計(jì)〔論文工作成果或用畢業(yè)設(shè)計(jì)〔論文工作成果發(fā)表論文時(shí)署名單位仍然為XX工業(yè)大學(xué)。學(xué)校有權(quán)保留送交的畢業(yè)設(shè)計(jì)〔論文的原文或復(fù)印件,允許畢業(yè)設(shè)計(jì)〔論文被查閱和借閱；學(xué)?？梢怨籍厴I(yè)設(shè)計(jì)〔論文的全部或部分內(nèi)容,可以采用影印、縮印或其他復(fù)制手段保存畢業(yè)設(shè)計(jì)〔論文?！脖Ｃ艿漠厴I(yè)設(shè)計(jì)〔論文在解密后應(yīng)遵守此規(guī)定畢業(yè)設(shè)計(jì)〔論文作者簽名：指導(dǎo)教師簽名：日期：..WORD格式可編輯專業(yè)知識(shí)分享畢業(yè)設(shè)計(jì)〔論文獨(dú)創(chuàng)性聲明秉承學(xué)校嚴(yán)謹(jǐn)?shù)膶W(xué)風(fēng)與優(yōu)良的科學(xué)道德,本人聲明所呈交的畢業(yè)設(shè)計(jì)〔論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知,除了文中特別加以標(biāo)注和致謝的地方外,畢業(yè)設(shè)計(jì)〔論文中不包含其他人已經(jīng)發(fā)表或撰寫過的成果,不包含他人已申請學(xué)位或其他用途使用過的成果。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了致謝。畢業(yè)設(shè)計(jì)〔論文與資料若有不實(shí)之處,本人承擔(dān)一切相關(guān)責(zé)任。畢業(yè)設(shè)計(jì)〔論文作者簽名：指導(dǎo)教師簽名：日期：..WORD格式可編輯專業(yè)知識(shí)分享參考文獻(xiàn)[1]KennedyJ,EberhartR.Particleswarmoptimization[A].in:Proceedingsofthe4thIEEEInternationalConferenceonNeuralNetworks[C],Piscataway:IEEEServiceCenter,1995,pp.1942-1948.[2]GarnierS,GautraisJ,TheraulazG.Thebiologicalprinciplesofswarmintelligence[J].SwarmIntelligence,vol.30,no.1,2007,pp.3-31.[3]EberhartR,ShiY.Particleswarmoptimization:Developments,applicationsandresources[A].in:Proc.IEEECongr.Evol.Comput.[C],vol.1,no.1,2001,pp.81-86.[4]ParsopoulosK,VrahatisM.Recentapproachestoglobaloptimizationproblemsthroughparticleswarmoptimization[J].NaturalComputing,vol.40,no.1,2002,pp.235-306.[5]謝曉鋒,張文俊,楊之廉.微粒群算法綜述[J].控制與決策,vol.18,no.2,2003:129-134.[6]HuX,ShiY,EberhartR.Recentadvancesinparticleswarm[A].in:Proc.IEEECongr.Evol.Comput.[C],vol.1,2004,pp.90-97.[7]BanksA,VincentJ,AnyakohaC.Areviewofparticleswarmoptimization.PartI:backgroundanddevelopment[J].NaturalComputing,vol.45,no.6,2007,pp.467-484.[8]王萬良,唐宇.微粒群算法的研究現(xiàn)狀與展望[J].XX工業(yè)大學(xué)學(xué)報(bào),vol.35,no.2,2007:136-141.[9]PoliR,KennedyJ,BlackwellT.Particleswarmoptimization:Anoverview[J].SwarmIntelligence,vol.1,no.1,2007,pp.33-57.[10]JelmerVanA,RobertB,BartDeS.Particleswarmsinoptimizationandcontrol[A].in:Proceedingsofthe17thWorldCongressTheInternationalFederationofAutomaticControl[C],Seoul,Korea,2008,pp.5131-5136.[11]黃嵐,王康平,周春光,等.粒子群優(yōu)化算法求解旅行商問題[J].XX大學(xué)學(xué)報(bào)〔理學(xué)版,2003〔4.[12]Clerc,M.DiscreteParticleSwarmOptimization,illustratedbytheTravelingSalesmanProblem.Newoptimizationtechniqueinengineering[C].Springer-Verlag,2004.[13]王翠茹,張江維,王,等.改進(jìn)粒子群優(yōu)化算法求解旅行商問題[J].華北電力大學(xué)學(xué)報(bào),2005〔6.[14]王翠茹,馮海迅,張江維,等.基于改進(jìn)粒子群優(yōu)化算法求解旅行商問題[J].微計(jì)算機(jī)信息,2006〔22.[15]傅剛.PSO-TSP問題綜述XX職業(yè)技術(shù)學(xué)院,XXXX350001科技論壇,2013.[16]龐巍,王康平,周春光,等.模糊離散粒子群優(yōu)化算法求解旅行商問題[J].小型微型計(jì)算機(jī)系統(tǒng),2005〔8.[17]郭文忠,陳國龍.求解TSP問題的模糊自適應(yīng)粒子群算法[J].計(jì)算機(jī)科學(xué),2006〔6.[18]易云飛陳國鴻,基于k-means的改進(jìn)粒子群算法求解旅行商問題<XX學(xué)院>2012<6>.[19]王文峰,劉光遠(yuǎn),溫萬惠求解TSP問題的自逃逸混合離散粒子群算法研究西南大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院XX400715,2007<6>...WORD格式可編輯專業(yè)知識(shí)分享附錄1程序程序1函數(shù)1function[xm,fv]=PSO<fitness,N,c1,c2,w,M,D>formatlong;%初始化種群的個(gè)體fori=1:Nforj=1:Dx<i,j>=randn;%隨機(jī)初始化位置v<i,j>=randn;%隨機(jī)初始化速度endend%先計(jì)算各個(gè)粒子的適應(yīng)度,并初始化Pi和Pgfori=1:Np<i>=fitness<x<i,:>>;y<i,:>=x<i,:>;endpg=x<N,:>;%Pg為全局最優(yōu)fori=1:<N-1>iffitness<x<i,:>><fitness<pg>pg=x<i,:>;endend%進(jìn)入主要循環(huán),按照公式依次迭代fort=1:Mfori=1:Nv<i,:>=w*v<i,:>+c1*rand*<y<i,:>-x<i,:>>+c2*rand*<pg-x<i,:>>;x<i,:>=x<i,:>+v<i,:>;iffitness<x<i,:>><p<i>p<i>=fitness<x<i,:>>;y<i,:>=x<i,:>;endifp<i><fitness<pg>pg=y<i,:>;endendPbest<t>=fitness<pg>;endxm=pg';fv=fitness<pg>;函數(shù)2：functionF=fitness<x>F=0;fori=1:30F=F+x<i>^2;end程序2城市的位置輸入到計(jì)算機(jī)中用下面的函數(shù)：function[DLn,cityn]=tsp<n>ifn==10city10=[0.40.4439;0.24390.1463;0.17070.2293;0.22930.761;0.51710.9414;0.87320.6536;0.68780.5219;0.84880.3609;0.66830.2536;0.61950.2634];%10citiesd'=2.691fori=1:10forj=1:10DL10<i,j>=<<city10<i,1>-city10<j,1>>^2+<city10<i,2>-city10<j,2>>^2>^0.5;endendDLn=DL10;cityn=city10;end適應(yīng)度函數(shù)：functionF=SumDistance<dislist,s>DistanV=0;n=size<s,2>;fori=1:<n-1>DistanV=DistanV+dislist<s<i>,s<i+1>>;%此函數(shù)用來計(jì)算總路程endDistanV=DistanV+dislist<s<n>,s<1>>;F=DistanV;繪圖：functionm=plotTSP10<Clist,BSF,bsf,p,f>CityNum=size<Clist,1>;fori=1:CityNum-1axis<[0,1,0,1]>;%繪制點(diǎn)的連線圖plot<[Clist<BSF<i>,1>,Clist<BSF<i+1>,1>],[Clist<BSF<i>,2>,Clist<BSF<i+1>,2>],'rs-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g'>;holdon;%'rs-','LineWidth',3,'MarkerEdgeColor','','MarkerFaceColor','g'-表示線為紅色實(shí)線線寬為2,點(diǎn)為方形綠點(diǎn)邊緣為黑色endaxis<[0,1,0,1]>;%繪制最后一個(gè)點(diǎn)和起始點(diǎn)的連線plot<[Clist<BSF<CityNum>,1>,Clist<BSF<1>,1>],[Clist<BSF<CityNum>,2>,Clist<BSF<1>,2>],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g'>;%'ms-','LineWidth',3,'MarkerEdgeColor','','MarkerFaceColor','g'-表示線為洋紅色實(shí)線線寬為2,點(diǎn)為方形綠點(diǎn)邊緣為黑色title<[num2str<CityNum>,'TSP']>;iff==0text<0.1,0.1,['迭代次數(shù)',int2str<p>,'最短距離',num2str<bsf>]>;endholdoff;pause<0.05>;初始化和變換：functionBasePSOforTSP%初始化w1=0.5;%個(gè)體經(jīng)驗(yàn)保留概率w2=0.5;%全局經(jīng)驗(yàn)保留概率M=200;%最大迭代次數(shù)m=30;%微粒數(shù)CityNum=10;%問題的規(guī)模〔城市個(gè)數(shù)[dislist,Clist]=tsp<CityNum>;%返回dislist可以求出兩城市間的距離,Clist表示城市的列表NC=1;%迭代計(jì)數(shù)器R_best=zeros<M,CityNum>;%各代最佳路線L_best=inf.*ones<M,1>;%各代最佳路線的長度L_ave=zeros<M,1>;%各代路線的平均長度%產(chǎn)生微粒的初始位置fori=1:mx<i,:>=randperm<CityNum>;%產(chǎn)生30個(gè)微粒要走的30各城市的列表L<i>=SumDistance<dislist,x<i,:>>;%產(chǎn)生這30個(gè)微粒各自按上邊路徑走的總路程endp=x;%p為個(gè)體最好解pL=L;%用數(shù)組表示每個(gè)個(gè)體目前的最短路徑,也是由于這也是初始化,以后這個(gè)距離也要不斷更新[L_best<1,1>,n_best]=min<L>;%L_best<1,1>表示初始化中30個(gè)粒子中最優(yōu)總距離,n_best表示第幾個(gè)粒子是最優(yōu)解R_best<1,:>=x<n_best,:>;%R_best<1,:>表示當(dāng)前最優(yōu)微粒所走城市的路徑L_ave<1,1>=mean<L>;%L_ave<1,1>,30個(gè)微粒走的總路程的平均值%初始交換序v=ones<CityNum-1,2,m>;figure<1>;whileNC<=M%停止條件之一：達(dá)到最大迭代次