Genetic Algorithm for Feature Selection

• Genetic Algorithm for Feature Selection
  • Introduction
  • Installation
    • Requirements
    • Standard Installation (from source)
  • Quickstart
  • Key Features
    • Selection Strategies
    • Example: A comparison of selection strategies
    • Crossover Operators
    • Example: A comparison of crossover operators
    • Mutation Strategies
    • Example: A comparison of mutation strategies
    • Additional Fitness Functions
    • Example: A comparison of fitness functions
    • Example: Parallel Computation
    • Example: Using Different Models
  • Testing
    • Running Unit Tests
    • Simulation Testing with Known Ground Truth
  • Contribution

This is the repository for stats-243/fall 2025 final project.

Genetic algorithm utilities for feature selection with multiple settings. The main entry point is GA.select.

Introduction

This package implements a configurable genetic algorithm (GA) for feature selection. A population of binary chromosomes encodes which features are included; each generation evaluates fitness, selects parents, recombines, mutates, and optionally carries elite individuals forward. Early stopping halts when fitness stalls, and parallel workers can speed up per-generation evaluation.

The final output is the best feature subset encountered across all generations, along with its corresponding fitness values.

Core loop (per generation)

At each generation, the GA performs the following steps:

• Initialize or carry over the population, optionally preserving elite individuals.
• Evaluate fitness using a user-specified criterion (penalized cross-validated $R^2$, AIC, or BIC).
• Select parent chromosomes using tournament, proportional, or hybrid selection strategies.
• Recombine parents using single-point, two-point, uniform, or correlated crossover.
• Apply mutation (bit-flip or swap), with intensity controlled by mutation_rate.
• Apply a generation gap to mix survivors and offspring.
• Iterate until the maximum number of generations is reached or early stopping is triggered.

Within each generation, several strategies are employed to improve convergence, stability, and computational efficiency.

Population Size

In practice, the population size is often specified explicitly to balance search quality and computational efficiency. When not provided by the user, the population size is set by default to twice the number of candidate features. This heuristic follows common guidance in the literature(Givens & Hoeting, Computational Statistics, p. 79).

Rank-based Fitness Evaluation

Rather than relying solely on raw fitness values, chromosomes can be ranked according to fitness and selected based on their relative ordering. This reduces sensitivity to scale differences in fitness scores and helps prevent premature domination by a few high-scoring individuals, leading to more stable evolutionary dynamics.

Elitism

Elitism ensures that the best-performing chromosomes are preserved across generations without modification. By carrying elite individuals forward, the algorithm prevents the loss of high-quality solutions due to stochastic crossover or mutation, improving convergence reliability.

Patience-based Early Stopping

The algorithm monitors improvements in the best fitness value across generations. If no improvement is observed for a user-defined number of generations (patience), the search terminates early. This prevents unnecessary computation once the algorithm has effectively converged.

Additional configuration options—including selection strategies, crossover operators, mutation schemes, and parallelization—are described in detail in the Key Features section.

Installation

Requirements

• Python ≥ 3.13
• numpy
• pandas
• scikit-learn

Standard Installation (from source)

To install the package from source, run the following commands from the project root:

pip install numpy pandas scikit-learn 
pip install .

After installation, verify that the package is available:

from GA import GA

If the import succeeds, the installation was successful.

Quickstart

from sklearn.datasets import load_diabetes
from GA import select

# Load example data
X_diab, y_diab = load_diabetes(return_X_y=True, as_frame=True)

# Run GA to select features
result = select(
    X_diab, y_diab,
    mutation_method="swap",
    mutation_rate=0.05,
    n_gen=80,
    seed=0
)

print(f"Selected features: {result['selected']}")
print(f"R² score: {result['R2']:.4f}")
print(f"Penalized R²: {result['R2pen']:.4f}")

Gen 0: Best Fitness (CV R2) = 0.4654, Best Fitness (Penalized): 0.4474
Gen 10: Best Fitness (CV R2) = 0.4724, Best Fitness (Penalized): 0.4604
Gen 20: Best Fitness (CV R2) = 0.4724, Best Fitness (Penalized): 0.4604
Gen 30: Best Fitness (CV R2) = 0.4724, Best Fitness (Penalized): 0.4604
Early stopping at generation 37 due to no improvement in 30 generations.
Selected features: [1 2 3 4 5 8]
R² score: 0.4724
Penalized R²: 0.4604

The select() function returns a dictionary with: - selected: Boolean array indicating which features were selected - R2: Cross-validated $R^2$ score on the selected features - R2pen: Penalized $R^2$ (fitness metric used during optimization) - fitness: Final fitness value

Key Features

The package supports a range of configurable options for feature selection:

• Multiple Selection Strategies: Tournament, proportional, and hybrid selection
• Flexible Crossover Operators: Single-point, two-point, uniform, and correlated crossover
• Mutation Methods: Bit-flip or swap with tunable mutation rates
• Elitism: Preserve best solutions across generations
• Early Stopping: Automatic termination when fitness plateaus
• Parallel Evaluation: Distributed fitness computation across CPU cores
• Multiple Prediction Models: Compatible with any scikit-learn estimator
• Flexible Fitness Functions: Cross-validated $R^2$, AIC, or BIC

For detailed and comprehensive comparison results of various features and strategies across multiple datasets, see the ga-dev-log.ipynb notebook.

Selection Strategies

The package supports 3 selection strategies: tournament selection, proportional selection, and hybrid selection.

• Tournament Selection: Selects parents via k-way tournaments, where the fittest individual in each randomly sampled subset is chosen.
  Key parameter: Tournament size (k) used in tournament selection, controls selection pressure. Larger values favor exploitation, while smaller values encourage diversity. Default: k = 2.

• Proportional Selection: Selects parents independently using fitness-proportionate (roulette-wheel) sampling. This favors higher-fitness chromosomes while retaining stochastic exploration.

• Hybrid Selection: Combines fitness-proportionate selection for one parent with random selection for the other, mitigating premature convergence by explicitly encouraging diversity.

The default selection strategy is tournament selection.

Example: A comparison of selection strategies

This example compares the three selection strategies (tournament, proportional, and hybrid) on the baseball salary dataset. All other parameters are held constant to isolate the effect of selection strategy.

import pandas as pd
from sklearn.linear_model import LinearRegression
import GA.GA as GA

# Load baseball dataset
baseball = pd.read_table("data/baseball.dat", sep=r'\s+')
y = baseball['salary']
X = baseball.drop(columns=['salary'])
common_params = {
    'n_gen': 50,
    'pop_size': 30,
    'mutation_rate': 0.1,
    'penalty': 0.02,
    'seed': 42,
    'verbose': False
}

# Run GA with different selection strategies
strategies = ['tournament', 'proportional', 'hybrid']
results = {}

for strategy in strategies:
    result = GA.select(
        X, y,
        selection_method=strategy,
        **common_params
    )
    results[strategy] = result
    n_features = len(result['selected'])
    print(f"\n{strategy.capitalize()} Selection:")
    print(f"  Selected features: {n_features}/{X.shape[1]}")
    print(f"  R² (CV): {result['R2']:.4f}")
    print(f"  R² (penalized): {result['R2pen']:.4f}")

Tournament Selection:
  Selected features: 11/27
  R² (CV): 0.6695
  R² (penalized): 0.6613

Proportional Selection:
  Selected features: 8/27
  R² (CV): 0.6656
  R² (penalized): 0.6597

Hybrid Selection:
  Selected features: 10/27
  R² (CV): 0.6668
  R² (penalized): 0.6594

Crossover Operators

The package supports 4 crossover operators: single-point crossover, two-point crossover, uniform crossover, and correlated crossover.

• Single-Point Crossover: Exchanges genetic material at a single crossover point, preserving contiguous feature blocks.

• Two-Point Crossover: Swaps a segment defined by two crossover points, allowing more flexible recombination while maintaining partial structure.

• Uniform Crossover
  Independently selects each gene from either parent, promoting maximal mixing across features.
  Key parameter: inheritance probability p (default: 0.5). Larger values bias inheritance toward the first parent.

• Correlated Crossover
  Uses a probabilistic switching mechanism along the chromosome to preserve local correlation structures among features.
  Key parameter: switching probability switch_prob (default: 0.2). Smaller values encourage longer contiguous segments from the same parent.

The default crossover operator is two-point crossover.

Example: A comparison of crossover operators

This example compares the four crossover operators (single-point, two-point, uniform, and correlated) on the baseball salary dataset. All other parameters are held constant to isolate the effect of crossover method.

# Run GA with different crossover operators
crossover_methods = ['single', 'two_point', 'uniform', 'correlated']
results = {}

for method in crossover_methods:
    result = GA.select(
        X, y,
        crossover_method=method,
        **common_params
    )
    results[method] = result
    
    n_features = len(result['selected'])
    print(f"\n{method.replace('_', '-').title()} Crossover:")
    print(f"  Selected features: {n_features}/{X.shape[1]}")
    print(f"  R² (CV): {result['R2']:.4f}")
    print(f"  R² (penalized): {result['R2pen']:.4f}")

Single Crossover:
  Selected features: 10/27
  R² (CV): 0.6685
  R² (penalized): 0.6611

Two-Point Crossover:
  Selected features: 11/27
  R² (CV): 0.6695
  R² (penalized): 0.6613

Uniform Crossover:
  Selected features: 9/27
  R² (CV): 0.6663
  R² (penalized): 0.6596

Correlated Crossover:
  Selected features: 9/27
  R² (CV): 0.6700
  R² (penalized): 0.6633

Mutation Strategies

The package supports two mutation strategies: bit-flip mutation and swap mutation, each offering different exploration characteristics.

• Bit-Flip Mutation: Independently flips each bit (feature) with probability mutation_rate. This allows the number of selected features to change dynamically, enabling both feature addition and removal in a single mutation step. Useful when the optimal feature count is unknown.

• Swap Mutation: Exchanges a randomly selected ‘1’ (selected feature) with a randomly selected ‘0’ (unselected feature), preserving the total number of selected features. The mutation_rate controls the expected number of swaps. This approach maintains feature count consistency across generations, which can stabilize convergence when the target feature count is approximately known.

The default mutation method is bit-flip with mutation_rate=0.01.

Example: A comparison of mutation strategies

This example compares bit-flip and swap mutation strategies on the baseball salary dataset, testing different mutation rates to demonstrate their effect on feature selection.

# Test different mutation configurations
mutation_configs = [
    ('flip', 0.01, 'Flip (rate=0.01)'),
    ('flip', 0.03, 'Flip (rate=0.03)'),
    ('swap', 0.03, 'Swap (rate=0.03)'),
    ('swap', 0.05, 'Swap (rate=0.05)')
]

results_mutation = {}

# Use common params but override mutation settings
mutation_params = {k: v for k, v in common_params.items() if k != 'mutation_rate'}

for method, rate, label in mutation_configs:
    result = GA.select(
        X, y,
        mutation_method=method,
        mutation_rate=rate,
        **mutation_params
    )
    results_mutation[label] = result
    
    n_features = len(result['selected'])
    print(f"\n{label}:")
    print(f"  Selected features: {n_features}/{X.shape[1]}")
    print(f"  R² (CV): {result['R2']:.4f}")
    print(f"  R² (penalized): {result['R2pen']:.4f}")

Flip (rate=0.01):
  Selected features: 8/27
  R² (CV): 0.6692
  R² (penalized): 0.6633

Flip (rate=0.03):
  Selected features: 7/27
  R² (CV): 0.6695
  R² (penalized): 0.6643

Swap (rate=0.03):
  Selected features: 9/27
  R² (CV): 0.6694
  R² (penalized): 0.6628

Swap (rate=0.05):
  Selected features: 8/27
  R² (CV): 0.6689
  R² (penalized): 0.6630

Additional Fitness Functions

Beyond the default penalized cross-validated $R^2$, the package supports information-theoretic fitness criteria that balance model fit against complexity.

• AIC (Akaike Information Criterion): Penalizes model complexity linearly with the number of parameters. For linear regression, AIC = $n \cdot \ln(\text{RSS}/n) + 2k$, where $n$ is the sample size, RSS is the residual sum of squares, and $k$ is the number of parameters (features + intercept). Lower AIC indicates better trade-off between fit and complexity. Since the GA maximizes fitness, the algorithm internally uses negative AIC.

• BIC (Bayesian Information Criterion): Applies a stronger complexity penalty that scales logarithmically with sample size. For linear regression, BIC = $n \cdot \ln(\text{RSS}/n) + k \cdot \ln(n)$. This leads to more parsimonious models, especially with larger datasets. As with AIC, the algorithm maximizes negative BIC internally.

Both criteria automatically balance goodness-of-fit against model complexity without requiring a user-specified penalty term.

Example: A comparison of fitness functions

This example compares the three fitness functions ($R^2$, AIC, and BIC) on the baseball salary dataset, illustrating how different criteria lead to different feature selection outcomes.

import numpy as np
from sklearn.model_selection import cross_val_score

# Test different fitness functions
fitness_functions = ['r2', 'aic', 'bic']
results_fitness = {}

for fitness_fn in fitness_functions:
    # Note: penalty only applies to R² fitness
    if fitness_fn == 'r2':
        result = GA.select(X, y, fitness_function=fitness_fn, penalty=0.02, 
                          n_gen=50, pop_size=30, seed=42, verbose=False)
    else:
        result = GA.select(X, y, fitness_function=fitness_fn,
                          n_gen=50, pop_size=30, seed=42, verbose=False)
    
    results_fitness[fitness_fn] = result
    
    # Calculate CV R² for all methods for comparison
    X_selected = X.iloc[:, result['selected']]
    model = LinearRegression()
    cv_r2 = np.mean(cross_val_score(model, X_selected, y, cv=10, scoring='r2'))
    
    n_features = len(result['selected'])
    print(f"\n{fitness_fn.upper()} Fitness:")
    print(f"  Selected features: {n_features}/{X.shape[1]}")
    print(f"  CV R²: {cv_r2:.4f}")
    if fitness_fn == 'r2':
        print(f"  Penalized R²: {result['R2pen']:.4f}")
    elif fitness_fn == 'aic':
        print(f"  AIC: {result['AIC']:.2f}")
    else:
        print(f"  BIC: {result['BIC']:.2f}")

R2 Fitness:
  Selected features: 8/27
  CV R²: 0.6692
  Penalized R²: 0.6633

AIC Fitness:
  Selected features: 14/27
  CV R²: 0.6642
  AIC: 4417.49

BIC Fitness:
  Selected features: 6/27
  CV R²: 0.6658
  BIC: 4447.13

Example: Parallel Computation

Use the n_workers parameter to parallelize fitness evaluation across multiple CPU cores. This parallelizes the fitness computation for each individual in the population, while each cross-validation fold remains single-threaded to avoid nested parallelism.

import time
import numpy as np

# Run with serial evaluation
t0 = time.time()
serial = select(
    X_diab, y_diab,
    penalty=0.02, verbose=False, n_gen=60,
    elitism=True, pop_size=40, seed=42
)
time_serial = time.time() - t0

# Run with parallel evaluation (4 cores)
t0 = time.time()
parallel = select(
    X_diab, y_diab,
    penalty=0.02, verbose=False, n_gen=60,
    elitism=True, pop_size=40, seed=42,
    n_workers=4
)
time_parallel = time.time() - t0

# Verify results are identical
assert np.array_equal(serial["selected"], parallel["selected"])
assert abs(serial["R2"] - parallel["R2"]) < 1e-6

print(f"Serial:   {time_serial:.2f}s")
print(f"Parallel: {time_parallel:.2f}s")
print(f"Speedup:  {time_serial/time_parallel:.2f}x")

Serial:   6.27s
Parallel: 4.93s
Speedup:  1.27x

Example: Using Different Models

The GA is compatible with any scikit-learn estimator. Use the model parameter to test different prediction algorithms:

from sklearn.linear_model import LinearRegression, Ridge
from GA import select

models = {
    "LinearRegression": LinearRegression(),
    "Ridge(alpha=1.0)": Ridge(alpha=1.0),
}

for name, mdl in models.items():
    res = select(
        X_diab,
        y_diab,
        model=mdl,
        penalty=0.02,
        n_gen=60,
        verbose=False,
        elitism=True,
        seed=42,
        n_workers=2,
    )
    print(f"\n{name}")
    print(f"Selected: {res['selected']}")
    print(f"R2: {res['R2']:.4f} | R2pen: {res['R2pen']:.4f}")

LinearRegression
Selected: [1 2 3 4 5 8]
R2: 0.4724 | R2pen: 0.4604

Ridge(alpha=1.0)
Selected: [1 2 3 6 8 9]
R2: 0.4074 | R2pen: 0.3954

Testing

Formal testing is included to verify both correctness and robustness of the package.

• Unit tests check individual GA components (population initialization, fitness functions, selection strategies, crossover operators, mutation methods, and other helpers) against expected behavior

• Validation and invalid-input tests ensure that improper configurations (e.g., invalid parameter values, incompatible dimensions, or unsupported options) are detected and handled gracefully, preventing silent failures.

• Simulation tests validate the algorithm’s ability to recover known ground truth. Synthetic datasets are generated where true feature relationships are explicitly defined, allowing quantitative assessment of feature selection accuracy, precision, and recall under controlled conditions.

Running Unit Tests

# Run all unit tests
cd GA/tests
pytest
python assess.py

Simulation Testing with Known Ground Truth

The package includes simulation testing framework that validates feature selection performance against datasets with known true features. This provides objective evaluation of the GA’s ability to identify relevant features while ignoring noise.

To run simulation tests:

# Generate simulation datasets with known ground truth
python create_simulation_data.py

# Run simulation tests with multiple replications
python test_simulation.py

The simulation framework tests three scenarios of increasing difficulty: - Easy: 20 features (5 true + 15 noise), 300 samples, low noise - Medium: 30 features (5 true + 25 noise), 400 samples, moderate noise - Hard: 40 features (5 true + 35 noise), 600 samples, higher noise

Each scenario is tested across multiple replications to compute precision, recall, and perfect selection rates, providing quantitative assessment of algorithm robustness.

Contribution

The following summarizes individual contributions to the development of this project:

Yijiao Zhou

• Designed and implemented the baseline version of core evolutionary loop of the Genetic Algorithm, from population initialization to generation updates.
• Implemented and refined elitism and early stopping mechanisms, ensuring stable convergence and preventing loss of high-quality feature subsets.
• Explored and integrated parallelization strategies to accelerate fitness evaluation, improving computational efficiency on multi-core systems.
• Extended the algorithm to support multiple prediction models, enabling compatibility with a wide range of scikit-learn estimators and allowing feature selection behavior to adapt to different modeling assumptions.

Ruoyang Li

• Implemented selection strategies, including tournament selection, proportional selection, and hybrid selection.
• Implemented crossover operators, including single-point crossover, two-point crossover, uniform crossover, and correlated crossover.
• Built a full unit test suite, ensuring the individual functions work as expected.
• Added comprehensive validation checks and invalid tests, improving error handling and overall package stability.

Chenfei Peng

• Implemented bit-flip and swap mutation strategies, providing different exploration mechanisms for the genetic algorithm.
• Integrated alternative fitness functions (AIC and BIC) alongside the default penalized $R^2$, enabling information-theoretic model selection criteria.
• Developed comprehensive mutation function tests, including statistical validation tests to verify mutation behavior across multiple trials and edge cases.
• Created a simulation testing framework with known ground truth to quantitatively evaluate feature selection accuracy, precision, and recall under controlled conditions, including reproducible test datasets across multiple difficulty levels (varying feature count, sample size, and noise) to validate algorithm robustness and performance characteristics.