In weighted random pattern testing based on deterministic test patterns. If the number of the deterministic test patterns with a low sampling probability is reduced, the number of the weighted random patterns required to achieve a high fault coverage can be decreased. The weight set that makes the variance of sampling probabilities for deterministic test patterns very small, can reduce the number of the deterministic test patterns with a low sampling probability. In this paper, we present a new weight set generation algorithm which can generate high performance weight sets by reducing the variance of the sampling probabilities. Experimental results on ISCAS-85 benchmark circuits prove the effectiveness of the new weight set generation algorithm.