Overview
A real-time visualization built in Processing (Java) that solves the Travelling Salesman Problem using two fundamentally different approaches displayed side by side. The left half runs a Genetic Algorithm that evolves a population of candidate routes through selection, crossover, and mutation, while the right half executes a Brute Force search that enumerates every possible permutation.
Both algorithms operate on the same set of 25 randomly placed cities, allowing a direct visual comparison of convergence speed and solution quality. Green paths indicate the best route found so far, while white paths show the current attempt being evaluated.
The Problem
Travelling Salesman Problem (TSP)
Given cities, the Travelling Salesman Problem asks: what is the shortest route that visits every city exactly once and returns to the starting city? Despite its simple statement, TSP is one of the most studied NP-hard problems in combinatorial optimization.
A brute force approach must evaluate every possible permutation of cities. For cities, the number of distinct routes is:
For the 25 cities used in this project, that means:
Even at billions of evaluations per second, exhaustively checking all routes would take longer than the age of the universe. This astronomical complexity motivates the use of metaheuristic algorithms like the Genetic Algorithm, which trade guaranteed optimality for practical run-time by exploring the search space intelligently.
Brute Force Approach
Lexicographic Permutation Enumeration
The brute force solver uses the lexicographic next-permutation algorithm to systematically enumerate every possible route without repetition. Starting from the identity permutation, each step produces the next permutation in lexicographic order by finding the rightmost ascent, swapping with the smallest larger element, and reversing the suffix.
Every generated permutation is evaluated as a candidate route — the total Euclidean distance is computed and compared against the current best. The display shows the current permutation number out of the total , the percentage completion, and the best distance found so far.
While this approach guarantees finding the optimal solution, its time complexity makes it computationally infeasible for anything beyond a handful of cities. For 25 cities, the percentage counter effectively never moves — a powerful visual demonstration of factorial growth.
Genetic Algorithm
Population-Based Metaheuristic
The Genetic Algorithm (GA) is a population-based metaheuristic inspired by natural selection. A population of 800 candidate routes evolves over successive generations, with fitter individuals more likely to pass their genetic material to the next generation.
Each route's fitness is computed using an inverse distance function with a high exponent to amplify differences between good and bad solutions:
Fitness values are normalized across the population so they sum to 1, enabling roulette wheel selection where the probability of selecting an individual is proportional to its normalized fitness. Two parents are selected this way, and their offspring inherits genetic material from both.
Mutation operates by swapping random adjacent cities in the route with a mutation rate of per gene — intentionally high to maintain diversity and prevent premature convergence. The display shows the current best of each generation in white and the overall best ever found in green, along with the generation count and best distance.
Unlike brute force, the GA converges to a near-optimal solution within seconds to minutes, demonstrating the power of evolutionary search on combinatorial problems.
Side-by-Side Comparison
Real-Time Visual Comparison
Both algorithms run simultaneously on the same randomly generated set of 25 cities, providing a direct comparison of their search strategies. The screen is split vertically: the Genetic Algorithm on the left and Brute Force on the right.
In both halves, green paths represent the best route discovered so far, while white paths show the current route being tested (brute force) or the best of the current generation (genetic algorithm).
The contrast is striking: the Genetic Algorithm rapidly converges on increasingly shorter routes, with the green path stabilizing within moments. Meanwhile, the Brute Force side churns through permutations with the percentage counter barely moving from 0%, its best route improving only occasionally. This visualization powerfully demonstrates why heuristic approaches are essential for NP-hard problems at scale.