Solving the feature selection problem is considered an important issue when addressing data from real applications that contain a large number of features. However, not all of these features are important; therefore, the redundant features must be removed because they affect the accuracy of the data representation and introduce time complexity into the analysis of these data. For these reasons, the feature selection problem is considered an NP-complete nonlinearly constrained optimization problem. The rough set (RS) and neighborhood rough set (NRS) are the most powerful methods used to solve the feature selection problem; however, both approaches suffer from high time complexity. To avoid these limitations, we combined the RS and NRS with a new metaheuristic algorithm called the runner-root algorithm (RRA). The spirit of the RRA originated from real-life plants called running plants, which have roots and runners that spread the plants in search of minerals and water resources through their root and runner development. To validate the proposed algorithm, several UCI Machine Learning Repository datasets are used to compute the performance of our algorithm employing two effective classifiers, the random forest and the K-nearest neighbor, in addition to some other measures for the performance evaluation. The experimental results illustrate that the proposed algorithm is superior to the state-of-the-art metaheuristic algorithms in terms of the performance measures. Additionally, the NRS increases the performance of the proposed method more than the RS as an objective function.