Applicability of elite samples in solving the traveling salesman problem by Goldberg model

Abstract

The work objective is to study a critical traveling salesman problem which is NP complicated task of the discrete optimization. It is shown that only heuristics is appropriate in achieving this goal. The result of the ant colony algorithm (ACA) and genetic algorithm (GA) sharing is presented for the problem solution. The point is that the problem is solved using only mutations of various types (without crossover). The investigated GA is improved by the elitist strategy. The testing is done on graphs of the middle and large dimension. An “elite” sample obtained by the ACA is improved by a mean of 11%. It is shown that the efficiency of the genetic algorithm depends directly on the number of ants in the generation, and on the number of algorithm iterations. Target function values are improved more than twofold after the introduction of the elitist strategy. Increasing the number of ACA runs raises the efficiency of the algorithm by approximately 2%.

Keywords

• задача коммивояжера
• генетический алгоритм
• граф
• модель гольдберга
• мутация
• кроссовер
• муравьиный алгоритм
• элитная особь
• феромон
• природные вычисления
• traveling salesman problem
• genetic algorithm
• graph
• goldberg model
• mutation
• crossover
• ant colony algorithm
• elite sample
• pheromone
• natural computing