Lately artificial intelligence has been becoming more and more popular, but at the same time a stereotype has been formed that AI is only is based solely on the neural networks even though a neural network is only one of the numerous directions of artificial intelligence. The aim of this paper is to bring attention to other directions of AI, such as genetic algorithms. Study the process of solving the travelling salesman problem (TSP) via genetic algorithms (GA) and take a look at the problems of this method. The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. One of the common problems in programming is the traveling salesman problem. There are many various methods that can be used to solve it, but the one we are going to take a look are the genetic algorithms. The aim of this study is to the most efficient application of genetic algorithms in the travelling salesman problem.
One of the common problems in programming is the traveling salesman problem. There are many
various methods that can be used to solve it, but the one we are going to take a look are the genetic
algorithms. The aim of this study is to the most efficient application of genetic algorithms in the
travelling salesman problem [
Lately artificial intelligence has been becoming more and more popular, but at the same time a
stereotype has been formed that AI is only is based solely on the neural networks even though a
neural network is only one of the numerous directions of artificial intelligence. The aim of this paper
is to bring attention to other directions of AI, such as genetic algorithms [
Study the process of solving the travelling salesman problem (TSP) via genetic algorithms (GA) and take a look at the problems of this method.
The origins of the travelling salesman problem are unclear. A handbook for travelling salesmen
from 1832 mentions the problem and includes example tours through Germany and Switzerland, but
contains no mathematical treatment [
It was first considered mathematically in the 1930s by Merrill M. Flood who was looking to solve
a school bus routing problem. Hassler Whitney at Princeton University introduced the name travelling
salesman problem soon after [
There are many methods of solving this problem. Some of them give exact results, others only
approximate. One of the more interesting methods is the methods of route optimization with the use
of genetic algorithms [
2021 Copyright for this paper by its authors.
First experiments which involved simulated evolution were conducted by Nils Aall Barricelli in
1945. Later they were also conducted by Nils Aall Barricelli, Ingo Rechenberg and Hans-Paul
Schwefel. Thanks to them artificial evolution became a well-known optimization method [
The travelling salesman problem is a problem of finding the fastest (most efficient) route between n cities where the route must go once through every city. If the problem is presented in the form of a graph, then the answer will be in the form of the shortest Hamiltonian cycle.
The travelling salesman problem can be presented as a [
There are two main groups of methods for solving the travelling salesman problem which can be
combined [
Genetic algorithms are generally more efficient than the complete vocabulary as there is no need to
go through all the possible combinations. At the same time genetic algorithms are heuristic which do
not guarantee a precise solution, but only the best possible approximation with the given amount of
time(iterations) [
traits child chromosomes are formed in a certain way by combining parent genes. This process is called a crossover.
In case when both mutation and cross-breeding have been performed in order to avoid a situation
in which the population did not improve or got stuck on a certain iteration some if not all individuals
are mutated. In other words one or some genes in a chromosome are replaced. Even though this
process of mutation is not mandatory as mutations can both improve the rate of approximation to the
result and slow it down [
After cross-breeding and mutating it is mandatory to correct the number of individuals in the population so that the population did not increase in size after each iteration. Only the most adapted individuals will go on into the next generation (the rest will be annihilated).
If the generation is not adapted enough we repeat processes of rating, selecting, crossbreeding / mutation and forming the new generation.
If the new generation is adapted enough, it can be considered to be resulting. In our case the route
is as short as possible and any improvements are either insignificant or are impossible [
The complexity of using this method is that isn’t possible to use a regular crossover or a mutation.
In classic genetic algorithms crossovers are generally presented as simple combinations of different parts of the parent chromosomes. For instance let us say we have the following parents:
As we can see the regular crossover is not applicable to this problem as it is possible to get to one city two times and do not get to another at all.
The same situation will occur with the use of the regular mutation.
This situation can be avoided if the complexity of the crossover and the mutation is increased.
As was mentioned before, in order to avoid getting to the same city twice merely differently combining halves of parent chromosomes will not be sufficient. The simplest way to resolve this is to change the city which is repeated to a city that is not present. But at the same time this method entails the fact that each possible descendant may have several options.
Back to the same example.
The main drawback of this method is the large amount of iterations which are required to find the repeats which are needed to be competed for this cross-breeding. As a result, this method is quite inefficient in terms of runtime.
Even though the operation of correcting children is similar to mutation, a full-fledged mutation still needs to be implemented, because otherwise child elements with similar genome might cease to evolve. 4.2.
The previous strategy was based on a basic crossover which had to be improved so that children could form a Hamiltonian cycle which in term would create a large quantity of children variations.
If we take the premade directions of movement which were taken from parent chromosomes, then there would be no reason to correct the children. As a result, by using this method we will acquire a wanted amount of children and will not be dependent on the amount of repeating cities.
The idea of this strategy is that the combination of parent genes should immediately form a
Hamiltonian cycle [
In addition to make sure that the child chromosome would not repeat its parent it necessary to limit the length parents chromosome from which the child will be built.
To understand this method let us look at the following example. We have our parents: E
A
B Parent 1
D
C
B
C
A Parent 2
E
D
To begin with let us take a part of genes from one of the parents, three genes from parent 1 to be exact.
Then we shall take the other fathers’ gene (BCAED). As we can see, it is in the first place. Next we choose a direction leading to a city in which we have not been yet. And because we are looking for a cyclic route we are not restricted to only moving from the previous gene to the next gene(city), but we can also move from the first to the last one and vice versa. In this case we can both move to D and C. For the sake of optimization let us assume and moving to the right has a higher priority, so we add C.
After that, we are going to be moving through the parent in the same direction until we hit a city to which we have been to before. Then we move to the next parent and repeat the previous step. This continues until we reach all the cities.
In our case after C comes A to which we have been before we also cannot move backwards and because of that we move to the next parent. Here we can go to D and that is going to be our last gene. As a result we will get:
In this case we are not just going to the first available city, but rather we choose and optimal path. In the beginning a starting gene is randomly chosen, so the simplicity sake in this example the first parent gene will be chosen, let us E. Next we have the options between A, C or D and the shortest one will be chosen. Given that we have not specified the distances between the cities let us assume that C is the shortest. And as a result we get more children which are more efficient than their parents.
In order to simplify the work we will take the method of mutation from the first method i.e. the process of mutation goes as it would go for a regular genetic algorithm. Then we will correct the cities which are missing. As a result, we will just swap the places of two random genes.
The chromosome before mutation:
The next problem that occurs is the selection of individuals which will be bred and how they will
be bred. The simplest and possibly the most efficient one method is sorting the individuals according
to some coefficient and pairwise crossing of the most adapted individuals [
That fact that crossing the same parents will yield the same individual. In order to avoid breeding the same pairs of parents each individual will have its list of partners with whom he created offspring and block its ability to breed with these individuals.
Development of the software solution
The structure of the software solution can be separated into three parts [
Structural specifics of the travelling salesman problem.
In order to work with genetic algorithms input data is required and in this particular problem it is presented in the form of the list of cities between which we are looking for the shortest route.
In order to be able to consider the graphic formulation of the route cities are represented as points with their names on the coordinate plane.
When selecting the structure to hold the data it is important to take into account that connections
between the cities are more important than the cities themselves (Figure 2) and that it is wise to store
the calculated distances and retrieve them rather than constantly recomputing them as it will create an
excessive load on the program. So for this purpose we will realize a sort of map which will store all
the cities and distances between them. To ease the access to data inside the said map the list of cities
and the list of distances between them will be presented as hash-maps. Cities will be accessed through
their name and the distances will be accessed by using a key which is composed out of the names of
the cities distance between which we are looking for [
Considering the fact that the algorithm is supposed to work with only one instance of the map we should restrict its access to creating multiple maps. This can be done by implementing map based on the Singleton pattern.
Also, in order to not repeat the operation of creating a map every time we call the algorithm options of saving the map to a file, loading it from the said file and generating it with randomized data have been implemented (Figure 3).
Genetic algorithm in this specific problem
An individual is the smallest structural unit in any genetic algorithm and all individuals have a
chromosome and an adaptivity score. In our case a chromosome is a sequence of cities a.k.a one of
the possible routes and the adaptivity score is the ratio of the length of the shortest known route to the
length of the current individual [
In order to determine the best adapted individuals, we need to be able to compare them by their adaptivity score and for this a “Comparable” will be used.
The first generation will be generated with random routes.
The process of generating individuals
We get our list of cities from the map and for this every individual should also have access to the
map. Individuals should also have the same access to the values of the shortest route and the size of
their chromosomes (Figure 4) [
Evolution occurs in each generation. Generation is an imitation of the life cycle where in every
generation there is a population of individuals and within that population that population the breed.
During the creation of the next generation only the individuals with the highest adaptivity score are
kept alive [
The two main methods are shown below. The first one launches the algorithm with required parameters and the second one save the resulting data into a file.
Implementation of the cross-breeding and mutation methods
Cross-breeding and mutation methods are implemented inside an enumerative class where each element represents one method of cross-breeding and mutation.
Also the ability of acquiring descendants from the breeding individuals has been added in that class.
The generalized representation of this class (Figure 6).
Inside the first method everything takes place in two steps. The first one is the combination of parent chromosomes and the second one is the formatting of the resulting chromosome to make sure it fits the standard model. This method involves adding two sequences of cities and removing repetitions from them.
Mutation on the other hand is realized as a swap of two random genes.
Inside the second method everything is a bit more complicated. First of all an attempt is made to copy parents transitions and if at some point it becomes impossible to do so then all the cities which were not visited are added to it.
The third method is similar to the second one but with a slight change. The shortest possible parent transition is selected.
We will conduct a study on equal terms for each one of the methods. For this we shall use the same map and the starting generation (Figure 7).
Let us generate a map with 20 cities (Table 1).
As we can see the third algorithm has the best runtime and gives us the shortest final route. The second algorithm is average in both runtime and the final route. And the third one has the worst runtime and returns mediocre results.
An analysis of the approximation to the optimal solution
As we can see from the chart the third method gives us the best results and the results of simple and cycle methods are actually quite similar (Figure 11).
The nearest algorithm has the largest decline and because of that it needs fewer generations to achieve the optimal solution.
Cycle gave us some interesting results (Figure 11). It has a jump-like approximation and it happens much less often than in other algorithms. And as a result, the best fitted individual survives for much longer compared to other simple and nearest algorithms.
In the article three methods of crossing are proposed. After all, in classical genetic algorithms, the crossover occurs through the simple bonding of different halves of the chromosomes of both parents. Therefore, it is not suitable for solving our task, because using it we will get to the same city twice and will not visit other cities. A similar situation will occur when using a normal mutation. Therefore, if you complicate the crossover and mutation, you can avoid this situation.
To do this, use three strategies. The first is to replace a recurring city with a missing one. At the same time, this method entails the fact that each possible offspring may have several options. The disadvantage of this method is the large number of iterations to find repetitions to be performed for one crossing.
The second strategy is the gluing of parental genes to form a Hamiltonian cycle. Based on the second method, you can create an even more efficient crossover.
The third strategy is to choose the most efficient move, to speed up the algorithm and to reduce the number of required generations. A side effect of this strategy is that the offspring can become a copy of the father: however, this can be solved either by mutating the offspring or removing it from the general genetic population. The third strategy has a feature of the method of the nearest neighbor, which in turn makes each offspring more effective than his father.
As we can see genetic algorithms are a nice way of locating the best possible solution. They have a quite short runtime where one iteration takes about 46-110 ms in 20 cities. We took a look at three methods of cross-breeding and from them the most efficient one was the third one. This is thanks to the fact that the third one has one special feature from the nearest neighbor which in terms makes every child have a better adaptivity score than its parents.
[19] A. Shabalov, E. Semenkin, P. Galushin, Automatized Design Application Of Intelligent Information Technologies for Data Mining Problems, in: The 7th Inter-national Conference on Natural Computation & The 8th International Conference on Fuzzy Systems and Knowledge Discovery, Shanghai, China, 2011, pp. 2659–2662. [20] E. Semenkin, M. Semenkina, Self configuring genetic algorithm with modified uniform crossover operator, in: Advances in Swarm Intelligence, ICSI 2012, Part 1, LNCS 7331, Springer, Heidelberg, 2012, pp. 414.–421. [21] X. Chen, P. Zhang, G. Du and F. Li, Ant colony optimization based memetic algorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems, 2018. Digital Object Identifier 10.1109/ACCESS.2018.2828499 [22] L. Grady, E. L.Schwartz, Isoperimetric Graph partitioning for Image segmentation, in: IEEE
Trans. on Pattern Analysis and Machine Intelligence, Vol.28(3), 2006, pp.469-475. [23] J. Gaber, M. Bakhouya, An Immune Inspired-based Optimization Algorithm: Application to the Traveling Salesman Problem, in: Advanced Modeling and Optimization, Vol. 9(1), 2007, pp. 105–116.