Chapter 1 of 5
Find the shortest round trip
A salesperson has to visit each of these six cities once and then come home. In which order is the trip shortest?
Click the cities on the map in the order you would visit them.
Chapter 1 of 5
A salesperson has to visit each of these six cities once and then come home. In which order is the trip shortest?
Click the cities on the map in the order you would visit them.
Chapter 2 of 5
An ant standing at A does not plan the whole trip. It picks the next city at random, but not evenly: close cities and cities with a strong pheromone trail are more likely.
τ is the pheromone on the edge, η is how close the city is. α and β say how much the ant trusts each one.
Chapter 3 of 5
Now three ants start at A, C and E. At every move each ant uses the rule from chapter 2 to pick a city it has not visited yet. After the last city it walks home.
Chapter 4 of 5
After the round, the pheromone changes in two steps. First every trail evaporates a little. Then each ant deposits pheromone on the edges it used: Q / L, so a shorter tour leaves more.
Chapter 5 of 5
That was one iteration. Now the colony repeats it: build tours, evaporate, deposit. Edges of short tours keep getting stronger, so later ants follow them more often. The colony also remembers the best tour it has seen.
One city per line: x y or name x y. Between 3 and 60 cities.
Tip: click a city to see where an ant there would go next.