High-dimensional Feature Selection Problems (HFSPs) have grown in popularity but remain challenging. When faced with such complex situations, the majority of currently employed Feature Selection (FS) methods for these problems drastically underperform in terms of effectiveness. To address HFSPs, a new Binary variant of the Ali Baba and the Forty Thieves (BAFT) algorithm known as binary adaptive elite opposition-based AFT (BAEOAFT), incorporating historical information and dimensional mutation is presented. The entire population is dynamically separated into two subpopulations in order to maintain population variety, and information and knowledge about individuals are extracted to offer adaptive and dynamic strategies in both subpopulations. Based on the individuals' history knowledge, Adaptive Tracking Distance (ATD) and Adaptive Perceptive Possibility (APP) schemes are presented for the exploration and exploitation subpopulations. A dynamic dimension mutation technique is used in the exploration subpopulation to enhance BAEOAFT's capacity in solving HFSPs. Meanwhile, the exploratory subpopulation uses Dlite Dynamic opposite Learning (EDL) to promote individual variety. Even if the exploitation group prematurely converges, the exploration subpopulation's variety can still be preserved. The proposed BAEOAFT-based FS technique was assessed by utilizing the k-nearest neighbor classifier on 20 HFSPs obtained from the UCI repository. The developed BAEOAFT achieved classification accuracy rates greater than those of its competitors and the conventional BAFT in more than 90% of the applied datasets. Additionally, BAEOAFT outperformed its rivals in terms of reduction rates while selecting the fewest number of features.