BRKGA for Orienteering

This post covers the BRKGA-Orienteering project, an NP complete optimization solved with Biased Random Key Genetic Algorithm.

It connects to Tetris-BRKG-AI which also uses BRKGA and to Cache-Engine-Deep-Dive where we evict like selection.

Encoding

Solution encoded as vector of random keys in [0,1). Decoder sorts keys to get visit order, then greedy insertion with depot constraints. Biased crossover keeps elite genes.

Why BRKGA

Classic GA loses structure. BRKGA bias preserves elite sub tours. Outperforms VNS baselines on our instances.

Relation to Systems

Optimization under constraints mirrors bounded queues in caching. See Cache-Engine-Deep-Dive and PR-Review-Agent for RAG ranking as optimization.

Project: BRKGA for Multi-Depot Orienteering Problem Related: ERPlag-Compiler-Build parsing is also search in grammar space.