An Ant Colony Optimization For Solving Set-covering Problem And Its Application

It is known that Set-Covering problem has been proved to be a NP-Complete problem, yet all NP-Complete problems can not be solved in polynomial time algorithm. Currently the approximate method is commonly used to optimizing Set-Covering problem. If Set-Covering problem is complicated, or the scale of the Set-Covering problem is huge, it is difficult for current algorithms to get an ideal optimization effect.The ant colony algorithm is a genetic algorithm based on the principle of swarm intelligence, which enhances on co-operation among individual ant, utilizes the mechanism of active-feedback of pheromone, and has strong ability of search better results. Ant colony algorithm has been applied successfully to many complicated optimization problems. Its excellent optimization ability provides a new idea to the solution of Set-Covering problem. Standard ant colony algorithm has the shortage of long time-consuming and easily trapped to local minima. After the analyzing the ant colony optimization, this paper propose an ant colony optimization based on penalty function (PFACO) and solve the set-covering problem with PFACO. The simulation results show that the PFACO has obvious effect in global searching for minima and convergence speed.The test set optimization problem in digital system is similar to Set-Covering problem principally. After two kinds of basic electric circuits are analyzed, test set optimization problem can be modeled as Set-Covering problem, so that test set optimization problem is converted to Set-Covering problem. For the time-sequence electric circuit, testing and finding a fault need to apply a test sequence. Then the produced set covering matrix gets large scale, and running efficiency of the algorithm is pretty low. This paper designs two rules which can decrease the scale of test set without affecting the optimal result. The simulated experiment shows that two rules have obvious effect, that the scale of test set is from several to ten times smaller than the original problem. Thus, the complexity of test set optimization is reduced. The ideal result of optimization problem is obtained by applying PFACO to compressed test set.