Editing Travelling salesman problem (section)

====Ant colony optimization====
{{Main|Ant colony optimization algorithms}}
[[Artificial intelligence]] researcher [[Marco Dorigo]] described in 1993 a method of heuristically generating "good solutions" to the TSP using a [[Ant colony optimization|simulation of an ant colony]] called ''ACS'' (''ant colony system'').<ref>{{cite journal|doi=10.1016/S0303-2647(97)01708-5|s2cid=8243011 |title=Ant Colonies for the Traveling Salesman Problem|year=1997|citeseerx=10.1.1.54.7734|last1=Dorigo |first1=Marco|last2=Gambardella|first2=Luca Maria |journal=Biosystems|volume=43|issue=2|pages=73–81 |pmid=9231906|bibcode=1997BiSys..43...73D }}</ref> It models behavior observed in real ants to find short paths between food sources and their nest, an [[emergence|emergent]] behavior resulting from each ant's preference to follow [[Pheromone#Trail|trail pheromones]] deposited by other ants.

ACS sends out a large number of virtual ant agents to explore many possible routes on the map. Each ant probabilistically chooses the next city to visit based on a heuristic combining the distance to the city and the amount of virtual pheromone deposited on the edge to the city. The ants explore, depositing pheromone on each edge that they cross, until they have all completed a tour. At this point the ant which completed the shortest tour deposits virtual pheromone along its complete tour route (''global trail updating''). The amount of pheromone deposited is inversely proportional to the tour length: the shorter the tour, the more it deposits.

[[File:Aco TSP.svg|600px|center|1) An ant chooses a path among all possible paths and lays a pheromone trail on it. 2) All the ants are travelling on different paths, laying a trail of pheromones proportional to the quality of the solution. 3) Each edge of the best path is more reinforced than others. 4) Evaporation ensures that the bad solutions disappear. The map is a work of Yves Aubry [http://openclipart.org/clipart//geography/carte_de_france_01.svg].]]
[[File:AntColony.gif|framed|center|Ant colony optimization algorithm for a TSP with 7 cities: Red and thick lines in the pheromone map indicate presence of more pheromone]]