Hello everybody! Today we are hear to talk a little about the power of genetic algorithms.

Traveling Salesman Problem

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?”

The traveling salesman problem is an NP-hard problem that does not have a general solution, meaning that in order to find the correct answer you would have to calculate each possible route. Let’s say for example you have just 3 cities, city1, city2, and city3. Let’s assume you are starting in city1. You would have to test the routes.

  • city1->city2->city3->city1
  • city1->city3->city2->city1

That’s not too bad, so let’s add 2 more cities, city4 and city5. Let’s list of the routes.

  • city1->city2->city3->city4->city5->city1
  • city1->city3->city2->city4->city5->city1
  • city1->city4->city3->city2->city5->city1
  • city1->city5->city2->city4->city2->city1
  • city1->city4->city2->city4->city5->city1
  • city1->city4->city2->city4->city5->city1

In the interest of time we are going to stop at 6. If we were to list all possible routes there would be 24. Why would it increase at such a fast rate? This is due to the fact that the number of possible paths is (n-1)! where n is the number of cities. Therefore we can calculate the number of routes as (5-1)!, or 4*3*2*1. So if we were to add in another city, city 6, we would have (6-1)! routes, which is 96. By the time we get to 11 cities, the number grows to 3,628,800. Calculating the distance on all those routes to find the best one is incredibly costly, so we are going to have to find another approach.

Genetic Algorithms to the rescue

Genetic Algorithms are a class of algorithms that can help find a suitable solution for an optimization problem by evolving a population of possible solutions. As you can probably guess, it is inspired by the biological evolution which operates with the assumption that the best organisms in a given generation pass their qualities to their offspring, therefore optimizing the species to better survive in it’s environment.

With genetic algorithms we can get a decent approximation of the best route to take in the traveling salesman problem, by evolving a population of routes into the shortest route possible.

Finally, some code

https://github.com/DavidMNewman/TravelingSalesmanGA

Here is the accompanying project that includes an implementation of a genetic algorithm that approximates solutions to the traveling salesman problem written in Swift. In it I have hardcoded 20+ international cities.

  1. Generate an initial population with random routes. This can be found in Population.swift
  2. Use a basic greedy algorithm that determines it’s route by simply moving to the next nearest city that has not yet been visited to generate a baseline tour that we can use for comparison. We also go ahead and add this tour to the initial population since it is certainly a better solution than most random tours. This is implemented near the top of the TravellingSalesmanAlgorithm.swift file.
  3. Create a new generation of routes, by creating child routes from a crossover operator https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm). This is implemented in the evolvePopulation function, which lives in TravellingSalesmanAlgorithm.swift.
  4. Apply mutations randomly to the new children. This helps prevent too many solutions from evolving to the same route by increasing diversity https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm). This is implemented in TravellingSalesmanAlgorithm.swift.

Each time we repeat steps 3 and 4 we are evolving the population and creating new generations that over time will get closer and closer to the best possible tour. The number of generations created depends on how much accuracy is required, and how much processing time we are comfortable with. Bear in mind that there are diminishing returns, and  doubling the number of generations may not necessarily generate a significantly better solution. Here are some results. Note that the distance is an estimate as the distance between longitudinal lines vary depending on how close to the poles the location is.

Tour generated using basic greedy algorithm

Basic Algorithm Distance: 52772.7516042231
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Charlotte: (35.0, -80.0), 
Washington D.C.: (38.0, -77.0), 
Buffalo: (42.0, -78.0), 
Cleveland: (41.0, -81.0), 
New York: (40.0, -73.0), 
Boston: (42.0, -71.0), 
Quebec: (46.0, -71.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Salt Lake City: (40.0, -111.0), 
Las Vegas: (36.0, -115.0), 
Los Angeles: (34.0, -118.0), 
Fresno: (36.0, -119.0), 
San Francisco: (37.0, -122.0), 
Vancouver: (49.0, -123.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
Toronto: (43.0, -40.0), 
London: (51.0, 0.0), 
Paris: (49.0, 2.0), 
Berlin: (52.0, 13.0), 
Atlanta: (33.0, -84.0)]

Tours generated using the genetic algorithm

After 25 Generations
Tour Distance: 49940.0770899216
Improvement: 5.67214685952737%
Time: 0.056672990322113 seconds
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Salt Lake City: (40.0, -111.0), 
Washington D.C.: (38.0, -77.0), 
Cleveland: (41.0, -81.0), 
Buffalo: (42.0, -78.0), 
New York: (40.0, -73.0), 
Boston: (42.0, -71.0), 
Quebec: (46.0, -71.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Charlotte: (35.0, -80.0), 
Las Vegas: (36.0, -115.0), 
Los Angeles: (34.0, -118.0), 
Fresno: (36.0, -119.0), 
Vancouver: (49.0, -123.0), 
San Francisco: (37.0, -122.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
London: (51.0, 0.0), 
Berlin: (52.0, 13.0), 
Paris: (49.0, 2.0), 
Toronto: (43.0, -40.0), 
Atlanta: (33.0, -84.0)]

After 50 Generations
Tour Distance: 49037.4801952331
Improvement: 7.61717648239414%
Time: 0.113097965717316 seconds
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Charlotte: (35.0, -80.0), 
Washington D.C.: (38.0, -77.0), 
New York: (40.0, -73.0), 
Boston: (42.0, -71.0), 
Quebec: (46.0, -71.0), 
Buffalo: (42.0, -78.0), 
Cleveland: (41.0, -81.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Salt Lake City: (40.0, -111.0), 
Las Vegas: (36.0, -115.0), 
Los Angeles: (34.0, -118.0), 
Fresno: (36.0, -119.0), 
Vancouver: (49.0, -123.0), 
San Francisco: (37.0, -122.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
Berlin: (52.0, 13.0), 
London: (51.0, 0.0), 
Paris: (49.0, 2.0), 
Toronto: (43.0, -40.0), 
Atlanta: (33.0, -84.0)]

After 100 Generations
Tour Distance: 48674.4101485061
Improvement: 8.41990985245195%
Time: 0.215808033943176 seconds
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Charlotte: (35.0, -80.0), 
Washington D.C.: (38.0, -77.0), 
New York: (40.0, -73.0), 
Boston: (42.0, -71.0), 
Quebec: (46.0, -71.0), 
Buffalo: (42.0, -78.0), 
Cleveland: (41.0, -81.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Salt Lake City: (40.0, -111.0), 
Paris: (49.0, 2.0), 
Los Angeles: (34.0, -118.0), 
Fresno: (36.0, -119.0), 
Vancouver: (49.0, -123.0), 
San Francisco: (37.0, -122.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
Berlin: (52.0, 13.0), 
Las Vegas: (36.0, -115.0), 
London: (51.0, 0.0), 
Toronto: (43.0, -40.0), 
Atlanta: (33.0, -84.0)]

After 1,000 Generations
Improvement: 9.36724551381963%
Time: 1.08338397741318 seconds
Tour Distance: 48252.7939295634
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Charlotte: (35.0, -80.0), 
Washington D.C.: (38.0, -77.0), 
New York: (40.0, -73.0), 
Boston: (42.0, -71.0), 
Quebec: (46.0, -71.0), 
Buffalo: (42.0, -78.0), 
Cleveland: (41.0, -81.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Salt Lake City: (40.0, -111.0), 
Vancouver: (49.0, -123.0), 
San Francisco: (37.0, -122.0), 
Fresno: (36.0, -119.0), 
Los Angeles: (34.0, -118.0), 
Las Vegas: (36.0, -115.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
Berlin: (52.0, 13.0), 
Paris: (49.0, 2.0), 
London: (51.0, 0.0), 
Toronto: (43.0, -40.0), 
Atlanta: (33.0, -84.0)]

After 10,000 Generations
Improvement: 12.0477993235991%
Time: 10.5947470068932 seconds
Tour Distance: 47098.4275664469
[
Atlanta: (33.0, -84.0), 
Jacksonville: (30.0, -81.0), 
Charlotte: (35.0, -80.0), 
Buffalo: (42.0, -78.0), 
Cleveland: (41.0, -81.0), 
Minneapolis: (44.0, -93.0), 
Fargo: (46.0, -96.0), 
Wichita: (37.0, -97.0), 
Dallas: (32.0, -96.0), 
Denver: (39.0, -105.0), 
Salt Lake City: (40.0, -111.0), 
Vancouver: (49.0, -123.0), 
San Francisco: (37.0, -122.0), 
Fresno: (36.0, -119.0), 
Los Angeles: (34.0, -118.0), 
Las Vegas: (36.0, -115.0), 
Mexico City: (-24.0, -103.0), 
Rio: (-23.0, -43.0), 
Berlin: (52.0, 13.0), 
Paris: (49.0, 2.0), 
London: (51.0, 0.0), 
Toronto: (43.0, -40.0), 
Quebec: (46.0, -71.0), 
Boston: (42.0, -71.0), 
New York: (40.0, -73.0), 
Washington D.C.: (38.0, -77.0), 
Atlanta: (33.0, -84.0)]

Conclusion

While 10 seconds of processing time for only a 12% improvement might not look that impressive, consider that it represents about 5,000 miles saved when compared to the simple greedy algorithm. Also consider the fact that in the initial first generation, if we ignore the greedy algorithm, the shortest routes were typically a little more than twice as long as the best route after 1,000 generations. This reduction in travel time and distance can result in a decent amount of time/money saved. If the idea of a traveling salesman isn’t interesting or relevant, consider other areas where this methodology could be used. Optimizing shipping and distribution routes maybe? How about in medicine via clinical decision support in ophthalmology and oncology? Maybe mobile communications infrastructure optimization is more you thing. In conclusion, Genetic Algorithms are incredibly versatile and can tackle a wide range of problems.

 

 

Related Posts

David Newman

David Newman

Lead Developer - David graduated from Kennesaw State University with a Bachelor of Science in Mathematics. David is a cross platform mobile developer who specializes in iOS, but is also very comfortable in Android, and back end web services. His previous mobile and web development work was in the banking, property management, and medical fields.