Artificial Bee Colony is a population based, bio-inspired optimization algorithm that developed for continues problems. The aim of this study is to develop a binary version of the Artificial Bee Colony (ABC) Algorithm to solve feature subset selection problem on bigger data. ABC Algorithm, has good global search capability but there is a lack of local search in the algorithm. To overcome this problem, the neighbor selection mechanism in the employed bee phase is improved by changing the new source generation formula that has hamming distance based local search capacity. With a re-population strategy, the diversity of the population is increased and premature convergence is prevented. To measure the effectiveness of the proposed algorithm, fourteen datasets which have more than 100 features were selected from UCI Machine Learning Repository and processed by the proposed algorithm. The performance of the proposed algorithm was compared to three well-known algorithms in terms of classification error, feature size and computation time. The results proved that the increased local search ability improves the performance of the algorithm for all criteria.