Study On Ant Colony Optimization And The Application Of This Algorithm To FPGA Segmentation Design And Routing

Ant colony algorithm was a novel simulated evolutionary algorithm which was used to solve combinatorial optimization problems. At first, this thesis introduces a new search method based on Metropolis rules, which is applied to a classical optimization problem. Many simulation results are given to illustrate the power of the approach. Next , Ant Colony System (ACS) algorithm is used in the segmentation design of FPGA for the first time. At last, ACS algorithm is used to resolve the K-routing problem of FPGA.In chapter 2, we present a modified ACS. Resent development of some heuristic algorithms were discussed. The focus was laid on the improvements of ACS algorithm based on the analysis of the performances of both simulated annealing (SA) and AC for the traveling salesman problem (TSP). The Metropolis rules in SA were applied to AC and turned out an improved ACS. We applied this modified ACS on some Bechmark TSP (include 10 cities, 30 cities, 50 cities, 75 cities).The computational results obtained from the case study demonstrate that the improved ACS has advantages over the sheer SA and unmixed ACS.In chapte 3, ACS algorithm is used to resolve the Segementation design problem of FPGA. FPGA is widely used in digital system currently. Its routability has close relationship with the physical architecture. The application of switches improved the flexibility of the nets to be routed. But too many switches will bring great performance penalty because of their high resistance and capacitance. To balance routing flexibility under performance constraints Chang and zhou et al proposed the Graph Matching-Based Algorithm and minimum spanning tree (MST) to construct good segmentation designs. It attempts to maximize routability under performance constraints, but its conclusion, which the solution obtained by MST is optimal, is not true.We give a counterexample to demonstrate it. Due to this, We present an improved algorithm, which combines the Prim algorithm with ACS.. Series of numerical experiments show the good performance of the algorithm.In chapter 4, ACS algorithm is used to resolve the FPGA K-routing problem. We know multi-routing problem has been shown being NP-complete. NP-complete problem cannot be solved by polynomial algorithm, so we introduce ACS to solve this problem. We transform this problem to a classical combinatorial optimization -Maximum...