NK Hybrid Genetic Algorithm for Clustering (NK-HGA)

Faithful Python implementation of the NK-HGA from Tinós, Zhao, Chicano & Whitley, "NK Hybrid Genetic Algorithm for Clustering" (IEEE TEVC), verified against the authors' reference C++ source (rtinos/NKGAclust).

• Reference paper: https://dl.acm.org/doi/abs/10.1109/TEVC.2018.2828643

Key Features

• NK landscape decomposition — Reformulates the clustering objective as an NK fitness landscape, decomposing the global fitness into N local subfunctions f_i, each depending on only K neighbors. This exploits problem structure that a standard GA treats as a black box.
• Density-based fitness (NKCV2) — Uses local density estimation (Gaussian kernel, Rodriguez–Laio cutoff) and an interaction graph Gep to define a density-aware internal validation criterion, capturing non-convex and arbitrary-shape clusters that centroid-based objectives miss.
• Partition Crossover (PX) — A deterministic, respectful crossover that evaluates 2^q offspring in O(N·K) time by exploiting the NK decomposition. Offspring are guaranteed to be at least as good as the better parent — a property no standard crossover can offer.
• O(Kout·K) delta-evaluation — Changing one variable affects only its subfunction and reverse neighbors, enabling incremental fitness updates orders of magnitude faster than full O(N·K) re-evaluation. This makes local search and mutation practically free.
• Memetic architecture — Combines the GA with a first-improvement local search (LsFi) featuring neutral-drift acceptance across plateaus, applied at initialization and periodically refreshed — not naïvely on every child.
• Structured mutation operators — Three topology-aware operators (reclassify 60% / merge 20% / split 20%): reclassify uses Δ-eval for best-improvement relabeling, merge selects clusters by proximity, and split uses density-weighted prototypes.
• Automatic cluster number discovery — The number of clusters Nc is not fixed a priori; it emerges from optimization via merge/split mutations and noise labeling (x_j = 0), unlike k-means or standard GAs that require k upfront.

Directory Structure

GAh/
├── src/                          # Algorithm modules
│   ├── nkcv2.py                  #   Preprocessing, interaction graph Gep, NKCV2 fitness, Δ-eval
│   ├── search.py                 #   First-improvement local search (LsFi)
│   ├── mutations.py              #   Reclassify / merge / split operators
│   ├── px.py                     #   Partition crossover (mapSolutions + px + fixLabels)
│   ├── ga.py                     #   NK-HGA memetic main loop
│   ├── cga.py                    #   CGA baseline (silhouette-maximizing)
│   └── run_comparison.py         #   Experiment harness (ARI, model selection, plot)
├── tests/
│   └── run_tests.py              # Standalone unit-test runner (no pytest needed)
├── data/                         # Benchmark datasets
│   ├── Aggregation.txt
│   ├── flame.txt
│   ├── jain.txt
│   └── iris.txt
├── docs/                         # Paper PDF and Markdown translation
├── reference/                    # Authors' original C++ source (nk.h, ga_clustering.cpp, …)
├── results/                      # Generated figures (comparison_result.png)
├── huong_cai_tien/               # Research: improving the NKCV2 objective
│   ├── README.md                 #   Consolidated improvement report
│   ├── models/                   #   Alternative objective models (CDW, Mahalanobis, Persist, …)
│   ├── experiments/              #   Screening / GA / ablation scripts & PX test suite
│   └── results/                  #   Figures and CSVs generated by experiments
├── requirements.txt
└── README.md

Research branch: huong_cai_tien/

A self-contained research log on improving the objective function. src/ is never modified — alternative models are swapped in by monkeypatching ga.NKCV2Model inside try/finally, and every model carries a self-test (neutral parameters must reproduce the original to 1e-12, and Δ-eval must match a full re-evaluation).

Start at huong_cai_tien/README.md. Headline finding: NK-HGA does not optimize badly — it optimizes a wrong criterion very well. On Flame the Spearman correlation between best-so-far fitness and ARI along the optimization trajectory is +0.999, i.e. optimizing NKCV2 monotonically destroys clustering quality.

Install

pip install -r requirements.txt

numba is optional — it JIT-compiles the hot NKCV2 kernels for a large speed-up. Without it the code falls back to pure Python (correct, just slower), so it runs even on interpreters that have no numba wheel yet.

Run

# unit tests (no pytest needed)
python tests/run_tests.py

# experiment on the Aggregation dataset
python src/run_comparison.py --pop 100 --gen 150 --K 3
#   options: --runs N (model selection), --time-budget (paper's N/2 s stop)

Result (Aggregation, 788 points, 7 true clusters)

Method	ARI	Clusters
NK-HGA	0.9876	7
CGA	0.7735	4
k-means	0.7113	7
DBSCAN	0.7338	4

NK-HGA matches the paper's target (ARI ≈ 0.99, ~7 clusters) and beats the CGA baseline and classic methods — validating the density-based NKCV2 + partition crossover + local search machinery.