Simulated Annealing — Traveling Salesman Problem
Metaheuristic optimization applied to the NP-hard TSP — with direct parallels to portfolio rebalancing and execution optimization.
View on GitHubResults
Key Metrics
NP-Hard
Problem Class
SA
Algorithm Type
Metaheuristic
Optimization Category
Tuned
Temperature Schedule
Approach
Technical Overview
Simulated Annealing Mechanics
The algorithm begins at a high 'temperature,' accepting worse solutions probabilistically to escape local optima. As temperature decreases according to a cooling schedule, the acceptance probability drops and the search converges toward a near-optimal solution. The balance between exploration and exploitation is controlled entirely by the temperature schedule.
Temperature Schedule Design
The cooling schedule — how quickly temperature decreases — was tuned empirically to balance solution quality against runtime. Too fast and the algorithm gets trapped in local optima; too slow and convergence takes prohibitively long. The final schedule was validated against known TSP benchmarks.
The TSP as a Benchmark
The Traveling Salesman Problem is a standard benchmark for combinatorial optimization because it is easy to state, NP-hard to solve exactly, and produces visual results that make convergence behavior intuitive to inspect. A working SA implementation on TSP demonstrates the algorithm is correctly implemented.
Applications in Finance
Simulated annealing and related metaheuristics are used in quantitative finance for portfolio rebalancing under transaction costs, optimal trade execution scheduling, and index replication. The combinatorial structure of these problems mirrors TSP — many discrete decisions with complex interdependencies and no tractable exact solution.
Gallery
Output & Visualizations
Demo screenshots and output visualizations — coming soon.
TSP: Before & After — Greedy initial tour vs SA-optimized route — 14.5% shorter
Convergence Curve — Tour length decreasing over iterations as temperature cools
Acceptance Probability — P = exp(−Δ/T) — how the algorithm trades exploration for exploitation
City Distance Matrix — Pairwise city distances with optimized tour path overlaid
Stack