A Hybrid Optimization Approach of Max-Min Ant System and Adaptive Genetic Algorithm for MCM Interconnect Test Generation

This paper presents a hybrid optimization approach of max-min ant system (MMAS) and adaptive genetic algorithm (AGA) for the MCM interconnect test generation problem. By combing the characteristics of MCM interconnect test generation, the pheromone updating rule and state transition rule of MMAS is designed. MMAS is applied as an improvement over the basic ant algorithm, in which the pheromone is forced to obey the lower and upper bounds in order to avoid premature stagnation. AGA is employed to evolve the candidates generated by MMAS, in order to get the best test vector with the high fault coverage. The international standard MCM benchmark circuit was used to verify the approach. Comparing with not only the evolutionary algorithms, but also the deterministic algorithms, experimental results demonstrate that the hybrid approach can achieve high fault coverage, short CPU time and compact test set, which shows that it is a novel optimized method deserving research.