Travelling Salesman Problem (TSP Problem) is a classic algorithm optimization Problem. It is described as follows: A Travelling Salesman needs to sell goods in several cities. He only goes to each city once.

A similar problem is described in the second part of the science fiction novel the Three-Body Problem, when water droplets of the Trisolarans attack the Earth fleet in space:

The relentless killing in space continued, and as the distance between the ships widened, the droplet accelerated rapidly, soon doubling its speed to 60 kilometers per second. In its relentless attacks, the droplet shows its cold, precise intelligence. Within a certain area, it solves the mailman problem perfectly, with almost no repetition of attack routes. Doing so while the target is constantly moving requires precise measurements from all angles and complex calculations, all of which are done quietly at high speed. Sometimes, however, it would break away from the single-minded slaughter of an area and run to the edge of the group, swiftly annihilating some of the ships that had broken away from the main group, and in so doing arrest the tendency of the group to flee in that direction. …

Liu wrote the postman problem in the story, which is slightly different from the traveling salesman problem. The former has a number of fixed routes (there may be no route connection between some points), while the latter all points can be directly connected. Therefore, it is more appropriate to say that water droplets in a certain area require the solution of the traveling salesman problem.

The traveling salesman problem is an NP problem, there is no perfect solution at present, but there are many efficient methods to deal with it, such as dynamic programming, genetic algorithm, etc. This article introduces the use of genetic algorithms to solve, and gives a JavaScript version of the example. (Note: Also see the Python version I wrote earlier.)

Genetic algorithm (ga)

Genetic algorithm is a simulated evolutionary method to solve specific problems, its core idea is to code for the “gene”, then generate a number of genes in different individuals, let these individuals competing with each other, and use a kind of evaluation mechanism to make them “evolution”, “evolution” good enough solution in the end.

Specifically, it has two core points: coding, the need to find an appropriate way to map a problem to be solved into a “genetic” code that generates multiple individuals; The second is evaluation, which requires a quantitative method to score each individual and evaluate which individual’s corresponding plan is closer to the best answer, so that the survival of the fittest can be determined according to this score.

Genetic algorithm is just an idea, and there are no specific methods, such as coding and evaluation methods, which need to be analyzed on a case-by-case basis. Its general process is shown in the figure below:

coding

For the sake of analysis, we can number all the cities. The travel agent starts from a city, each city only once, and no city is left out, so the travel agent’s track can actually be simplified to a permutation of city numbers, which can be represented by a sequence (array).

For example, if there are 50 cities in total and we number the cities starting with 1, we get the sequence like this:

One, two, three, four, five, six… 47, 48, 49, 50

The sequence of numbers can be arbitrarily shuffled, and each permutation corresponds to a move. Such as:

12, 50, 30, 26, 13, 45… 39, 18, 41, 17

This sequence shows that the traveler starts from city 12, goes to city 50, to city 30, to city 26, to city 13, to city 45… And then you go to city 39, then you go to city 18, then you go to city 41, then you go to city 17, and of course, finally you go back to city 12.

Being randomly generated, this route might look like a mess on the graph:

Such sequences are a way of coding, and each sequence is called a gene. The array for a gene looks something like this:

At the beginning of the calculation, we can randomly generate N sequences and then evaluate the next step. In this case, the number of cities is 50, and the corresponding number of gene individuals is 100.

assessment

The objective of the traveller problem is very clear: the shortest total distance traveled.

For the sake of convenience, we usually hope that the score of each individual is as big as possible. Since the total distance is as small as possible, the realization of the evaluation function has a very simple and direct scheme — take the reciprocal of the total distance. In our example, this simple scheme works, but some complex scenarios may require more complex evaluation functions.

rate (gene) {
  return 1 / this.getDistance(gene)
}Copy the code

With the evaluation function, we can score all the “genes” and produce the next generation based on that score.

The number of the next generation is usually the same as the previous generation. The general generation rule is:

  1. The best genes of the previous generation go directly to the next generation;
  2. Two genes were selected from the previous generation, and the selection probability was proportional to the score. The two genes were randomly crossed and mutated to generate the next generation.
  3. Repeat step 2 until the desired number of offspring is reached.

cross

Genetic algorithms mimic the evolution of living things. Each time a new generation is created, two previous generations always swap genes (cross over) to produce one offspring. The crossover process is shown in the figure below:

1. Enter two parents

2. Random selection of paternal gene fragments

3. Exchange gene fragments

That gives us two new offspring, and we just have to return one at random.

It should be noted that the city cannot be repeated nor omitted in the travel salesman problem, and the offspring produced by the above method obviously cannot meet this requirement. The solution is also very simple, we directly connect another parent gene after the child, and then undo the array:

xFunc (lf1, lf2) { let p1 = Math.floor(Math.random() * (this.n - 2)) + 1 let p2 = Math.floor(Math.random() * (this.n - p1)) + p1 let  piece = lf2.gene.slice(p1, p2) let new_gene = lf1.gene.slice(0, p1) piece.concat(lf2.gene).map(i => { if (! new_gene.includes(i)) { new_gene.push(i) } }) return new_gene }Copy the code

variation

Genetic algorithm is essentially a search algorithm, in order to avoid falling into the local optimal solution, we have to mutate genes with a certain probability. As in biology, genetic mutations are mostly bad, but without them, it is difficult to create a new species by simply exchanging genes between existing individuals, and the whole population may linger at a low level of local optimal solution.

Since our genes are an array, common basic variants can be switched, moved, reversed, and so on.

exchange

Swapping involves taking two pieces of a gene at random and swapping their positions. As shown below:

Reverse order

A random section of a gene is selected and its order reversed. As shown below:

mobile

Pick a random segment of a gene and move it to another location. As shown below:

The codes corresponding to the three variants are as follows:

Let funcs = [(g, p1, p2) = > {/ / exchange let t = g [p1] g [p1] [p2] [p2] g = g = t}, (g, p1, P2) = > {/ / reverse let t = g.s lice (p1, p2). The reverse () g.s plice (p1, p2 and p1,... t)}, (g, p1, P2) => {// let t = g.floor (p1, p2-P1) g.floor (math.floor () * g.length), 0,...t)}]Copy the code

practice

With this foundation in place, you are ready for coding practice. All code for this article is open source on GitHub.

First of all, N cities are randomly generated. Here we take N = 50, and each city contains x and y coordinates. Draw them in red circles on the canvas and randomly generate a route that looks something like this:

Then start iterating and plot the route with the highest score for each generation. Here’s what the 710th generation looks like:

As you can see, it’s much better than the original, but there are still a few areas where there is clearly room for improvement. Continuing the evolutionary iteration, approximately to the 3000th generation, the following figure is obtained:

Thousands more iterations followed, but the route remained unchanged. And it looks like that’s the best solution we can find right now.

Here’s a GIF from another trial:

You can visit the following link to experience online:

Oldj.net/static/tsp/…

summary

This paper introduces the main idea of genetic algorithm and an example of traveling salesman problem.

The application of genetic algorithm is very wide, and many engineering optimization problems that cannot be solved by conventional methods can be solved elegantly by genetic algorithm. However, genetic algorithm is not a panacea, it should be noted that genetic algorithm can not guarantee to find the global optimal solution, if the code design is not good, or the parameters are not appropriate, it is likely to fall into a local optimal solution.

In addition, the application of genetic algorithm has two main limitations:

  1. Problems must be encoded as “genes”;
  2. There are appropriate evaluation functions.

Many problems seem to be simple, but it is very difficult to translate the solution into gene coding. Only when the solution is encoded as gene can the next operation such as crossover and mutation be carried out.

For most of the problems, there are coding methods, some of which are less obvious, but it is a real challenge to have an appropriate evaluation function that is stable (identical genes get the same score) and efficient enough to automate the iteration.

A few years ago, we explored the use of genetic algorithms to generate beautiful advertising images. The image contains many elements, the coding is complicated, but it is not difficult in nature. Finally, we could not find the appropriate evaluation function — what is “beautiful”? Without defining an evaluation function, the entire iteration cannot be automated. We also tried semi-automation, the process of making, crossing and mutating genes, and then manually scoring the results of each generation. But later found that this approach doesn’t work, because first of all, usually need to thousands of iterations can be available as a result, the people, the time cost is too high, the second is more important is that people actually is not very good and stable to identify what is “beautiful”, sometimes feel that combination is very beautiful, but after a while to see may feel general again. The instability of the scoring leads to the instability of the evolutionary process, and it is difficult to converge to the optimal solution. If you need to deal with problems like this, the better solution for now is probably deep learning.

Finally, post a link to the online demo: oldj.net/static/tsp/… .