Traveling Salesman Problem

Comparison of "Genetic Algorithm"

On the previous page, he stated that there are various learning methods in the "genetic algorithm".

So, what kind of learning method is good for you? I tried to compare some.

Used in Verifications

For the Verifications used this time, we will use TSP simulation, with the permission to use and publish from Mr. Hiroshi Iba, professor of electronic information science at the University of Tokyo graduate school of information science and engineering.

　This simulation was developed in Macro mode of Excel in order to solve the traveling salesman problem with "genetic algorithm", and it is possible to set the probability of mutation / crossover, how to select parent data, etc. .

Also, in this simulation, the goodness of fit is output with goodness of fit = 1 / distance.

In the Verification of this time, we set 20 visiting places within the range of 1 × 1 (distance is outputted at 500 (m) × 500 (m) for easy understanding this time).

Differences according to selection method

Verificational method

Here I would like to change the selection method of parent data between ➁ and ③ in the above figure.

As mentioned earlier, there are mainly three kinds of parent data selection method.

• Random selection
• Roulette selection
• Tournament selection

Result

Consideration

From the table above, the degree of conformity of the tournament selection was the highest.

This probably can be inferred that, unlike roulette selection, we have chosen a certain degree of goodness of fit from an arbitrary number.

Difference in crossover rate

Verificational method

Here I would like to change the crossover rate between 3 and 4 in the above figure.
At the same time, we will change the selection method for comparison.

Crossover rate is like reading letters, What percentage of the selected data crossover occurs.

Result

Consideration

From the above table, in any selection method, the higher the crossover rate, the higher the degree of conformity was generally.

This probably seems to be due to the increased opportunities for new data to be generated one after another due to crossover, so the probability of seeking a high degree of conformity has increased.

Difference in mutation rate

Verificational method

Here I would like to change the mutation rate between 3 and 4 in the above figure.
At the same time, we will change the selection method for comparison.

The mutation rate is the rate at which the mutation occurs in selected data among the selected data as it reads.

Result

Consideration

From the table above, in any selection method, the higher the mutation rate, the higher the fitness degree was generally.

This probably seems to be that the probability of seeking a product with a high degree of conformity has risen, as opportunities for new data are generated one by one by mutating as well as the crossover rate.

After finishing the Verification

It is understood from this Verification that there is a difference of about 400 m at maximum with the learning method of "genetic algorithm".

Some people think that "There is not much difference."
However, if this continues every day, it will be a very large distance difference.

Therefore, neglecting to consider which learning method, it will be a waste of considerable time and fuel in the year.

We think that it is quite effective data because it is the result of outputting 5 times each time this time, but the "genetic algorithm" has a stochastic part and it may not be like the Verification result this time.

Also in 2017, Yamato etc. tried AI to the delivery planning system on a trial basis. However, it seems like this time we do not consider only the distance but we will output the optimum route by including conditions such as delivery place and designated time.

However, from the voice of the site, there is something that said "It is not good to turn mechanically", "Some experienced drivers seem to be unnecessary longs", and there is something like "genetic algorithm" There are still many issues to introduce AI.

In the future it is said that opportunities to deliver by drone and the labor burden of the driver will increase. Regarding drones, we can fly almost freely, regardless of roads, so there is a need to think about more appropriate routes. Also in the future, as a result of popularization of mail-order sales etc., the labor burden will be further increased from now on, if the "genetic algorithm" is used, the delivery route can be somewhat shortened and the burden on the driver will be reduced, so even while considering the aforementioned problem I think that further introduction or improvement of AI such as "genetic algorithm" will be advanced further in the logistics industry.

---

BackVerificationNext