brunovandekerkhove/evolutionary-computing

Purpose and Runtime

This is a MATLAB evolutionary-computing project for solving symmetric Travelling Salesman Problem instances. It extends a bundled Genetic Algorithm Toolbox with TSP-specific representations, operators, stopping rules, local search, experiments, and visualization. It has no service/API deployment layer; primary execution is interactive MATLAB or batch experiment scripts, optionally using MATLAB Parallel Computing Toolbox.

Entry Points and Problem Boundary

The principal solver entry point is src/template/run_ga.m; an experiment-oriented variant is src/template/experiments/adapted_run_ga.m. The interactive entry point is src/template/tspgui.m, with tour rendering in src/template/visualizeTSP.m. TSP instance ingestion and objective evaluation are centered on src/template/input_cities.m and src/template/tspfun.m, consuming .tsp datasets such as src/template/datasets/xqf131.tsp.

Genetic-Algorithm Orchestration

src/template/run_ga.m controls the generation loop: initialize/evaluate a population, select parents, generate offspring by crossover and mutation, optionally apply improvement, select survivors, and stop at a generation limit or convergence criterion. Shared runtime state/configuration is likely established through src/template/context.m. The bundled generic GA implementation in src/gatbx/sga.m and population migration support in src/gatbx/mpga.m form a legacy/toolbox boundary; the template layer supplies TSP-aware behavior.

Representation and Fitness Flow

Individuals are tours, with path, adjacency, and ordinal conversions available through src/template/conversions/path2adj.m, src/template/conversions/adj2path.m, and src/template/conversions/ord2path.m. Operators can use their preferred encoding, but tour fitness ultimately flows through src/template/tspfun.m, which evaluates total route distance against coordinates loaded by src/template/input_cities.m. This representation-conversion boundary is important: path-specific crossover/mutation must preserve valid city permutations, while evaluation requires a valid closed tour.

Evolution Operators and Selection

TSP operator dispatchers isolate algorithm choices from the GA loop: src/template/crossovers/recombineTSP.m, src/template/mutations/mutateTSP.m, src/template/selection/selectTSP.m, and src/template/reinsertion/reinsTSP.m. Concrete crossover implementations include edge- and order-based methods in src/template/crossovers/xedge_heuristic.m, src/template/crossovers/xorder.m, and src/template/crossovers/xseq_constructive.m. Parent selection includes rank, fitness-proportional, and tournament methods; survivor policies include fitness-based, μ+λ, round-robin, and uniform selection.

Convergence, Diversity, and Hybrid Search

Termination is delegated to src/template/stop_criteria/check_stop_criterion.m, including windowed efficiency/stability rules such as src/template/stop_criteria/stdfrac_efficiency.m. Diversity and stagnation recovery are supported by population-level path improvement in src/template/loop_detection/improve_population.m; island-model migration is supplied by src/gatbx/migrate.m. Hybrid local optimization and initialization are separate from core GA operators: nearest-neighbor seeding, 2-opt, and Or-opt live in src/template/hybridisation/nearest_neighbor.m, src/template/hybridisation/twoopt.m, and src/template/hybridisation/oropt.m.

Experiment and Reporting Pipeline

Batch studies sweep configurations, collect run-level fitness/runtime outcomes, and produce report-ready artifacts. Key drivers are src/template/experiments/experimentation.m, src/template/experiments/tuning.m, and src/template/experiments/optimal_window_size_test.m; results are persisted as MATLAB workspaces under src/template/results/. MATLAB-to-LaTex reporting adapters include src/template/experiments/crossoverlatex.m and src/template/experiments/mutationlatex.m, feeding the academic report rooted at report/report.tex.