The feature selection (FS) is a binary optimization problem in the discrete optimization problem category. Maximizing the accuracy by using fewer features is the main aim of FS. Metaheuristic algorithms are widely used for FS in literature. Redundant and irrelevant features are selected/unselected by a binary metaheuristic optimization algorithm for FS. Search in a metaheuristic optimization algorithm is directed with a fitness function. The type and landscape of the search space affect the success of the algorithm. Generally, accuracy-based fitness functions of metaheuristic algorithms are used for FS. In this work, eleven existing and six novel fitness functions are analyzed on eleven various datasets with a novel binary threshold Lévy flight distribution (BTLFD) algorithm. The large datasets (Yale, ORL, and COIL20) have 1024 features. The medium datasets (SpectEW, BreastEW, Ionosphere, and SonarEW) has 22–60 features. The small datasets (Tic-tac-toe, WineEW, Zoo, and Lymphography) have 9–18 features. K-nearest neighbor is used as a classifier with five-fold cross-validation and the experimental results showed that three rarely used fitness functions produced more accurate solutions. In the comparisons, BTFLD outperformed 8 state-of-the-art metaheuristic algorithms on 21 datasets for FS.