AI with PHP Examples (v0.7.0)

Practical Applications

Traveling Salesman Problem

Show Code

Simulated annealing is a probabilistic optimization technique inspired by the annealing process in metallurgy, where metals are heated and then slowly cooled to reduce defects.

How It Works:
  • Temperature: Controls the probability of accepting worse solutions. High temperature = more exploration, low temperature = more exploitation.
  • Cooling: Temperature gradually decreases, reducing the chance of accepting worse solutions over time.
  • Neighbor Generation: In this TSP (Traveling Salesperson Problem) example, we swap two random cities to explore new routes.
  • Acceptance Rule: Better solutions are always accepted. Worse solutions may be accepted based on the current temperature and how much worse they are.

This approach helps avoid getting stuck in local optima by occasionally accepting worse solutions, allowing the algorithm to explore the solution space more thoroughly before converging.

In the visualization:
- The red dashed line represents the current solution being explored
- The green solid line represents the best solution found so far
- The event log shows the decision-making process, including acceptance probabilities
- As temperature decreases, the algorithm becomes less likely to accept worse solutions

The simulation demonstrates how simulated annealing balances exploration (trying many different possibilities) with exploitation (refining good solutions) to find near-optimal solutions to complex problems.

Step-by-Step: Simulated Annealing for TSP

This explanation walks through exactly how the simulated annealing algorithm works in the visualization to solve the Traveling Salesman Problem with 6 cities.

Algorithm Initialization

The algorithm starts with:

  • Initial temperature: 1000 (high to allow extensive exploration)
  • Initial route: Cities visited in order [0, 1, 2, 3, 4, 5] (New York, Los Angeles, Chicago, Houston, Phoenix, Boston)
  • Initial distance: The total distance of traveling this route and returning to the start

This initial route is stored as both the "current route" and the "best route so far".

Main Algorithm Loop

Generate a neighboring solution

The algorithm creates a new potential route by randomly selecting two cities and swapping their positions in the route.

For example: If current route is [0,1,2,3,4,5] and cities at positions 2 and 4 are selected, the new route becomes [0,1,4,3,2,5].

Calculate distances

The algorithm calculates:

  • The distance of the current route
  • The distance of the new potential route (neighbor)
  • The difference between these distances (Δ = new distance - current distance)

Apply the acceptance rule

The algorithm decides whether to accept the new route based on:

  • If the new route is shorter (Δ < 0): Always accept it
  • If the new route is longer (Δ > 0): Accept with probability P = e(-Δ/T), where T is the current temperature

Why accept worse solutions? This is the key feature of simulated annealing. By occasionally accepting worse solutions, especially early in the process when temperature is high, the algorithm can escape local optima and potentially find better solutions later.

Update the current solution

If the new route is accepted:

  • The current route is updated to the new route
  • If this new route is better than the best route found so far, the best route is also updated

The visualization shows this by updating the red dashed line (current route) and potentially the green solid line (best route).

Decrease the temperature

After each iteration, the temperature is reduced by multiplying it by a cooling factor (0.99 in this demo):

Tnew = Tcurrent × 0.99

As the temperature decreases:

  • The probability of accepting worse solutions decreases
  • The algorithm gradually shifts from exploration to exploitation

Repeat until stopping condition

The algorithm continues this process until:

  • The temperature falls below a threshold (0.1 in this demo)
  • The user manually stops the simulation

The final result is the best route found throughout the entire process.

What You're Seeing in the Visualization

Red dashed line: The current route being explored. This changes frequently as the algorithm tries different paths.
Green solid line: The best route found so far. This only changes when a better solution is discovered.
Event log: Shows details for each iteration including temperature, distances, and whether a new route was accepted or rejected.

By observing the visualization over time, you can see how the algorithm initially explores widely (accepting many worse solutions) and then gradually focuses on refining the best solutions as the temperature decreases.

Graph: