摘要
旅行商问题(TSP)是一个经典的、易于描述却难以处理的组合优化问题,被证明属于NP完全问题,在实际中有着广泛的应用,因此快速、有效地解决TSP问题有着重要的实际应用价值。遗传算法是一种模拟生物进化启发式全局优化搜索算法,在组合优化领域得到了相当广泛的研究。文中根据硬件的特点,用遗传算法来求解TSP问题,并用Handel-C语言对算法进行编程,最终在FPGA上实现对TSP问题的求解,真正做到了用软件的方法来设计硬件,有效地缩短了系统实时响应周期,提高了系统的可靠性,为设计高速运行的复杂算法提供了可能。
Traveling ,Salesman Pmblem（TSP）is a kind of classical combination optimal problem that is easy to be described but difficult to be solved. It belongs to NP- complete problem and is applied broadly in practice. Thus rapid and effective solving TSP problem is very important application value in practice. Genetic Algorithm（GA） is a kind of heuristic global optimization searching algorithm that simulates the biology evolutionary system. GA is applied quite broadly to the combination optimization domain. According to the attribute of hardware, TSP problem is solved based on GA for which Handel - C language can program in this paper. Eventually, the implementation of FPGA can solve TSP problem in effect. The design can use the method of software to design hardware in deed that can shorten real time responding period of the system in effect and improve reliability of the system. The design method of the paper provides a kind of possibility in order to design the complex algorithm of high speed running.
出处
《计算机技术与发展》
2009年第4期54-56,60,共4页
Computer Technology and Development
基金
2008年建设部科技计划项目(2008-K6-25)
安徽省2007年度科技攻关计划项目(07010202056)
关键词
旅行商问题
硬件实现
遗传算法
Handel—C语言
现场可编程门阵列
traveling salesman problem
hardware implementation
genetic algorithm
Handel - C language
field programmable gate array
