Skip to content

GA-Optimized Decision Trees

🌳 GA-Optimized Decision Trees

Evolving decision trees that balance accuracy and interpretability using multi-objective genetic algorithms.

Search the accuracy–complexity spectrum directly and choose the operating point, instead of accepting whatever a greedy split rule produces.

NSGA‑II
Multi-objective search
4
Mutation operators
25+
Loadable datasets
3.9–3.12
Python support

🚀 Quick Start

Install:

git clone https://github.com/ibrah5em/ga-optimized-trees.git
cd ga-optimized-trees
python -m venv venv && source venv/bin/activate
pip install -e .          # core only
pip install -e .[all]     # all optional features

Train a tree from a config:

python scripts/train.py --config configs/paper.yaml --dataset iris

Or from Python:

import numpy as np
from sklearn.model_selection import train_test_split

from ga_trees import FitnessCalculator, GAConfig, GAEngine, Mutation, TreeInitializer
from ga_trees.data import DatasetLoader
from ga_trees.fitness import TreePredictor

data = DatasetLoader().load_dataset("breast_cancer", test_size=0.2)
X_train, y_train = data["X_train"], data["y_train"]

# Hold a slice of the training data out of the search. Without it the GA fits
# and scores leaves on the same rows and rewards whichever tree overfits most.
X_fit, X_val, y_fit, y_val = train_test_split(
    X_train, y_train, test_size=0.25, stratify=y_train, random_state=0
)
n_features = X_fit.shape[1]

initializer = TreeInitializer(
    n_features, n_classes=2, max_depth=5, min_samples_split=10, min_samples_leaf=5
)
mutation = Mutation(
    n_features,
    feature_ranges={
        i: (X_fit[:, i].min(), X_fit[:, i].max()) for i in range(n_features)
    },
    X=X_fit,  # lets mutation pick thresholds from values that actually reach the node
    min_samples_leaf=5,
)
fitness = FitnessCalculator(accuracy_weight=0.9, interpretability_weight=0.1)

engine = GAEngine(
    GAConfig(population_size=80, n_generations=40, random_state=42),
    initializer,
    fitness.calculate_fitness,
    mutation,
)
best = engine.evolve(X_fit, y_fit, X_val=X_val, y_val=y_val, verbose=False)

# Structure was chosen on the validation split; refit the leaves on all training rows.
predictor = TreePredictor()
predictor.fit_leaf_predictions(best, X_train, y_train)
accuracy = np.mean(predictor.predict(best, data["X_test"]) == data["y_test"])
print(
    f"{best.get_num_nodes()} nodes, depth {best.get_depth()}, test accuracy {accuracy:.3f}"
)

To compare the GA with CART and random search on your own data, see the benchmarking harness: scripts/benchmark.py (one tuned tree per method, nested CV) and scripts/frontier_benchmark.py (accuracy–size frontiers).


📚 Documentation


📄 Research paper

A paper on the full study behind this framework is in preparation. It'll be linked here when it's out; until then, cite the software (see the FAQ).


🆚 When to use it

Aspect CART GA-Optimized
Search Greedy, top-down Evolutionary, over whole trees
Objective Impurity, then pruning Any function of the tree — size, features used, custom metrics
Speed Milliseconds Seconds to minutes

Use CART when you want the most accurate small tree for plain accuracy. The GA is worth it when the objective is something a greedy split rule can't optimise directly.


v1.0.2 Python 3.9+ MIT License