Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 36 ยท Applications and Tuning

Feature Selection with a Genetic Algorithm

Use a genetic algorithm to choose the best subset of features for a machine learning model. Bit-mask chromosomes, cross-validated fitness and a size penalty in Python.

Machine learning datasets often have dozens or thousands of features, and many are useless or even harmful: noise, duplicates, irrelevant measurements. Feature selection picks a subset that keeps the model accurate while making it smaller, faster and easier to explain. With n features there are 2^n subsets, far too many to test. A genetic algorithm is a natural fit: a chromosome is a bit mask with one bit per feature, where 1 means "use this feature".

This is a wrapper method: the fitness is the performance of a real model trained on the selected features. Wrappers can find feature combinations that simple filters (like correlation) miss, at a higher computational cost.

Design

  • Chromosome: a binary vector of length n_features.
  • Fitness: cross-validated accuracy of a model on the selected columns, minus a small penalty per selected feature, so that of two equally accurate subsets the smaller one wins.
  • Guard: a mask with no 1s gets a very low fitness.
  • Operators: tournament selection, uniform crossover, bit-flip mutation with a low rate, plus elitism.
flowchart LR
    M["Bit mask [1,0,1,1,0,...]"] --> S["Select columns X[:, mask]"]
    S --> C["Cross-validate a model"]
    C --> A["Accuracy"]
    M --> N["Count selected features"]
    A --> F["fitness = accuracy - penalty * count"]
    N --> F

Each fitness evaluation trains a model several times, so evaluations are expensive: cache them (see Fitness Caching).

A dataset with known answers

We build a synthetic dataset in which we know the truth: 24 features, only 5 of them informative (the target depends on them), 4 redundant (combinations of the informative ones) and 15 pure noise. A good selector should keep the informative ones and drop the noise.

Python GA feature selection with cross-validated fitness

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see the number of features fall from about 12 (random masks) to a handful, with accuracy as good as or better than using all 24 features. The exact subset depends on the seed and the penalty.

Avoiding selection bias

There is a subtle trap. The GA tries thousands of subsets and keeps the one with the best cross-validated score. That best score is optimistically biased: with enough tries, some subset looks good by luck. To get an honest estimate:

  1. Split off a test set before the GA starts.
  2. Run the GA (with cross-validation) on the training part only.
  3. Evaluate the final subset once on the untouched test set.
Python Honest evaluation on a held-out test set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cross-validated score used to pick the subset is biased upward on average, and in small samples the held-out score can land above or below it by chance (it did not follow the textbook pattern in this particular run, which is a good reminder of how noisy small datasets are). Only the test score is honest, because the test set never influenced the choice. Report it.

Practical tips

  • Pick a fast model for the fitness. Linear models, small trees, k-nearest neighbors. After selection, you can train a stronger model on the chosen features.
  • Seed the population with known-good subsets (all features, filter-method picks) to speed convergence.
  • Cache fitness by mask. Subsets repeat often.
  • Multi-objective version: treat accuracy and feature count as two objectives and use NSGA-II. You get a whole front of trade-offs and no penalty weight to tune.
  • Stability: run the GA several times and count how often each feature is chosen. Features chosen in most runs are trustworthy.

Common mistakes

  • Selecting features on the full dataset and then splitting for testing. This leaks information.
  • Too few cross-validation folds or samples. Fitness noise lets the GA chase luck.
  • No size penalty. Almost-equal accuracy with 20 features instead of 6 is not a win.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a GA for feature selection, what does a chromosome usually look like?

    A 1 means the feature is used, a 0 means it is dropped.
  2. 2. Why is a penalty per selected feature added to the fitness?

    Smaller subsets are cheaper and easier to explain.
  3. 3. Why can the best cross-validated score found by the GA be too optimistic?

    Selecting the maximum over many noisy scores inflates the estimate (selection bias).
  4. 4. How do you get an honest final performance estimate?

    The test set never influenced the choice of features.

Summary

  • Feature selection with a GA uses a bit-mask chromosome and a model-based (wrapper) fitness.
  • Fitness = cross-validated score minus a small penalty per feature; cache repeated masks.
  • Evolution typically removes noise features and keeps informative ones.
  • Selection bias is real: evaluate the final subset on a held-out test set.
  • A multi-objective GA can return the accuracy-versus-size trade-off directly.

Next: A Genetic Algorithm for the Traveling Salesman Problem