An Effective and Simple Heuristic for Analog Test Point Selection

An important problem that arises in the area of fault diagnosis and circuit testing is the analog test point selection (ATPS), which is known to be NP-hard. In this paper, we present a new approach for the ATPS problem based on greedy randomized adaptive search procedure (GRASP), with the objective of overcoming the shortcoming of the greedy algorithms which are easily getting trapped into local optima. The proposed method first generates a feasible test point set by introducing randomness into greedy algorithm, and then a local search algorithm is designed to further improve the quality of the test point set got before. The efficiency of the proposed algorithm is demonstrated by a benchmark circuit. Results indicate that the proposed method, compared with other ATPS methods, more efficiently and more accurately finds the optimum set of test points.