資源描述：
《求解tsp問題的遺傳算法硬件實現(xiàn)new》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第9期計算機技術與發(fā)展VO1．19No．42009年4月COMPUTERTECHNOL0GYANI)DEVEIPMENTApr．2009求解TSP問題的遺傳算法硬件實現(xiàn)楊益，方潛生，高翠云(安徽建筑工業(yè)學院電子與信息X--程學院，安徽合肥230601)摘要：旅行商問題(TSP)是一個經典的、易于描述卻難以處理的組合優(yōu)化問題，被證明屬于NP完全問題，在實際中有著廣泛的應用，因此快速、有效地解決"ISP問題有著重要的實際應用價值。遺傳算法是一種模擬生物進化啟發(fā)式全局優(yōu)化搜索算法，在組合優(yōu)化領域得到了相當廣泛的研究。文中根據(jù)硬件的特點，用遺傳算法來求解T
2、sP問題，并用Handel—C語言對算法進行編程，最終在FPGA上實現(xiàn)對TSP問題的求解，真正做到了用軟件的方法來設計硬件，有效地縮短了系統(tǒng)實時響應周期，提高了系統(tǒng)的可靠性，為設計高速運行的復雜算法提供了可能。關鍵詞：旅行商問題；硬件實現(xiàn)；遺傳算法；Handel—c語言；現(xiàn)場可編程門陣列中圖分類號：TP18文獻標識碼：A文章編號：1673—629X(2009)04—0054—03ImplementationofHardwareBasedonGeneticAlgorithmforSolvingTSPProblemYANGYi，F(xiàn)ANGQian—she
3、ng，GAOCui—yun(Sctx~lofElectronicandInformationEngineering，AnhuiUniversityofArchitecture，Hefei230601，China)Abstract：TravelingSalemaanProblem(TSP)isakindofclassicalcombinationoptimalproblemthatiseasytobedescribedbutdifficulttobesolved．ItbelongstoNP—completeproblemandisappliedbro
4、adlyinpractice．ThusrapidandeffectivesolvingTsPproblemisveryimportantapplicationvalueinpractice．GeneticAlgorithrn(GA)isakindofheuristicglobaloptimizationsearchingalgorithmthatsimu-latesthebk~logyevolutionarysystem．GAisappliedquitebroadlytothecombinationoptimizationdomain．Accord
5、ingtotheattributeofhardware，TSPproblemissolvedbasedonGAforwhichHandel～Clanguageexqnprograminthispaper．Eventually，theimplementationofF】Acansolve丁sPproblemineffect．Thedesigncanusethemethodofsoftw~etodesignhardwareindeedthat鋤shortenrealtimerespondingpe~ndofthesystemineffectandimp
6、rovereliabilityofthesystem．Thedesignmethodofthepaperpm~desakindofpossibilityinordertodesignthecomplexalgorithmofhighspeedrunning．Key鉀nrds：travelingsale目瑚problem；hardwareimplementation；geneticalgorithm；Handel—Clanguage；fieldprogrammablegatearrayO引言TSP問題在實際中有很多典型的應用，如可以解決連旅行商問題(
7、TravelingSalesmanProblem，TSP)也鎖店的貨物配送路線、分配問題、車輛調度問題、切割稱貨郎擔問題是一個典型的、易于描述卻難以處理的問題等。因此快速、有效地解決TsP問題有著重要的組合優(yōu)化問題，并且是一個經典的NP完全問題J。實際應用價值。它是指：已知N個城市之間的相互距離，現(xiàn)有一個旅遺傳算法(GeneticAlgorithm，GA)是一類借鑒生行商從某一城市出發(fā)，環(huán)游所有城市后回到原出發(fā)地，物界自然選擇和自然遺傳機制的隨機化搜索算法-2J，且每個城市只能經過一次，要求找出一條最短路線。其其主要特點是群體搜索策略和群體中個體之
8、間的信息可能的路徑總的回路數(shù)與城市數(shù)目N是成指數(shù)型增交換，搜索不依賴于梯度信息。就其本質來說，主要是長的，很容易出現(xiàn)“組合
