Implementation of genetic algorithm for TSP based on FPGA
Yancong Zhou, GU Jun-hua, Yongfeng Dong, Han Huan-ping · 2011
TSP is a typical combinatorial optimization problems and GA is an adaptive searching algorithm for global optimization with the natural parallelism. The running speed of GA's software implementation for TSP is too slow, so a new scheme for hardware implementation was put forward. The pipelining structure for GA was designed for facilitating hardware implementation, and other parallel mechanisms were also added to it, thus greatly enhanced the speed. The design and structure of genetic operators - selection, crossover and mutation, individual population and fitness memory were given. The overall design idea, the sub-module program, as well as simulation and experimental data were presented in details. For the memory design of distance matrix, the use of symmetric matrix of compressed storage ideas made the uses of memory cells saved 50%. In the whole design Altera's EP2C70F896C6 chip was used and Verilog was the program language. Testing results have shown the running speed under hardware implementation is faster 2 to 3 orders than the software implementation. Thus its application in practical engineering can be greatly promoted.