If you’re not already familiar with genetic algorithms and like to know how they work, then please have a look at the introductory tutorial below:Ĭreating a genetic algorithm for beginnersįinding a solution to the travelling salesman problem requires we set up a genetic algorithm in a specialized way. In this tutorial however, we will be using genetic algorithms as our optimization technique. These algorithms are capable of finding a ‘good-enough’ solution to the travelling salesman problem surprisingly quickly. So going back to our original problem, if we want to find the shortest route for our map of 20 locations we would have to evaluate 2432902008176640000 different routes! Even with modern computing power this is terribly impractical, and for even bigger problems, it’s close to impossible.įinding a solutionAlthough it may not be practical to find the best solution for a problem like ours, we do have algorithms that let us discover close to optimum solutions such as the nearest neighbor algorithm and swarm optimization. The number of possible routes is a factorial of the number of locations to visit, and trouble with factorials is that they grow in size remarkably quick!įor example, the factorial of 10 is 3628800, but the factorial of 20 is a gigantic, 2432902008176640000. If you're good at maths you may have already realized what the problem is here.
So for this case of just 3 locations it's reasonably trivial to calculate each of those 6 routes and find the shortest. That means, for this example, there are only 6 different routes to pick from.
This would mean there are 3 x 2 x 1 different routes to pick in total. Next, we’d have a choice of 2 cities for the second location, then finally there is just 1 city left to pick to complete our route. To find a single route, we first have to choose a starting location from the three possible locations on the map. To understand why it's so difficult to prove the optimal route let’s consider a similar map with just 3 locations instead of the original 20. Well, in short, we can’t - at least not practically. However, when we’ve found a route that we believe is optimal, how can we test if it's really the optimal route? Fortunately, humans are pretty good at this, we can easily work out a reasonably good route without needing to do much more than glance at the map. On it you see that the map contains a total of 20 locations and you're told it’s your job to visit each of these locations to make a sell.īefore you set off on your journey you'll probably want to plan a route so you can minimize your travel time. Imagine you're a salesman and you've been given a map like the one opposite. By Lee Jacobson Applying a genetic algorithm to the traveling salesman problem To understand what the traveling salesman problem (TSP) is, and why it's so problematic, let's briefly go over a classic example of the problem.
0 kommentar(er)
