Travelling Salesman

Solve the Travelling Salesman Problem with genetic algorithms — watch evolution find the shortest route through dozens of cities in real time
Page: Travelling Salesman Problem (TSP)
Description: "Finding the shortest route through all cities"
Category: artificial-intelligence
Icon: map-marker-path
Tags: genetic, optimization
Status: validated

Front matter (index.md):
  title: "Travelling Salesman"
  description: "Finding the shortest route through all cities"
  icon: "map-marker-path"
  tags: ["genetic", "optimization"]
  status: ["validated"]

HTML structure (index.md):
  <section class="container visual size-800 ratio-1-1 canvas-contain">
    <canvas id="tsp-canvas"></canvas>
  </section>

Widget files:
- _stats.right.md (weight: 10): ##### Statistics, <dl> with Generation/Best/NN Baseline/Confidence stats
- _history.right.md (weight: 15): ##### Convergence, <section class="history-container card" style="aspect-ratio: 3/1; width: 100%;"><canvas id="history-canvas">
- _controls.right.md (weight: 20): ##### Controls, div.tsp-controls with 3 buttons:
    {{< button id="start-btn" label="Start" >}}
    {{< button id="reset-btn" label="Reset" >}}
    {{< button id="new-btn" label="New" >}}
- _options.right.md (weight: 30): ##### Options, <dl> with:
    - Algorithm: <select id="algorithm"> with 3 optgroups:
      Constructive: nearest/greedy
      Improvement: 2opt/3opt
      Metaheuristic: genetic(selected)/simulated-annealing/ant-colony/tabu
    - Cities: <select id="city-type"> with 3 optgroups:
      Basic: random(selected)/clusters/manual
      Geometric: circle/two-circles/grid/line
      Special: star/spiral/convex
    - Count: <input type="number" id="city-count" min=5 max=50 value=20 step=5>
    - Population: <input type="number" id="population-size" min=20 max=500 value=100 step=10>
    - Mutation: <input type="range" id="mutation-rate" min=5 max=50 value=15>
    - Speed: <input type="range" id="speed" min=1 max=10 value=1>
    - Adaptive: <input type="checkbox" id="adaptive-mutation" checked>
    - Labels: <input type="checkbox" id="show-labels" checked>

- _algorithm.after.md: Explains TSP as NP-hard, describes GA approach (encoding, selection, crossover OX, mutation swap+2opt, elitism), adaptive mutation, NN baseline.

Architecture (multi-file):
- default.js: Main orchestrator (IIFE), imports 8 algorithm modules + 9 city pattern modules + panic
- Algorithm modules (ES modules with uniform interface: init/step/isDone/getBestRoute/getBestDistance/getIteration/reset + name/type exports):
  - _algorithm-nearest.lib.js: Constructive, visits nearest unvisited city
  - _algorithm-greedy.lib.js: Constructive, adds shortest edges avoiding premature cycles (union-find)
  - _algorithm-2opt.lib.js: Improvement, iteratively reverses segments, stops after 2 passes without improvement
  - _algorithm-3opt.lib.js: Improvement, considers all 7 reconnection types for 3 edges, stops after 2 passes
  - _algorithm-simulated-annealing.lib.js: Metaheuristic, accepts worse solutions with probability exp(-delta/T), cooling rate 0.9995, min temp 0.01
  - _algorithm-ant-colony.lib.js: Metaheuristic, pheromone-based (alpha=1, beta=2, evaporation=0.5, Q=100), 20 ants, 500 max iterations
  - _algorithm-tabu.lib.js: Metaheuristic, 2-opt neighborhood with tabu list (tenure=n/4), aspiration criterion, max 1000 iterations or 100 no-improvement
  - _algorithm-genetic.lib.js: Metaheuristic, imports GA from /_lib/ga_v1.js, population 100, elitism 5, crossover rate 0.9, order crossover (OX), swap+2opt mutation at 15%, max 1000 generations or 100 no-improvement
- City pattern modules (ES modules with generate(count, width, height, padding) + name export):
  _cities-random/circle/clusters/grid/star/two-circles/line/spiral/convex.lib.js

SCSS file (default.scss):
- layout-main main: flex column, centered, padding 2rem, gap 1.5rem
- #tsp-canvas: 100% size, border, border-radius 4px, background surface
- .tsp-controls: flex row, gap 0.5rem, .button flex:1
- .history-container #history-canvas: 100% size
- Confidence colors: .confidence-high (#27ae60), .confidence-medium (#f39c12), .confidence-low (#e74c3c)

State management:
- Distance matrix precomputed (n×n) on city generation
- NN baseline calculated for comparison (greedy nearest neighbor heuristic)
- Manual mode: click canvas to place cities (min 3 required)
- distanceHistory[] tracks best distance per frame for convergence graph

Rendering:
- Best route drawn as connected path (primary color, lineWidth 2)
- Cities drawn as filled circles (text color), numbered labels if showLabels
- Manual mode hint: "Click to add cities (min 3)" when < 3 cities
- History graph: line chart with NN baseline as dashed line, axes with labels

Controls:
- Space: toggle Start/Pause
- R: reset (keep cities, reinit algorithm)
- N: new cities (regenerate)
- Speed slider: controls steps per frame (1-10)
- Algorithm change triggers reset
- City type change: "manual" enables click-to-place mode

Canvas: fixed 800x800 (main), history canvas sized to parent rect
Color caching: lazy CSS var reading (--background-color-surface, --draw-color-primary, --text-color-surface)

Confidence rating based on ratio bestDist/nnDist:
- < 0.85: "Excellent" (green)
- < 0.95: "Good" (yellow)
- < 1.0: "Fair" (red)
- >= 1.0: "Searching..."
Page entièrement générée et maintenue par IA, sans intervention humaine.
See also
