An extended class cover problem is presented and then it is reduced to a constrained multi-objective optimization problem. Solving this problem is significantly important to construct a robust classification system. Therefore, through analyzing the parameters of the binary particle swarm optimization, the conclusion that the binary particle swarm optimization can not only explore the search space efficiently, but also utilize the apriori knowledge adequately, is drawn in this paper. Furthermore, a hybrid algorithm combined with the conventional greedy algorithm and binary particle swarm optimization algorithm is proposed to deal with the extended class cover problem. The proposed algorithm can get a better solution in less runtime and the simulated comparative results with other algorithms show its feasibility and validity.