MOELIGA: a multi-objective evolutionary approach for feature selection with local improvement

1. Problem Statement

The paper addresses the Feature Selection (FS) problem in high-dimensional machine learning scenarios. As data dimensions increase (often exceeding thousands of features), models suffer from the "curse of dimensionality," leading to overfitting, increased computational cost, and reduced interpretability.

The core challenge is a multi-objective optimization problem involving two conflicting goals:

1. Maximizing Classification Accuracy: Selecting features that best separate classes.
2. Minimizing Feature Subset Size: Reducing dimensionality to improve generalization and efficiency.

Traditional single-objective methods often fail to balance these competing goals effectively or require the user to pre-specify the number of features to select, which is often unknown. Furthermore, many existing methods struggle to maintain population diversity and may overfit to specific classifiers.

2. Methodology: MOELIGA

The authors propose MOELIGA (Multi-Objective Locally-Improved Genetic Algorithm), a novel evolutionary algorithm designed to navigate the trade-off between accuracy and dimensionality while ensuring robustness.

A. Core Architecture

MOELIGA is a Multi-Objective Genetic Algorithm (MOGA) that incorporates an Evolutionary Local Improvement (ELI) strategy.

• Main Population: Evolves over the full feature space.
• Subordinate Populations: For the top-performing chromosomes (parents) in the main population, the algorithm creates "subordinate populations." These sub-populations evolve locally within the specific feature subspace defined by the parent chromosome.
• Replacement Strategy: After the subordinate populations evolve, the best individuals are compared against their parent templates. If an improvement is found (better accuracy or fewer features without degrading the other), the parent is replaced. This acts as an intensification mechanism.

B. Key Components & Innovations

1. Staggered Initialization:
   To ensure diversity in the initial population regarding feature count, the population is divided into three segments with different probabilities of active genes:

   • 55% of individuals: 3% active genes.
   • 30% of individuals: 15% active genes.
   • 15% of individuals: 35% active genes.
     This guarantees a wide range of subset sizes from the start.

2. Three-Objective Function Formulation:
   MOELIGA optimizes three distinct objectives simultaneously:

   • Objective 1 (Accuracy): Uses Unweighted Average Recall (UAR) (Balanced Accuracy) to handle class imbalance. It is evaluated via $N$-fold cross-validation to prevent overfitting.
   • Objective 2 (Compactness): Uses a Sigmoid Transformation ($CR_\lambda$) of the feature cardinality ratio. This non-linear mapping makes the difference between small subsets (e.g., 10 vs. 15 features) more significant than between large subsets (e.g., 1000 vs. 1005), guiding the search toward compact solutions.
   • Objective 3 (Classifier Independence/Geometry): A distance-based metric ($M_d$) derived from nearest neighbors. It measures the ratio of distance to the nearest "Miss" (different class) vs. the nearest "Hit" (same class). This objective promotes feature subsets that provide geometric class separability independent of a specific classifier, acting as a regularization mechanism.

3. Crowding-Based Fitness Sharing:
   To maintain diversity and prevent premature convergence, MOELIGA employs a fitness sharing mechanism. It penalizes individuals based on their proximity to others in both the objective space and decision variable space. This encourages the algorithm to explore less crowded regions of the Pareto front.

3. Key Contributions

• Local Improvement Strategy: The integration of subordinate populations that evolve within the active feature subspace of elite individuals, refining solutions without losing global search capabilities.
• Novel Fitness Sharing: A crowding-based mechanism that penalizes solutions in dense clusters, ensuring a well-distributed Pareto front.
• Sigmoid Transformation for Compactness: A mathematical approach to prioritize the reduction of small feature subsets more aggressively than large ones.
• Geometry-Based Regularization: The introduction of a third objective based on nearest-neighbor distances to ensure selected features are robust and classifier-independent.
• Automatic Dimensionality Determination: Unlike many wrapper methods that require a pre-defined $k$ (number of features), MOELIGA automatically discovers the optimal subset size.

4. Experimental Results

The authors evaluated MOELIGA on 14 diverse datasets (ranging from 34 to 20,531 features and 2 to 14 classes) and compared it against 11 state-of-the-art methods (including RFE, SFS, SFFS, Boruta, ReliefF, and various MultiSURF variants).

• Performance: MOELIGA achieved superior classification performance (UAR) in 9 out of 14 datasets, with improvements up to 30% over the best competing methods. In the remaining 5 datasets, it was competitive (within ~3%).
• Feature Reduction: MOELIGA consistently identified smaller feature subsets than competing methods while maintaining or improving accuracy. In high-dimensional datasets, it reduced dimensionality by 50–80%.
• Statistical Significance: Friedman and Wilcoxon signed-rank tests confirmed that MOELIGA's performance is statistically significantly better than all 10 competing algorithms.
• Classifier Independence: When tested with different classifiers (Random Forest, SVM, AdaBoost, Naive Bayes, MLP), feature subsets selected by MOELIGA (trained with Decision Trees) maintained high performance across all classifiers, whereas subsets from other methods often degraded significantly.
• Computational Cost: While MOELIGA has higher computational overhead for low-dimensional problems due to local improvements, its cost scales efficiently for high-dimensional data, often outperforming exhaustive search methods (like SFFS) in time when optimizing for the best subset size.

5. Significance and Conclusion

MOELIGA represents a significant advancement in multi-objective feature selection by effectively addressing the accuracy-dimensionality trade-off. Its ability to automatically determine the optimal number of features, combined with its robustness against overfitting and classifier dependency, makes it particularly valuable for high-dimensional, complex scenarios (e.g., genomics, bioinformatics, and image analysis).

The paper concludes that while MOELIGA requires more computational resources than simple filter methods, its ability to produce a diverse set of high-quality, compact, and generalizable feature subsets makes it a superior choice for complex machine learning problems where interpretability and generalization are critical. Future work suggests adaptive mechanisms for subordinate population evolution and ensemble-based fitness evaluation.