Optimised Feature Subset Selection via Simulated Annealing

We introduce a novel algorithm for ℓ0-norm feature selection that formulates the task as a combinatorial optimisation problem solved through Simulated Annealing (SA) to optimise the Fisher Discriminant Ratio (FDR), which serves as a computationally efficient proxy for model quality in classification tasks. The resulting SA-FDR algorithm is evaluated on multiple publicly available datasets with up to hundreds of thousands of samples and hundreds of features, consistently achieving high predictive accuracy while selecting more compact feature subsets than other commonly used algorithms such as recursive feature elimination or Lasso. This ability to recover informative yet minimal sets of features stems from its capacity to capture inter-feature dependencies often missed by greedy optimisation approaches. Therefore, SA-FDR constitutes a flexible and effective approach for designing models in high-dimensional settings, particularly when model sparsity, interpretability, and performance are crucial.