As many redundant and irrelevant features exist, there is a challenge in classifying biology data. These features mislead the classification algorithms and increase the error rate of classification. Feature selection (FS) can identify redundant features and remove them from the raw data to solve this problem. However, it is plagued by high computational costs and local optimization. The heuristic algorithm is utilized to solve this problem in this article. Adaptive Fish Migration Optimization (AFMO) is a population-based heuristic algorithm with excellent performance to efficiently solve optimization problems and is an improved version of Fish Migration Optimization (FMO). In this paper, Binary Adaptive Fish Migration Optimization (BAFMO) is proposed, a multi-group strategy is presented, and a new transition function based on Gaussian probability distribution is introduced. Furthermore, a novel binary algorithm is combined with the K-Nearest Neighbors (KNNs) method to optimize the feature selection problem. Publicly available data and some Parkinson’s disease data were used to validate the new algorithm’s performance. The comparison results with other well-known binary heuristic algorithms show that the new algorithm performs better than various algorithms in feature selection.