INVESTIGATION OF THE INFLUENCE OF STRONG MUTATIONS IN THE SOLUTION OF THE TRAVELING SALESMAN PROBLEM BY THE MODIFIED GOLDBERG MODEL
The present paper studies the influence of a combination of various crossovers and mutations on the result of genetic algorithm (GA) performance in solving the traveling salesman problem (TSP). TSP is an NP challenging discrete optimization problem, for which there is no algorithm found, and perhaps there is no algorithm which would allow finding the exact solution in polynomial time. The probability of a mutation and crossovers in the proposed algorithm is 100 %. The tests were carried out on average dimension graphs. GA is one of the effective polynomial algorithms for finding approximate solutions of TSP. GAs refer to the evolutionary methods of solving problems designed to find the preferred solutions and are based on the statistical approach to the study of situations and the iterative approximation to the sought-for state of systems. As a selection policy we used the "comparison of a mutating individual with an ancestor, and then the best of them with a random individual in the generation." It has shown itself as one of the best in the course of various computational experiments. The software implementing this algorithm was developed. This version of the GA uses a modified Goldberg model. The proposed algorithm allows us to find the known best solution for graphs up to 30 vertices. And also the deviation of the best solution found from the optimal does not exceed 5.1 %, which is quite acceptable for graphs with a dimension from 50 to 60 vertices. It should also be noted that the difference between the best and the average of 30 starts is about 1.5 %.