求解tsp问题的遗传算法硬件实现new

《求解tsp问题的遗传算法硬件实现new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9期计算机技术与发展VO1．19No．42009年4月COMPUTERTECHNOL0GYANI)DEVEIPMENTApr．2009求解TSP问题的遗传算法硬件实现杨益，方潜生，高翠云(安徽建筑工业学院电子与信息X--程学院，安徽合肥230601)摘要：旅行商问题(TSP)是一个经典的、易于描述却难以处理的组合优化问题，被证明属于NP完全问题，在实际中有着广泛的应用，因此快速、有效地解决"ISP问题有着重要的实际应用价值。遗传算法是一种模拟生物进化启发式全局优化搜索算法，在组合优化领域得到了相当广泛的研究。文中根据硬件的特点，用遗传算法来求解T

2、sP问题，并用Handel—C语言对算法进行编程，最终在FPGA上实现对TSP问题的求解，真正做到了用软件的方法来设计硬件，有效地缩短了系统实时响应周期，提高了系统的可靠性，为设计高速运行的复杂算法提供了可能。关键词：旅行商问题；硬件实现；遗传算法；Handel—c语言；现场可编程门阵列中图分类号：TP18文献标识码：A文章编号：1673—629X(2009)04—0054—03ImplementationofHardwareBasedonGeneticAlgorithmforSolvingTSPProblemYANGYi，FANGQian—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问题有着重要的组合优化问题，并且是一个经典的NP完全问题J。实际应用价值。它是指：已知N个城市之间的相互距离，现有一个旅遗传算法(GeneticAlgorithm，GA)是一类借鉴生行商从某一城市出发，环游所有城市后回到原出发地，物界自然选择和自然遗传机制的随机化搜索算法-2J，且每个城市只能经过一次，要求找出一条最短路线。其其主要特点是群体搜索策略和群体中个体之

8、间的信息可能的路径总的回路数与城市数目N是成指数型增交换，搜索不依赖于梯度信息。就其本质来说，主要是长的，很容易出现“组合