Computing Minimal Hitting Sets with Particle Swarm Optimization Combined Characteristics Learning
Liu Jua · Dianzi xuebao · 2015
In model-based diagnosis,minimal hitting sets problem is an important topic of artificial intelligence,and a lot of practical problems can be converted into it,such as teachers and curricula problem,minimum covering sets problem,etc. By studying the characteristics of minimal hitting sets,combining with the original PSO algorithm of computing minimal hitting sets,this paper proposes a new algorithm to guide the minimum hitting sets computation: introducing a learning mechanism to cut down some search of the no-solution space; adding a flipping strategy to accelerate some solving of solution space. Experimental results show a significant improvement of this new algorithm in computing minimal hitting sets.