Meta-Heuristic Algorithms for FPGA Segmented Channel Routing Problems with Non-standard Cost Functions

摘要

In this paper we present three meta-heuristic approaches for FPGA segmented channel routing problems (FSCRPs) with a new cost function in which the cost of each assignment is not known in advance, and the cost of a solution only can be obtained from entire feasible assignments. Previous approaches to FSCPs cannot be applied to this kind of cost functions, and meta-heuristics are a good option to tackle the problem. We present two hybrid algorithms which use a Hopfield neural network to solve the problem's constraints, mixed with a Genetic Algorithm (GA) and a Simulated Annealing (SA). The third approach is a GA which manages the problem's constraints with a penalty function. We provide a complete analysis of the three metaheuristics, by tested them in several FSCRP instances, and comparing their performance and suitability to solve the FSCRP.